CSE 531: Complexity Theory

• Languages over a finite alphabet
• Turing machines
  • finite state space
  • alphabet
  • tape alphabet
  • transition function
  • start, accept, and reject states
• Universality, simulation, and the Church-Turing thesis
• Turing-decidable and Turing-recognizable languages
• The set of languages is uncountable, while the set of decidable languages is countable

• Turing machine descriptions; TMs taking other TMs as input
• Diagonalization and the halting problem
• $A_{\mathrm{TM}}$ is undecidable
• $E_{\mathrm{TM}}$ is undecidable (by reduction)
• Computable functions
• A function that grows faster than any computable function: Enumerate computable functions $f_1, f_2, f_3, \ldots$ and define \[ g(n) = n \cdot \max \{ f_j(k) : 1 \leq j,k \leq n \}\,. \]
• Mapping reductions: $A \leq_m B$ if there is a computable mapping $f : \Sigma^* \to \Sigma^*$ such that $x \in A \iff f(x) \in B$.
• If $A \leq_m B$, then $A$ undecidable $\implies B$ undecidable
• $A_{\mathrm{TM}} \leq_m ALL_{\mathrm{TM}}$

• Time complexity
• The time hierarchy theorem
• P = poly-time decidable languages
• NP = poly-time verifiable languages
• Poly-time reductions and NP-completeness

• NP = Non-deterministic poly time
• The Cook-Levin Theorem

• Oracle machines and relativizing arguments
• Baker-Gill-Solovay (there are oracles $A,B$ such that $P^A=NP^A$ and $P^B \neq NP^B$)
• Space complexity

• Savitch’s theorem
• PSPACE and two-player games
• TQBF is PSPACE complete

• Interactive proofs
• #P is in IP

NO CLASS

NO CLASS

The polynomial hierarchy

• Circuit complexity
• The Karp-Lipton theorem

Midterm out

Parity is not in $\mathsf{AC}_0$

Let $\mathbb{F}_3$ denote the finite field with $3$ elements (where arithmetic is modulo $3$).

Fact: Every function $f : \mathbb{F}_3^n \to \mathbb{F}_3$ is uniquely expressed as a polynomial where each variable has degree at most $2$.

Note that the $\mathbb{F}_3$-linear space of such functions has dimension $3^n$ and the number of monomials where every variable has degree at most $2$ is also $3^n$. Thus such monomials form a basis for the vector space of such functions.

Lemma (Low-degree approximation of AND): If $f_1, f_2, \ldots, f_t : \mathbb{F}_3^n \to \mathbb{F}_3$ each of degree at most $r$, then there is a $g : \mathbb{F}_3^n \to \mathbb{F}_3$ with degree at most $2 \ell r$ and such that $\mathbb{P}_{x \in \{0,1\}^n} [g(x) \neq f_1(x) \wedge f_2(x) \wedge \cdots \wedge f_t(x)] \leq 2^{-\ell}.$

Proof: Let $S_1, S_2, \ldots, S_{\ell} \subseteq \{1,2,\ldots,t\}$ be independent and uniformly random sets. We take

Note that $2^2 \equiv 1^2 \equiv 1 \ \mathrm{mod}\ 3$, so

Exercise: Prove that for any fixed $x \in \{0,1\}^n$, it holds that $\mathbb{P}[g(x) \neq f_1(x) \wedge f_2(x) \wedge \cdots f_t(x)] \leq 2^{-\ell}$, where the probability is over the random choice of sets $S_1, S_2, \ldots, S_{\ell}$.

Using the preceding lemma, we can approximate any depth $d$ circuit $C$ with $s$ gates by a polynomial $p$ of degree at most $(2\ell)^d$, and such that the $p$ agrees with the circuit on at least a $1-s 2^{-\ell}$ fraction of inputs. So if the circuit $C$ has $n$ gates we set $\ell = \Theta((\log n)^2)$, then we get a polynomial $p$ of degree at most $O((\log n)^{2d})$ that agrees with $C$ on (say) 99% of inputs.

To finish the argument, we need to show that PARITY cannot have such a low-degree approximation.

Lemma: Let $f : \mathbb{F}_3^n \to \mathbb{F}_3$ be a polynomial of degree $k$. Then $f$ can correctly compute PARITY on at most a $1/2 + O(k/\sqrt{n})$ fraction of the inputs in $\{-1,1\}^n$.

Proof: This argument proceeds as we discussed in class. Suppose that $f$ correctly computes the parity on a subset $A \subseteq \{-1,1\}^n$. Then for every $x \in A$ and $S \subseteq \{1,2,\ldots,n\}$, we can write

Thus using $f$ to replace high-degree monomials, for every function $q : A \to \mathbb{F}_3$, there is a polynomial $\tilde{q}$ such that $q = \tilde{q}|_A$ and $\deg(\tilde{q}) \leq n/2 + k$.

The dimension of the space of functions $q : A \to \mathbb{F}_3$ is $|A|$, so to finish we can compare this to the dimension of the space spanned by such monomials:

Razborov’s method of approximation, Part I

• Gowers notes
• Lecture 1 and Lecture 2 of Tim Gowers on Razborov’s argument

Razborov’s method of approximation, Part II

The Erdos-Rado sunflower conjecture

Overview of the PCP theorem and hardness of approximation

Course notes of Guruswami and O’Donnell we will follow

Expander graphs (Rory)

Notes:

• Lecture 2 from OV
• Lecture 3 from OV

Degree reduction and expanderization

Notes:

• Lecture 4 from OV

Gap amplification I

Notes:

• Lecture 5 from OV

Gap amplication II

Notes:

• Lecture 6 from OV

Alphabet reduction

Notes:

• Lecture 7 from OV
• Lecture 8 from OV
• Lecture 9 from OV