Guy Kindler

80 papers A* 22A 8B 1Journal 47Unranked 1
YearRankTypeTitle / Venue / Authors
2024 J jnl
Limits of Preprocessing.
Comput. Complex.
Yuval Filmus, Yuval Ishai, Avi Kaplan, Guy Kindler
2024 A* conf
Product Mixing in Compact Lie Groups.
STOC
David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer
2024 J jnl
Product Mixing in Compact Lie Groups.
CoRR
David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer
2023 A* conf
An Analogue of Bonami's Lemma for Functions on Spaces of Linear Maps, and 2-2 Games.
STOC
David Ellis, Guy Kindler, Noam Lifshitz
2023 A conf
Improved Monotonicity Testers via Hypercube Embeddings.
ITCS
Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer
2023 J jnl
Product mixing in compact Lie groups.
Electron. Colloquium Comput. Complex.
David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer
2023 J jnl
The Success Probability in Levine's Hat Problem, and Independent Sets in Graphs.
SIAM J. Discret. Math.
Noga Alon, Ehud Friedgut, Gil Kalai, Guy Kindler
2022 J jnl
Improved Monotonicity Testers via Hypercube Embeddings.
CoRR
Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer
2022 J jnl
Isoperimetric Inequalities Made Simpler.
CoRR
Ronen Eldan, Guy Kindler, Noam Lifshitz, Dor Minzer
2021 A conf
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality.
ITCS
Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2021 J jnl
Towards a quantum-inspired proof for IP = PSPACE.
Quantum Inf. Comput.
Ayal Green, Guy Kindler, Yupan Liu
2020 J jnl
Hypercontractivity on the symmetric group.
CoRR
Yuval Filmus, Guy Kindler, Noam Lifshitz, Dor Minzer
2020 A conf
Limits of Preprocessing.
CCC
Yuval Filmus, Yuval Ishai, Avi Kaplan, Guy Kindler
2020 J jnl
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality.
Electron. Colloquium Comput. Complex.
Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2020 A* conf
Towards a Proof of the Fourier-Entropy Conjecture?
FOCS
Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, Muli Safra
2019 J jnl
Revisiting Bourgain-Kalai and Fourier Entropies.
CoRR
Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, Muli Safra
2019 J jnl
Towards a quantum-inspired proof for IP = PSPACE.
CoRR
Ayal Green, Yupan Liu, Guy Kindler
2018 J jnl
Invariance Principle on the Slice.
ACM Trans. Comput. Theory
Yuval Filmus, Guy Kindler, Elchanan Mossel, Karl Wimmer
2018 A* conf
On non-optimally expanding sets in Grassmann graphs.
STOC
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2018 A* conf
Towards a proof of the 2-to-1 games conjecture?
STOC
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2017 J jnl
Direct Sum Testing.
SIAM J. Comput.
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar
2017 J jnl
On Non-Optimally Expanding Sets in Grassmann Graphs.
Electron. Colloquium Comput. Complex.
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2017 A* conf
Quantum Automata Cannot Detect Biased Coins, Even in the Limit.
ICALP
Guy Kindler, Ryan O'Donnell
2017 J jnl
Traffic Engineering With Equal-Cost-MultiPath: An Algorithmic Perspective.
IEEE/ACM Trans. Netw.
Marco Chiesa, Guy Kindler, Michael Schapira
2016 A* conf
Approximation of non-boolean 2CSP.
SODA
Guy Kindler, Alexandra Kolla, Luca Trevisan
2016 A conf
Invariance Principle on the Slice.
CCC
Yuval Filmus, Guy Kindler, Elchanan Mossel, Karl Wimmer
2016 J jnl
Property Testing, PCP, andJuntas.
Electron. Colloquium Comput. Complex.
Guy Kindler
2016 J jnl
Quantum automata cannot detect biased coins, even in the limit.
CoRR
Guy Kindler, Ryan O'Donnell
2016 J jnl
Towards a Proof of the 2-to-1 Games Conjecture?
Electron. Colloquium Comput. Complex.
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2015 J jnl
Approximation of non-boolean 2CSP.
CoRR
Guy Kindler, Alexandra Kolla, Luca Trevisan
2015 J jnl
Continuous analogues of the Most Informative Function problem.
CoRR
Guy Kindler, Ryan O'Donnell, David Witmer
2015 A conf
Direct Sum Testing.
ITCS
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar
2015 J jnl
Geometric stability via information theory.
CoRR
David Ellis, Ehud Friedgut, Guy Kindler, Amir Yehudayoff
2015 A* conf
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition.
STOC
Irit Dinur, Prahladh Harsha, Guy Kindler
2015 J jnl
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition.
CoRR
Irit Dinur, Prahladh Harsha, Guy Kindler
2015 J jnl
Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition.
Electron. Colloquium Comput. Complex.
Irit Dinur, Prahladh Harsha, Guy Kindler
2015 J jnl
Unique Games on the Hypercube.
Chic. J. Theor. Comput. Sci.
Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan
2014 J jnl
Direct Sum Testing.
Electron. Colloquium Comput. Complex.
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar
2014 J jnl
Gaussian Noise Sensitivity and BosonSampling.
CoRR
Gil Kalai, Guy Kindler
2014 A* conf
Traffic engineering with Equal-Cost-Multipath: An algorithmic perspective.
INFOCOM
Marco Chiesa, Guy Kindler, Michael Schapira
2014 J jnl
Unique Games on the Hypercube.
CoRR
Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan
2013 A conf
On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction.
ITCS
Boaz Barak, Guy Kindler, David Steurer
2013 J jnl
Quantitative relation between noise sensitivity and influences.
Comb.
Nathan Keller, Guy Kindler
2012 A conf
Gaussian Noise Sensitivity and Fourier Tails.
CCC
Guy Kindler, Ryan O'Donnell
2012 J jnl
Spherical cubes: optimal foams from computational hardness amplification.
Commun. ACM
Guy Kindler, Anup Rao, Ryan O'Donnell, Avi Wigderson
2012 J jnl
The geometry of manipulation - A quantitative proof of the Gibbard-Satterthwaite theorem.
Comb.
Marcus Isaksson, Guy Kindler, Elchanan Mossel
2011 J jnl
Hardness of Approximating the Closest Vector Problem with Pre-Processing.
Comput. Complex.
Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi
2011 J jnl
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability.
Comput. Complex.
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
2010 J jnl
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors.
Electron. Colloquium Comput. Complex.
Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson
2010 J jnl
Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors.
J. ACM
Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson
2010 A* conf
The Geometry of Manipulation: A Quantitative Proof of the Gibbard-Satterthwaite Theorem.
FOCS
Marcus Isaksson, Guy Kindler, Elchanan Mossel
2010 J jnl
The UGC Hardness Threshold of the
Math. Oper. Res.
Guy Kindler, Assaf Naor, Gideon Schechtman
2008 J jnl
Eliminating Cycles in the Discrete Torus.
Algorithmica
Béla Bollobás, Guy Kindler, Imre Leader, Ryan O'Donnell
2008 J jnl
Lower Bounds for the Noisy Broadcast Problem.
SIAM J. Comput.
Navin Goyal, Guy Kindler, Michael E. Saks
2008 A* conf
Spherical Cubes and Rounding in High Dimensions.
FOCS
Guy Kindler, Ryan O'Donnell, Anup Rao, Avi Wigderson
2008 A* conf
The UGC hardness threshold of the ℓ
SODA
Guy Kindler, Assaf Naor, Gideon Schechtman
2007 J jnl
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?.
SIAM J. Comput.
Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell
2007 A conf
Understanding Parallel Repetition Requires Understanding Foams.
CCC
Uriel Feige, Guy Kindler, Ryan O'Donnell
2007 J jnl
Understanding Parallel Repetition Requires Understanding Foams.
Electron. Colloquium Comput. Complex.
Uriel Feige, Guy Kindler, Ryan O'Donnell
2006 B conf
Eliminating Cycles in the Discrete Torus.
LATIN
Béla Bollobás, Guy Kindler, Imre Leader, Ryan O'Donnell
2006 A* conf
On the fourier tails of bounded functions over the discrete cube.
STOC
Irit Dinur, Ehud Friedgut, Guy Kindler, Ryan O'Donnell
2005 A* conf
Hardness of Approximating the Closest Vector Problem with Pre-Processing.
FOCS
Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi
2005 A* conf
Lower Bounds for the Noisy Broadcast Problem.
FOCS
Navin Goyal, Guy Kindler, Michael E. Saks
2005 J jnl
On Non-Approximability for Quadratic Programs
Electron. Colloquium Comput. Complex.
Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra
2005 A* conf
On Non-Approximability for Quadratic Programs.
FOCS
Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra
2005 J jnl
On the Error Parameter of Dispersers
Electron. Colloquium Comput. Complex.
Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma
2005 — conf
On the Error Parameter of Dispersers.
APPROX-RANDOM
Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma
2005 J jnl
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?
Electron. Colloquium Comput. Complex.
Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel
2005 A* conf
Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors.
STOC
Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson
2004 J jnl
On Distributions Computable by Random Walks on Graphs.
SIAM J. Discret. Math.
Guy Kindler, Dan Romik
2004 A* conf
On distributions computable by random walks on graphs.
SODA
Guy Kindler, Dan Romik
2004 A* conf
Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?
FOCS
Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell
2004 J jnl
Testing juntas.
J. Comput. Syst. Sci.
Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
2003 J jnl
Approximating CVP to Within Almost-Polynomial Factors is NP-Hard.
Comb.
Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra
2002 — —
Property testing PCP and juntas
Guy Kindler
2002 A* conf
Testing Juntas.
FOCS
Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
1999 A* conf
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.
STOC
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
1998 J jnl
Approximating CVP to Within Almost Polynomial Factor is NP-Hard
Electron. Colloquium Comput. Complex.
Irit Dinur, Guy Kindler, Shmuel Safra
1998 A* conf
Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard.
FOCS
Irit Dinur, Guy Kindler, Shmuel Safra
1998 J jnl
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability
Electron. Colloquium Comput. Complex.
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra