Noah Singer

Generating author description...

All published works

Action	Title	Year	Authors
+ PDF Chat	Streaming Algorithms via Local Algorithms for Maximum Directed Cut	2025	Raghuvansh R. Saxena Noah Singer Madhu Sudan Santhoshini Velusamy
+ PDF Chat	Streaming Algorithms via Local Algorithms for Maximum Directed Cut	2024	Raghuvansh R. Saxena Noah Singer Madhu Sudan Santhoshini Velusamy
+ PDF Chat	Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds	2024	Seongwon Hwang Noah Singer Santhoshini Velusamy
+ PDF Chat	Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots	2023	Raghuvansh R. Saxena Noah Singer Madhu Sudan Santhoshini Velusamy
+ PDF Chat	Streaming complexity of CSPs with randomly ordered constraints	2023	Raghuvansh R. Saxena Noah Singer Madhu Sudan Santhoshini Velusamy
+	On streaming approximation algorithms for constraint satisfaction problems	2023	Noah Singer
+	Oblivious algorithms for the Max-$k$AND Problem	2023	Noah Singer
+ PDF Chat	Point-hyperplane Incidence Geometry and the Log-rank Conjecture	2022	Noah Singer Madhu Sudan
+	Streaming complexity of CSPs with randomly ordered constraints	2022	Raghuvansh R. Saxena Noah Singer Madhu Sudan Santhoshini Velusamy
+	Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots	2022	Raghuvansh R. Saxena Noah Singer Madhu Sudan Santhoshini Velusamy
+ PDF Chat	Closed-form expressions for the sketching approximability of (some) symmetric Boolean CSPs	2021	Joanna Boyland Michael Hwang Tarun Prasad Noah Singer Santhoshini Velusamy
+ PDF Chat	On sketching approximations for symmetric Boolean CSPs	2021	Joanna Boyland Michael Hwang Tarun Prasad Noah Singer Santhoshini Velusamy
+ PDF Chat	Streaming approximation resistance of every ordering CSP	2021	Noah Singer Madhu Sudan Santhoshini Velusamy
+	On sketching approximations for symmetric Boolean CSPs	2021	Joanna Boyland Michael Hwang Tarun Prasad Noah Singer Santhoshini Velusamy
+	Streaming approximation resistance of every ordering CSP	2021	Noah Singer Madhu Sudan Santhoshini Velusamy
+	Point-hyperplane incidence geometry and the log-rank conjecture	2021	Noah Singer Madhu Sudan

Common Coauthors

Coauthor	Papers Together
Santhoshini Velusamy	12
Madhu Sudan	8
Raghuvansh R. Saxena	6
Michael Hwang	3
Joanna Boyland	3
Tarun Prasad	3
Madhu Sudan	2
Seongwon Hwang	1

Commonly Cited References

