2-to-2 Games Theorem via Expansion in the Grassmann Graph

2-to-2 Games Theorem via Expansion in the Grassmann Graph

2-to-2 Games Theorem via Expansion in the Grassmann Graph Based on joint works with Irit Dinur, Guy Kindler, Dor Minzer, Muli Safra NP-hard Problems Traveling Salesperson 3-SAT All equivalent to each other (in the exact version). P NP There is no fast (polynomial time) algorithm.

Can we compute approximate solutions fast? (practice, theory, math). NP-hard Problems How well can we approximate? Traveling Salesperson Within 1% [Arora, Mitchell 98] Focus of this talk: Hardness of approximation Amazing progress so far. Many challenges remain. Exact versus Approximate: a different ballgame. 3-SAT but not better [Hstad 96] Hardness of Approximation: Historically

1970 NP-hardness 1990 PCP Theorem [Cook, Karp, Levin] [Arora, Babai, Feige, Fortnow, Goldwasser] [Karloff, Lund, Motwani, Nisan, Safra, Shamir, Sudan, Szegedy] 19952015 Recipe: 2-Prover-1-Round Games, Parallel Repetition, Fourier Analysis [Bellare, Chan, Dinur, Feige, Goldreich, Guruswami, Hstad, K] [Kindler, Moshkovitz, Mossel, ODonnell, Raz, Regev] [Raghavendra, Safra, Samorodnitsky, Sudan, Steurer, Trevisan]

2018 2-to-2 Games Theorem [Dinur, K, Kindler, Minzer, Safra] ?? Unique Games Conjecture [K] ?? Small Set Expansion Conjecture [Raghavendra, Steurer] PCP Theorem

Gap-SAT , s.t. given satisfiable NP-hard to satisfy fraction of clauses. Gap-reductions Use PCP Theorem as starting point for hardness of approx. results. Often challenging. Examples [Hastad, Feige] 3SAT hard to approx. within Clique , Set-Cover (1-) . Limits Clique [Hastad] Hardness of approx.

Given , it is NP-hard to distinguish between two cases: YES case: has clique of size . NO case: has no clique of size . Hardness when clique size is ? Equivalent Promise formulation promised to contain clique of size . Hard to find clique of size . Clique: Gap-Clique , is a Clique if any are adjacent.

Promise: Goal: find a Clique of size ? of size ? of size ? Still seemingly hard. Related: Independent Set, Vertex Cover, Graph Coloring Towards hardness: stronger assumptions? Unique Games Definition A unique game[q]: variables , equations Each equation of form . E.g: Max-cut ( , ) , =1( 2) Assignment is a mapping .

Satisfies the equation for if Goal 0 Find an assignment that satisfies as many equations as possible. Value = max fraction of satisfied equations by any assignment. 1 Unique Games Conjecture [2002] s.t. given UG[q] instance -- NP-hard to distinguish between: Value Value Implications Evidence?

Many In the eyes of the beholder. Absence of evidence is not evidence of absence. For: basic integrality gaps [K Vishnoi], candidate construction [K Moshkovitz]. Against: seemingly plenty. Simplest Hard Problem ? Many other problems are hard to approximate. Many more . Max Acyclic Subgraph Unique / 2-to-2 Games Conjecture All CSPs Clique, Independent Set Max Cut Algorithms, Optimization.

Computational complexity. (Boolean function) Analysis, Geometry. 2-to-2 Games Definition Similar to Unique-Games. Equations of the form . Conjecture For every , NP-hard to distinguish between: Value = Value Theorem Evidence towards UGC [K Minzer Safra, Dinur K Kindler MS, DKKMS, KMS] [K, KS, Barak Kothari Steurer,

, given a 2-to-2 Game it is NP-hard to distinguish: Value Value KM Moshkovitz S] is NP-hard Implications: New NP-Hardness Games Results 2-to-2-Games, Unique-Games. Clique, Graph Coloring, Max-Cut Clique Vertex-Cover. [Dinur Safra, K ] Coloring (almost) 4-colorable graphs with O(1) colors [Dinur Mossel Regev]. Max-Cut-Gain: Max-Cut[K ODonnell]. Intermediate CSP [Barak] Under standard complexity assumption, such that UG is solved in

