Guy Kindler

Noam Lifshitz

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Improved Monotonicity Testers via Hypercube Embeddings.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

Isoperimetric Inequalities Made Simpler.

[BibT_eX]

[DOI]

CoRR, 2022

2021

Towards a quantum-inspired proof for IP = PSPACE.

[BibT_eX]

[DOI]

Ayal Green

Yupan Liu

Quantum Inf. Comput., 2021

Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality.

[BibT_eX]

[DOI]

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

2020

Hypercontractivity on the symmetric group.

[BibT_eX]

[DOI]

CoRR, 2020

Towards a Proof of the Fourier-Entropy Conjecture?

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Limits of Preprocessing.

[BibT_eX]

[DOI]

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Revisiting Bourgain-Kalai and Fourier Entropies.

[BibT_eX]

[DOI]

CoRR, 2019

2018

On non-optimally expanding sets in Grassmann graphs.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Towards a proof of the 2-to-1 games conjecture?

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

Quantum Automata Cannot Detect Biased Coins, Even in the Limit.

[BibT_eX]

[DOI]

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

2016

Property Testing, PCP, andJuntas.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Approximation of non-boolean 2CSP.

[BibT_eX]

[DOI]

Alexandra Kolla

Luca Trevisan

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Invariance Principle on the Slice.

[BibT_eX]

[DOI]

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition.

[BibT_eX]

[DOI]

Prahladh Harsha

Electron. Colloquium Comput. Complex., 2015

Continuous analogues of the Most Informative Function problem.

[BibT_eX]

[DOI]

David Witmer

CoRR, 2015

Geometric stability via information theory.

[BibT_eX]

[DOI]

CoRR, 2015

Unique Games on the Hypercube.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2015

Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition.

[BibT_eX]

[DOI]

Prahladh Harsha

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Direct Sum Testing.

[BibT_eX]

[DOI]

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

2014

Gaussian Noise Sensitivity and BosonSampling.

[BibT_eX]

[DOI]

Gil Kalai

CoRR, 2014

Traffic engineering with Equal-Cost-Multipath: An algorithmic perspective.

[BibT_eX]

[DOI]

Marco Chiesa

Michael Schapira

Proceedings of the 2014 IEEE Conference on Computer Communications, 2014

2013

Quantitative relation between noise sensitivity and influences.

[BibT_eX]

[DOI]

Nathan Keller

Comb., 2013

On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction.

[BibT_eX]

[DOI]

Boaz Barak

David Steurer

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Spherical cubes: optimal foams from computational hardness amplification.

[BibT_eX]

[DOI]

Commun. ACM, 2012

Gaussian Noise Sensitivity and Fourier Tails.

[BibT_eX]

[DOI]

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability.

[BibT_eX]

[DOI]

Comput. Complex., 2011

2010

The UGC Hardness Threshold of the Lp Grothendieck Problem.

[BibT_eX]

[DOI]

Assaf Naor

Gideon Schechtman

Math. Oper. Res., 2010

The Geometry of Manipulation: A Quantitative Proof of the Gibbard-Satterthwaite Theorem.

[BibT_eX]

[DOI]

Marcus Isaksson

Elchanan Mossel

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2008

The UGC hardness threshold of the ℓp Grothendieck problem.

[BibT_eX]

[DOI]

Assaf Naor

Gideon Schechtman

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Spherical Cubes and Rounding in High Dimensions.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Understanding Parallel Repetition Requires Understanding Foams.

[BibT_eX]

[DOI]

Uriel Feige

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006

On the fourier tails of bounded functions over the discrete cube.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Eliminating Cycles in the Discrete Torus.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

2005

Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Lower Bounds for the Noisy Broadcast Problem.

[BibT_eX]

[DOI]

Navin Goyal

Michael E. Saks

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005

On Non-Approximability for Quadratic Programs.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005

Hardness of Approximating the Closest Vector Problem with Pre-Processing.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005

On the Error Parameter of Dispersers.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2005

2004

On distributions computable by random walks on graphs.

[BibT_eX]

[DOI]

Dan Romik

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

2003

Approximating CVP to Within Almost-Polynomial Factors is NP-Hard.

[BibT_eX]

[DOI]

Comb., 2003

2002

Property testing PCP and juntas

[BibT_eX]

[DOI]

PhD thesis, 2002

Testing Juntas.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

1999

PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998

Approximating CVP to Within Almost Polynomial Factor is NP-Hard

[BibT_eX]

[DOI]

Shmuel Safra

Electron. Colloquium Comput. Complex., 1998

Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard.

[BibT_eX]

[DOI]