| Publication | Date of Publication | Type |
|---|
| Tight hardness results for training depth-2 ReLU networks | 2026-04-15 | Paper |
Inoculation strategies for bounded degree graphs
Theoretical Computer Science | 2025-03-11 | Paper |
| How many neurons does it take to approximate the maximum? | 2024-11-28 | Paper |
| Local treewidth of random and noisy graphs with applications to stopping contagion in networks | 2024-08-22 | Paper |
Erratum to: ``Multitasking capacity: hardness results and improved constructions''
SIAM Journal on Discrete Mathematics | 2024-07-16 | Paper |
New ordering methods to construct contagious sets and induced degenerate subgraphs
Involve | 2023-05-08 | Paper |
String Matching: Communication, Circuits, and Learning.
(available as arXiv preprint) | 2023-02-03 | Paper |
| A note on the largest induced matching in graphs avoiding a fixed bipartite graph | 2020-06-05 | Paper |
Fast-Match: fast affine template matching
International Journal of Computer Vision | 2020-06-03 | Paper |
Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays
(available as arXiv preprint) | 2020-05-27 | Paper |
Multitasking capacity: hardness results and improved constructions
SIAM Journal on Discrete Mathematics | 2020-03-26 | Paper |
On the existence of Nash equilibrium in games with resource-bounded players
(available as arXiv preprint) | 2020-02-04 | Paper |
| On the existence of Nash equilibrium in games with resource-bounded players | 2020-02-04 | Paper |
On percolation and \(\mathcal{NP}\)-hardness
Random Structures & Algorithms | 2019-05-02 | Paper |
LP-based robust algorithms for noisy minor-free and bounded treewidth graphs
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Contagious sets in random graphs
The Annals of Applied Probability | 2018-01-04 | Paper |
Contagious sets in random graphs
The Annals of Applied Probability | 2018-01-04 | Paper |
| On percolation and NP-hardness | 2017-12-19 | Paper |
Contagious sets in dense graphs
European Journal of Combinatorics | 2017-11-14 | Paper |
Contagious sets in expanders
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
| Smoothed Analysis on Connected Graphs | 2017-03-22 | Paper |
On giant components and treewidth in the layers model
Random Structures & Algorithms | 2016-06-10 | Paper |
Contagious sets in dense graphs
Lecture Notes in Computer Science | 2016-04-04 | Paper |
Smoothed Analysis on Connected Graphs
SIAM Journal on Discrete Mathematics | 2015-09-23 | Paper |
Smoothed Analysis on Connected Graphs
SIAM Journal on Discrete Mathematics | 2015-09-23 | Paper |
Recoverable values for independent sets
Random Structures & Algorithms | 2015-02-20 | Paper |
New bounds for contagious sets
Discrete Mathematics | 2012-05-30 | Paper |
Recoverable values for independent sets
Lecture Notes in Computer Science | 2011-07-06 | Paper |
Approximating maximum satisfiable subsystems of linear equations of bounded width
Information Processing Letters | 2010-04-19 | Paper |
On the hardness of approximating max-satisfy
Information Processing Letters | 2009-12-18 | Paper |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2005-08-25 | Paper |
