| Publication | Date of Publication | Type |
|---|
Towards a proof of the 2-to-1 games conjecture
Theory of Computing | 2026-02-10 | Paper |
On independent sets, 2-to-2 games and Grassmann graphs
Theory of Computing | 2026-02-10 | Paper |
Small-set expansion in the Johnson graph
Theory of Computing | 2026-02-10 | Paper |
| Approximating-CVP to within almost-polynomial factors is NP-hard | 2025-10-29 | Paper |
| Towards a proof of the Fourier-entropy conjecture? | 2025-08-12 | Paper |
| Pseudorandom sets in Grassmann graph have near-perfect expansion | 2025-08-12 | Paper |
| On monotonicity testing and Boolean isoperimetric type theorems | 2025-08-05 | Paper |
| Hardness of finding independent sets in almost 3-colorable graphs | 2025-04-29 | Paper |
| NP-hardness of almost coloring almost 3-colorable graphs | 2025-01-14 | Paper |
Mathematics of computation through the lens of linear equations and lattices
International Congress of Mathematicians | 2024-03-20 | Paper |
Multivariate generating functions for information spread on multi-type random graphs
Journal of Statistical Mechanics: Theory and Experiment | 2023-11-01 | Paper |
| On the Shortest Lattice Vector vs. the Shortest Basis | 2023-05-31 | Paper |
Pseudorandom sets in Grassmann graph have near-perfect expansion
Annals of Mathematics. Second Series | 2023-05-31 | Paper |
Pandemic spread in communities via random graphs
Journal of Statistical Mechanics: Theory and Experiment | 2021-11-19 | Paper |
On non-optimally expanding sets in Grassmann graphs
Israel Journal of Mathematics | 2021-08-24 | Paper |
Superspreaders and high variance infectious diseases
Journal of Statistical Mechanics: Theory and Experiment | 2021-06-08 | Paper |
Heterogeneity and superspreading effect on herd immunity
Journal of Statistical Mechanics: Theory and Experiment | 2021-04-01 | Paper |
Pandemic Spread in Communities via Random Graphs
(available as arXiv preprint) | 2021-01-13 | Paper |
Towards a proof of the Fourier-entropy conjecture?
Geometric and Functional Analysis. GAFA | 2020-12-16 | Paper |
Towards a proof of the 2-to-1 games conjecture?
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
On non-optimally expanding sets in Grassmann graphs
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
On Monotonicity Testing and Boolean Isoperimetric-type Theorems
SIAM Journal on Computing | 2018-12-19 | Paper |
On independent sets, 2-to-2 games, and Grassmann graphs
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Towards an optimal query efficient PCP?
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
PCP characterizations of NP: towards a polynomially-small error-probability
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
| Boolean functions whose Fourier transform is concentrated on pairwise disjoint subsets of the input | 2015-12-30 | Paper |
Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
Algorithmic construction of sets for <i>k</i> -restrictions
ACM Transactions on Algorithms | 2015-09-02 | Paper |
| On the Converse of Talagrand's Influence Inequality | 2015-06-21 | Paper |
| The complexity of low-distortion embeddings between point sets | 2014-10-13 | Paper |
A two-prover one-round game with strong soundness
Theory of Computing | 2014-10-06 | Paper |
A Two Prover One Round Game with Strong Soundness
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
PCP characterizations of NP: toward a polynomially-small error-probability
Computational Complexity | 2011-11-30 | Paper |
Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Inapproximability of vertex cover and independent set in bounded degree graphs
Theory of Computing | 2011-05-24 | Paper |
| scientific article; zbMATH DE number 5764834 (Why is no real title available?) | 2010-08-06 | Paper |
The importance of being biased
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
On the complexity of equilibria
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
On the complexity of approximating \(k\)-dimensional matching
Lecture Notes in Computer Science | 2010-05-26 | Paper |
On the complexity of approximating TSP with neighborhoods and related problems
Lecture Notes in Computer Science | 2010-03-03 | Paper |
On the hardness of approximating label-cover
Information Processing Letters | 2009-07-09 | Paper |
| scientific article; zbMATH DE number 5504150 (Why is no real title available?) | 2009-02-09 | Paper |
The Erdős-Hajnal conjecture for bull-free graphs
Journal of Combinatorial Theory. Series B | 2008-12-08 | Paper |
Exponential Determinization for ω‐Automata with a Strong Fairness Acceptance Condition
SIAM Journal on Computing | 2007-06-26 | Paper |
On the complexity of approximating TSP with neighborhoods and related problems
Computational Complexity | 2006-11-17 | Paper |
On the complexity of approximating \(k\)-set packing
Computational Complexity | 2006-09-28 | Paper |
Extractors from Reed-Muller codes
Journal of Computer and System Sciences | 2006-07-12 | Paper |
On the hardness of approximating minimum vertex cover
Annals of Mathematics. Second Series | 2006-03-10 | Paper |
Relating word and tree automata
Annals of Pure and Applied Logic | 2005-12-29 | Paper |
On the complexity of price equilibria
Journal of Computer and System Sciences | 2004-11-18 | Paper |
Approximating CVP to within almost-polynomial factors is NP-hard
Combinatorica | 2004-09-07 | Paper |
Testing juntas
Journal of Computer and System Sciences | 2004-08-06 | Paper |
Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
Information Processing Letters | 2002-07-25 | Paper |
| scientific article; zbMATH DE number 1263186 (Why is no real title available?) | 2001-08-27 | Paper |
On the hardness of approximating the chromatic number
Combinatorica | 2001-06-12 | Paper |
| scientific article; zbMATH DE number 1559563 (Why is no real title available?) | 2001-02-28 | Paper |
| scientific article; zbMATH DE number 1256635 (Why is no real title available?) | 2000-05-28 | Paper |
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
SIAM Journal on Computing | 2000-03-19 | Paper |
| scientific article; zbMATH DE number 708807 (Why is no real title available?) | 1999-08-30 | Paper |
On data structures and asymmetric communication complexity
Journal of Computer and System Sciences | 1999-01-06 | Paper |
Probabilistic checking of proofs
Journal of the ACM | 1998-10-25 | Paper |
Interactive proofs and the hardness of approximating cliques
Journal of the ACM | 1998-01-21 | Paper |
A well-characterized approximation problem
Information Processing Letters | 1994-03-13 | Paper |