time [Arora Barak Steurer], but not in time . Evidence Against Unique Games Conjecture No known distribution over hard instances. In contrast to 3SAT, Factoring, Clique( n1/3 ). No known counter-example to Sum-of-Squares algorithm. Strengthening of Lovasz -function, Goemans-Williamson Semi-Definite Program. Common techniques cannot construct a counter-example. [ Arora Barak Brando Harrow Kelner Kolla Makarychev2 Steurer Zhou ] Evidence Against Unique Games Conjecture Improve Arora-Barak-Steurer algorithm? to ? n variable constraint satisfaction problem with intermediate 2-to-2 Games Conjecture complexity [ would be

counter-intuitive. correct nevertheless! Cart before the Horse Run the reduction: 3SAT 2-to-2 Games. Distribution over hard instances. Counter-example to Sum-of-Squares algorithm. Logically should precede NP-hardness reduction, but happens the other way around . [Barak, Windows on Theory] One way to resolve this conundrum is that while the unique games problem may well be hard in the worst case, it is extremely hard to come up with actual hard instances for it. .. Trump

While it is theoretically still possible for the unique games conjecture to be false (as I personally believed would be the case until this latest sequence of results) the most likely scenario is now that the UGC is true, PCPs and Codes PCP: how gap NP-hardness is obtained The core of a typical PCP contains: An error-correcting code (RM, Hadamard, Long-code) A query-efficient test: 1. Query t entries in given word F. 2. Accept/Reject 3. Pr[Accept]> F close to codeword

From test to PCP? not clear. But, Properties of test determine gap-problem shown to be hard. PCPs and codes PCP: how gap NP-hardness is obtained The core of a typical PCP contains: Anhardness To get for 2-to-2 Games, we need

a new code and a error-correcting code (RM, Hadamard, Long-code) A new test: query-efficient test: 1. Query t entries The in given word F. Grassmann code/test 2. Accept/Reject 3. Pr[Accept]> F close to codeword

From test to PCP? not clear. But, Properties of test determine gap-problem shown to be hard. 2-to-2 Games Hardness (~ A + B pages) PCP Theorem Gap-3SAT

Parallel Repetition Smooth Parallel Repetition Gap-Linear-LabelCover Encoding by Grassmann Code Subcode covering Gap-LablelCover Proof complexity of random 3LIN(2) Encoding by Longcode Gap-3LIN(2) Zoom (decoding from next-to-nothing) Expansion of Grassmann graph

Hardness of 2-to-2 Games The Grassmann Graph Definition ( , ) V is a linear space over F2, dimension Vertices: . Edges : . Next Grassmann Code + Grassmann Test Expansion in the Grassmann Graph. 1

Grassmann-code Grassmann Test Encoding of linear is . Test: Each edge - local consistency check: edge tests whether , agree on 2-to-2 Test Agreeing assignments align in pairs according to restrictions to . Any function on has two extension to and to Local to Global Completeness: codeword G passes test w.p. 1. Soundness: If G passes of the tests, then G corresponds to a global ? Not in the most obvious sense

Graph Expansion Definition G=(V,E) d-regular The expansion of is is the set of edges from S to its complement. S Expander Usually: for all often constant degree. For us: concern is: expansion for small sets, e.g. In Grassmann Fact: A random small set has expansion 1Are o(1).there ?

sets with Yes! Subgraphs that are Grassmann-- non expanding Example: zoom-in For any consider . for all , a random neighbor in w. Dual example: zoom-out Take of co-dimension 1. . : , a random neighbor is in w. Note Induced subgraph is isomorphic to smaller Grassmann Graph.

zooming into spaces contain ing- / ed-in- gives constant density Definition is -pseudorandom if density of after combination of dimension remains Expansion statement every zoom-in/out Note Random small set is pseudorandom. Previous two examples: not -pseudorandom. I.e. zo om in/ out, increa se den Expansion Statement: si ty

signifi cantly If has expansion , then S is not-pseudorandom. Expansion Statement (contra-positive) [proposed in DKKMS]: If is pseudorandom, then near-perfect expansion. Motivation? hoped studying this question would help analyze local to global Grassmann Test. Turns out we were right (and blind). [DKKMS] Statement s u ffices to prove 2-to2 Theorem

[DKKMS]: Theorem [Barak Kothari Steurer] Expansion Statement local to global test works! Results Definition is -pseudorandom if density of after combination of dimension remains Expansion Statement [KMS] s.t. if -pseudorandom, then . Earlier [DKKMS] If S is pseudorandom, then If S is pseudorandom, then

every zoom-in/out Tools in the proof Ingredients: Lots of Fourier Analysis. On the Boolean hypercube: can be represented as monomial basis. Fourier analysis on Grassmann No such canonical basis need to use block decomposition. Or on different but related graph Summary Theorems On Grassmann: Pseudorandomness near-perfect expansion. Also on Johnson Graphs [KM Moshkovitz S] Implications Refuting UG must exploit

near perfect completeness. 2-to-2 Games, NP-hard New NP-hardness for Clique, Vertex Cover, (almost) Graph Coloring, Max-Cut Mysteries finally unraveling. Future research Greater mysteries ahead.

Recently Viewed Presentations