Daniel Reichman

Jonathan Shafer

CoRR, July, 2025

The Computational Complexity of Counting Linear Regions in ReLU Neural Networks.

[BibT_eX]

[DOI]

Moritz Stargalla

Christoph Hertrich

CoRR, May, 2025

On the Depth of Monotone ReLU Neural Networks and ICNNs.

[BibT_eX]

[DOI]

CoRR, May, 2025

The Karp Dataset.

[BibT_eX]

[DOI]

CoRR, January, 2025

Inoculation strategies for bounded degree graphs.

[BibT_eX]

[DOI]

Henry Poskanzer

Theor. Comput. Sci., 2025

Improved Lower Bounds on the Expected Length of Longest Common Subsequences.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2025

Nearest Neighbor Complexity and Boolean Circuits.

[BibT_eX]

[DOI]

Vladimir Podolskii

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

Depth Separations in Neural Networks: Separating the Dimension from the Accuracy.

[BibT_eX]

[DOI]

Itay Safran

Paul Valiant

Proceedings of the Thirty Eighth Annual Conference on Learning Theory, 2025

Time Lower Bounds for the Metropolis Process and Simulated Annealing.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2025

2024

Erratum: Multitasking Capacity: Hardness Results and Improved Constructions.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2024

How Many Neurons Does it Take to Approximate the Maximum?

[BibT_eX]

[DOI]

Itay Safran

Paul Valiant

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

The Computational Challenges of Means Selection Problems: Network Structure of Goal Systems Predicts Human Performance.

[BibT_eX]

[DOI]

Cogn. Sci., August, 2023

The Learning and Communication Complexity of Subsequence Containment.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2023

2022

Size and depth of monotone neural networks: interpolation and approximation.

[BibT_eX]

[DOI]

Dan Mikulincer

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in Networks.

[BibT_eX]

[DOI]

Hermish Mehta

Proceedings of the Approximation, 2022

2021

The Sketching and Communication Complexity of Subsequence Detection.

[BibT_eX]

[DOI]

CoRR, 2021

Size and Depth Separation in Approximating Natural Functions with Neural Networks.

[BibT_eX]

[DOI]

CoRR, 2021

Tight Hardness Results for Training Depth-2 ReLU Networks.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Size and Depth Separation in Approximating Benign Functions with Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

Multitasking Capacity: Hardness Results and Improved Constructions.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2020

2019

On percolation and -hardness.

[BibT_eX]

[DOI]

Huck Bennett

Random Struct. Algorithms, 2019

Predicting human decisions with behavioral theories and machine learning.

[BibT_eX]

[DOI]

CoRR, 2019

On the Existence of Nash Equilibrium in Games with Resource-Bounded Players.

[BibT_eX]

[DOI]

Joseph Y. Halpern

Rafael Pass

Proceedings of the Algorithmic Game Theory - 12th International Symposium, 2019

Cognitive model priors for predicting human decisions.

[BibT_eX]

[DOI]

Proceedings of the 36th International Conference on Machine Learning, 2019

String Matching: Communication, Circuits, and Learning.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

The Computational Complexity of Training ReLU(s).

[BibT_eX]

[DOI]

Pasin Manurangsi

CoRR, 2018

Inference in Sparse Graphs with Pairwise Measurements and Side Information.

[BibT_eX]

[DOI]

Dylan J. Foster

Karthik Sridharan

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2018

2017

Detecting Patterns Can Be Hard: Circuit Lower Bounds for the String Matching Problem.

[BibT_eX]

[DOI]

Alexander Golovnev

CoRR, 2017

LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs.

[BibT_eX]

[DOI]

Nikhil Bansal

Seeun William Umboh

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

A graph-theoretic approach to multitasking.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays.

[BibT_eX]

[DOI]

Omri Ben-Eliezer

Simon Korman

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

The Structure of Goal Systems Predicts Human Performance.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual Meeting of the Cognitive Science Society, 2017

2016

On giant components and treewidth in the layers model.

[BibT_eX]

[DOI]

Jonathan Hermon

Random Struct. Algorithms, 2016

Testing Pattern-Freeness.

[BibT_eX]

[DOI]

Simon Korman

CoRR, 2016

A Graph-Theoretic Approach to Multitasking.

[BibT_eX]

[DOI]

CoRR, 2016

Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs.

[BibT_eX]

[DOI]

Nikhil Bansal

Seeun William Umboh

CoRR, 2016

On Percolation and NP-Hardness.

[BibT_eX]

[DOI]

Huck Bennett

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

On Percolation and NP-Hardness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

On the Non-Existence of Nash Equilibrium in Games with Resource-Bounded Players.

[BibT_eX]

[DOI]

Joseph Y. Halpern

Rafael Pass

CoRR, 2015

Contagious Sets in Expanders.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank-One Perturbations of Gaussian Tensors.

[BibT_eX]

[DOI]

Andrea Montanari

Ofer Zeitouni

Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Contagious Sets in Dense Graphs.

[BibT_eX]

[DOI]

Daniel Freund

Matthias Poloczek

Proceedings of the Combinatorial Algorithms - 26th International Workshop, 2015

2014

Smoothed Analysis on Connected Graphs.

[BibT_eX]

[DOI]

Michael Krivelevich

Wojciech Samotij

Proceedings of the Approximation, 2014

2013

FasT-Match: Fast Affine Template Matching.

[BibT_eX]

[DOI]

Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition, 2013

2012

New bounds for contagious sets.

[BibT_eX]

[DOI]

Discret. Math., 2012

2011

Tight Approximation of Image Matching

[BibT_eX]

[DOI]

Simon Korman

Gilad Tsur

CoRR, 2011

Recoverable Values for Independent Sets.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Influence is a Matter of Degree: New Algorithms for Activation Problems

[BibT_eX]

[DOI]

CoRR, 2010

2008

Approximating maximum satisfiable subsystems of linear equations of bounded width.

[BibT_eX]

[DOI]

Zeev Nutov

Inf. Process. Lett., 2008

2004

On The Hardness of Approximating Max-Satisfy

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

On Systems of Linear Equations with Two Variables per Equation.

[BibT_eX]

[DOI]