Pseudorandom sets in Grassmann graph have near-perfect expansion. (English) Zbl 07690461
Summary: We prove that pseudorandom sets in Grassmann graph have near-perfect expansion. This completes the proof of the \(2\)-to-\(2\) Games Conjecture (albeit with imperfect completeness). Some implications of this new result are improved hardness results for Minimum Vertex Cover, improving on the work of Dinur and Safra [Ann. of Math. 162 (2005), 439-485], and new hardness gaps for Unique-Games.
The Grassmann graph \(\mathsf{Gr}_{\mathsf{global}}\) contains induced subgraphs \(\mathsf{Gr}_{\mathsf{local}}\) that are themselves isomorphic to Grassmann graphs of lower orders. A set is called pseudorandom if its density is \(o(1)\) inside all subgraphs \(\mathsf{Gr}_{\mathsf{local}}\) whose order is \(O(1)\) lower than that of \(\mathsf{Gr}_{\mathsf{global}}\). We prove that pseudorandom sets have expansion \(1-o(1)\), greatly extending the results and techniques of a previous work of the authors with Dinur and Kindler.
The Grassmann graph \(\mathsf{Gr}_{\mathsf{global}}\) contains induced subgraphs \(\mathsf{Gr}_{\mathsf{local}}\) that are themselves isomorphic to Grassmann graphs of lower orders. A set is called pseudorandom if its density is \(o(1)\) inside all subgraphs \(\mathsf{Gr}_{\mathsf{local}}\) whose order is \(O(1)\) lower than that of \(\mathsf{Gr}_{\mathsf{global}}\). We prove that pseudorandom sets have expansion \(1-o(1)\), greatly extending the results and techniques of a previous work of the authors with Dinur and Kindler.
MSC:
| 68-XX | Computer science |
Keywords:
probabilistically checkable proofs; unique-games conjecture; small-set expansion; hypercontractivityReferences:
| [1] | Arora, Sanjeev; Lund, Carsten, Approximation Algorithms for {NP-hard} Problems (1996) · Zbl 1368.68010 · doi:10.1145/261342.571216 |
| [2] | Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario, Proof verification and the hardness of approximation problems, J. ACM. Journal of the ACM, 45, 501-555 (1998) · Zbl 1065.68570 · doi:10.1145/278298.278306 |
| [3] | Arora, Sanjeev; Safra, Shmuel, Probabilistic checking of proofs: a new characterization of {NP}, J. ACM. Journal of the ACM, 45, 70-122 (1998) · Zbl 0903.68076 · doi:10.1145/273865.273901 |
| [4] | Arora, Sanjeev; Barak, Boaz; Steurer, David, Subexponential algorithms for unique games and related problems, J. ACM. Journal of the ACM, 62, 42-25 (2015) · Zbl 1426.05159 · doi:10.1145/2775105 |
| [5] | Arora, Sanjeev; Khot, Subhash A.; Kolla, Alexandra; Steurer, David; Tulsiani, Madhur; Vishnoi, Nisheeth K., Unique games on expanding constraint graphs are easy [extended abstract]. S{TOC}\('08, 21-28 (2008)\) · Zbl 1231.68147 · doi:10.1145/1374376.1374380 |
| [6] | Barak, Boaz, The intermediate complexity conjecture · Zbl 1512.94062 |
| [7] | Barak, Boaz; Brand\~{a}o, Fernando G. S. L.; Harrow, Aram W.; Kelner, Jonathan; Steurer, David; Zhou, Yuan, Hypercontractivity, sum-of-squares proofs, and their applications [extended abstract]. S{TOC}’12—{P}roceedings of the 2012 {ACM} {S}ymposium on {T}heory of {C}omputing, 307-326 (2012) · Zbl 1286.68176 · doi:10.1145/2213977.2214006 |
| [8] | Barak, Boaz; Gopalan, Parikshit; H{\aa}stad, Johan; Meka, Raghu; Raghavendra, Prasad; Steurer, David, Making the long code shorter, SIAM J. Comput.. SIAM Journal on Computing, 44, 1287-1324 (2015) · Zbl 1330.68089 · doi:10.1137/130929394 |
| [9] | Barak, Boaz; Kothari, Pravesh K.; Steurer, David, Small-set expansion in shortcode graph and the 2-to-2 conjecture. 10th {I}nnovations in {T}heoretical {C}omputer {S}cience, LIPIcs. Leibniz Int. Proc. Inform., 124, 9-1 (2019) · Zbl 1518.68136 · doi:10.4230/LIPIcs.ITCS.2019.9 |
| [10] | Barak, Boaz; Kothari, Pravesh; Steurer, David, personal communication (2017) |
| [11] | Barak, Boaz; Raghavendra, Prasad; Steurer, David, Rounding semidefinite programming hierarchies via global correlation. 2011 {IEEE} 52nd {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience—{FOCS} 2011, 472-481 (2011) · Zbl 1292.90226 · doi:10.1109/FOCS.2011.95 |
| [12] | Bellare, Mihir; Goldreich, Oded; Sudan, Madhu, Free bits, {PCP}s, and nonapproximability-towards tight results, SIAM J. Comput.. SIAM Journal on Computing, 27, 804-915 (1998) · Zbl 0912.68041 · doi:10.1137/S0097539796302531 |
| [13] | Bhangale, Amey; Khot, Subhash, U{G}-hardness to {NP}-hardness by losing half. 34th {C}omputational {C}omplexity {C}onference, LIPIcs. Leibniz Int. Proc. Inform., 137, 3-20 (2019) · Zbl 07564403 |
| [14] | Braverman, Mark; Khot, Subhash; Minzer, Dor, On rich 2-to-1 games. 12th {I}nnovations in {T}heoretical {C}omputer {S}cience {C}onference, LIPIcs. Leibniz Int. Proc. Inform., 185, 27-20 (2021) |
| [15] | Chawla, Shuchi; Krauthgamer, Robert; Kumar, Ravi; Rabani, Yuval; Sivakumar, D., On the hardness of approximating multicut and sparsest-cut, Comput. Complexity. Computational Complexity, 15, 94-114 (2006) · Zbl 1132.68418 · doi:10.1007/s00037-006-0210-9 |
| [16] | Dinur, Irit; Khot, Subhash; Kindler, Guy; Minzer, Dor; Safra, Muli, On non-optimally expanding sets in {G}rassmann graphs. S{TOC}’18—{P}roceedings of the 50th {A}nnual {ACM} {SIGACT} {S}ymposium on {T}heory of {C}omputing, 940-951 (2018) · Zbl 1429.68077 · doi:10.1145/3188745.3188806 |
| [17] | Dinur, Irit; Khot, Subhash; Kindler, Guy; Minzer, Dor; Safra, Muli, Towards a proof of the 2-to-1 games conjecture?. S{TOC}’18—{P}roceedings of the 50th {A}nnual {ACM} {SIGACT} {S}ymposium on {T}heory of {C}omputing, 376-389 (2018) · Zbl 1429.68076 · doi:10.1145/3188745.3188804 |
| [18] | Dinur, Irit; Mossel, Elchanan; Regev, Oded, Conditional hardness for approximate coloring, SIAM J. Comput.. SIAM Journal on Computing, 39, 843-873 (2009) · Zbl 1192.68317 · doi:10.1137/07068062X |
| [19] | Dinur, Irit; Safra, Samuel, On the hardness of approximating minimum vertex cover, Ann. of Math. (2). Annals of Mathematics. Second Series, 162, 439-485 (2005) · Zbl 1084.68051 · doi:10.4007/annals.2005.162.439 |
| [20] | Efron, B.; Stein, C., The jackknife estimate of variance, Ann. Statist.. The Annals of Statistics, 9, 586-596 (1981) · Zbl 0481.62035 |
| [21] | Feige, Uriel, A threshold of {\( \ln n\)} for approximating set cover, J. ACM. Journal of the ACM, 45, 634-652 (1998) · Zbl 1065.68573 · doi:10.1145/285055.285059 |
| [22] | Feige, Uriel; Goldwasser, Shafi; Lov{\'{a}}sz, Laszlo; Safra, Shmuel; Szegedy, Mario, Interactive proofs and the hardness of approximating cliques, J. ACM. Journal of the ACM, 43, 268-292 (1996) · Zbl 0882.68129 · doi:10.1145/226643.226652 |
| [23] | Feige, Uriel; Lov{\'{a}}sz, Laszlo, Two-prover one-round proof systems, their power and their problems, Proc. 24th Annual ACM Symposium on Theory of Computing, 733-744 (1992) · doi:10.1145/129712.129783 |
| [24] | Filmus, Yuval; Kindler, Guy; Lifshitz, Noam; Minzer, Dor, Hypercontractivity on the symmetric group (2020) · Zbl 1474.94058 |
| [25] | Gowers, Timothy; Janzer, Oliver, Subsets of {C}ayley graphs that induce many edges, Theory Comput.. Theory of Computing. An Open Access Journal, 15, 20-29 (2019) · Zbl 1496.05073 · doi:10.4086/toc.2019.v015a020 |
| [26] | Grigoriev, Dima, Linear lower bound on degrees of {P}ositivstellensatz calculus proofs for the parity, Theoret. Comput. Sci.. Theoretical Computer Science, 259, 613-622 (2001) · Zbl 0974.68192 · doi:10.1016/S0304-3975(00)00157-2 |
| [27] | Guruswami, Venkatesan; Manokaran, Rajsekar; Raghavendra, Prasad, Beating the random ordering is hard: {I}napproximability of maximum acyclic subgraph. Proc. Annual IEEE Symposium on Foundations of Computer Science, 573-582 (2008) |
| [28] | Guruswami, Venkatesan; Sinop, Ali Kemal, Improved inapproximability results for maximum {\(k\)}-colorable subgraph, Theory Comput.. Theory of Computing. An Open Access Journal, 9, 413-435 (2013) · Zbl 1448.68246 · doi:10.4086/toc.2013.v009a011 |
| [29] | H{\aa}stad, Johan, Clique is hard to approximate within {\(n^{1-\epsilon}\)}, Acta Math.. Acta Mathematica, 182, 105-142 (1999) · Zbl 0989.68060 · doi:10.1007/BF02392825 |
| [30] | H{\aa}stad, Johan, Some optimal inapproximability results, J. ACM. Journal of the ACM, 48, 798-859 (2001) · Zbl 1127.68405 · doi:10.1145/502090.502098 |
| [31] | H{\aa}stad, Johan, On the efficient approximability of constraint satisfaction problems. Surveys in Combinatorics 2007, London Math. Soc. Lecture Note Ser., 346, 201-221 (2007) · Zbl 1129.68082 · doi:10.1017/CBO9780511666209.008 |
| [32] | Holenstein, Thomas, Parallel repetition: simplifications and the no-signaling case (extended abstract). S{TOC}’07—{P}roceedings of the 39th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing, 411-419 (2007) · Zbl 1211.68211 · doi:10.1145/1250790.1250852 |
| [33] | Karlin, Samuel; Rinott, Yosef, Applications of {ANOVA} type decompositions for comparisons of conditional variance statistics including jackknife estimates, Ann. Statist.. The Annals of Statistics, 10, 485-501 (1982) · Zbl 0491.62036 |
| [34] | Karp, Richard M., Reducibility among combinatorial problems. Complexity of Computer Computations, 85-103 (1972) · Zbl 1467.68065 · doi:10.1007/978-1-4684-2001-2_9 |
| [35] | Keevash, Peter; Lifshitz, Noam; Long, Eoin; Minzer, Dor, Hypercontractivity for global functions and sharp thresholds (2019) |
| [36] | Keevash, Peter; Lifshitz, Noam; Long, Eoin; Minzer, Dor, Sharp thresholds and expanded hypergraphs (2019) |
| [37] | Khot, Subhash, Inapproximability of {NP}-complete problems, discrete {F}ourier analysis, and geometry. Proceedings of the {I}nternational {C}ongress of {M}athematicians. {V}olume {IV}, 2676-2697 (2010) · Zbl 1252.68143 |
| [38] | Khot, Subhash, On the power of unique 2-prover 1-round games. Proceedings of the {T}hirty-{F}ourth {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing, 767-775 (2002) · Zbl 1192.68367 · doi:10.1145/509907.510017 |
| [39] | Khot, Subhash, On the unique games conjecture. 25th {A}nnual {IEEE} {C}onference on {C}omputational {C}omplexity—{CCC} 2010, 99-121 (2010) |
| [40] | Khot, Subhash, Hardness of approximation. Proceedings of the {I}nternational {C}ongress of {M}athematicians—{S}eoul 2014. {V}ol. 1, 711-728 (2014) · Zbl 1373.68239 · doi:10.1142/9789814324359_0163 |
| [41] | Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O’Donnell, Ryan, Optimal inapproximability results for {MAX}-{CUT} and other 2-variable {CSP}s?, SIAM J. Comput.. SIAM Journal on Computing, 37, 319-357 (2007) · Zbl 1135.68019 · doi:10.1137/S0097539705447372 |
| [42] | Subhash Khot; Dor Minzer; Dana Moshkovitz; Muli Safra, Small Set Expansion in The {J}ohnson Graph, Electron. Colloquium Comput. Complex.. https://dblp.org/rec/journals/eccc/KhotMMS18.bib, {TR18-078} (2018) |
| [43] | Khot, Subhash; Minzer, Dor; Safra, Muli, On independent sets, 2-to-2 games, and {G}rassmann graphs. S{TOC}’17—{P}roceedings of the 49th {A}nnual {ACM} {SIGACT} {S}ymposium on {T}heory of {C}omputing, 576-589 (2017) · Zbl 1370.68130 · doi:10.1145/3055399.3055432 |
| [44] | Khot, Subhash; Moshkovitz, Dana, {\( \mathcal{N}\mathcal{P} \)}-hardness of approximately solving linear equations over reals, SIAM J. Comput.. SIAM Journal on Computing, 42, 752-791 (2013) · Zbl 1272.68144 · doi:10.1137/110846415 |
| [45] | Khot, Subhash; Moshkovitz, Dana, Candidate hard unique game. S{TOC}’16—{P}roceedings of the 48th {A}nnual {ACM} {SIGACT} {S}ymposium on {T}heory of {C}omputing, 63-76 (2016) · Zbl 1373.68240 · doi:10.1145/2897518.2897531 |
| [46] | Khot, Subhash; O’Donnell, Ryan, S{DP} gaps and {UGC}-hardness for max-cut-gain, Theory Comput.. Theory of Computing. An Open Access Journal, 5, 83-117 (2009) · Zbl 1213.68313 · doi:10.4086/toc.2009.v005a004 |
| [47] | Khot, Subhash; Regev, Oded, Vertex cover might be hard to approximate to within {\(2-\epsilon \)}, J. Comput. System Sci.. Journal of Computer and System Sciences, 74, 335-349 (2008) · Zbl 1133.68061 · doi:10.1016/j.jcss.2007.06.019 |
| [48] | Khot, Subhash; Safra, Muli, A two prover one round game with strong soundness. 2011 {IEEE} 52nd {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience—{FOCS} 2011, 648-657 (2011) · Zbl 1292.68075 · doi:10.1109/FOCS.2011.62 |
| [49] | Khot, Subhash A.; Vishnoi, Nisheeth K., The unique games conjecture, integrability gap for cut problems and embeddability of negative-type metrics into {\( \ell_1\)}, J. ACM. Journal of the ACM, 62, 8-39 (2015) · Zbl 1321.68316 · doi:10.1145/2629614 |
| [50] | Kolla, Alexandra; Makarychev, Konstantin; Makarychev, Yury, How to play unique games against a semi-random adversary: study of semi-random models of unique games. 2011 {IEEE} 52nd {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience—{FOCS} 2011, 443-452 (2011) · Zbl 1292.68114 · doi:10.1109/FOCS.2011.78 |
| [51] | Lifshitz, Noam; Minzer, Dor, Noise sensitivity on the {\(p\)}-biased hypercube. 2019 {IEEE} 60th {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience, 1205-1226 ([2019] ©2019) · doi:10.1109/FOCS.2019.00075 |
| [52] | O’Donnell, Ryan, Analysis of {B}oolean Functions, xx+423 pp. (2014) · Zbl 1336.94096 · doi:10.1017/CBO9781139814782 |
| [53] | Raghavendra, Prasad; Steurer, David, Graph expansion and the unique games conjecture. S{TOC}’10—{P}roceedings of the 2010 {ACM} {I}nternational {S}ymposium on {T}heory of {C}omputing, 755-764 (2010) · Zbl 1293.05373 · doi:10.1145/1806689.1806792 |
| [54] | Raghavendra, Prasad, Optimal algorithms and inapproximability results for every {CSP}? [extended abstract]. S{TOC}\('08, 245-254 (2008)\) · Zbl 1231.68142 · doi:10.1145/1374376.1374414 |
| [55] | Rao, Anup, Parallel repetition in projection games and a concentration bound [extended abstract]. S{TOC}\('08, 1-10 (2008)\) · Zbl 1231.91025 · doi:10.1145/1374376.1374378 |
| [56] | Raz, Ran, A parallel repetition theorem, SIAM J. Comput.. SIAM Journal on Computing, 27, 763-803 (1998) · Zbl 0911.68082 · doi:10.1137/S0097539795280895 |
| [57] | Schoenebeck, Grant, Linear level {L}asserre lower bounds for certain k-{CSP}s. 49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS} 2008, October 25-28, 2008, Philadelphia, PA, {USA}, 593-602 (2008) |
| [58] | Trevisan, Luca, 2nd. Inapproximability of combinatorial optimization problems, Optimisation Combinatiore, 381-434 (2014) · Zbl 1204.90088 · doi:10.1002/9781119005353.ch13 |
| [59] | Trevisan, Luca, On {K}hot’s unique games conjecture, Bull. Amer. Math. Soc. (N.S.). American Mathematical Society. Bulletin. New Series, 49, 91-111 (2012) · Zbl 1280.68102 · doi:10.1090/S0273-0979-2011-01361-1 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
