Daniel Reichman

Publication Activity (10 Years)

Years Active: 2004-2024
Publications (10 Years): 42

Top Topics

String Matching

Bounded Treewidth

Top Venues

Random Struct. Algorithms

Publications

Mason DiCicco, Vladimir Podolskii, Daniel Reichman
Nearest Neighbor Complexity and Boolean Circuits. CoRR (2024)
Mason DiCicco, Vladimir Podolskii, Daniel Reichman
Nearest Neighbor Complexity and Boolean Circuits. Electron. Colloquium Comput. Complex. (2024)
Itay Safran, Daniel Reichman, Paul Valiant
How Many Neurons Does it Take to Approximate the Maximum? SODA (2024)
Itay Safran, Daniel Reichman, Paul Valiant
Depth Separations in Neural Networks: Separating the Dimension from the Accuracy. CoRR (2024)
Daniel Reichman, Falk Lieder, David D. Bourgin, Nimrod Talmon, Thomas L. Griffiths
The Computational Challenges of Means Selection Problems: Network Structure of Goal Systems Predicts Human Performance. Cogn. Sci. 47 (8) (2023)
Itay Safran, Daniel Reichman, Paul Valiant
How Many Neurons Does it Take to Approximate the Maximum? CoRR (2023)
Zongchen Chen, Dan Mikulincer, Daniel Reichman, Alexander S. Wein
Time Lower Bounds for the Metropolis Process and Simulated Annealing. CoRR (2023)
Mason DiCicco, Henry Poskanzer, Daniel Reichman
Inoculation strategies for bounded degree graphs. CoRR (2023)
Mason DiCicco, Daniel Reichman
The Learning and Communication Complexity of Subsequence Containment. ISIT (2023)
Hermish Mehta, Daniel Reichman
Local treewidth of random and noisy graphs with applications to stopping contagion in networks. CoRR (2022)
Hermish Mehta, Daniel Reichman
Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in Networks. APPROX/RANDOM (2022)
Dan Mikulincer, Daniel Reichman
Size and depth of monotone neural networks: interpolation and approximation. NeurIPS (2022)
Dan Mikulincer, Daniel Reichman
Size and depth of monotone neural networks: interpolation and approximation. CoRR (2022)
Gal Vardi, Daniel Reichman, Toniann Pitassi, Ohad Shamir
Size and Depth Separation in Approximating Benign Functions with Neural Networks. COLT (2021)
Mason DiCicco, Daniel Reichman
The Sketching and Communication Complexity of Subsequence Detection. CoRR (2021)
Gal Vardi, Daniel Reichman, Toniann Pitassi, Ohad Shamir
Size and Depth Separation in Approximating Natural Functions with Neural Networks. CoRR (2021)
Surbhi Goel, Adam R. Klivans, Pasin Manurangsi, Daniel Reichman
Tight Hardness Results for Training Depth-2 ReLU Networks. ITCS (2021)
Surbhi Goel, Adam R. Klivans, Pasin Manurangsi, Daniel Reichman
Tight Hardness Results for Training Depth-2 ReLU Networks. CoRR (2020)
Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, Alexander Y. Ku
Multitasking Capacity: Hardness Results and Improved Constructions. SIAM J. Discret. Math. 34 (1) (2020)
David D. Bourgin, Joshua C. Peterson, Daniel Reichman, Stuart J. Russell, Thomas L. Griffiths
Cognitive model priors for predicting human decisions. ICML (2019)
Alexander Golovnev, Mika Göös, Daniel Reichman, Igor Shinkar
String Matching: Communication, Circuits, and Learning. APPROX-RANDOM (2019)
Huck Bennett, Daniel Reichman, Igor Shinkar
On percolation and -hardness. Random Struct. Algorithms 54 (2) (2019)
Ori Plonsky, Reut Apel, Eyal Ert, Moshe Tennenholtz, David Bourgin, Joshua C. Peterson, Daniel Reichman, Thomas L. Griffiths, Stuart J. Russell, Evan C. Carter, James F. Cavanagh, Ido Erev
Predicting human decisions with behavioral theories and machine learning. CoRR (2019)
Joseph Y. Halpern, Rafael Pass, Daniel Reichman
On the Existence of Nash Equilibrium in Games with Resource-Bounded Players. SAGT (2019)
David D. Bourgin, Joshua C. Peterson, Daniel Reichman, Thomas L. Griffiths, Stuart J. Russell
Cognitive Model Priors for Predicting Human Decisions. CoRR (2019)
Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, Alexander Y. Ku
Multitasking Capacity: Hardness Results and Improved Constructions. CoRR (2018)
Daniel Freund, Matthias Poloczek, Daniel Reichman
Contagious sets in dense graphs. Eur. J. Comb. 68 (2018)
Dylan J. Foster, Karthik Sridharan, Daniel Reichman
Inference in Sparse Graphs with Pairwise Measurements and Side Information. AISTATS (2018)
Pasin Manurangsi, Daniel Reichman
The Computational Complexity of Training ReLU(s). CoRR (2018)
Andrea Montanari, Daniel Reichman, Ofer Zeitouni
On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors. IEEE Trans. Inf. Theory 63 (3) (2017)
Alexander Golovnev, Daniel Reichman, Igor Shinkar
Detecting Patterns Can Be Hard: Circuit Lower Bounds for the String Matching Problem. CoRR (2017)
Omri Ben-Eliezer, Simon Korman, Daniel Reichman
Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays. ICALP (2017)
David Bourgin, Falk Lieder, Daniel Reichman, Nimrod Talmon, Tom Griffiths
The Structure of Goal Systems Predicts Human Performance. CogSci (2017)
Simon Korman, Daniel Reichman, Gilad Tsur, Shai Avidan
Fast-Match: Fast Affine Template Matching. Int. J. Comput. Vis. 121 (1) (2017)
Dylan J. Foster, Daniel Reichman, Karthik Sridharan
Inference in Sparse Graphs with Pairwise Measurements and Side Information. CoRR (2017)
Noga Alon, Daniel Reichman, Igor Shinkar, Tal Wagner, Sebastian Musslick, Jonathan D. Cohen, Tom Griffiths, Biswadip Dey, Kayhan Özcimder
A graph-theoretic approach to multitasking. NIPS (2017)
Nikhil Bansal, Daniel Reichman, Seeun William Umboh
LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs. SODA (2017)
Simon Korman, Daniel Reichman
Testing Pattern-Freeness. CoRR (2016)
Jonathan D. Cohen, Biswadip Dey, Tom Griffiths, Sebastian Musslick, Kayhan Özcimder, Daniel Reichman, Igor Shinkar, Tal Wagner
A Graph-Theoretic Approach to Multitasking. CoRR (2016)
Huck Bennett, Daniel Reichman, Igor Shinkar
On Percolation and NP-Hardness. ICALP (2016)
Uriel Feige, Jonathan Hermon, Daniel Reichman
On giant components and treewidth in the layers model. Random Struct. Algorithms 48 (3) (2016)
Nikhil Bansal, Daniel Reichman, Seeun William Umboh
Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs. CoRR (2016)
Uriel Feige, Daniel Reichman
Recoverable values for independent sets. Random Struct. Algorithms 46 (1) (2015)
Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich, Daniel Reichman
Contagious Sets in Expanders. SODA (2015)
Daniel Reichman, Igor Shinkar
On Percolation and NP-Hardness. Electron. Colloquium Comput. Complex. 22 (2015)
Andrea Montanari, Daniel Reichman, Ofer Zeitouni
On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank-One Perturbations of Gaussian Tensors. NIPS (2015)
Daniel Freund, Matthias Poloczek, Daniel Reichman
Contagious Sets in Dense Graphs. IWOCA (2015)
Daniel Freund, Matthias Poloczek, Daniel Reichman
Contagious Sets in Dense Graphs. CoRR (2015)
Joseph Y. Halpern, Rafael Pass, Daniel Reichman
On the Non-Existence of Nash Equilibrium in Games with Resource-Bounded Players. CoRR (2015)
Daniel Reichman, Igor Shinkar
On Percolation and NP-Hardness. CoRR (2015)
Michael Krivelevich, Daniel Reichman, Wojciech Samotij
Smoothed Analysis on Connected Graphs. SIAM J. Discret. Math. 29 (3) (2015)
Michael Krivelevich, Daniel Reichman, Wojciech Samotij
Smoothed Analysis on Connected Graphs. APPROX-RANDOM (2014)
Andrea Montanari, Daniel Reichman, Ofer Zeitouni
On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors. CoRR (2014)
Uriel Feige, Jonathan Hermon, Daniel Reichman
On giant components and treewidth in the layers model. CoRR (2014)
Simon Korman, Daniel Reichman, Gilad Tsur, Shai Avidan
FasT-Match: Fast Affine Template Matching. CVPR (2013)
Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich, Daniel Reichman
Contagious Sets in Expanders. CoRR (2013)
Daniel Reichman
New bounds for contagious sets. Discret. Math. 312 (10) (2012)
Uriel Feige, Daniel Reichman
Recoverable Values for Independent Sets. ICALP (1) (2011)
Simon Korman, Daniel Reichman, Gilad Tsur
Tight Approximation of Image Matching CoRR (2011)
Uriel Feige, Daniel Reichman
Recoverable Values for Independent Sets CoRR (2011)
Daniel Reichman
Influence is a Matter of Degree: New Algorithms for Activation Problems CoRR (2010)
Zeev Nutov, Daniel Reichman
Approximating maximum satisfiable subsystems of linear equations of bounded width. Inf. Process. Lett. 106 (5) (2008)
Uriel Feige, Daniel Reichman
On the hardness of approximating Max-Satisfy. Inf. Process. Lett. 97 (1) (2006)
Uriel Feige, Daniel Reichman
On Systems of Linear Equations with Two Variables per Equation. APPROX-RANDOM (2004)
Uriel Feige, Daniel Reichman
On The Hardness of Approximating Max-Satisfy Electron. Colloquium Comput. Complex. (119) (2004)