Daniel Reichman

Generating author description...

All published works

Action	Title	Year	Authors
+ PDF Chat	The Karp Dataset	2025	Mason DiCicco Eamon Worden Conner Olsen Nikhil Gangaram Daniel Reichman Neil T. Heffernan
+ PDF Chat	Improved Lower Bounds on the Expected Length of Longest Common Subsequences	2024	George T. Heineman Chase Miller Daniel Reichman Andrew Salls Gábor N. Sárközy Duncan Soiffer
+ PDF Chat	Depth Separations in Neural Networks: Separating the Dimension from the Accuracy	2024	Itay Safran Daniel Reichman Paul Valiant
+ PDF Chat	Nearest Neighbor Complexity and Boolean Circuits	2024	Mason DiCicco Vladimir V. Podolskii Daniel Reichman
+ PDF Chat	How Many Neurons Does it Take to Approximate the Maximum?	2024	Itay Safran Daniel Reichman Paul Valiant
+ PDF Chat	Size and Depth of Monotone Neural Networks: Interpolation and Approximation	2024	Dan Mikulincer Daniel Reichman
+ PDF Chat	Inoculation Strategies for Bounded Degree Graphs	2024	Mason DiCicco Henry Poskanzer Daniel Reichman
+ PDF Chat	The Learning and Communication Complexity of Subsequence Containment	2023	Mason DiCicco Daniel Reichman
+	New ordering methods to construct contagious sets and induced degenerate subgraphs	2023	Connor C. Anderson Akshaj Balasubramanian Henry Poskanzer Daniel Reichman Gábor N. Sárközy
+	Inoculation strategies for bounded degree graphs	2023	Mason DiCicco Henry Poskanzer Daniel Reichman
+	How Many Neurons Does it Take to Approximate the Maximum?	2023	Itay Safran Daniel Reichman Paul Valiant
+	Time Lower Bounds for the Metropolis Process and Simulated Annealing	2023	Zongchen Chen Dan Mikulincer Daniel Reichman Alexander S. Wein
+	Local treewidth of random and noisy graphs with applications to stopping contagion in networks	2022	Hermish Mehta Daniel Reichman
+	Size and depth of monotone neural networks: interpolation and approximation	2022	Dan Mikulincer Daniel Reichman
+ PDF Chat	The Sketching and Communication Complexity of Subsequence Detection	2021	Mason DiCicco Daniel Reichman
+	Size and Depth Separation in Approximating Benign Functions with Neural Networks	2021	Gal Vardi Daniel Reichman Toniann Pitassi Ohad Shamir
+	The Learning and Communication Complexity of Subsequence Containment	2021	Mason DiCicco Daniel Reichman
+	Tight Hardness Results for Training Depth-2 ReLU Networks	2020	Surbhi Goel Adam R. Klivans Pasin Manurangsi Daniel Reichman
+ PDF Chat	On the Rational Boundedness of Cognitive Control: Shared Versus Separated Representations	2020	Sebastian Musslick Andrew Saxe Abigail Novick Hoskin Yotam Sagiv Daniel Reichman Giovanni Petri Jonathan D. Cohen
+	A note on the largest induced matching in graphs without short cycles	2020	Ben Lund Daniel Reichman
+ PDF Chat	Multitasking Capacity: Hardness Results and Improved Constructions	2020	Noga Alon Jonathan D. Cohen Thomas L. Griffiths Pasin Manurangsi Daniel Reichman Igor Shinkar Tal Wagner Alexander Yu
+	A note on the largest induced matching in graphs avoiding a fixed bipartite graph	2020	Ben Lund Daniel Reichman
+	Tight Hardness Results for Training Depth-2 ReLU Networks	2020	Surbhi Goel Adam R. Klivans Pasin Manurangsi Daniel Reichman
+	Cognitive Model Priors for Predicting Human Decisions	2019	David Bourgin Joshua C. Peterson Daniel Reichman Thomas L. Griffiths Stuart Russell
+	The Computational Complexity of Training ReLU(s)	2018	Pasin Manurangsi Daniel Reichman
+ PDF Chat	The Computational Challenges of Pursuing Multiple Goals: Network Structure of Goal Systems Predicts Human Performance	2018	Daniel Reichman Falk Lieder David Bourgin Nimrod Talmon Thomas L. Griffiths
+ PDF Chat	On percolation and ‐hardness	2018	Huck Bennett Daniel Reichman Igor Shinkar
+	Multitasking Capacity: Hardness Results and Improved Constructions	2018	Noga Alon Jonathan D. Cohen Thomas L. Griffiths Pasin Manurangsi Daniel Reichman Igor Shinkar Tal Wagner Alexander Yu
+	The Computational Complexity of Training ReLU(s)	2018	Pasin Manurangsi Daniel Reichman
+ PDF Chat	Contagious sets in random graphs	2017	Uriel Feige Michael Krivelevich Daniel Reichman
+	Detecting Patterns Can Be Hard: Circuit Lower Bounds for the String Matching Problem.	2017	Alexander Golovnev Daniel Reichman Igor Shinkar
+ PDF Chat	Contagious sets in dense graphs	2017	Daniel Freund Matthias Poloczek Daniel Reichman
+	Inference in Sparse Graphs with Pairwise Measurements and Side Information	2017	Dylan J. Foster Daniel Reichman Karthik Sridharan
+	String Matching: Communication, Circuits, and Learning	2017	Alexander Golovnev Mika Göös Daniel Reichman Igor Shinkar
+	LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs	2017	Nikhil Bansal Daniel Reichman Seeun William Umboh
+	Inference in Sparse Graphs with Pairwise Measurements and Side Information	2017	Dylan J. Foster Daniel Reichman Karthik Sridharan
+	On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors	2016	Andrea Montanari Daniel Reichman Ofer Zeitouni
+	A Graph-Theoretic Approach to Multitasking	2016	Noga Alon Jonathan D. Cohen Biswadip Dey Thomas L. Griffiths Sebastian Musslick Kayhan Özcimder Daniel Reichman Igor Shinkar Tal Wagner
+	Testing Pattern-Freeness.	2016	Simon Korman Daniel Reichman
+	Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs.	2016	Nikhil Bansal Daniel Reichman Seeun William Umboh
+	Contagious Sets in Random Graphs	2016	Uriel Feige Michael Krivelevich Daniel Reichman
+	Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays	2016	Omri Ben‐Eliezer Simon Korman Daniel Reichman
+ PDF Chat	Contagious Sets in Dense Graphs	2016	Daniel Freund Matthias Poloczek Daniel Reichman
+	A Graph-Theoretic Approach to Multitasking	2016	Noga Alon Jonathan D. Cohen Biswadip Dey Thomas L. Griffiths Sebastian Musslick Kayhan Özcimder Daniel Reichman Igor Shinkar Tal Wagner
+	LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs	2016	Nikhil Bansal Daniel Reichman Seeun William Umboh
+	Contagious Sets in Random Graphs	2016	Uriel Feige Michael Krivelevich Daniel Reichman
+	On the limitation of spectral methods: from the Gaussian hidden clique problem to rank-one perturbations of Gaussian tensors	2015	Andrea Montanari Daniel Reichman Ofer Zeitouni
+	On Percolation and $NP$-Hardness	2015	Daniel Reichman Igor Shinkar
+ PDF Chat	On giant components and treewidth in the layers model	2015	Uriel Feige Jonathan Hermon Daniel Reichman
+	Contagious Sets in Dense Graphs	2015	Daniel Freund Matthias Poloczek Daniel Reichman
+	Contagious sets in expanders	2015	Amin Coja‐Oghlan Uriel Feige Michael Krivelevich Daniel Reichman
+ PDF Chat	Smoothed Analysis on Connected Graphs	2015	Michael Krivelevich Daniel Reichman Wojciech Samotij
+	Contagious Sets in Dense Graphs	2015	Daniel Freund Matthias Poloczek Daniel Reichman
+	On Percolation and $NP$-Hardness	2015	Daniel Reichman Igor Shinkar
+	On the Non-Existence of Nash Equilibrium in Games with Resource-Bounded Players	2015	Joseph Y. Halpern Rafael Pass Daniel Reichman
+	Contagious Sets in Expanders	2014	Amin Coja‐Oghlan Uriel Feige Michael Krivelevich Daniel Reichman
+	On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors	2014	Andrea Montanari Daniel Reichman Ofer Zeitouni
+	Smoothed Analysis on Connected Graphs	2014	Michael Krivelevich Daniel Reichman Wojciech Samotij
+	On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors	2014	Andrea Montanari Daniel Reichman Ofer Zeitouni
+	Smoothed analysis on connected graphs	2013	Michael Krivelevich Daniel Reichman Wojciech Samotij
+	Expansion in randomly perturbed connected graphs and its consequences	2013	Michael Krivelevich Daniel Reichman Wojciech Samotij
+ PDF Chat	Recoverable values for independent sets	2013	Uriel Feige Daniel Reichman
+	Contagious Sets in Expanders	2013	Amin Coja‐Oghlan Uriel Feige Michael Krivelevich Daniel Reichman
+	Smoothed analysis on connected graphs	2013	Michael Krivelevich Daniel Reichman Wojciech Samotij
+	New bounds for contagious sets	2012	Daniel Reichman
+	Tight Approximation of Image Matching	2011	Simon Korman Daniel Reichman Gilad Tsur
+	Recoverable Values for Independent Sets	2011	Uriel Feige Daniel Reichman
+ PDF Chat	Recoverable Values for Independent Sets	2011	Uriel Feige Daniel Reichman
+	Tight Approximation of Image Matching	2011	Simon Korman Daniel Reichman Gilad Tsur
+	Recoverable Values for Independent Sets	2011	Uriel Feige Daniel Reichman
+	Influence is a Matter of Degree: New Algorithms for Activation Problems	2010	Daniel Reichman
+	On Systems of Linear Equations with Two Variables per Equation	2004	Uriel Feige Daniel Reichman

