Unique Games Conjecture

  • Unique Label Cover(ULC): An undirected graph $G(V,E)$, $q$ colors, each dege $e$ associated with a bijection $\phi_e:[q]\rightarrow[q]$. A coloring $\sigma\in[q]^V$ satisfies the constraint of the edge $e=(u,v)\in E$ if $\phi_{e}(\sigma_u)=\phi_e(\sigma_v)$
  • UGC(2002 Khot): $\forall e,\exists q$ such that this is $\text{NP}$-hard to ditinguish between ULC instances:
    • $>1-\epsilon$ fraction of edges satisfied by a coloring;
    • no more than $\epsilon$ fraction of edges satisfied by any coloring

Constraint Satisfaction Problem

  • CSP Definition
    • variables: $V={v_1,v_2,\cdots,v_n},v_i\in\Omega$
    • constraints: $C_1,C_2,\cdots,C_m,C_i:\Omega^{S_i}\rightarrow{T,F},S_i\subset X$
    • assignment: $\sigma\in[q]^V$
    • $\mu(\sigma)=\prod_{i=1}^mC_i(\sigma_{S_i})/Z$
  • CSP
    • satisfiability: determine whether $\exists$ an assignment satisfying all constraints
      • search: find an assignment
    • optimization: find an assignment satisfying as may constraints as possible
      • refutation: find a proof of no assignment can satisfy $>m^$ constraints for $m^$ as small as possible
    • counting: estimate the number of satisfying assignments
      • sampling: random sample a satisfying assignments
      • inference: calculate the possibility of a variable being assigned certain value
CSP Satisfiability Optimization Counting
2SAT P NP-hard #P-complete
3SAT NP-complete NP-hard #P-complete
matching P P #P
2-coloring(cut) P NP-hard FP
3-coloring NP-complete NP-hard #P-complete
  • Poly-time inter-reducible
    • appox. counting
    • sampling
    • approx. inference
  • Random Sampling
    • Uniform independent set in graphs of max-degree $\Delta$: (poly-time when $\Delta$≤5, NP-hard when $\Delta$≥6 or higher
    • Uniform matching in any graph (always poly-time)
    • Uniform proper$q$-coloring of graphs of max-dgree $\Delta$: NP-hard when $q<\Delta$
  • $k$-SAT
    • $\Omega={T,F}$, constraints are clauses
    • $k$-CNF: each clause contains $k$ variables
    • Determine satisfiability
    • degree $d$: each clause intersects with $\leq d$ other clauses

Lovász Local Lemma

  • Goal: $P(\bigwedge_{i=1}^m\overline{A}_i)>0$, $m$ bad event $A_1,\cdots,A_m$
    • union bound: $\sum_{i=1}^mP(A_i)<1$
    • PIE: $\sum_{I\subseteq{m},|I|>0}(-1)^{|I|-1}P(\bigwedge_{i\in S}A_i)<1$
    • LLL: $\forall i,P(A_i)\leq\frac{1}{4d}$ and $A_i$ is independent of all but $\leq d$ other bad events
  • LLL for $k$-SAT: $d\leq 2^{k-2}\Rightarrow\phi$ is always satisfiable
  • LLL (asymmetric version): $\exists \alpha_1,\alpha_2,\cdots,\alpha_m\in[0,1)$

$$\forall i:P(A_i)\leq\alpha_i\prod_{j\sim i}(1-\alpha_j)\Rightarrow P(\wedge_{i=1}^m\overline{A}_i)>\prod_{i=1}^m(1-\alpha_i)$$

Algorithmic LLL

Moser’s Algorithm

  • Algorithmic LLL for $k$-SAT(Moser 2009): $d\leq 2^{k-c}\Rightarrow$ satisfying assignment can be found in time $O(n+km)$ w.h.p.
  • Algorithm
    • Solve($\phi$)
      • sample a uniform random assignment
      • while $\exists$ unsatisfied clause $C$: Fix($C$)
    • Fix($C$)
      • resample variables in $C$ uniformly at random
      • while $\exists$ unsatisfied clause $D$ intersecting $C$: Fix($D$)
  • Analysis
    • $T$: total # of calls to Fix($C$)
    • # of random bits: $n+kT$
      • $n$: intial bits
      • $kT$: each calls resampling uses $k$ bits
    • transcript($\leq m+T(\log_2 d+O(1))$ bits) + $n$ bits
      • $n$: final bits
      • $m$: Fix calls order in Solve
      • $T(\log_2 d+O(1))$: recursive calls order
    • 1-1 mapping between above: $n+kT-\log_2 n\leq m+T(\log_2d+O(1))+n\Rightarrow T\leq m+\log_2n$
    • $O(n+k(m+\log n))=O(n+km)$
  • Incompressibility Theorem(Kolmogorov): $N$ uniform random bits cannot be encoded to less than $N-l$ bits with probability at least $1-O(2^{-l})$

Moser-Tardos Algorithm

  • Suppose $A_1,\cdots,A_m$ are determined by mutually independent random variables $X_1,\cdots,X_n$, then LLL conditions $\Rightarrow\exists$ an assignment of $X_1,\cdots,X_n$ avoiding all bad events $A_1,\cdots,A_m$
    • $\text{vbl}(A_i)$: set of variables on which $A_i$ is defined
    • $\Gamma(A_i)={A_j|j\neq i\wedge\text{vbl}(A_i)\cap\text{vbl}(A_j)\neq\emptyset}$
  • Assumption: followings can be done efficiently
    • draw an independent sample on a random variable $X_j$
    • check whether a bad event $A_i$ occurs on current $X_1,\cdots,X_n$
  • Moser-Tardos Algorithm
    • sample all $X_1,\cdots,X_n$
    • while $\exists$ an occurring bad event $A_i$
      • resample all $X_j\in\text{vbl}(A_i)$
  • Algorithmic LLL(Moser-Tardos 2010): $\exists\alpha_1,\alpha_2,\cdots,\alpha_m\in[0,1)$

$$\forall i,P(A_i)\leq\alpha_i\prod_{j\sim i}(1-\alpha_j)\Rightarrow E[\text{resamples until a satisfying assignment is returned}]\leq \sum_{i=1}^m\frac{\alpha_i}{1-\alpha}$$

$$\forall i,P(A_i)\leq\frac{1}{e(d+1)}\Rightarrow E[\text{resamples until a satisfying assignment is returned}]\leq \frac{m}{d}$$

$$\forall i,P(A_i)\leq\frac{1}{4d}\Rightarrow E[\text{resamples until a satisfying assignment is returned}]\leq \frac{m}{2d-1}$$

  • Ananlysis
    • execution log $\Lambda$: $\Lambda_i\in\mathcal{A}$
    • total # of times $A$ is resampled: $N_A=|{i|\Gamma_i=A}|$