Lower Bounds in Computational Complexity Boot Camp

Lower Bounds in Computational Complexity Boot Camp

• Based on Simons Institute Lectures: Lower Bounds in Computational Complexity Boot Camp on Simons

Circuit Lower Bounds from Algorithm Design Part 1

• Find Task $A'$ is possible for computation model $B'$ implies Task $A$ is possible for model $B$.
• Show that Task $A'$ is possible for computation model $B'$.
  • Task $A'$ is about analyzing model $B$.
  • Define Task $A$ in terms of model $B'$.
• If there exists a non-trivial circuit analysis, then this tells us about the limiatations of circuits in modeling algorithms.

Open Questions:

• $NEXP\subseteq P/poly$?
• $NP\subseteq SIZE(O(n))$? Best known $NP\subseteq SIZE(5n), SIZE(3.01n)$.

Generalized Circuit Satisfiability

• For any circuit class $\mathcal{C}$ we can define $\mathcal{C}$-Sat: Given a circuit $C$ from $\mathcal{C}$ is there an assignment such that $C(a_1,\dots,a_n)=1$?
  • $\mathcal{C}$-Sat is NP-complete and solvable in $O(2^n \lvert C\rvert)$
• Gap-$\mathcal{C}$-Sat, with promise $C\equiv 0$ or $\Pr[C(x)=1]\geq 1/2$. Decide which true.
  • Solvable in randomized polytime.
  • If Gap-Circuit-SAT in $P$ then $P=RP$.
  • Gap-kSAT is $P$ for all $k$.

Proved Connections:

• Deterministic for Circuit SAT in $O(2^n/n^{10})$ with $N$ inputs and $n^k$ gates then $NEXP\not\subseteq P/poly$.
• Formula SAT in $O(2^n/n^{10})$ then $NEXP\not\subseteq$ Poly size formulas
• $\mathcal{C}-SAT$ in $O(2^n/n^{10})$ then $NEXP\not\subseteq $poly size $\mathcal{C}$ (under reasonable assupmption)
• Gap-$\mathcal{C}$-SAT in $O(2^n/n^{10})$ time on $n^k$ size then $NEXP\not\subseteq $poly size $\mathcal{C}$.
• Notice that the model on the left side does not really matter.
• For ACC and ACC of Thr, the concrete lower bounds improved.
• If you improve the circuit SAT on the left, we get better lower bounds, i.e., Circuit SAT in $O(2^{n-n^\varepsilon})$ and $2^{n^\varepsilon}$ gates then NTIME[$n^P polylog n}]\not\subseteq P/poly$.

Even Finer Grained Sat gives us bound against NP

• Circuit SAT in $O(2^{(1-\varepsilon)n})$ on $n$ inputs and $2^{n\varepsilon}$ then NP does not have $n^k$ size circuits for all $k$.
  • This is not equal to $NP\neq P/poly$.
  • I.e., You pick a $k$ and it will not have a $n^k$ size circuit (but might have $n^{k^k})$ circuits.
• Some variants of this would refute Strong ETH
• Gap-$\mathcal{C}$-SAT in $O(2^{(1-\varepsilon)n})$ on $2^{\varepsilon n}$ gates is believed to be true.
• Proven for some circuit class SUM of THR, RUM of RELL, SUM of POL [W18].

Circuit Lower Bounds from Algorithm Design Part 2

• Quasi-NP does not have ACC $\circ$ Thr circuits of polynomial size.

• Theorem A: If for all $k$, Gap $\mathcal{C}$-SAT on $n^k$ size is in $O(2^n/n^k)$ time then NEXP does not have poly size $\mathcal{C}$ circuits.

  • Proof by contradiction, assume NEXP has poly-size $\mathcal{C}$ circuits and a faster GAP $\mathcal{C}$-SAT algorithm, then NTIME$[2^n]\subseteq$ NTIME[$o(2^n)]$.
  • Guess a witness of $O(2^n)$ length and check if it is a witness for $x$ in $O(2^n)$. Easy Witness Lemma
  • Speed up both of these steps.
  • If NEXP has small poly size circuits, then there are witnesses of length $o(2^n)$.
  • Use highly-structured PCPs to check a witness $y$ for $x$ in $o(2^n)$ time (reduces to GAP $\mathcal{C}$-SAT to check the PCP).

• Easy Witness Lemma:

• For all verifiers, if we have a witness than the verifier accepts on that witness and it can be compressed, i.e., there exists a circuit of $\lvert x\rvert + d$ inputs and the truth table is also a witness

• If NEXP is in P/poly than all NEXP problems have easy witnesses [IKW02].

• If NEXP is in P/poly, we can guess a circuit that is the compressed witness.

• Then use GAP $\mathcal{C}$-SAT algorithm to check if the circuit encodes a witness.

• Easy Witness Lemma only works for NEXP.

• New Easy Witness Lemma exists for NP and Quasi-NP [ME28].

IKW Easy Witness Lemma

• NTIME[$2^n$] $\subseteq $ SIZE[$n^k$] for some $k$ then NTIME[$$2^n$] has $n^c$ size witness circuits for some $c$.
• Proof:
  • Assume the negation: exists k NTIME[$2^n$]$\subseteq$ SIZE[n^k]]]$ and for all $c$ NTIME[$2^n$] does not have $n^c$ size witness circuits.
  • Start with $L$ that is solvable in SPACE[$n^{k+1}$] but not in SIZE[$n^k$] infinitely often.
  • Assumptions now apply SPACE[$n^{k+1}$] $\subseteq $ MA $\subseteq$ infinitely often NTIME[$2^n$]$/n$ ($n$ bit advice) $\subseteq$ infinitely often SIZE[$n^k$].

Scaling Witness Lemma down to NP

• New lower bound for MA lower bound.
• There is a language $L$ in MA-TIME[$n^{k^2}$]$/O(\log n)$ such that for all but finitely many input length $n$, either $L_n$ has circuit complexity at least $n^k$ or $L_{n^k}$ has circuit complexity at least $n^{k^2}$.