\

(Back to homepage)

The UGC hardness threshold of the Lp Grothendieck problem. (pdf)

Guy Kindler, Assaf Naor and Gideon Schechtman.

A preliminary version will appear in SODA, 2008. Submitted for journal publication.

Understanding parallel repetition requires understanding foams. (preliminary verion: pdf)

Uri Feige, Guy Kindler, and Ryan O’Donnell.

Preliminary version appeared in Computational Complexity Conference (CCC), 2007. (also mentioned here).

Eliminating cycles in the discrete torus. (ps, pdf)

Béla Bollobás, Guy Kindler, Imre Leader and Ryan O’Donnell.

Invited, and accepted for publication in Algorithmica. Preliminary version appeared in LATIN 2006..

Lower Bounds for the Noisy Broadcast Problem. (ps, pdf)

Navin Goyal, Guy Kindler, Michael Saks.

Invited, and accepted for publication in the SIAM journal on Computing. Preliminary version appeared in FOCS 2005.

On Non-Approximability for Quadratic Programs (preliminary verion: ps, pdf)

Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler and Muli Safra.

Preliminary version appeared in FOCS 2005.

Hardness of Approximating the Closest Vector Problem with Pre-Processing. (ps, pdf)

Mikhail Alekhnovich, Subhash A. Khot, Guy Kindler and Nisheeth K. Vishnoi.

Preliminary version appeared in FOCS 2005.

On the error parameter of dispersers. (preliminary version: ps)

Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma.
Preliminary version appeared in RANDOM 2005.

Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors. (ps, pdf)

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, and Avi Wigderson.
Preliminary version appeared in STOC 2005.

Optimal Inapproximability Results for MAX-CUT and Other 2-variable CSPs? (ps, pdf)

Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell.
Invited, and accepted for publication in the SIAM Journal on Computing. Preliminary version appeared in FOCS 2004.

On the Fourier tails of bounded functions over the discrete cube. (pdf)

Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O’Donnell.
Accepted for publication in the Israel Journal of Mathematics. Preliminary version appeared in STOC 2006.

On Distributions Computable by Random Walks on Graphs. (ps)

Guy Kindler, Dan Romik.
SIAM Journal on Discrete Mathematics, 2004. Preliminary version appeared in SODA 2004, and was invited to its special issue journal.

Noise-insensitive Boolean-Functions are Juntas. (ps)

Guy Kindler, Shmuel Safra.
Manuscript.

Testing Juntas. (ps)

Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky.
Journal of Computer and System Sciences (invited paper), 2004. Preliminary version appeared in FOCS 2002.

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

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, and Shmuel Safra.
Submitted. Preliminary version appeared in STOC 1999, and was invited to its special issue journal.

An Improved Lower Bound for Approximating CVP. (ps)

Irit Dinur, Guy Kindler, Ran Raz, and Shmuel Safra.
Combinatorica, 2003. Preliminary version appeared in FOCS 1998.

Ph.D. thesis. (pdf)

Received with distinction.

Found a mistake/omission/problem with the list of papers or the links? Please email me!