Common Coauthors

Coauthor	Papers Together
Uriel Feige	12
Michael Krivelevich	10
Igor Shinkar	9
Mason DiCicco	7
Thomas L. Griffiths	6
Pasin Manurangsi	6
Jonathan D. Cohen	5
Wojciech Samotij	5
Andrea Montanari	4
Daniel Freund	4
Noga Alon	4
Tal Wagner	4
Matthias Poloczek	4
Simon Korman	4
Ofer Zeitouni	4
Dan Mikulincer	3
Amin Coja‐Oghlan	3
Seeun William Umboh	3
Itay Safran	3
Nikhil Bansal	3
Henry Poskanzer	3
Paul Valiant	3
Sebastian Musslick	3
David Bourgin	2
Kayhan Özcimder	2
Gilad Tsur	2
Alexander Golovnev	2
Alexander Yu	2
Dylan J. Foster	2
Adam R. Klivans	2
Ben Lund	2
Biswadip Dey	2
Gábor N. Sárközy	2
Karthik Sridharan	2
Surbhi Goel	2
Nikhil Gangaram	1
Connor C. Anderson	1
Toniann Pitassi	1
Stuart Russell	1
Andrew Saxe	1
Zongchen Chen	1
Alexander S. Wein	1
George T. Heineman	1
Akshaj Balasubramanian	1
Gal Vardi	1
Falk Lieder	1
Vladimir V. Podolskii	1
Omri Ben‐Eliezer	1
Joshua C. Peterson	1
Jonathan Hermon	1

