default search action
Guy Kindler
Person information
- affiliation: The Hebrew University of Jerusalem, Israel
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [j20]Yuval Filmus, Yuval Ishai, Avi Kaplan, Guy Kindler:
Limits of Preprocessing. Comput. Complex. 33(1): 5 (2024) - [c32]David Ellis
, Guy Kindler
Product Mixing in Compact Lie Groups. STOC 2024: 1415-1422 - [i27]David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer:
Product Mixing in Compact Lie Groups. CoRR abs/2401.15456 (2024) - 2023
- [j19]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): 2717-2729 (2023) - [c31]Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer:
Improved Monotonicity Testers via Hypercube Embeddings. ITCS 2023: 25:1-25:24 - [c30]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: 656-660 - [i26]David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer:
Product mixing in compact Lie groups. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [i25]Ronen Eldan, Guy Kindler, Noam Lifshitz, Dor Minzer:
Isoperimetric Inequalities Made Simpler. CoRR abs/2204.06686 (2022) - [i24]Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer:
Improved Monotonicity Testers via Hypercube Embeddings. CoRR abs/2211.09229 (2022) - 2021
- [j18]Ayal Green, Guy Kindler, Yupan Liu
Towards a quantum-inspired proof for IP = PSPACE. Quantum Inf. Comput. 21(5&6): 377-386 (2021) - [c29]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: 26:1-26:17 - 2020
- [c28]Yuval Filmus, Yuval Ishai, Avi Kaplan, Guy Kindler:
Limits of Preprocessing. CCC 2020: 17:1-17:22 - [c27]Esty Kelman, Guy Kindler, Noam Lifshitz
Towards a Proof of the Fourier-Entropy Conjecture? FOCS 2020: 247-258 - [i23]Yuval Filmus, Guy Kindler, Noam Lifshitz, Dor Minzer:
Hypercontractivity on the symmetric group. CoRR abs/2009.05503 (2020) - [i22]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. TR20 (2020)
2010 – 2019
- 2019
- [i21]Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, Muli Safra:
Revisiting Bourgain-Kalai and Fourier Entropies. CoRR abs/1911.10579 (2019) - [i20]Ayal Green, Yupan Liu
Towards a quantum-inspired proof for IP = PSPACE. CoRR abs/1912.11611 (2019) - 2018
- [j17]Yuval Filmus, Guy Kindler, Elchanan Mossel, Karl Wimmer:
Invariance Principle on the Slice. ACM Trans. Comput. Theory 10(3): 11:1-11:37 (2018) - [c26]Irit Dinur
Towards a proof of the 2-to-1 games conjecture? STOC 2018: 376-389 - [c25]Irit Dinur
On non-optimally expanding sets in Grassmann graphs. STOC 2018: 940-951 - 2017
- [j16]Roee David, Irit Dinur
Direct Sum Testing. SIAM J. Comput. 46(4): 1336-1369 (2017) - [j15]Marco Chiesa
Traffic Engineering With Equal-Cost-MultiPath: An Algorithmic Perspective. IEEE/ACM Trans. Netw. 25(2): 779-792 (2017) - [c24]Guy Kindler, Ryan O'Donnell:
Quantum Automata Cannot Detect Biased Coins, Even in the Limit. ICALP 2017: 15:1-15:8 - [i19]Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
On Non-Optimally Expanding Sets in Grassmann Graphs. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [c23]Yuval Filmus, Guy Kindler, Elchanan Mossel, Karl Wimmer:
Invariance Principle on the Slice. CCC 2016: 15:1-15:10 - [c22]Guy Kindler, Alexandra Kolla, Luca Trevisan:
Approximation of non-boolean 2CSP. SODA 2016: 1705-1714 - [i18]Guy Kindler, Ryan O'Donnell:
Quantum automata cannot detect biased coins, even in the limit. CoRR abs/1610.03543 (2016) - [i17]Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
Towards a Proof of the 2-to-1 Games Conjecture? Electron. Colloquium Comput. Complex. TR16 (2016) - [i16]Guy Kindler:
Property Testing, PCP, andJuntas. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j14]Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan:
Unique Games on the Hypercube. Chic. J. Theor. Comput. Sci. 2015 (2015) - [c21]Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar:
Direct Sum Testing. ITCS 2015: 327-336 - [c20]Irit Dinur
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition. STOC 2015: 267-276 - [i15]Guy Kindler, Alexandra Kolla, Luca Trevisan:
Approximation of non-boolean 2CSP. CoRR abs/1504.00681 (2015) - [i14]Irit Dinur, Prahladh Harsha, Guy Kindler:
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition. CoRR abs/1505.06362 (2015) - [i13]Guy Kindler, Ryan O'Donnell, David Witmer:
Continuous analogues of the Most Informative Function problem. CoRR abs/1506.03167 (2015) - [i12]David Ellis, Ehud Friedgut, Guy Kindler, Amir Yehudayoff:
Geometric stability via information theory. CoRR abs/1510.00258 (2015) - [i11]Irit Dinur, Prahladh Harsha, Guy Kindler:
Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [c19]Marco Chiesa
Traffic engineering with Equal-Cost-Multipath: An algorithmic perspective. INFOCOM 2014: 1590-1598 - [i10]Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan:
Unique Games on the Hypercube. CoRR abs/1405.1374 (2014) - [i9]Gil Kalai, Guy Kindler:
Gaussian Noise Sensitivity and BosonSampling. CoRR abs/1409.3093 (2014) - [i8]Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar:
Direct Sum Testing. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j13]Nathan Keller, Guy Kindler:
Quantitative relation between noise sensitivity and influences. Comb. 33(1): 45-71 (2013) - [c18]Boaz Barak, Guy Kindler, David Steurer
On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction. ITCS 2013: 197-214 - 2012
- [j12]Guy Kindler, Anup Rao, Ryan O'Donnell, Avi Wigderson:
Spherical cubes: optimal foams from computational hardness amplification. Commun. ACM 55(10): 90-97 (2012) - [j11]Marcus Isaksson, Guy Kindler, Elchanan Mossel
The geometry of manipulation - A quantitative proof of the Gibbard-Satterthwaite theorem. Comb. 32(2): 221-250 (2012) - [c17]Guy Kindler, Ryan O'Donnell:
Gaussian Noise Sensitivity and Fourier Tails. CCC 2012: 137-147 - 2011
- [j10]Irit Dinur
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability. Comput. Complex. 20(3): 413-504 (2011) - [j9]Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi:
Hardness of Approximating the Closest Vector Problem with Pre-Processing. Comput. Complex. 20(4): 741-753 (2011) - 2010
- [j8]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): 20:1-20:52 (2010) - [j7]Guy Kindler, Assaf Naor, Gideon Schechtman:
The UGC Hardness Threshold of the Lp Grothendieck Problem. Math. Oper. Res. 35(2): 267-283 (2010) - [c16]Marcus Isaksson, Guy Kindler, Elchanan Mossel
The Geometry of Manipulation: A Quantitative Proof of the Gibbard-Satterthwaite Theorem. FOCS 2010: 319-328 - [i7]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. TR10 (2010)
2000 – 2009
- 2008
- [j6]Béla Bollobás, Guy Kindler, Imre Leader, Ryan O'Donnell:
Eliminating Cycles in the Discrete Torus. Algorithmica 50(4): 446-454 (2008) - [j5]Navin Goyal, Guy Kindler, Michael E. Saks:
Lower Bounds for the Noisy Broadcast Problem. SIAM J. Comput. 37(6): 1806-1841 (2008) - [c15]Guy Kindler, Ryan O'Donnell, Anup Rao, Avi Wigderson:
Spherical Cubes and Rounding in High Dimensions. FOCS 2008: 189-198 - [c14]Guy Kindler, Assaf Naor, Gideon Schechtman:
The UGC hardness threshold of the ℓp Grothendieck problem. SODA 2008: 64-73 - 2007
- [j4]Subhash Khot, Guy Kindler, Elchanan Mossel
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?. SIAM J. Comput. 37(1): 319-357 (2007) - [c13]Uriel Feige, Guy Kindler, Ryan O'Donnell:
Understanding Parallel Repetition Requires Understanding Foams. CCC 2007: 179-192 - [i6]Uriel Feige, Guy Kindler, Ryan O'Donnell:
Understanding Parallel Repetition Requires Understanding Foams. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [c12]Béla Bollobás, Guy Kindler, Imre Leader, Ryan O'Donnell:
Eliminating Cycles in the Discrete Torus. LATIN 2006: 202-210 - [c11]Irit Dinur, Ehud Friedgut, Guy Kindler, Ryan O'Donnell:
On the fourier tails of bounded functions over the discrete cube. STOC 2006: 437-446 - 2005
- [c10]Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma
On the Error Parameter of Dispersers. APPROX-RANDOM 2005: 294-305 - [c9]Navin Goyal, Guy Kindler, Michael E. Saks:
Lower Bounds for the Noisy Broadcast Problem. FOCS 2005: 40-52 - [c8]Sanjeev Arora, Eli Berger, Elad Hazan
On Non-Approximability for Quadratic Programs. FOCS 2005: 206-215 - [c7]Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi:
Hardness of Approximating the Closest Vector Problem with Pre-Processing. FOCS 2005: 216-225 - [c6]Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson:
Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. STOC 2005: 1-10 - [i5]Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra
On Non-Approximability for Quadratic Programs. Electron. Colloquium Comput. Complex. TR05 (2005) - [i4]Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma:
On the Error Parameter of Dispersers. Electron. Colloquium Comput. Complex. TR05 (2005) - [i3]Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel:
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j3]Eldar Fischer, Guy Kindler, Dana Ron
Testing juntas. J. Comput. Syst. Sci. 68(4): 753-787 (2004) - [j2]Guy Kindler, Dan Romik:
On Distributions Computable by Random Walks on Graphs. SIAM J. Discret. Math. 17(4): 624-633 (2004) - [c5]Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell:
Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? FOCS 2004: 146-154 - [c4]Guy Kindler, Dan Romik:
On distributions computable by random walks on graphs. SODA 2004: 131-138 - 2003
- [j1]Irit Dinur
Approximating CVP to Within Almost-Polynomial Factors is NP-Hard. Comb. 23(2): 205-243 (2003) - 2002
- [b1]Guy Kindler:
Property testing PCP and juntas. Tel Aviv University, Israel, 2002 - [c3]Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra
Testing Juntas. FOCS 2002: 103-112
1990 – 1999
- 1999
- [c2]Irit Dinur
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. STOC 1999: 29-40 - 1998
- [c1]Irit Dinur, Guy Kindler, Shmuel Safra
Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard. FOCS 1998: 99-111 - [i2]Irit Dinur, Guy Kindler, Shmuel Safra
Approximating CVP to Within Almost Polynomial Factor is NP-Hard. Electron. Colloquium Comput. Complex. TR98 (1998) - [i1]Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. Electron. Colloquium Comput. Complex. TR98 (1998)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 21:23 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: