2024
Comput. Complex., June, 2024
2023
The Success Probability in Levine's Hat Problem, and Independent Sets in Graphs.
SIAM J. Discret. Math., December, 2023
Product mixing in compact Lie groups.
Electron. Colloquium Comput. Complex., 2023
An Analogue of Bonami's Lemma for Functions on Spaces of Linear Maps, and 2-2 Games.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023
Improved Monotonicity Testers via Hypercube Embeddings.
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023
2022
Isoperimetric Inequalities Made Simpler.
CoRR, 2022
2021
Towards a quantum-inspired proof for IP = PSPACE.
Quantum Inf. Comput., 2021
2020
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality.
Electron. Colloquium Comput. Complex., 2020
Hypercontractivity on the symmetric group.
CoRR, 2020
Towards a Proof of the Fourier-Entropy Conjecture?
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020
2019
Revisiting Bourgain-Kalai and Fourier Entropies.
CoRR, 2019
2018
Invariance Principle on the Slice.
ACM Trans. Comput. Theory, 2018
2017
Traffic Engineering With Equal-Cost-MultiPath: An Algorithmic Perspective.
IEEE/ACM Trans. Netw., 2017
On Non-Optimally Expanding Sets in Grassmann Graphs.
Electron. Colloquium Comput. Complex., 2017
Quantum Automata Cannot Detect Biased Coins, Even in the Limit.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017
2016
Property Testing, PCP, andJuntas.
Electron. Colloquium Comput. Complex., 2016
Towards a Proof of the 2-to-1 Games Conjecture?
Electron. Colloquium Comput. Complex., 2016
Approximation of non-boolean 2CSP.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016
2015
Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition.
Electron. Colloquium Comput. Complex., 2015
Continuous analogues of the Most Informative Function problem.
CoRR, 2015
Geometric stability via information theory.
CoRR, 2015
Unique Games on the Hypercube.
Chic. J. Theor. Comput. Sci., 2015
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015
2014
Gaussian Noise Sensitivity and BosonSampling.
CoRR, 2014
2013
Quantitative relation between noise sensitivity and influences.
Comb., 2013
On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction.
Proceedings of the Innovations in Theoretical Computer Science, 2013
2012
The geometry of manipulation - A quantitative proof of the Gibbard-Satterthwaite theorem.
Comb., 2012
Spherical cubes: optimal foams from computational hardness amplification.
Commun. ACM, 2012
Gaussian Noise Sensitivity and Fourier Tails.
Proceedings of the 27th Conference on Computational Complexity, 2012
2011
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability.
Comput. Complex., 2011
Hardness of Approximating the Closest Vector Problem with Pre-Processing.
Comput. Complex., 2011
2010
The UGC Hardness Threshold of the <i>L<sub>p</sub></i> Grothendieck Problem.
Math. Oper. Res., 2010
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors.
Electron. Colloquium Comput. Complex., 2010
2008
Lower Bounds for the Noisy Broadcast Problem.
SIAM J. Comput., 2008
Eliminating Cycles in the Discrete Torus.
Algorithmica, 2008
The UGC hardness threshold of the ℓ<sub><i>p</i></sub> Grothendieck problem.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008
Spherical Cubes and Rounding in High Dimensions.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
2007
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?.
SIAM J. Comput., 2007
Understanding Parallel Repetition Requires Understanding Foams.
Electron. Colloquium Comput. Complex., 2007
2006
On the fourier tails of bounded functions over the discrete cube.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
2005
On the Error Parameter of Dispersers
Electron. Colloquium Comput. Complex., 2005
On Non-Approximability for Quadratic Programs
Electron. Colloquium Comput. Complex., 2005
2004
On Distributions Computable by Random Walks on Graphs.
SIAM J. Discret. Math., 2004
J. Comput. Syst. Sci., 2004
2003
Approximating CVP to Within Almost-Polynomial Factors is NP-Hard.
Comb., 2003
2002
Property testing PCP and juntas
PhD thesis, 2002
1998
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability
Electron. Colloquium Comput. Complex., 1998
Approximating CVP to Within Almost Polynomial Factor is NP-Hard
Electron. Colloquium Comput. Complex., 1998
Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998