ACM Digital Library home
ACM home
Advanced Search
10.1145/3568031acmbooksBook PagePublication PagesBookacm-pubtype
Skip header Section
On Monotonicity Testing and the 2-to-2 Games ConjectureDecember 2022
Publisher:
  • Association for Computing Machinery
  • New York
  • NY
  • United States
ISBN:978-1-4503-9968-5
Published:14 December 2022
Pages:
218
Appears In:
ACMACM Books
Purchase this BookRecommend ACM DL
ALREADY A SUBSCRIBER?SIGN IN
Skip Bibliometrics Section
Bibliometrics
Citation count
0
Downloads (6 weeks)
5
Downloads (12 months)
49
Downloads (cumulative)
49
Skip Abstract Section
Abstract

This book discusses two questions in Complexity Theory: the Monotonicity Testing problem and the 2-to-2 Games Conjecture.

Monotonicity testing is a problem from the field of property testing, first considered by Goldreich et al. in 2000. The input of the algorithm is a function, and the goal is to design a tester that makes as few queries to the function as possible, accepts monotone functions and rejects far-from monotone functions with a probability close to 1.

The first result of this book is an essentially optimal algorithm for this problem. The analysis of the algorithm heavily relies on a novel, directed, and robust analogue of a Boolean isoperimetric inequality of Talagrand from 1993.

The probabilistically checkable proofs (PCP) theorem is one of the cornerstones of modern theoretical computer science. One area in which PCPs are essential is the area of hardness of approximation. Therein, the goal is to prove that some optimization problems are hard to solve, even approximately. Many hardness of approximation results were proved using the PCP theorem; however, for some problems optimal results were not obtained. This book touches on some of these problems, and in particular the 2-to-2 games problem and the vertex cover problem.

The second result of this book is a proof of the 2-to-2 games conjecture (with imperfect completeness), which implies new hardness of approximation results for problems such as vertex cover and independent set. It also serves as strong evidence towards the unique games conjecture, a notorious related open problem in theoretical computer science. At the core of the proof is a characterization of small sets of vertices in Grassmann graphs whose edge expansion is bounded away from 1.

Book Downloads

PDFFront matter (Title page, ACM Books, Contents, Acknowledgments, Bibliography, Biographies, Index)

