| 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 |
On approximability of satisfiable \(k\)-CSPs: II
Combinatorics, Probability and Computing | 2025-12-30 | Paper |
An invariance principle for the multi-slice, with applications
Advances in Mathematics | 2025-11-17 | Paper |
| Parallel repetition of \(k\)-player projection games | 2025-10-06 | Paper |
Effective bounds for restricted \(3\)-arithmetic progressions in \(\mathbb{F}_p^n\)
Discrete Analysis | 2025-09-12 | Paper |
On approximability of satisfiable \(k\)-CSPs. I
Computational Complexity | 2025-08-25 | Paper |
| Parallel repetition for the GHZ game: exponential decay | 2025-08-15 | Paper |
| An invariance principle for the multi-slice, with applications | 2025-08-13 | Paper |
| On monotonicity testing and Boolean isoperimetric type theorems | 2025-08-05 | Paper |
| Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors | 2025-08-05 | Paper |
| Improved monotonicity testers via hypercube embeddings | 2024-09-25 | Paper |
| Almost polynomial factor inapproximability for parameterized \(k\)-clique | 2024-07-05 | Paper |
| On approximability of satisfiable k-CSPs. II | 2024-05-08 | Paper |
| On approximability of satisfiable k-CSPs. III | 2024-05-08 | Paper |
On approximability of satisfiable k -CSPs: I
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Optimal inapproximability of satisfiable k-LIN over non-abelian groups
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
| Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$ | 2023-08-12 | Paper |
| On Approximability of Satisfiable k-CSPs: IV | 2023-07-30 | Paper |
Pseudorandom sets in Grassmann graph have near-perfect expansion
Annals of Mathematics. Second Series | 2023-05-31 | Paper |
| scientific article; zbMATH DE number 7650076 (Why is no real title available?) | 2023-02-03 | Paper |
| Improved Monotonicity Testers via Hypercube Embeddings | 2022-11-16 | Paper |
| UG-hardness to NP-hardness by losing half | 2022-07-27 | Paper |
| Simultaneous max-cut is harder to approximate than max-cut | 2022-07-21 | Paper |
UG-hardness to NP-hardness by losing half
Theory of Computing | 2022-05-18 | Paper |
The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics
Springer Optimization and Its Applications | 2021-12-14 | Paper |
On the proof of the 2-to-2 games conjecture
Current Developments in Mathematics | 2021-12-09 | Paper |
| An Invariance Principle for the Multi-slice, with Applications | 2021-10-20 | Paper |
On non-optimally expanding sets in Grassmann graphs
Israel Journal of Mathematics | 2021-08-24 | Paper |
An improved dictatorship test with perfect completeness
(available as arXiv preprint) | 2020-11-25 | Paper |
The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | 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 |
Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
On Monotonicity Testing and Boolean Isoperimetric-type Theorems
SIAM Journal on Computing | 2018-12-19 | Paper |
An \(\widetilde O(n)\) queries adaptive tester for unateness
(available as arXiv preprint) | 2018-04-19 | Paper |
| Near-optimal approximation algorithm for simultaneous Max-Cut | 2018-03-15 | Paper |
Near-optimal approximation algorithm for simultaneous Max-Cut
(available as arXiv preprint) | 2018-03-15 | Paper |
| Hardness of bipartite expansion | 2018-03-02 | Paper |
| Hardness of approximation | 2017-10-25 | Paper |
Candidate hard unique game
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | 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 |
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
IEEE Transactions on Information Theory | 2017-05-16 | Paper |
A characterization of approximation resistance for even \(k\)-partite CSPs
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
Towards an optimal query efficient PCP?
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
SIAM Journal on Computing | 2017-03-10 | Paper |
On hardness of approximating the parameterized clique problem
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science | 2016-04-15 | Paper |
Approximating CSPs using LP relaxation
Automata, Languages, and Programming | 2015-10-27 | Paper |
The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
Journal of the ACM | 2015-08-14 | Paper |
A characterization of strong approximation resistance
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Integrality gaps for sparsest cut and minimum linear arrangement problems
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
On earthmover distance, metric labeling, and 0-extension
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
A two-prover one-round game with strong soundness
Theory of Computing | 2014-10-06 | Paper |
Almost polynomial factor hardness for closest vector problem with preprocessing
SIAM Journal on Computing | 2014-09-18 | Paper |
A Two Prover One Round Game with Strong Soundness
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Optimal Long Code Test with One Free Bit
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
SDP Integrality Gaps with Local ell_1-Embeddability
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
The Complexity of Somewhat Approximation Resistant Predicates
Automata, Languages, and Programming | 2014-07-01 | Paper |
NP-hardness of approximately solving linear equations over reals
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
| Sharp kernel clustering algorithms and their associated Grothendieck inequalities | 2014-05-22 | Paper |
\(2^{\log^{1-\varepsilon} n}\) hardness for the closest vector problem with preprocessing
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
\(\mathcal{NP}\)-hardness of approximately solving linear equations over reals
SIAM Journal on Computing | 2013-09-25 | Paper |
Sharp kernel clustering algorithms and their associated Grothendieck inequalities
Random Structures & Algorithms | 2013-05-28 | Paper |
Hardness of approximating the closest vector problem with pre-processing
Computational Complexity | 2012-06-26 | Paper |
Grothendieck-type inequalities in combinatorial optimization
Communications on Pure and Applied Mathematics | 2012-06-25 | Paper |
| scientific article; zbMATH DE number 5971212 (Why is no real title available?) | 2011-11-11 | Paper |
A simple deterministic reduction for the gap minimum distance of code problem
Automata, Languages and Programming | 2011-07-06 | Paper |
Combinatorial theorems about embedding trees on the real line
Journal of Graph Theory | 2011-06-07 | Paper |
Inapproximability of vertex cover and independent set in bounded degree graphs
Theory of Computing | 2011-05-24 | Paper |
SDP gaps and UGC-hardness for max-cut-gain
Theory of Computing | 2011-05-24 | Paper |
Query efficient PCPs with perfect completeness
Theory of Computing | 2011-05-24 | Paper |
On the hardness of learning intersections of two halfspaces
Journal of Computer and System Sciences | 2011-01-18 | Paper |
Hardness of Reconstructing Multivariate Polynomials over Finite Fields
SIAM Journal on Computing | 2011-01-17 | Paper |
Approximate Lasserre integrality gap for unique games
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Inapproximability of hypergraph vertex cover and applications to scheduling problems
Automata, Languages and Programming | 2010-09-07 | Paper |
SDP gaps for 2-to-1 and other Label-Cover variants
Automata, Languages and Programming | 2010-09-07 | Paper |
A new multilayered {PCP} and the hardness of hypergraph vertex cover
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Cell-probe lower bounds for the partial match problem
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
On the power of unique 2-prover 1-round games
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Hardness results for approximate hypergraph coloring
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Fitting algebraic curves to noisy data
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
On agnostic learning of parities, monomials, and halfspaces
SIAM Journal on Computing | 2010-04-29 | Paper |
On earthmover distance, metric labeling, and 0-extension
SIAM Journal on Computing | 2010-04-29 | Paper |
Inapproximability Results for Computational Problems on Lattices
The LLL Algorithm | 2010-03-05 | Paper |
Approximate kernel clustering
Mathematika | 2010-02-05 | Paper |
Linear Equations Modulo 2 and the $L_1$ Diameter of Convex Bodies
SIAM Journal on Computing | 2009-08-20 | Paper |
Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
Automata, Languages and Programming | 2009-03-12 | Paper |
Hardness of Embedding Metric Spaces of Equal Size
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
Approximation Algorithms for the Max-Min Allocation Problem
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
| Unique games on expanding constraint graphs are easy (extended abstract) | 2009-01-05 | Paper |
| scientific article; zbMATH DE number 5485546 (Why is no real title available?) | 2009-01-05 | Paper |
Hardness of approximating the shortest vector problem in lattices
Journal of the ACM | 2008-12-21 | Paper |
Inapproximability results for combinatorial auctions with submodular utility functions
Algorithmica | 2008-09-12 | Paper |
Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
SIAM Journal on Computing | 2008-03-28 | Paper |
Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Journal of Computer and System Sciences | 2008-03-11 | Paper |
Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
SIAM Journal on Computing | 2007-09-07 | Paper |
Improved lower bounds on the randomized complexity of graph properties
Random Structures & Algorithms | 2007-05-11 | Paper |
Nonembeddability theorems via Fourier analysis
Mathematische Annalen | 2006-05-26 | Paper |
Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms
Journal of Computer and System Sciences | 2006-04-28 | Paper |
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
SIAM Journal on Computing | 2005-09-16 | Paper |
Cell-probe lower bounds for the partial match problem
Journal of Computer and System Sciences | 2004-11-18 | Paper |
Fitting algebraic curves to noisy data
Journal of Computer and System Sciences | 2004-11-18 | Paper |
Parameterized complexity of finding subgraphs with hereditary properties.
Theoretical Computer Science | 2003-01-21 | Paper |
| scientific article; zbMATH DE number 1696630 (Why is no real title available?) | 2002-07-22 | Paper |
| scientific article; zbMATH DE number 1754599 (Why is no real title available?) | 2002-06-12 | Paper |
Evasiveness of subgraph containment and related properties
SIAM Journal on Computing | 2002-04-23 | Paper |
| scientific article; zbMATH DE number 1688357 (Why is no real title available?) | 2002-01-09 | Paper |
