Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? S Khot, G Kindler, E Mossel, R O’Donnell SIAM Journal on Computing 37 (1), 319-357, 2007 | 873 | 2007 |
Approximating-CVP to within almost-polynomial factors is NP-hard I Dinur, G Kindler, S Safra Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat …, 1998 | 312 | 1998 |
Traffic engineering with equal-cost-multipath: An algorithmic perspective M Chiesa, G Kindler, M Schapira IEEE/ACM Transactions on Networking 25 (2), 779-792, 2016 | 208 | 2016 |
Testing juntas E Fischer, G Kindler, D Ron, S Safra, A Samorodnitsky Journal of Computer and System Sciences 68 (4), 753-787, 2004 | 175 | 2004 |
Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors B Barak, G Kindler, R Shaltiel, B Sudakov, A Wigderson Proceedings of the thirty-seventh annual ACM symposium on Theory of …, 2005 | 137 | 2005 |
Towards a proof of the 2-to-1 games conjecture? I Dinur, S Khot, G Kindler, D Minzer, M Safra Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing …, 2018 | 101 | 2018 |
On non-approximability for quadratic programs S Arora, E Berger, H Elad, G Kindler, M Safra 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 206-215, 2005 | 98 | 2005 |
On non-optimally expanding sets in Grassmann graphs I Dinur, S Khot, G Kindler, D Minzer, M Safra Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing …, 2018 | 89 | 2018 |
On the Fourier tails of bounded functions over the discrete cube I Dinur, E Friedgut, G Kindler, R O'Donnell Proceedings of the thirty-eighth annual ACM symposium on Theory of computing …, 2006 | 78 | 2006 |
The geometry of manipulation—a quantitative proof of the Gibbard-Satterthwaite theorem M Isaksson, G Kindler, E Mossel Combinatorica 32 (2), 221-250, 2012 | 75 | 2012 |
Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors B Barak, G Kindler, R Shaltiel, B Sudakov, A Wigderson Journal of the ACM (JACM) 57 (4), 1-52, 2010 | 69 | 2010 |
Lower bounds for the noisy broadcast problem N Goyal, G Kindler, M Saks SIAM Journal on Computing 37 (6), 1806-1841, 2008 | 69 | 2008 |
Gaussian noise sensitivity and BosonSampling G Kalai, G Kindler arXiv preprint arXiv:1409.3093, 2014 | 63 | 2014 |
Understanding parallel repetition requires understanding foams U Feige, G Kindler, R O'Donnell Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07 …, 2007 | 63 | 2007 |
PCP characterizations of NP: Towards a polynomially-small error-probability I Dinur, E Fischer, G Kindler, R Raz, S Safra Proceedings of the thirty-first annual ACM symposium on theory of computing …, 1999 | 59 | 1999 |
Noise-resistant boolean functions are juntas G Kindler, S Safra preprint 5 (7), 19, 2002 | 56 | 2002 |
Direct sum testing R David, I Dinur, E Goldenberg, G Kindler, I Shinkar Proceedings of the 2015 Conference on innovations in theoretical computer …, 2015 | 44 | 2015 |
The UGC hardness threshold of the Lp Grothendieck problem G Kindler, A Naor, G Schechtman Mathematics of Operations Research 35 (2), 267-283, 2010 | 43 | 2010 |
Property testing PCP G Kindler Tel-Aviv University, 2002 | 41 | 2002 |
Hardness of approximating the closest vector problem with pre-processing M Alekhnovich, SA Khot, G Kindler, NK Vishnoi 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 216-225, 2005 | 37 | 2005 |