Guy Kindler

Publication Activity (10 Years)

Years Active: 1998-2024
Publications (10 Years): 37

Top Topics

Top Venues

Electron. Colloquium Comput. Complex.

Publications

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