Action	Title	Year	Authors	# of times referenced
+ PDF Chat	Oblivious Algorithms for the Maximum Directed Cut Problem	2013	Uriel Feige Shlomo Jozeph	2
+ PDF Chat	Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat	2020	Chi-Ning Chou Alexander Golovnev Santhoshini Velusamy	2
+	Linear space streaming lower bounds for approximating CSPs	2022	Chi-Ning Chou Alexander Golovnev Madhu Sudan Ameya Velingker Santhoshini Velusamy	2
+	On streaming approximation algorithms for constraint satisfaction problems	2023	Noah Singer	2
+ PDF Chat	An optimal space lower bound for approximating MAX-CUT	2019	Michael Kapralov Dmitry Krachun	2
+	Streaming Hardness of Unique Games	2018	Venkatesan Guruswami Runzhou Tao	2
+ PDF Chat	Concentration Inequalities and Martingale Inequalities: A Survey	2006	Fan Chung Linyuan Lü	1
+	Bounds on Pairs of Families with Restricted Intersections	1999	Jiřį́ Sgall	1
+ PDF Chat	A Positive Fraction Erdos - Szekeres Theorem	1998	Imre Bárány Pável Valtr	1
+ PDF Chat	On a Set of Almost Deterministic $k$-Independent Random Variables	1974	A. Joffe	1
+	Homogeneous selections from hyperplanes	2013	Imre Bárány János Pach	1
+ PDF Chat	Some remarks on the theory of graphs	1947	P. Erdős	1
+	A Sharp Bound for the Number of Sets that Pairwise Intersect at k Positive Values	2003	Hunter S. Snevily	1
+	Crossing Patterns of Segments	2001	János Pach József Solymosi	1
+	On a combinatorial problem in geometry	1975	H. L. Abbott D. Hanson	1
+ PDF Chat	Ramsey-type results for semi-algebraic relations	2014	David Conlon Jacob Fox János Pach Benny Sudakov Andrew Suk	1
+ PDF Chat	Bounds for Pach’s Selection Theorem and for the Minimum Solid Angle in a Simplex	2015	Роман Карасев Jan Kynčl Pavel Paták Zuzana Patáková Martin Tancer	1
+ PDF Chat	Random sampling with a reservoir	1985	Jeffrey Scott Vitter	1
+ PDF Chat	Set Systems with Restricted Cross-Intersections and the Minimum Rank ofInclusion Matrices	2005	Peter Keevash Benny Sudakov	1
+	Extremal problems in discrete geometry	1983	Endre Szemerédi W. T. Trotter	1
+ PDF Chat	Communication is Bounded by Root of Rank	2016	Shachar Lovett	1
+	Testable Bounded Degree Graph Properties Are Random Order Streamable	2017	Morteza Monemizadeh S. Muthukrishnan Pan Peng Christian Sohler	1
+ PDF Chat	Streaming Lower Bounds for Approximating MAX-CUT	2014	Michael Kapralov Sanjeev Khanna Madhu Sudan	1
+ PDF Chat	A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing	2016	Jacob Fox János Pach Andrew Suk	1
+ PDF Chat	Erdős–Hajnal Conjecture for Graphs with Bounded VC-Dimension	2018	Jacob Fox János Pach Andrew Suk	1
+ PDF Chat	The Largest Complete Bipartite Subgraph in Point-Hyperplane Incidence Graphs	2020	Thao Do	1
+ PDF Chat	Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples	2019	Michael Kapralov Slobodan Mitrović Ashkan Norouzi-Fard Jakab Tardos	1
+ PDF Chat	Approximability of all finite CSPs with linear sketches	2022	Chi-Ning Chou Alexander Golovnev Madhu Sudan Santhoshini Velusamy	1
+	Sketching Approximability of (Weak) Monarchy Predicates	2022	Chi-Ning Chou Alexander Golovnev Amirbehshad Shahrasbi Madhu Sudan Santhoshini Velusamy	1
+	Streaming and Sketching Complexity of CSPs: A survey	2022	Madhu Sudan	1
+ PDF Chat	Forbidden intersections	1987	Péter Frankl Vojtěch Rödl	1
+	On sketching approximations for symmetric Boolean CSPs	2021	Joanna Boyland Michael Hwang Tarun Prasad Noah Singer Santhoshini Velusamy	1
+	Analysis of Boolean Functions	2021	Ryan O’Donnell	1
+	Streaming approximation resistance of every ordering CSP	2021	Noah Singer Madhu Sudan Santhoshini Velusamy	1
+	Approximability of all Boolean CSPs with linear sketches	2021	Chi-Ning Chou Alexander Golovnev Madhu Sudan Santhoshini Velusamy	1
+ PDF Chat	Streaming complexity of CSPs with randomly ordered constraints	2023	Raghuvansh R. Saxena Noah Singer Madhu Sudan Santhoshini Velusamy	1
+	Approximability of all finite CSPs with linear sketches	2021	Chi-Ning Chou Alexander Golovnev Madhu Sudan Santhoshini Velusamy	1
+	Oblivious algorithms for the Max-$k$AND Problem	2023	Noah Singer	1
+	A Ramsey-type theorem for bipartite graphs	2000	Paul Erdös A. Hajnal János Pach	1
+ PDF Chat	Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots	2023	Raghuvansh R. Saxena Noah Singer Madhu Sudan Santhoshini Velusamy	1
+ PDF Chat	Overlap properties of geometric expanders	2011	Jacob Fox M. Gromov Vincent Lafforgue Assaf Naor János Pach	1
+	A direct proof for Lovett's bound on the communication complexity of low rank matrices.	2014	Thomas Rothvoß	1
+	Incidences of not-too-degenerate hyperplanes	2005	György Elekes Csaba D. Tóth	1
+ PDF Chat	Sketching Cuts in Graphs and Hypergraphs	2015	Dmitry Kogan Robert Krauthgamer	1
+	A Tverberg-type result on multicolored simplices	1998	János Pach	1