Commonly Cited References

Action	Title	Year	Authors	# of times referenced
+	New bounds for contagious sets	2012	Daniel Reichman	10
+	Bootstrap percolation on a Bethe lattice	1979	J. Chalupa P. L. Leath Gary Reich	9
+ PDF Chat	Bootstrap percolation on the random graph $G_{n,p}$	2012	Svante Janson Tomasz Łuczak Tatyana S. Turova Thomas Vallier	9
+	Random disease on the square grid	1998	J�zsef Balogh Gábor Pete	8
+ PDF Chat	Bootstrap percolation on the hypercube	2005	József Balogh Béla Bollobás	8
+ PDF Chat	The sharp threshold for bootstrap percolation in all dimensions	2011	József Balogh Béla Bollobás Hugo Duminil‐Copin Robert Morris	8
+	Bootstrap percolation on the random regular graph	2006	József Balogh Boris Pittel	8
+	Contagious Sets in Expanders	2014	Amin Coja‐Oghlan Uriel Feige Michael Krivelevich Daniel Reichman	6
+ PDF Chat	Bootstrap Percolation on Infinite Trees and Non-Amenable Groups	2006	József Balogh Yuval Peres Gábor Pete	5
+	What I Tell You Three Times Is True: Bootstrap Percolation in Small Worlds	2012	Hamed Amini Nikolaos Fountoulakis	5
+ PDF Chat	The time of bootstrap percolation with dense initial sets for all thresholds	2014	Béla Bollobás Paul Smith Andrew J. Uzzell	5
+	Smoothed analysis of algorithms	2004	Daniel A. Spielman Shang‐Hua Teng	4
+	Contagious sets in expanders	2015	Amin Coja‐Oghlan Uriel Feige Michael Krivelevich Daniel Reichman	4
+ PDF Chat	The phase transition in random graphs: A simple proof	2012	Michael Krivelevich Benny Sudakov	4
+ PDF Chat	On percolation in random graphs with given vertex degrees	2009	Svante Janson	4
+	The time of bootstrap percolation for dense initial sets	2012	Béla Bollobás Cecilia Holmgren Paul Smith Andrew J. Uzzell	4
+	A proof of Alon’s second eigenvalue conjecture and related problems	2008	Joel Friedman	4
+	The time of bootstrap percolation with dense initial sets	2014	Béla Bollobás Cecilia Holmgren Paul Smith Andrew J. Uzzell	4
+	Probability and Computing: Randomized Algorithms and Probabilistic Analysis	2005	Michael Mitzenmacher Eli Upfal	4
+ PDF Chat	An Introduction to Random Matrices	2009	Greg W. Anderson Alice Guionnet Ofer Zeitouni	3
+ PDF Chat	Large induced degenerate subgraphs	1987	Noga Alon J. Kahn Paul Seymour	3
+ PDF Chat	Contagious sets in random graphs	2017	Uriel Feige Michael Krivelevich Daniel Reichman	3
+	A spectral algorithm for learning Hidden Markov Models	2012	Daniel Hsu Sham M. Kakade Tong Zhang	3
+ PDF Chat	Random Matrices and Complexity of Spin Glasses	2012	Antonio Auffinger Gérard Ben Arous Jǐŕı Černý	3
+ PDF Chat	Free energy of the spherical mean field model	2005	Michel Talagrand	3
+ PDF Chat	The mixing time of the giant component of a random graph	2014	Itaı Benjamini Gady Kozma Nicholas Wormald	3
+	The absolute-value estimate for symmetric multilinear forms	1990	William C. Waterhouse	3
+ PDF Chat	Matrix Optimization Under Random External Fields	2015	Amir Dembo Ofer Zeitouni	3
+	Models of Random Regular Graphs	1999	N. C. Wormald	3
+ PDF Chat	Renormalization group analysis of the small-world network model	1999	M. E. J. Newman Duncan J. Watts	3
+ PDF Chat	The Largest Eigenvalue of Rank One Deformation of Large Wigner Matrices	2007	Delphine Féral Sandrine Péché	3
+	Asymptotic power of sphericity tests for high-dimensional data	2013	Alexei Onatski Marcelo J. Moreira Marc Hallin	3
+ PDF Chat	On combinatorial testing problems	2010	Louigi Addario‐Berry Nicolas Broutin Luc Devroye Gábor Lugosi	3
+	Hamiltonian circuits in random graphs	1976	L. Pósa	3
+ PDF Chat	Finding a large hidden clique in a random graph	1998	Noga Alon Michael Krivelevich Benny Sudakov	3
+ PDF Chat	Recoverable values for independent sets	2013	Uriel Feige Daniel Reichman	3
+	Minimax Localization of Structural Information in Large Noisy Matrices	2011	Mladen Kolar Sivaraman Balakrishnan Alessandro Rinaldo Aarti Singh	3
+	Computational barriers in minimax submatrix detection	2015	Zongming Ma Yihong Wu	3
+	On colouring random graphs	1975	Geoffrey Grimmett Colin McDiarmid	3
+	Lower bounds on the independence number in terms of the degrees	1983	Jerrold R. Griggs	3
+ PDF Chat	The Isotropic Semicircle Law and Deformation of Wigner Matrices	2013	Antti Knowles Jun Yin	3
+	A statistical model for tensor PCA	2014	Andrea Montanari Émile Richard	3
+	Proof of Straley's argument for bootstrap percolation	1987	Aernout C. D. van Enter	3
+	Searching for a trail of evidence in a maze	2008	Ery Arias-Castro Emmanuel J. Candès Hannes Helgason Ofer Zeitouni	3
+	Heuristics for Semirandom Graph Problems	2001	Uriel Feige Joe Kilian	3
+	The eigenvalues of random symmetric matrices	1981	Zoltán Füredi János Komlós	3
+ PDF Chat	Expansion and Lack Thereof in Randomly Perturbed Graphs	2008	Abraham D. Flaxman	3
+ PDF Chat	Existence and construction of edge disjoint paths on expander graphs	1992	Andrei Broder Alan Frieze Eli Upfal	2
+	The mixing time of the Newman: Watts small world	2012	Louigi Addario‐Berry Tao Lei	2
+	Random graph models and their applications	2007	Thomas Vallier	2