References

  1. N. Ailon, B. Chazelle, S. Comandur, and D. Liu. 2007. Estimating the distance to a monotone function. Random Struct. Algorithms 31, 3, 371–383. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  2. A. Antoniadis, S. Kisfaludi-Bak, B. Laekhanukit, and D. Vaz. 2022. On the approximability of the traveling salesman problem with line neighborhoods. In A. Czumaj and Q. Xin (Eds.), 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022, June 27–29, 2022, Tórshavn, Faroe Islands. Vol. 227. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 10:1–10:21. DOI: . Retrieved from https://arxiv.org/abs/2008.12075.Google ScholarGoogle ScholarCross RefCross Ref
  3. S. Arora. 1994. Probabilistic Checking of Proofs and the Hardness of Approximation Problems. Ph.D. thesis. UC Berkeley.Google ScholarGoogle Scholar
  4. S. Arora and S. Safra. 1998. Probabilistic checking of proofs: A new characterization of NP. J. ACM 45, 1, 70–122. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. S. Arora and M. Sudan. 2003. Improved low-degree testing and its applications. Combinatorica 23, 3, 365–426. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  6. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. 1998. Proof verification and the hardness of approximation problems. J. ACM 45, 3, 501–555. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. S. Arora, E. Berger, E. Hazan, G. Kindler, and M. Safra. 2005. On non-approximability for quadratic programs. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005). IEEE Computer Society, 206–215. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. S. Arora, S. Khot, A. Kolla, D. Steurer, M. Tulsiani, and N. K. Vishnoi. 2008. Unique games on expanding constraint graphs are easy: Extended abstract. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC 2008. ACM, 21–28. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. S. Arora, B. Barak, and D. Steurer. 2015. Subexponential algorithms for unique games and related problems. J. ACM 62, 5, 1–25. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. M. Bafna, B. Barak, P. K. Kothari, T. Schramm, and D. Steurer. 2021. Playing unique games on certified small-set expanders. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, STOC’21. ACM, 1629–1642. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. M. Bafna, M. Hopkins, T. Kaufman, and S. Lovett. 2022a. Hypercontractivity on high dimensional expanders. In S. Leonardi and A. Gupta (Eds.), STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20–24, 2022. ACM, 185–194. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. M. Bafna, M. Hopkins, T. Kaufman, and S. Lovett. 2022b. High dimensional expanders: Eigenstripping, pseudorandomness, and unique games. In Proceedings of the 2022 Annual ACM–SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1069–1128. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  13. B. Barak. 2017. The intermediate complexity conjecture. Blog post. https://windowsontheory.org/2017/08/09/the-intermediate-complexity-conjecture/.Google ScholarGoogle Scholar
  14. B. Barak, F. G. S. L. Brandão, A. W. Harrow, J. A. Kelner, D. Steurer, and Y. Zhou. 2012. Hypercontractivity, sum-of-squares proofs, and their applications. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012. ACM, 307–326. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. B. Barak, P. K. Kothari, and D. Steurer. 2019. Small-set expansion in shortcode graph and the 2-to-2 conjecture. In A. Blum (Ed.), 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10–12, 2019, San Diego, California, USA. Vol. 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 9:1–9:12. DOI: . https://eccc.weizmann.ac.il/report/2018/077.Google ScholarGoogle ScholarCross RefCross Ref
  16. A. Belovs and E. Blais. 2015. Quantum algorithm for monotonicity testing on the hypercube. Theory Comput. 11, 403–412. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  17. A. Belovs and E. Blais. 2021. A polynomial lower bound for testing monotonicity. SIAM J. Comput. 50, 3. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  18. M. Bellare, O. Goldreich, and M. Sudan. 1998. Free its, PCPs, and nonapproximability—Towards tight results. SIAM J. Comput. 27, 3, 804–915. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. A. Bhangale and S. Khot. 2022. UG-hardness to NP-hardness by Losing Half. Theory Comput. 18, 1, 1–28. Theory of Computing Exchange.Google ScholarGoogle ScholarCross RefCross Ref
  20. A. Bhangale, S. Khot, and D. Minzer. 2022. On approximability of satisfiable k-CSPs: I. In S. Leonardi and A. Gupta (Eds.), STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20–24, 2022. ACM, 976–988. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. M. Blum, M. Luby, and R. Rubinfeld. 1993. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47, 3, 549–595. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. V. M. Blinovsky. 1986. Bounds for codes in the case of list decoding of finite volume. Probl. Inf. Transm. 22, 1, 7–19. https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=839&option_lang=eng.Google ScholarGoogle Scholar
  23. J. Brakensiek, V. Guruswami, and S. Sandeep. 2021. Conditional dichotomy of Boolean ordered promise CSPs. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021. Schloss Dagstuhl–Leibniz-Zentrum für Informatik 37, 1–37, 15. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  24. M. Braverman, S. Khot, N. Lifshitz, and D. Minzer. 2021a. An invariance principle for the multi-slice, with applications. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022. IEEE, 228–236. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  25. M. Braverman, S. Khot, and D. Minzer. 2021b. On rich 2-to-1 games. In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 27, 1–27, 20. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  26. J. Briët, S. Chakraborty, D. Garca-Soriano, and A. Matsliah. 2012. Monotonicity testing and shortest-path routing on the cube. Combinatorica 32, 1, 35–53. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. D. Chakrabarty and C. Seshadhri. 2013a. A o(n) monotonicity tester for Boolean functions over the hypercube. In Symposium on Theory of Computing Conference, STOC’13. ACM, 411–418. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. D. Chakrabarty and C. Seshadhri. 2013b. Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. In Symposium on Theory of Computing Conference, STOC’13. ACM, 419–428. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. D. Chakrabarty and C. Seshadhri. 2013c. An optimal lower bound for monotonicity testing over hypergrids. In Proceedings Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques—16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Vol. 8096: Lecture Notes in Computer Science. Springer, 425–435. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  30. M. Charikar, K. Makarychev, and Y. Makaryshev. 2006. Near-optimal algorithms for unique games. In Proc. 38th ACM Symposium on Theory of Computing. ACM, 205–214. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar. 2006. On the hardness of approximating multicut and sparsest-cut. Comput. Complex. 15, 2, 94–114. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. X. Chen, R. A. Servedio, and L. Y. Tan. 2014. New algorithms and lower bounds for monotonicity testing. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014. IEEE Computer Society, 286–295. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  33. X. Chen, A. De, R. A. Servedio, and L. Y. Tan. 2015. Boolean function monotonicity testing requires (almost) n1/2 non-adaptive queries. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2015. ACM, 519–528. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  34. X. Chen, E. Waingarten, and J. Xie. 2017a. Beyond Talagrand functions: New lower bounds for testing monotonicity and unateness. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017. ACM, 523–536. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  35. X. Chen, E. Waingarten, and J. Xie. 2017b. Boolean unateness testing with Õ(n3/4) adaptive queries. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017. IEEE, 868–879. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  36. V. Cohen-Addad, C. S. Karthik, and E. Lee. 2021. On approximability of clustering problems without candidate centers. In Proceedings of the 2021 ACM–SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2635–2648. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  37. P. Crescenzi, R. Silvestri, and L. Trevisan. 2001. On weighted vs unweighted versions of combinatorial optimization problems. Inf. Comput. 167, 1, 10–26. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  38. I. Dinur and S. Safra. 2005. On the hardness of approximating minimum vertex cover. Ann. Math. 162, 1, 439–485. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  39. I. Dinur and D. Steurer. 2014. Analytical approach to parallel repetition. In Symposium on Theory of Computing, STOC 2014. ACM, 624–633. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  40. I. Dinur, E. Friedgut, and O. Regev. 2008. Independent sets in graph powers are almost contained in juntas. Geom. Funct. Anal. 18, 1, 77–97. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  41. I. Dinur, E. Mossel, and O. Regev. 2009. Conditional hardness for approximate coloring. SIAM J. Comput. 39, 3, 843–873. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  42. I. Dinur, S. Khot, G. Kindler, D. Minzer, and M. Safra. 2018a. Towards a proof of the 2-to-1 games conjecture? In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018. ACM, 376–389. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  43. I. Dinur, S. Khot, G. Kindler, D. Minzer, and M. Safra. 2018b. On non-optimally expanding sets in Grassmann graphs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018. ACM, 940–951. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  44. S. Fattal and D. Ron. 2010. Approximating the distance to monotonicity in high dimensions. ACM Trans. Algorithms 6, 3, 1–37. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  45. U. Feige. 1998. A threshold of ln n for approximating set cover. J. ACM 45, 4, 634–652. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  46. U. Feige and D. Reichman. 2004. On systems of linear equations with two variables per equation. In 8th International Workshop on Randomization and Computation, RANDOM 2004, Vol. 3122. Lecture Notes in Computer Science. Springer, 117–127. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  47. U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy. 1996. Interactive proofs and the hardness of approximating cliques. J. ACM 43, 2, 268–292. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  48. Y. Filmus, G. Kindler, N. Lifshitz, and D. Minzer. 2020. Hypercontractivity on the symmetric group. arXiv:2009.05503. Retrieved from .Google ScholarGoogle ScholarCross RefCross Ref
  49. E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and A. Samorodnitsky. 2002. Monotonicity testing over general poset domains. In Proceedings on 34th Annual ACM Symposium on Theory of Computing. ACM, 474–483. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  50. C. M. Fortuin, P. W. Kasteleyn, and J. Ginibre. 1971. Correlation inequalities on some partially ordered sets. Comm. Math. Phys. 22, 89–103. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  51. E. Friedgut. 1998. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica 18, 1, 27–35. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  52. E. Friedgut and O. Regev. 2018. Kneser graphs are like Swiss cheese. Discrete Anal. 2, 18. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  53. O. Goldreich. 2017. Introduction to Property Testing. Cambridge University Press. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  54. O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samorodnitsky. 2000. Testing monotonicity. Combinatorica 20, 3, 301–337. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  55. D. Grigoriev. 2001. Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theor. Comput. Sci. 259, 1–2, 613–622. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  56. A. Gupta and K. Talwar. 2006. Approximating unique games. In Proceedings of the Seventeenth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2006. Society for Industrial and Applied Mathematics, 99–106. http://dl.acm.org/citation.cfm?id=1109557.1109569.Google ScholarGoogle ScholarCross RefCross Ref
  57. T. Gur, N. Lifshitz, and S. Liu. 2021. Hypercontractivity on high dimensional expanders: Approximate Efron–Stein decompositions for ϵ-product spaces. Electron. Colloquium Comput. Complex. 168. https://eccc.weizmann.ac.il/report/2021/168.Google ScholarGoogle Scholar
  58. V. Guruswami and A. K. Sinop. 2013. Improved inapproximability results for maximum k-colorable subgraph. Theory Comput. 9, 413–435. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  59. J. Håstad. 1999. Clique is hard to approximate within n1−ε. Acta Math. 182, 1, 105–142. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  60. J. Håstad. 2001. Some optimal inapproximability results. J. ACM 48, 4, 798–859. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  61. J. Håstad, S. Huang, R. Manokaran, R. O’Donnell, and J. Wright. 2017. Improved NP-inapproximability for 2-variable linear equations. Theory Comput. 13, 1, 1–51. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  62. R. Impagliazzo and R. Paturi. 2001. On the complexity of k-SAT. J. Comput. Syst. Sci. 62, 2, 367–375. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  63. T. Kaufman and D. Minzer. 2022. Improved optimal testing results from global hypercontractivity. arXiv:2202.08688. Retrieved from .Google ScholarGoogle ScholarCross RefCross Ref
  64. P. Keevash, N. Lifshitz, E. Long, and D. Minzer. 2021a. Forbidden intersections for codes. arXiv:2103.05050. Retrieved from .Google ScholarGoogle ScholarCross RefCross Ref
  65. P. Keevash, N. Lifshitz, E. Long, and D. Minzer. 2021b. Global hypercontractivity and its applications. arXiv:2103.04604. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  66. P. Keevash, N. Lifshitz, E. Long, and D. Minzer. 2022. On the largest product-free subsets of the alternating groups. arXiv preprint arXiv:2205.15191.Google ScholarGoogle Scholar
  67. S. Khot. 2002. On the power of unique 2-prover 1-round games. In Proceedings of the 17th Annual IEEE Conference on Computational Complexity. IEEE, 25. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  68. S. Khot. 2010. Inapproximability of NP-complete problems, discrete Fourier analysis, and geometry. In Proceedings of the International Congress of Mathematicians 2010. World Scientific, 2676–2697. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  69. S. Khot and R. O’Donnell. 2009. SDP gaps and UGC-hardness for max-cut-gain. Theory Comput. 5, 1, 83–117. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  70. S. Khot and O. Regev. 2008. Vertex cover might be hard to approximate to within 2 − ε. J. Comput. Syst. Sci. 74, 3, 335–349. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  71. S. Khot and M. Safra. 2013. A two-prover one-round game with strong soundness. Theory Comput. 9, 863–887. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  72. S. Khot, G. Kindler, E. Mossel, and R. O’Donnell. 2007. Optimal inapproximability results for max-cut and other 2-variable CSPs? SIAM J. Comput. 37, 1, 319–357. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  73. S. Khot, D. Minzer, and M. Safra. 2015. On monotonicity testing and Boolean isoperimetric type theorems. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. IEEE, 52–58. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  74. S. Khot, D. Minzer, and M. Safra. 2017. On independent sets, 2-to-2 games, and Grassmann graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017. ACM, 576–589. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  75. S. Khot, D. Minzer, D. Moshkovitz, and M. Safra. 2018a. Small set expansion in the Johnson graph. Electron. Colloquium Comput. Complex. 25, 78. https://eccc.weizmann.ac.il/report/2018/078.Google ScholarGoogle Scholar
  76. S. Khot, D. Minzer, and M. Safra. 2018b. Pseudorandom sets in Grassmann graph have near-perfect expansion. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018. IEEE, 592–601. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  77. A. Kolla. 2011. Spectral algorithms for unique games. Comput. Complex. 20, 2, 177–206. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  78. E. Lehman and D. Ron. 2001. On disjoint chains of subsets. J. Comb. Theory A 94, 2, 399–404. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  79. N. Lifshitz and D. Minzer. 2019. Noise sensitivity on the p-biased hypercube. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019. IEEE, 1205–1226. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  80. G. A. Margulis. 1974. Probabilistic characteristics of graphs with large connectivity. Problemy Peredači Informacii 10, 2, 101–108. http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=1034&option_lang=eng.Google ScholarGoogle Scholar
  81. R. O’Donnell and J. Wright. 2012. A new point of NP-hardness for unique games. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012. ACM, 289–306. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  82. C. H. Papadimitriou and M. Yannakakis. 1991. Optimization, approximation, and complexity classes. J. Comput. Sys. Sci. 43, 3, 425–440. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  83. P. Raghavendra. 2008. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC’08. ACM, 245–254. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  84. P. Raghavendra and D. Steurer. 2010. Graph expansion and the unique games conjecture. In Proceedings of the 42nd ACM Symposium on Theory of Computing. ACM, 755–764. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  85. A. Rao. 2011. Parallel repetition in projection games and a concentration bound. SIAM J. Comput. 40, 6, 1871–1891. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  86. R. Raz. 1998. A parallel repetition theorem. SIAM J. Comput. 27, 3, 763–803. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  87. R. Raz and S. Safra. 1997. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing. ACM, 475–484. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  88. D. Ron, R. Rubinfeld, M. Safra, A. Samorodnitsky, and O. Weinstein. 2012. Approximating the Influence of monotone Boolean functions in O(√n) query complexity. ACM Trans. Comput. Theory 4, 4, 1–12. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  89. R. Rubinfeld and M. Sudan. 1996. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25, 2, 252–271. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  90. L. Russo. 1982. An approximate zero-one law. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 61, 1, 129–139. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  91. G. Schoenebeck. 2008. Linear level Lasserre lower bounds for certain k-CSPs. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008. IEEE, 593–602. DOI: .Google ScholarGoogle ScholarDigital LibraryDigital Library
  92. M. Talagrand. 1993. Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis’ graph connectivity theorem. Geom. Funct. Anal. 3, 3, 295–314. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  93. L. Trevisan. 2008. Approximation algorithms for unique games. Theory Comput. 4, 1, 111–128. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  94. L. Trevisan. 2012. On Khot’s unique games conjecture. Bull. Am. Math. Soc. (N.S.) 49, 1, 91–111. DOI: .Google ScholarGoogle ScholarCross RefCross Ref
  95. E. Waingarten. 2018. Personal communication.Google ScholarGoogle Scholar
Contributors
  • Dor Minzer
    Massachusetts Institute of Technology

Index Terms

(auto-classified)
  1. On Monotonicity Testing and the 2-to-2 Games Conjecture
        Comments
        About Cookies On This Site

        We use cookies to ensure that we give you the best experience on our website.

        Learn more

        Got it!