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

2020

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Invariance Principle on the Slice.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2018

2017

Traffic Engineering With Equal-Cost-MultiPath: An Algorithmic Perspective.

[BibT_eX]

[DOI]

Marco Chiesa

Michael Schapira

IEEE/ACM Trans. Netw., 2017

On Non-Optimally Expanding Sets in Grassmann Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Towards a Proof of the 2-to-1 Games Conjecture?

[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

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

2014

Direct Sum Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Gaussian Noise Sensitivity and BosonSampling.

[BibT_eX]

[DOI]

Gil Kalai

CoRR, 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

The geometry of manipulation - A quantitative proof of the Gibbard-Satterthwaite theorem.

[BibT_eX]

[DOI]

Marcus Isaksson

Elchanan Mossel

Comb., 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

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

[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

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

[BibT_eX]

[DOI]

J. ACM, 2010

2008

Lower Bounds for the Noisy Broadcast Problem.

[BibT_eX]

[DOI]

Navin Goyal

Michael E. Saks

SIAM J. Comput., 2008

Eliminating Cycles in the Discrete Torus.

[BibT_eX]

[DOI]

Algorithmica, 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

Electron. Colloquium Comput. Complex., 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

2005

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

On the Error Parameter of Dispersers

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

On Non-Approximability for Quadratic Programs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

2004

On Distributions Computable by Random Walks on Graphs.

[BibT_eX]

[DOI]

Dan Romik

SIAM J. Discret. Math., 2004

Testing juntas.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 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

1998

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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]