Paper Info
Title
On Non-Optimally Expanding Sets in Grassmann Graphs.
Abstract
We study the structure of non-expanding sets in the Grassmann graph. We put forth a hypothesis stating that every small set whose expansion is smaller than 1−δ must be correlated with one of a specified list of sets which are isomorphic to smaller Grassmann graphs. We develop a framework of Fourier analysis for analyzing functions over the Grassmann graph, and prove that our hypothesis holds for all sets whose expansion is below 7/8. In the companion submitted paper [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018], the authors show that a linearity agreement hypothesis implies an NP-hardness gap of 1/2− vs for unique games and other inapproximability results. In [Barak, Kothari and Steurer, ECCC TR18-077], the authors show that the hypothesis in this work implies the linearity agreement hypothesis of [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018]. Combined with our main theorem here this proves a version of the linearity agreement hypothesis with certain specific parameters. Short of proving the entire hypothesis, this nevertheless suffices for getting new unconditional NP hardness gaps for label cover with 2-to-1 and unique constraints. Our Expansion Hypothesis has been subsequently proved in its full form [Khot, Minzer and Safra, ECCC TR18-006] thereby proving the agreement hypothesis of [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] and completing the proof of the 2-to-1 Games Conjecture (albeit with imperfect completeness).
Year
DOI
Venue
2018
10.1145/3188745.3188806
STOC '18: Symposium on Theory of Computing Los Angeles CA USA June, 2018
Keywords
DocType
ISSN
PCP,2-to-2 Games,Unique Games,Grassmann Graph
Conference
0737-8017
ISBN
Citations 
PageRank 
978-1-4503-5559-9
7
0.54
References 
Authors
7
5
Name
Order
Citations
PageRank
Irit Dinur1118785.67
Subhash Khot22064112.51
Guy Kindler351532.02
Dor Minzer4366.60
Muli Safra514912.53