15-855: Intensive Intro to Computational Complexity

Wrapup

2009-05-03T13:51:00.003-04:00

Thanks again to all the hardy souls who hung in there for the semester!

Please remember to fill in the course evaluation at my.cmu.edu, under Academics.

Final grades are more or less tabulated; please email us if you want to learn them early.

best,
Ryan

Parameterized Complexity and ETH

2009-05-01T16:00:00.006-04:00

We look into Parameterized Complexity theory (introduced by Downey and Fellows via many papers) and its connections to classical complexity theory specifically via the Exponential Time Hypothesis (of Impaggliazzo and Paturi 2001) in this post. Parameterized complexity provides a framework for a more refined analysis of hard problems. Heuristics, parallel algorithms, approximation schemes, randomized algorithms are some of the approaches used to counter such problems. But these approaches suffer from many defects ranging from no hard bounds on the quality of the solution (heuristics), to not being applicable to really large instances (parallel algorithms) to impractical solutions (like some PTAS's etc.).

Introduction:

Classical complexity classifies problems using the concept of some resource (time or space). This leads to a good theory but it also ignores any structural information in the input which makes problems appear harder then they really are. There is a wide variation in the worst-case complexities of known exact algorithms for the NP-complete problems. For e.g., there are pretty good 3SAT solvers present right now which scale to a large number of variables.

Parameterized complexity tries to explain these differences by assuming that there is some part of the problem (the `parameter') will be small and allow us to develop efficient poly-time algorithms. The classic example for this is to consider a database query - it has two parts the database and the query of which query is usually much smaller than the database. The query size $k$ would be the natural paramter for a parameterized complexity analysis by admitting algorithms whose non-polynomial behavior is restricted by the parameter: if $k$ is small and $n$ is large, $O(2^k . n)$ is better than $O(n^k)$.

The main contribution of the theory is establishing the intractability of certain problems by classifying problems into complexity classes by reductions which are inherently 2-dimensional depending on the problem size as well the parameter. A problem can have different parameterizations also, each leading to different results.

Complexity Classes - FPT and the W[t] hierarchy:

A parameterized language $L$ is a subset of $\Sigma^* x \Sigma^*$ where $\Sigma$ is a finite alphabet. Let $(x, k) \in L$, then we call $x$ the main part and $k$ the parameter.

a) Tractability - Fixed-parameter tractable (FPT): $L \in FPT$ if it can be decided in time at most $f(k) . |x|^{O(1)}$ for an arbitary function $f$. For a fixed $k$ it is in P, moreover for every $k$ it is in the same polynomial class via the same machine. As an example, consider the $p-SAT$ problem where given the formula $\phi$ and the parameter $k = $ number of variables in $\phi$ decide whether $\phi$ is satisfiable. This is clearly in FPT as the obvious brute force approach for formula of size $n$ with $k$ variables will take time $O(2^k . n)$. There are many real world problems which are in FPT like parameterized Vertex Cover which uses the kernelization technique to get a $O(k . n + 1.286^k)$ algorithm (due to Chen, Kanj and Jia, 2001). Note that the classical Vertex Cover is NP complete - yet this result shows that it
is not as `hard' as say Independent Set.

b) Parametric Intractability: Analogously to classical complexity theory, Downey and Fellows developed a completeness program for intractable parameterized problems. In order to compare the hardness of parameterized problems, we need a 2-dimensional reduction (called `parameterized-reduction'). Roughly, a language $L$ is parameterically reducible to $L'$ if there is an FPT algorithm that transforms $(x, k)$ to $(x', k')$ so that $(x, k) \in L$ iff $(x', k') \in L'$ and $k' = g(k)$ where $g$ is an unrestricted function. Note that Karp reductions are rarely parameterized reductions (e.g. Clique to Independent Set is one of the exceptions).

1) W[1]: The lowest class of parameterized intractability can be defined as the set of languages that are reducible to the Short-Turing Machine Acceptance problem (also called the $k$-step halting problem) where we want to determine for an input consisting of a nondeterministic Turing machine M and a string x, whether M has a computation path accepting x in at most k steps. In some sense, this is the parameterized analogue to the Turing machine acceptance problem: the basic generic NP-complete problem in classical complexity theory. Canonical problems include Independent Set (does $G$ have an independent of size $k$), Weighted 3SAT (does $\phi$ have a satisfying assignment of weight $k$) etc. We will also give an alternative definition of W[1] afterwards which is actually used for the basic results.

2) The W[t] hierarchy: Interestingly, while general $k-$SAT and 3SAT are equivalent for NP-hardness in classical complexity, there is no known parameterized reduction computing general satisfiability from 3-CNF formulae. This leads to a realization that the logical depth of a formula affects its parameterized complexity. Intuitively it is related to the number of alternations between unbounded fan-in AND and OR gates. Hence, we can base the hierarchy on the complexity of circuits required to check a solution.

The W[t] is based on Circuit-SAT problem (parameterized by the weight of input like for Weighted 3SAT) for family of circuits $F_{h, t}$ having:
1. Small gates: with constant fan-in
2. Large gates: with unbounded fan-in

and of depth $h$ (max. number of gates in the path) and weft (max. number of large gates in the path) at most $t$. Clearly, we have the containments:

$FPT \subseteq W[1] \subseteq W[2] \ldots $

It is not known whether the containments are strict or not. Note that W[1] can now be defined as the class that can be reduced to an parameterized Circuit SAT on the family of constant depth weft 1 circuits. Downey and Fellows (1995) proved that parameterized Independent Set is W[1]-complete. The hardness proof is very intricate and we omit it here. Note that using this definition it is easy to see why Independent Set is in W[1] (sketch):
1. Each vertex in $G$ corresponds to one input gate in the circuit
2. For every edge $(v, u) \in G$ build a small OR gate: $(1-v) \wedge (1-u))$
3. Output from small gates are given as input to a single large AND gate.

Interestingly unlike NP-hardness results, W[1]-hardness for the $k-$Halting Problem uses Independent Set completeness as intermediate results. There have been many papers demonstrating naturally occuring W[t]-complete problems like Dominating Set for W[2] etc.)- for an extensive list of already classified problems see the Downey and Fellows monograph.

Exponential Time Hypothesis (ETH)

ETH was first studied by Impagliazzo, Paturi and Zane 2001 and it states that 3SAT $\notin$ DTIME$(2^{o(n)})$, where $n$ is the number of variables. They also proved that the hypothesis is robust to analogous hypotheses for other NP-complete problems like Independent Set etc. In fact, they also showed that the ETH is independent of size measure: 3SAT is solvable in time $2^{o(n)}$ iff it is solvable in time $2^{o(m)}$ for input size $m$. Note that this suggests that weighted 3SAT should also be intractable for `any parameter'.

Connections with Classical complexity:

The above paragraph suggests that ETH and parameterized complexity might be related. In fact they are and Chen and Grohe recently proved that ETH and paramterized complexity theory are isomorphic by an explicit reduction preserving isomorphism. We don't show that here, instead we prove a simpler result that yet provides a strong link to ETH (proof is a version from Downey, Castro et. al 2003 and uses parameterized miniaturization and is different from the original proof by Abhramson, Downey and Fellows):

Theorem: If FPT = W[1], then ETH fails i.e. 3SAT $\in$ DTIME$(2^{o(n)})$.

Proof: We use the equivalent definition of ETH based on simple Circuit SAT. The idea is to capture the ETH perfectly in a parameterized complexity class. The starting point is the Mini-Circuit SAT problem which is a parameterized miniaturization of simple Circuit SAT:
Input: Positive integers $k$ and $n$, and a Boolean circuit of total size at most $k\log n$.
Decision: Does there exist any $x$ for which $C(x) = 1$.

Note that the parameter here is $k$. Also, trying all possible inputs gives a brute force $O(n^k)$ algorithm. Next we give a cruicial lemma due to Cai and Juedes 2001. It essentially fully characterizes the ETH with a complexity class in parameterized theory.

Lemma 1: Mini-Circuit SAT is in FPT iff ETH fails.
Proof: One direction follows from the brute force algorithm and noting that $2^{o(k \log n)}$ is a FPT function.

Now suppose we are given a boolean circuit $C$ of size $N$ and that Mini-Cirsuit SAT is solvable in FPT time $f(k)n^c$. Set $k = f^{-1}(N)$ and $n = 2^{N/k}$. In general $k = f^{-1}(N)$ will be some slowly growing function of $N$; so $N/k = o(N)$ and also $cN/k = o(N)$. Hence using the FPT algorithm for Mini-Circuit SAT we have a running time for Circuit SAT as: $f(f^{-1}(N)) (2^{N/k})^c = N 2^{cN/k} = 2^{cN/k + \log N} = 2^{o(N)}$.
Thus ETH fails. Proved.

Now lets define the complexity class MINI[1] to be the set of languages that are FPT reducible to Mini-Circuit SAT. It turns out that many $k\log n$ miniatures of familiar NP-complete problems are MINI[1] complete (Downey, Fellows et al. 2002). It is easy to see this because essentially all the usual NP-complete reductions of Circuit SAT to these problems work as FPT reductions because they were also linear size reductions.

We concentrate on the Mini-Independent Set problem. Surprisingly, it can be reduced to the usual parameterized Independent Set problem.

Lemma 2: Independent Set parameterized by the size of independent set is MINI[1]-hard.
Proof: We give a Turing reduction. Let graph $G = (V, E)$ be the miniature, for which we wish to determine whether $G$ has an independent set of size $r$ with $|V| \leq k\log n$. We can think of verices of $G$ as organized in $k$ blocks $V_1, V_2, \ldots, V_k$ each of size $\log n$. So for each possible way of writing $r$ as a sum of $k$ terms $r = r_1 + r_2 + r_3 + \ldots + r_k$ with each $r_i \leq \log n$, we have a turing reduction branch which represnts a commitment to choose $r_i$ vertices from the corresponding block $V_i$ to be in the independent set. The total number of branches are $(\log n)^k$ and again it is a FPT-function.

For each branch, we produce a graph $G'$ that has an independent set of size $k$ iff the miniature $G$ has an independent set of size $r$ distributed as indicated by the commitment made on that branch. The graph $G'$ consists of $k$ cliques with some cross edges. The ith clique consists of vertices in correspondence with the subsets of $V_i$ of size $r_i$. An edge connects a vertex $x$ in the ith clique and a vertex $y$ in the jth clique iff there is a vertex $u$ in the subset $S_x \subseteq V_i$ represented by $x$ and a vertex $v$ in the subset $S_y \subseteq V_j$ represented by $y$, such that $(u, v) \in E$.

From Lemma 2 we can conclude that $FPT \subseteq MINI[1] \subseteq W[1]$. We just need to observe now that if FPT = W[1] it implies $M[1] \subseteq FPT$. By Lemma 1, ETH fails.
Proved.

Discussion:

The above result hints that FPT vs W[1] problem is like the P vs NP problem of classical complexity theory. In fact it was also proved by Downey and Fellows that FPT $\neq$ W[1] implies P $\neq$ NP. But it is not known that if FPT $\neq$ W[1] implies anything about the rest of W[t] hierarchy. Importantly, practical intracbility of problems in NP, which are unlikely to be complete for NP, can be shown using W[t] hardness results. Parameterized complexity has deep connections to other complexity results as well. Just recently (a week back) Galesi and Lauria showed a connection with Proof Complexity based on randomized algorithms for W[t]-hard problems. The field is very active and there are many papers and surveys being published in it.

Lower bounds for locally decodable codes

2009-05-01T08:54:00.017-04:00

In this blog, we will look at upper bounds on the rates of locally decodable codes and their relation to a problem called Private Information Retrieval. Some of the proofs presented here are unique in that they relate the complexity of classical algorithms to quantum algorithms and prove lower bounds on quantum algorithms!

Locally decodable codes are codes that can probabilistically recover a bits from corrupted codewords by querying a small number of bits, Hadamard code being a straightforward example. While an ideal code would have have rate, be resilient to large number of errors and would be locally decodable, it as been shown that it is not possible to do extremely well on all the criteria. Specifically, locally decodable codes imply that the code rate is $o(1)$.

The first paper in this direction ([Katz, Trevisan STOC'00]) showed that any locally decodable code with constant number of query bits has codewords of superlinear length. The main ideas behind these bounds is that smooth codes (codes which are queried uniformly for local decoding) are not much worse than non-smooth ones and that such smooth codes need super-linear encoding lengths.

Def 1: Suppose that a code maps $C:\{0,1\}^n\rightarrow \Sigma^m$. For fixed $\delta, \epsilon$ and integer $q$, $C$ is $(q,\delta,\epsilon)$-locally decodable code if there exists a probabilistic algorithm that recover an arbitrary bit $x_i$ of the input $x$ with probability at least $1/2+\epsilon$ from a corrupted codeword $y$ which is with in a distance $d(y,C(x))<\delta m$ of $C(x)$ after querying no more than $q$ indices of $y$.

Intuitively, smooth code words are those for which there exist probabilistic decoding
algorithms that query the codeword (roughly) uniformly, i.e., are not heavily biased
towards querying few indices of codeword. More formally:

Def 2: A codeword $C:\{0,1\}^n\rightarrow \Sigma^m$ is $(q,c,\epsilon)$-smooth
for fixed $c,\epsilon$ and integer $q$ if there exists a local decoding algorithm $A$
that can recover an aribitrary bit of input $x$ from codeword $C(x)$ with probability at least $1/2 + \epsilon$ using no more than $q$ indices of $y$ with the added condition that $\prob[A(x,i) \textrm{reads index} j] \leq c/m$. This definition does not require $A$ to recover bits from corrupted codewords.

Lemma 1: If $C$ is a $(q,\delta,\epsilon)$-locally decodable code, then it is also a $(q,q/\delta,\epsilon)$-smooth.
Proof sketch: Take the decoder for $C$ and identify all the locations that are queried with probability greater than $q/\delta m$ while trying to decode $m$. Construct a new decoder that just assumes the value $0$ for queries to all such locations. Since there no more than $\delta m$ of these, the new decodder can still recover from errors. This new decoder has the smoothness properties we want.

Lets start with case $q=1$, and see why it is not possible to construct locally decodable codes that encode inputs of length greater than a constant. Suppose that the algorithm is trying to decode the $i$-th bit $x_i$ by reading just a single index of the (corrupt) codeword $y$. Then, $\sum_{j\in[m]} Pr_x[A(C(x),i)=x_i | A(\cdot,i) ~\textrm{reads}~ j] Pr[A(\cdot,i) ~\textrm{reads}~ j]$
$ = Pr_x[A(C(x),i) = x_i] \geq 1/2 + \epsilon$,

beacuse of which there must exist a good index $j_1$ such that $Pr_x[A(C(x),i) = x_i | A(\cdot,i) ~\textrm{reads}~ j_1] \geq 1/2 + \epsilon$. Suppose that the code got randomly corrupt at index $j_1$. Then $y_{j_1}$ has no correlation with $x_i$ and the algorithm $A$ can not infer any information from index $j_1$. But since $A$ can recover from $\delta m$ errors, there must exist another index $j_2$ which also \textit{good} in the sense that it can be queried to get information about $x_i$. By extending the above reasoning, we can see that we can also corrupt $y_{j_2}$ randomly along with $y_{j_1}$ and can expect to find another index $j_3$ with reasonable correlation to $x_i$. We can extend the same argument $\delta m$ times to reason that there are at least $\delta m$ indices $j\in[m]$ such that $A$ can compute $x_i$ from $C(x)_{j}$ with probability at least $1/2 + \epsilon$. This is true of all inputs $x$, which by the pigeon hole principle implies that there is at least one index $j'\in [m]$ such that at least $\delta n$ of $x_i$s can extracted with $1/2 + \epsilon$ probability by querying $y_{j'}$. Now this means that the code should put an enormous amount of information about the input in to one index of the output. Consider the following quantitive
lemma about limit of information recovery from a function:

Lemma 2: If $C:\{0,1\}^n\rightarrow R$, and there exists a $A$ such that $Pr[A(C(x),i)=x_i] \geq 1/2 + \epsilon$,
then $\log{|R|} \geq (1-{\mathsf H}(1/2 + \epsilon))n$, where ${\mathsf H}$ is the binary entropy function.
Idea: if a decoder has an any hope of recovering bits with reasonable probability,
the compression should not e too high.

Setting $|R| = |\Sigma|$, we have $n\leq \frac{\log{|\Sigma|}}{\delta(1-{\mathsf H}(1/2 + \epsilon))}$ (Therorem 3).

Now, consider the case $q>1$. A generalization of this same argument can be used
to show superlinear bounds on the length of the codewords as follows:

Suppose that $A$ is a $(q,c,\epsilon)$-smooth decoder for code $C$.
Similar to the $q=1$ case, call a set $S$ ($S\subseteq[m], |S|\leq q$) $\epsilon$-good for $i$ if $Pr[A(C(x),i) = x_i | A\textrm{reads} s] \geq 1/2 + \epsilon$. Define hypergraph $H_i$ with vertices labelled $[m]$ and egde set $E_i$ defined by the $\epsilon/2$-good sets for $i$. A matching of a hypergraph is an edge set with no common vertex and a vertex cover is a vertex set such that every edge contains at least one vertex from the vertex set.

Lemma 4: $H_i$ has a matching $M_i$ of size at least $\epsilon m/cq$.
Proof:
$1/2 + \epsilon$
$\leq Pr_x[A(C(x),i) = x_i | A(\cdot,i) ~\textrm{reads}~ E_i] Pr [A(\cdot,i) ~\textrm{reads}~ E_i]$
$+ Pr_x[A(C(x),i) = x_i | A(\cdot,i) ~\textrm{reads}~ E^c_i] Pr {A(\cdot,i) ~\textrm{reads}~ E^c_i]$
$< Pr[A(\cdot,i) ~\textrm{reads}~ E_i] + (1/2 + \epsilon/2)(1-Pr[A(\cdot,i) \textrm{reads} E_i])$,
which implies that $Pr[A(\cdot,i) \textrm{reads from} E_i] > \epsilon$. If $P_e$ denotes the probability that $A(\cdot,i)$ reads $e\in E_i$, then we have $\epsilon < \sum_{e\in E_i} P_e$. Also for every $j\in [m]$, $\sum_{e\in E_i | j\in e} \leq c/m$
by smoothness condition. Now, if $V$ is vertex cover of $H_i$, $e\cap V \neq \emptyset$ for all $e\in E_i$. Putting this together with the earlier fact, we have $\epsilon < \sum_{s\in E_i | e\cap V\neq \emptyset} P_e \leq \sum_{j\in V}\sum_{e\in E_i | j\in e} P_e \leq |V|c/m$ which implies $|V| > \epsilon m/c$, and therefore, $H_i$ has a matching $M_i$ of size at least $\epsilon m/cq$.

Say that a set $S$ hits matching $M_i$ if there is some set $s\subseteq S$ such that $s\in M_i$. The following lemma gives a bound on the number of vertices to be selected from $H_i$ so that selected set hits a constant fraction of $M_i$s.

Lemma 5: If $H$ is a hypergraph on $m$ vertices containing hyperedges of at most than $q$ vertices. Suppose $H$ has a matching of size $\gamma m$($\gamma < 1/q$). There exists $t=\Theta(\gamma^{-1/q}m^{(q-1)/q})$ so that for a randomly chosen (from $H$) set of $t$ elements, such that the probability of this set hitting an arbitrary matching is $3/4$.

Theorem 6: If $C:\{0,1\}^n\rightarrow \Sigma^m $ is a $(q,c,\epsilon)$-locally decodable codes, then:
$m\geq (\epsilon\delta/q^2)^{1/(q-1)}{\left(\frac{3n(1-{\mathsf H}(1/2 + \epsilon))}{4\log{|\Sigma|}}\right)}^{(\frac{q}{q-1})$.
Proof: Lemma 1 shows that $C$ is $(q,q/\delta, \epsilon)$-smooth. Lemma 4 shows that for every $i$, there exists a set $M_i$ consisting of disjoint set of size at most $q$ such, each $m\in M_i$ is $\epsilon/2$-good for $i$ and $|M_i| \geq \epsilon\delta m/q^2$. Lemma 5 says that there exists a set of $t = \Theta((\epsilon\delta/q^2)^{-1/q}m^{(q-1)/q}))$ indices from $[n]$ so that the values at these locations have enough information to help decode at least $3/4$ of the inputs bits with advantage at least $\epsilon /2$. Applying Lemma 2 which gives us a lower bound on $t$ proves the theorem.

While this is some start, this still leaves a large gap between existing locally decodable codes (which are exponential long) and the lower bound. Goldreich, Karloff, Schulman and Trevisan improve the lower bound for the specific case of linear codes and decoding algorithms that query only 2 bits. They show that in such a case, $m = 2^{\Omega(n)}$. Using new techniques (reduction to quantum queries), Kerenidis and Wolf (arXiv: quant-ph/0208062v2) show that any 2-query LDC (not necessarily linear) is exponentially long. Their work is as follows.

Quantum queries
---------------

In an earlier post, Matt talked about the fact that QM systems exist in a linear superposition of several states. The choice of basis vectors used to describe can of course be chosen according to convenience (the choice is usually the eigenstates of the measurement). A superposition of states does not mean a statistical mix of different states, rather it means that the state of the particle itself is a complex vector. Such a state is called a pure state (can be expressed as $|\phi\rangle = \sum_{i} \alpha_i |i\rangle$). The density matrix of a pure state (or qubit) is the outer product $M = |\phi\rangle\langle\phi|$, where $\langle\phi| = {|\phi\rangle}^{\dagger} = {{|\phi\rangle}^T}^{*}$ is the complex conjugate transpose of $|\phi\rangle$. Note that an arbitrary matrix $M$ need not in general be the density matrix of a pure state. Matrices of the form $\rho = \sum_{i}p_i|\phi_i\rangle\langle\phi_i|$ are called mixed states. As against a pure system, such mixed states are statistical ensembles of different pure states. Obviously, such a mixed state does not represent any pure state. However, the set of pure states of which $\rho$ is an ensemble is not uniquely determined by $\rho$ alone. $\rho$ represents both $\{(p_i,|v_i\rangle\}_{i}$ and $\{(p'_i,|v'_i\rangle}\}_{i}$ as long there is a unitary matrix $U$ such that $|v_i\rangle=\sum_{j} \sqrt{p_j/p'_i}U_{ij}|v_j\rangle$. Another context where mixed systems are useful for us is to describe a subsystem of an entangled state. For example, in the entangled state $(|00\rangle + |11\rangle)/\sqrt{2}$, the second qubit alone is not a pure system. It can be viewed as the mixed state $(|0\rangle\langle 0| + |1\rangle\langle 1|)/2$.

Measurement of a qubit can be thought of as projecting the qubit in to a subspace. Based on the set of subspaces we are trying to project our qubit in to, the qubit has different probability of collapsing in to these subspaces. We can generalise this notion to arbitrary positive operators (not just orthonormal projectors) and mixed states -- such a measurement system is called positive operator valued measurement (POVM). A POVM is a set of positive operators $E_i = M_i^{\dagger} M_i$ such that $\sum_{i=1}^{k} E_i = I$. When such a measurement is made on state $\rho$, the outcome is any one of the states $M_i\rho M_i^{\dagger}/Tr(M_i\rho M_i^{\dagger})$, the probabilities of the respective outcomes being $p_i = Tr(M_i\rho M_i^{\dagger})$.

In what follows we usually deal with $k$ of the form $2^m$ and systems of $m$ qubits.
If $B=\{\ket{\psi_i}\}$ is an orthonormal basis for the system, measuring in $B$-basis means using the POVM: $E_i = \ket{\psi_i}\bra{\psi_i}$. Then, the outcome of measuring a pure state $\ket{\phi}$ is simply $|\braket{\phi}{\psi}|^2$ as we expect.

Now, we are ready to define a quantum query:
A query to $j$-th bit of a length $m$ string $y$ is the unitary operation (quantum mechanics mandates that all state transformations are unitary):
$|c\rangle|j\rangle \mapsto (-1)^{c\cdot y_j}|c\rangle |j\rangle$.
Of course, the fact that we can apply this query transformation to superposition states to (indirectly) read off several values of the function is what makes quantum queries powerful (for that matter, this ability to manipulate superposition states is what gives extra power to quantum algorithms). The following lemma illustrates this power right away:

Lemma 7: Let $f:\{0,1\}^2\mapsto \{0,1\}$ and suppose that we have $a=a_1 a_2 \in \{0,1\}^2$ whose bits are to be queried in order to compute $f(a)$. There exists a quantum algorithm that uses just one query, and outputs $f(a)$ with probability exactly $11/14$, and outputs $1-f(a)$ otherwise.
Proof: Note that a classical algorithm has to query both bits before it can compute $f(a)$ with any accuracy. The quantum algorithm is as follows: query $(|01\rangle
+ |11\rangle + |12\rangle)/\sqrt{3}$. The output of the query would be:
$|\phi_a\rangle = (|01\rangle + (-1)^{a_1}|11\rangle + (-1)^{-a_2}|12\rangle)/\sqrt{3}$, the mutual phase shifts now holding information about $a_1, a_2$. To extract this information, we measure this state (i.e., cause it to collapse to basis) with the basis $\{|\psi_b\rangle\} (b\in \{0,1\}^2)$, where $|\psi_b\rangle = (|01\rangle + (-1)^{b_1}|01\rangle + (-1)^{b_2}|10\rangle + (-1)^{b_1+b_2}|11\rangle)/2$.

$|\phi_a\rangle$ gives outcome $a$ with probability $|\langle\phi_a|\psi_a\rangle|^2 = 3/4$, the other three outcomes being equally probable ($1/12$). Suppose that the measurement outcome is $m$. The following procedure does exactly what we want:

$f$ is a constant. Output the constant with probability $11/14$.

$|f(1)^{-1}|=1$. If $f(m) = 1$, then output $1$. If $f(m)=0$, then output $0$ with probability $6/7$ and $1$ with probability $1/7$. Now, if $f(a) = 1$, then probability of the algorithm outputting $1$ is $(3/4).1 + (1/4)(1/7) = 11/14$. If $f(a) = 0$, then probability of algorithm outputting $0$ is $(11/12)(6/7) = 11/14$.

$|f(1)^{-1}|=2$. Output $f(m)$ with probability $13/14$ and $1-f(m)$ with probability $1/14$.

$|f(1)^{-1}|=3$. Similar to case $|f(1)^{-1}|=1$.

Definition: A $(q,\delta, \epsilon)$-LQDC (locally quantum-decoable code) is the same as a LDC except that we replace the probabilistic decoder with a quantum decoder and queries are quantum-queries that probe superpositions. Now we can use the earlier lemma to show that:

Theorem 8: A $(2,\delta,\epsilon)$-LDC is a $(1,\delta,4\epsilon/7)$-LQDC.
Proof: The idea is to replace the two classical queries with one quantum query (allowing for a bit of inaccuracy) based algorithm. The quantum decoder will choose two target bits the same way the classical decoder works, and instead of reading both bits and applying a function $f$, the LQDC does a quantum query on this two bits and outputs the value of $f$ on this bits (with $11/14$ accuracy). This suffices to get a $4\epsilon/7$ predictor.

Now we want to show lower bounds on 1-query LQDCs. The starting point as in the
case of 1-query LDCs is a theorem that gives a relation between the space
used to store information and fidelity of information reconstruction:

Theeorem 9: If $f$ maps $n$ bit strings to $m$-qubit states (mixed) states with
recovery probability at least $p$, then $m\geq (1 - {\mathsf H}(p))n$. This leads to:

Theeorem 10: If $C:\{0,1\}^n \rightarrow \{0,1\}^m$ is a $(1,\delta,\epsilon)$-LQDC, then $m\geq 2^{cn} - 1$, for $c=1-H(1/2 + \delta\epsilon/4)$.

Wehner and Wolf (arXiv: quant-ph/0403140v2) consider the case where the LDC encode
over larger alphabets and when the decoder uses only a part of the information from each query. Briet and Wolf (arXiv: quant-ph/0806.2101v1) further study the relation between LQDC and LDC and conclude that their powers are roughly the same for small constant number of queries.

Despite all this work, the best lower bounds on the overheads for >3 query LDC is only polynomial while known >3-query LDCs are eponentially long. This gap leaves a big open question.

LDCs and Private Information Retrieval (PIR)
--------------------------------------
The relation between LDCs and PIRs is close and worth mentioning since PIR systems yield some of the best LDCs. PIR is the problem of distribution a database among different servers so that a client can query a particular bit (by sending randomized queries to different servers) so that individual servers have almost no clue about the particular query bit that the client is accessing (information theoretic security, not computational). Here is the definition of a 2-server PIR system.

Def [GKST CCC'02]: A one-round, database size $n$, $(1-\delta)$ secure, 2-server PIR with recovery probability $p$, query size $q$, answer size $a$ is the set of algorithms $(Q,(S_1,S_2),D)$, where:
- $Q$ on input $i$ uses a randomness ($r$) to generate two $q$ bit long queries $(q_1,q_2)=Q(i,r)$. $q_1$ and $q_2$ are sent off to the two servers which use algorithms $S_1$ and $S_2$ to respond with length $a$-answers to these queries. The decoder algorithm $D$ uses $i,r$ and the answers of the servers to decode $x_i$. Given that the random string for input to $Q$ is selected from uniform distribution, the decoder $D$ should succeed with probability at least $p$. The secrecy condition is that the distribution of queries send to servers should be different for different target bits by more than a distance of $\delta$.

The same authors show that if there is a $1$-round, $(1-\delta)$-secure $2$-server PIR of database size $n$, query size $t$, answer size $a$ with recovery probability at least $1/2 + \epsilon$, then there exists a $(2,3,\epsilon-\delta)$-smooth code $C:\{0,1\}^n\rightarrow (\{0,1\}^a)^m$, where $m \leq 6.2^t$. This reduction can be used to show that a query sizes $\Theta(n^c) (c>0)$ are needed for PIR with constant answer sizes.

Kolmogorov Complexity and derandomization

2009-05-01T02:53:00.008-04:00

Motivation
------------

The sets $R_{\mu}$ of random strings with high Kolmogorov complexity and bounded resources are good examples of sets with a lot of information content that is difficult to access. Many of these sets have been studied [BM97,Ko91,KC00] as possible examples of intractable sets that are not complete for any of the standard complexity classes. Based on [Al05], we now show that these sets can, in fact, be exploited by efficient reductions.

The completeness results are obtained via derandomization techniques, mostly relativizing hardness vs randomness tradeoffs in the contrapositive: If there exists a problem in complexity class $C$ that is hard when given oracle access to $A$, then there exists a pseudorandom generator secure against $A$ that is computable within $C$. We argue that no pseudorandom generator computable in $C$ can be secure against $R_{\mu}$, and thus every problem in $C$ is easy given oracle access to $R_{\mu}$. In other words, $C$ reduces to $R_{\mu}$.

Definitions
-----------

The computational model that we use is the multi-tape Turing machine with random-access to its input tape (the ideas work in any general model). Wlg, we pick a single universal machine $U$.
Kolmogorov complexity $C^A(x)$ is usually defined as the length of the shortest description $d\in \{0,1\}^*$ such that $U^A(d) = x$, where $U$ is a universal Turing machine with oracle access to $A$. The definition we use is slightly different: instead of requiring $U^A(d)$ to produce $x$, it should recognize the correct value of $x_i$ for every $i$.
We now define several resource-bounded Kolmogorov complexity measures:

Definition 1 [Kt,KT,KS]
$Kt^A(x) = \min\{ |d| + \log t : U^A(d,i,b)$ accepts in $t$ steps iff $x_i=b \}$
$KT^A(x) = \min\{ |d| + t : U^A(d,i,b)$ accepts in $t$ steps iff $x_i=b \}$

The only difference is that in $KT$ the time bound is given exponentially more weight. Considering space-bounded notions, too, will yield complete problems for space-bounded
classes:

$KS^A(x) = \min\{ |d| + s : U^A(d,i,b)$ accepts in $s$ space iff $x_i=b \}$

Both $Kt$ and $KS$ can be approximated in terms of $KT^A$, for appropriate oracle choices:

Theorem 2:
There exist a complete set $A$ for $E$, a complete set $B$ for $DSPACE(n)$, and a constant $c$ s.t.
$Kt(x)/c\leq KT^A(x)$
$KS(x)/c\leq KT^B(x)$

Proof sketch: Let $A \in E$ and let $x$ be given, s.t. $KT^A(x) = m$. Thus, there is a description $d_x$ of length $\leq m$, s.t. $U^A(d_x,i,b)$ accepts iff $x_i=b$ in time at most $m$. During computation, $U$ asks queries of length at most $m$. Since $A \in E$, each query can be answered in time $2^{O(m)}$.
Let $M$ denote the algorithm simulating the computation of $U^A(d_x,i,b)$ for every $i$ by directly computing the answers of $A$, then the description $d'_x= \langle M,d_x \rangle$ is sufficient for $U$ to compute $U(d'_x,i,b)$ in time $2^{O(m)}$. As $|d'_x|=m+O(1)$, we can conclude that $Kt(x) \leq m + O(1) + \log(2^{O(m)}) = O(m)$.
The proof for $KS$ is similar.

We focus on sets containing strings of high complexity, for various measures.

Definition 3:
For any Kolmogorov complexity measure $\mu$, define
$R_{\mu} = \{x : \mu(x) \geq |x|/2\}$.

The bound of $|x|/2$ is arbitrary. Essentially, all we need is that the set $R_{\mu}$ has polynomial density (it contains at least $2^n/n^k$ strings of each length $n$, for some $k$).
The following propositions are straightforward.

Proposition 4:
$R_{Kt} \in E$, $R_{KS} \in DSPACE(n)$, and $R_{KT} \in coNP$.

Proposition 5:
The sets $R_{Kt}$, $R_{KS}$ all have polynomial density.

Nonuniform Hardness Results
-------------------------------

We show that strings of high Kolmogorov complexity are very useful as oracles. We will argue that an appropriate set $R_{\mu}$ of Kolmogorov random strings can be used to distinguish the output of a pseudorandom generator $G_f$ from truly random strings. This in turn will enable us to efficiently reduce $f$ to $R_{\mu}$.

Recall that $A$ is PSPACE-robust if $PSPACE^A = P^A$ (machines are allowed to ask oracle
queries of only polynomial size). The complete sets for many large complexity classes (PSPACE, EXP, EXPSPACE) have this property, as well as the complete sets (under linear-time
reductions) for classes like $DSPACE(n)$ and $E$.

We will build a pseudorandom generator based on the Nisan-Wigderson paradigm [NW94]. [BFNW93] construct, for any $\epsilon > 0$, a variant $G^{BFNW}_f : \{0,1\}^{n^\epsilon}\rightarrow \{0,1\}^n$ such that for any $x$ of size $n^\epsilon$, the function is computable in space $O(n^\epsilon)$ given access to the Boolean function $f$ on inputs of size at most $n^\epsilon$. If $f$ is PSPACE-robust, there is a constant $c$ independent of $\epsilon$, such that each bit is computable in time $n^{\epsilon \cdot c}$ with oracle access to $f$. The following hardness versus randomness tradeoff holds.

Theorem 6 [BFNW93]
Let $f$ be a Boolean function, $\epsilon > 0$, and $G^{BFNW}_f$ be the pseudorandom generator described above. Let $T$ be a set and $p(n)$ a polynomial. If
$|P_{r\in U_n}[r \in T]-P_{x\in U_{n^\epsilon}}[G^{BFNW}_f(x)\in T]|\geq 1/p(n)$
for all large $n$, then there exists a polynomial size oracle circuit family $\{ C_n \}$ with oracle $T$ that computes $f$ and queries $T$ non-adaptively.

We use the notation $A\leq ^{P/poly}_{tt} B$ to denote that there exists a truth-table (i.e., nonadaptive) reduction from $A$ to $B$ that is computable by a family of polynomial-size circuits.
(A truth-table reduction is a reduction from one set of natural numbers to another. Truth-table reductions are more powerful than Turing reductions in a mathematical sense, since they provide finer equivalent class, but they are a weaker tool.)

Theorem 7:
Let $A$ be any PSPACE-robust set. Let $L$ be a set of polynomial density s.t. for every $x \in L$, $KT^A(x) > |x|^\gamma$ for some constant $\gamma > 0$. Then $A$ is reducible to $L$ via $\leq^{P/poly}_{tt}$ reductions.

Proof Sketch: Let $f$ be the characteristic function of $A$. Consider $G^{BFNW}_f$,
choose $\epsilon$ as follows. We know that every bit of $G^{BFNW}_f$ is computable in time $n^{\epsilon \cdot c}$ for some constant $c$ independent of $\epsilon$, given access to $A$. Set $\epsilon= \gamma/2c$ (wlg $c > 1$).

Any string in the range of $G^{BFNW}_f$ has small $KT^A$ complexity: Let $y = G^{BFNW}_f (x)$, for some $x$. On $x$, every bit of $G^{BFNW}_f$ is computable in time $n^{\gamma/2}$ with access to oracle $A$. Hence, $KT^A(y) \leq |x|+O(n^{\gamma/2} \log n)+O(1) \leq n^{\gamma}$. Thus, $L$ distinguishes the output of $G^{BFNW}_f$ from random, and by Theorem 6, $f$ is $\leq^{P/poly}_{tt}$ reducible to $L$.

By Theorem 2 and Proposition 5, we can apply Theorem 7 to
$\langle $the set $A$ from Theorem 2, $R_{Kt}\rangle $, and $\langle $the set $B$ from Theorem 2, $R_{KS}\rangle $.
($A$ and $B$ are clearly PSPACE-robust, since they are complete for EXP and PSPACE, respectively.) Combining this with Proposition 4, we get:

Corollary 8:
$R_{Kt}$ is complete for EXP under $\leq ^{P/poly}_{tt}$ reductions. $R_{KS}$ is complete for PSPACE under $\leq ^{P/poly}_{tt}$ reductions.

Those results also obtain natural examples that witness the difference in power of various reducibilities, as some of the sets which we show are complete under truth-table reductions are provably not complete under polynomial-time many-one reductions.

Lecture 28

2009-04-30T17:45:00.001-04:00

Today we talked about barriers to proving $P \neq NP$ and other complexity-theory results: specifically, the "relativization" barrier introduced by Baker-Gill-Solovay, and the "natural proofs" barrier introduced by Razborov-Rudich.

We also talked about results that evade them. For example, the Hopcroft-Paul-Valiant Theorem, $TIME[f(n)] \neq SPACE[f(n)]$, and the Paul-Pippenger-Szemeredi-Trotter Theorem, $DTIME[n] \neq NTIME[n]$, do not relativize. Nor do they algebrize, according to the Aaronson-Wigderson notion. (At least, my opinion is that the notion of relativizing/algebrizing makes sense for these theorems, and in this sense they do not relativ/algebrize.)

As for natural proofs, we discussed how proofs by diagonalization do not seem to naturalize, and we mentioned explicit circuit lower bound which are by diagonalization; for example, Kannan's result that $\Sigma_4$ not in $SIZE(n^{1000})$.

Finally, we mentioned some theorems that neither relativize nor (seem to) naturalize: for example, Vinodchandran's Theorem that $PP$ not in $SIZE(n^{1000})$, and Santhanam's improvement of this to an explicit promise problem in $MA$ which isn't in $SIZE(n^{1000})$.

Game theory complexity and computing Nash Equilibrium

2009-04-30T01:09:00.021-04:00

In 1944 von Neumann and Morgenstern introduced the subject of Game Theory in their book Theory of Games and Economic Behavior. von Neumann and Morgenstern showed that there always exists a equilibrium solution to any two-person zero-sum game. (They also showed any n-person non-zero-sum game can be trivially turned into a (n+1)-person zero-sum game by adding a player who represents the net global profit or loss.) Nash extended this work to show that there exists a equilibrium for any (zero or non-zero-sum) n-person game. (A Nash Equilibrium is a set of mixed strategies for the players such that each individual player has perfect knowledge of the other players' strategies and has no benefit from changing their strategy unilaterally under this knowledge.)

However, Nash's proof is not constructive in a computational sense, in that it does not imply a general algorithm for determining the equilibrium point for an arbitrary game. There is good reason for this. We can show that there is no general algorithm for determining the equilibrium of a given game on the reals.

We must first give a definition of what we mean by a computable real. In this analysis, I will use the definition given in Computability in Analysis and Physics by Pour-El and Richards. We say a real number x is computable if there exists a computable sequence of rationals that converge effectively to x. (Converges effectively means that for some sequence of rationals ${r}_k$ there is a computable function $e$:$\mathbb{N}\to\mathbb{N}$ such that for all $N$, $k \geq e(N)$ implies $|{r}_k-x|\leq {2}^{-N}$ ) A computable sequence of reals is defined similarly (There is a computable double sequence of rationals $\{{r}_nk\}$ that converges effectively to ${x}_n$ as $n,k\rightarrow \inf$ ) Finally, a computable function is defined by saying that every computable sequence of inputs ${x}_n$ yields a computable sequence of outputs $f({x}_n)$, and that the function is effectively uniformly continuous. (Generally, given a computable function $d(n)$, for all $x,y\in \mathbb{R}$, $|x-y|\leq d(n)\implies |f(x)-f(y)|\leq {2}^{-n}$.)

Now that we have a framework to examine computability in the reals, we can move to the question of the computability of Nash equilibrium. Obviously, if the payoffs are given as uncomputable functions, determining an equilibrium is also uncomputable. However, if every payoff is computable, there does exist a computable equilibrium. The proof relies on the fact that we can generate a function that is maximized at the equilibrium of the game ($h(s)$), and we can computably determine the maximal value of a computable function. From this we can get finer and finer approximations of the maximal input to the function (since $h$ is effectively uniformly continuous), thus generating a sequence that converges to a maximal input.

But, we can also show that not every sequence of computable games is computable. This implies that there is no general procedure to compute Nash equilibrium (The proof of this relies on constructing a sequence of computable games that are not computable by using payoffs generated from two recursively inseparable sets and then showing a computable equilibrium sequence would separate them.)

We can do one better by showing that for a limited set of games, given a computable sequence of strategies for one player, the sequence of best response strategies for the other player is not computable. (Motivation for this is the idea that actually playing a game involves observing the opponent's strategy over time and computing a best response.) The proof involves showing the result for a specific, simple game.

Allowing players to make some amount of error in their responses does lead to computable strategies, however. Consider the logistic quantal response function: ${\sigma}_{ij}(\pi)=(exp(\lambda u_{ij}(\pi))/(\sum_{k\in A_{i}} exp(\lambda u_{ik}(\pi)))$, where $u_{ij}(\pi)$ is the payoff to $i$ from using pure strategy $j$ given a strategy profile (list of all player's strategies) $\pi$, and $A_{i}$ is the set of actions available to $i$. If we allow players to choose strategies with probabilities given by the logistic quantal response function for a given $\lambda$, instead of choosing a best response with certainty, then we can generate a computable "equilibrium". Note however, that no matter how tight we make this function, we have no guarantees that the resulting strategies are anywhere near a true equilibrium.

Looking at the problem of Nash equilibrium from another viewpoint entirely, we can examine the complexity of $\epsilon$-equilibrium. An $\epsilon$-Nash equilibrium is one in which each player has knowledge of other player's strategies and has at most an $epsilon$ benefit from changing their strategies under this knowledge. By taking $\epsilon=1/{2}^k$ for $k$ related to the length of the description of the given game, we can show that $r$-player $\epsilon$-Nash equilibrium is complete for the class PPAD.

PPAD is defined as (taken from Wikipedia):

G is a (possibly exponentially large) directed graph with no isolated vertices, and with every vertex having at most one predecessor and one successor. G is specified by giving a polynomial-time computable function f(v) that returns the predecessor and successor (if they exist) of the vertex v. Given a vertex s in G with no predecessor, find a vertex t≠s with no predecessor or no successor. In other words, we want any source or sink of the directed graph other than s.

PPAD is a subclass of TFNP, which is the set of FNP problems that are total. (A binary relation P(x,y) is in TFNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(x,y) holds given both x and y, and for every x, there exists a y such that P(x,y) holds. (again, taken from Wikipedia))

The proof that $r$-player $\epsilon$-Nash equilibrium is PPAD-complete was show in a sequence of papers that first showed that 4-or-more player games can be reduced to 4-player graphical games (graphical games are ones in which the players can be viewed as vertices on a graph, and each player's payoffs are only related to the actions of that player's direct graphical neighbors), and then showing that 4-player games are PPAD-complete by reducing another PPAD-complete problem to it, and then separate proofs were given for 3 and 2-player games.

This work places Nash equilibrium into a concrete place in the complexity hierarchy as well as expanding the interest and scope of the class PPAD.

References:

Prasad, Kislaya. "The rationality/computability trade-off in finite games." Journal of Economic Behavior & Organization 69(2009): 17-26. Print. Link

Chen, Xi; Deng, Xiaotie "Settling the complexity of 2-player Nash equilibrium" Electronic Colloquium on Computational Complexity, Revision 1 of Report No. 140 Link

Daskalakis, Constantinos; Goldberg, Paul W.; Papadimitriou, Christos H. "The complexity of computing Nash equilibrium" Link

-Kevin Mc Inerney

Last lecture

2009-04-29T12:05:00.001-04:00

Hi -- don't forget to not each lunch tomorrow; we'll bring it for the last lecture, wherein we'll also cover Natural Proofs.

Course evaluations

2009-04-28T15:46:00.001-04:00

Please also do the online course evaluation: go to https://my.cmu.edu/site/main/page.academics, log in with your Andrew ID, and click on "University Course Assessment". Thanks!

(And if you didn't get a copy of the paper one for the CS department, please ask Deb for one. Thanks!)

Lecture 27

2009-04-28T15:41:00.003-04:00

In this lecture we covered Reingold's Theorem, SL = L; i.e., undirected connectivity can be solved in log space. Here are my abridged notes on actually doing Reingold's algorithm in log-space. It's not a full proof, just a "proof by example" -- but I hope it's nevertheless clearer than a hand-wave.

For the Martin-Randall Theorem, you can consult the original Martin-Randall paper. There is a clearer proof -- but of a much more general theorem -- in a paper by Jerrum, Son, Tetali, and Vigoda. It's still not the clearest thing. If I get time I will try to write up a stripped-down, simplified version of the proof. You can also consult the Arora-Barak book for a proof of a weaker but still sufficient result: $\epsilon(G r H) \geq \Omega(\epsilon(G) \epsilon(H)^2)$. Note that it is okay to have the square on $\epsilon(H)$ here since it's an absolute constant anyway -- but it would not help if the square were on $\epsilon(G)$.

Lecture 26

2009-04-23T14:49:00.003-04:00

Today we covered...

Proof Complexity and the NP vs. coNP problem. The "Resolution" proof system with the resolution rule ($C \vee x$, $C \vee \overline{x}$ $\vdash$ $C \vee C'$) and the weakening rule ($C \vdash C \vee x$). Completeness of Resolution with proof sketch. Various contradictions (tautologies, in fact): Pigeonhole Principle, Tseitin Tautologies, Random 3-CNF. Treelike Resolution. Resolution width. Short Proofs Are Narrow Theorem, proved for Treelike Resolution. Ben-Sasson & Wigderson Theorem: Unsatisfiable $k$-CNFs with "expansion" require wide Resolution proofs.

By the way, the question came up as to separating Treelike Resolution from General Resolution. A very strong result was proved for this problem by Ben-Sasson, Impagliazzo, and Wigderson: There is a natural family of contradictions with $n$ variables and $O(n)$ clauses, which have Resolution refutations of length $O(n)$ but requires Treelike Resolution refutations of length $2^{\Omega(n / \log n)}$.

The contradictions here are based on "pebbling" expander graphs; more specifically, the results in an old paper of Paul, Tarjan, and Celoni.

Blogging

2009-04-21T14:59:00.002-04:00

Hi all. If you have not yet written a blog post -- you're one! Your deadline is the last day of class. Please email us to confirm a topic.

Lecture 25

2009-04-21T14:12:00.003-04:00

Today Eric gave an introduction to Property Testing. Among other things, we covered the BLR Linearity Test with the Bellare-Coppersmith-Håstad-Kiwi-Sudan proof using Fourier analysis.

Homework 5 Correction

2009-04-19T22:41:00.002-04:00

In Problem #4b, the everywhere you see $B_\delta(f)$ this should be $B_\delta(C)$.

Thanks to Or for pointing this out.

Updated: Another small bug-fix to Problem #4b, in the definition of $S'$. Corrected version is on the course web page.

Easy Witnesses

2009-04-15T05:45:00.008-04:00

While doing the proof of IKW theorem in class, we came across the easy witness method introduced by Kabanets. The original usage of this method in Kabanets'00 paper was to show that any randomized algorithm in $\mathrm{RP}$ can be simulated by a zero-error probabilistic algorithm in expected $2^{n^\varepsilon}$-time for some $\varepsilon>0$, such that no expected sub-exponential time algorithm can refute the simulation infinitely often (io). In other words, there is no algorithm of the form $R(1^n)\in \{0,1\}^n$ in this time class such that simulation makes a mistake on input $R(1^n)$ for almost all $n$.

Before going to prove this result, we look at something simpler first, which also introduces the easy witness method:

Theorem 1: At least one of the following holds:

For every $\varepsilon>0$, any language in $\mathrm{RP}$ can be simulated in $\mathrm{DTIME}(2^{n^\varepsilon})$ such that no language in $\mathrm{ZPP}$ can refute the simulation io.
$\mathrm{BPP}=\mathrm{ZPP}$.

Proof: Consider the set $S$ of easy witness strings. A string $\alpha \in S$ is an easy witness iff it has a concise description (ie. it is the truth table of some circuit with low complexity). For an algorithm $A$ and input $x$ in $\mathrm{RP}$ we can test $A$ against all such strings and accept iff there is one that makes $A$ accept. The crucial insight is that if this algorithm makes frequent mistakes, then the set of random strings that makes $A$ accept have high circuit complexity. Thus if fix the input $x$, $A$ is a good hardness test for strings $r$, accepting only if $r$ has no small description. Notice that a significant fraction of strings have this property. Therefore using this as a source for Impagliazzo - Wigderson generator, we can derandomize BPP.

More formally, for given randomized algorithm $A(x,r)$ on input $x,|x|=n$ and random bits $r,|r|=m=n^a$ for some constant $a$, let $S^{\delta}_m$ be the set of truth tables of all $\lceil \log m\rceil$-variable Boolean functions with low circuit complexity (at most $m^\delta$). Hence $S^{\delta}_m$ contains strings of length $m$, and it can be enumerated in $\mathrm{DTIME}(2^{n^{2\delta}})$. Therefore checking for all $\alpha \in {S^{\delta}_m}$ if $R(x,\alpha)$ accepts takes time at most $(2^{n^\varepsilon})$ for $\delta = \varepsilon/(2a)$. Let this algorithm be $B^{\varepsilon}_{A}(x)$.

If this algorithm $B^{\varepsilon}_{A}$ works for every $A \in \mathrm{RP}$ and $\varepsilon>0$, then (1) holds and we are done. Otherwise, there exists $A$,$\varepsilon>0$ and an expected polynomial time refuter $R(1^n)\in\{0,1\}^n$ such that, for almost all $n$, $B^{\varepsilon}_{A}(R(1^{n}))$ does not accept whereas $A(R(1^{n}),r)$ accepts for some $r$. Therefore $A(R(1^{n}),r)$ can be viewed as a Boolean circuit $C^{\mathrm{hard}}(r)$ which accepts almost all $m$-bit strings and all accepted strings are truth tables of a $\log m$-variable Boolean function with the smallest circuit size at least $m^{\varepsilon/(2a)}$. Since $R(1^{n})$ halts in polynomial time with high probability, we have an algorithm in $\mathrm{ZPP}$ which can construct such circuits $C^{\mathrm{hard}}$.

Given such a circuit $C^{\mathrm{hard}}$, we can guess a string uniformly at random $\beta\in\{0,1\}^m$ which $C^{\mathrm{hard}}$ accepts. Reminding ourselves of IW result:

Impagliazzo-Wigderson Generator: Given $r\in\{0,1\}^{n^c}$, truth table of a circuit on $c \log n$-Boolean variables with circuit complexity at least $n^{\varepsilon c}$, there exists $c,d\in\mathbb{N}$ and a polynomial time computable generator $G_r(s):\{0,1\}^{d \log n} \rightarrow \{0,1\}^n$ with hardness $H(G_r)> n$.

If we use this $\beta$ to construct the generator $G_{\beta}$ of IW mapping $\{0,1\}^{d \log k}$ to $\{0,1\}^k$, we get a generator $G_{\beta}$ with hardness greater than $k$ for sufficiently large $k$. Constructing these takes expected polynomial time, and last step takes deterministic polynomial time, therefore for every $L \in \mathrm{BPP}$, we have $L \in \mathrm{ZPP}$. QED

Instead of IW generator, we can use Babai-Fortnow-Nisan-Wigderson generator, to arrive at the following result.

Theorem 2: At least one of the following holds:

Any language in $\mathrm{RP}$ can be simulated in $\mathrm{DTIME}(2^{(\log n)^{\log\log n}})$ such that no language in $\mathrm{ZPP}$ can refute the simulation io.
$\mathrm{BPP}\subseteq \mathrm{ZPSUBEXP}$ where $\mathrm{ZPSUBEXP}$ denotes the class of languages with an expected sub exponential time algorithm.

Instead of fiddling with the generator, we can increase the power of refuter. In Theorem 1, when first condition fails, we can allow the refuter to take expected sub exponential time. After changing the circuit size and parameters appropriately, we have the following result:

Theorem 3: At least one of the following holds:

For every $\varepsilon>0$, any language in $\mathrm{RP}$ can be simulated in $\mathrm{DTIME}(2^{n^{\varepsilon}})$ such that no language in $\mathrm{ZPSUBEXP}$ can refute the simulation io.
$\mathrm{BPP}\subseteq \mathrm{ZPSUBEXP}$.

Noting that $\mathrm{DTIME}(2^{n^{\varepsilon}})$ and $\mathrm{ZPSUBEXP}$ are in $\mathrm{ZPTIME}(2^{n^{\varepsilon}})$, and $\mathrm{RP}\subseteq \mathrm{BPP}$, we can replace the above with an unconditional result:

Corollary 1: For every $\varepsilon>0$, any language in $\mathrm{RP}$ can be simulated in $\mathrm{ZPTIME}(2^{n^{\varepsilon}})$ such that no language in $\mathrm{ZPSUBEXP}$ can refute the simulation io.

Notice that above results imply that we can get analogous results to the ones obtained in IW paper:

In IW, assuming $\mathrm{BPP}\neq \mathrm{EXP}$, deterministic subexponential time bound was shown for $\mathrm{BPP}$. Using the machinery developed above, we can answer a weaker question: What happens when $\mathrm{ZPP}\neq \mathrm{EXP}$?

Theorem 4: If $\mathrm{ZPP}\neq \mathrm{EXP}$, then any language in $\mathrm{RP}$ can be simulated in $\mathrm{DTIME}(2^{n^{\varepsilon}})$ for all $\varepsilon>0$ such that no language in $\mathrm{ZPP}$ can refute the simulation io.

Proof: Assume otherwise. Then by Theorem 1, $\mathrm{BPP}=\mathrm{ZPP}$. But for some $\varepsilon>0$, $\mathrm{BPP}$ is a proper subset of $\mathrm{DTIME}(2^{n^\varepsilon})$ for $\mathrm{BPP}$ refuters (by Time Hierarchy Theorem). Using IW theorem, this implies
$\mathrm{BPP} = \mathrm{EXP} = \mathrm{ZPP}$. QED

The gap theorem of IW (either no derandomization of BPP is possible, or BPP can be simulated in deterministic $2^{n^\varepsilon}$ time for every $\varepsilon>0$) can be shown for ZPP as follows:

Theorem 5: Either $\mathrm{ZPP}=\mathrm{EXP}$ or for every $\varepsilon>0$, any language in $\mathrm{RP}$ can be simulated in $\mathrm{DTIME}(2^{n^{\varepsilon}})$ for all $\varepsilon>0$ such that no language in $\mathrm{ZPP}$ can refute the simulation io.

Proof: Assume $\mathrm{ZPP}=\mathrm{EXP} = \mathrm{RP}$. By Time Hierarchy Theorem, for every $\varepsilon>0$, $\mathrm{EXP}$ is not in $\mathrm{DTIME}(2^{n^\varepsilon})$ with $\mathrm{ZPP}$ refuters. Thus at most one of the conditions holds. By Theorem 4, at least one of the conditions holds. The result follows. QED

Notice that "easy witness'' method applies even when the refuters are allowed to be non-deterministic Turing machines, and by essentially using the same proof structure, we can obtain the following result:

Theorem 6: At least one of the following holds:

For every $\varepsilon>0$, any language in $\mathrm{NP}$ can be simulated in $\mathrm{DTIME}(2^{n^\varepsilon})$ such that no language in $\mathrm{NP}$ can refute the simulation io.
$\mathrm{BPP}\subseteq \mathrm{NP}$.

THURSDAY'S CLASS CANCELED

2009-04-14T15:05:00.003-04:00

I was informed by Deb that all classes on Thursday are canceled. So, see you on Tuesday, April 21, when Eric will tell us about Property Testing.

(This kills a lecture, which was going to be on quantum, but Matt already told us about it in his blog post, so no great loss.)

As an interesting fact, I learned that Carnival is scheduled to precisely be the "Thanksgiving weekend" of the Spring Term. That way, the Fall and Spring schedules can match exactly.

Lecture 24

2009-04-14T15:02:00.001-04:00

In today's class we covered many of the gory details of expander graphs. I didn't quite get a chance to finish the last details, so there are the notes.

Bounds on BQP

2009-04-10T22:18:00.012-04:00

Quantum computation presents the attractive possibility of computing some functions exponentially faster than would be possible under a classical model. The most compelling example is perhaps Shor's quantum factoring algorithm, which runs in polylog time. But how powerful is quantum computation? Getting some of the basic answers involves (surprisingly, to me anyway) getting into some counting complexity.

To begin, we'll need to establish a basic set of definitions. The fundamental unit of quantum computation is the qubit. Like classical bits, qubits have two states; however, qubits can exist in linear superpositions of these states, $|\psi\rangle = \alpha |0\rangle + \beta |1\rangle$, where $\alpha$ and $\beta$ are complex amplitudes subject to $|\alpha|^2 + |\beta|^2 = 1$. We cannot observe these amplitudes directly, however; to determine the state of this qubit, we need to take a measurement, the result of which will always be a pure basis state. In the previous example, measuring $|\psi \rangle$ will result in $|0\rangle$ with a probability of $|\alpha|^2$ and $|1\rangle$ with a probability of $|\beta|^2$.

If you have multiple qubits, they can become entangled with each other, meaning (roughly speaking) that their measurement probabilities are no longer independent. So, for example, if we have two entangled qubits, the states $|00\rangle$ and $|11\rangle$ could each have probability $1/2$, while the other two states have probability $0$. If you somehow knew that their states were entangled in this way, then measuring only one qubit would tell you the value of the other -- although there would be no way to predict the value of either qubit before taking the measurement. If we have a quantum register of $k$ qubits, then each of its $2^k$ possible states effectively have distinct complex amplitudes. The vector of all of these $2^k$ complex amplitudes is our state vector, which completely encodes the statistical behavior of measurements of the system.

So now we have quantum registers, to store our information. In order to perform computations, we need quantum gates. These gates are simply unitary linear operators acting on the state vector. In order to talk about quantum time classes in a meaningful way, however, we need to restrict the set of allowable fundamental gates. (Since the composition of two unitary operators is also a unitary operator, you could design a single gate that would carry out any desired computation!) One common circuit basis involves only two fundamental gates. The first is the Hadamard gate, which takes

$|0\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$
and
$|1\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

The second is the Toffoli gate, which takes three bits as input, passes through the first two bits unmodified, and XORs the third bit with the product of the first two.

Note that the fact that all changes in the state happen due to unitary operators implies that the number of outputs qubits is always equal to the number of input qubits. When dealing with quantum computation, we can assume without loss of generality that the quantum register has only a single accepting state.

Definition: BQP is the quantum analog of BPP. (Quantum computation is inherently probabilistic.) It is the class of languages decidable by polynomial-size quantum circuits that (to enforce uniformity) can be generated in polytime by a classical TM, accepting with probability at least $2/3$ for $x \in L$ and with probability less than $1/3$ for $x \notin L$. (Amplification theorems with similar results to those for BPP hold here, so any values $1/2 + \epsilon$ and $1/2 - \epsilon$ will work.)

How powerful is BQP? On the lower end, we know $BPP \subseteq BQP$: we can efficiently simulate classical circuits by quantum circuits. The Toffoli gate is universal for classical computation; if you hardwire the third input to $1$ it is simply a NAND gate. Coin flips can be simulated by Hadamard gates, since they transform pure states into equal superpositions.

What about upper bounds? Clearly $BQP \subseteq EXP$, since we can simulate any BQP machine by applying a polynomial number of linear operators to the exponential-size density matrix. It's also true, but less obvious, that $BQP \subseteq PSPACE$. We can show this by integrating over computational "paths". Recall that in a quantum computation, we apply a new small unitary operator to our state at each time step. For each accepting state $|y\rangle$ at time $t$, we can compute that state's amplitude by applying the operator $U_{t-1}$ to each predecessor state $x_0,\ldots,x_{2^n}$ and summing the results. By recursive application of this same step, we can compute the amplitude of any state anywhere in the computation at any time in polynomial space (although we do require exponential time).

But we can do better, namely $BQP \subseteq PP$.

Definition: GapP is the set of functions $f(x)$ such that, for some polynomial time NTM $M$, $f(x)$ is the difference between the number of accepting and rejecting paths in $M$. Note that this gives us an alternative definition for PP: a language $L$ is in PP if and only if there is some GapP function $f(x)$ such that when $x \in L$, $f(x) \gt 0$, and when $x \notin L$, $f(x) \leq 0$.

Fact: GapP is closed under negation, (exponential) sum, and (polynomial) product.

Fact: If there exist two GapP functions describing the real and complex parts of the entries of a polynomial sequence of complex-valued matrices, then there also exist two GapP functions describing their product.

More precisely (statement due to Watrous): let $p(x)$ and $q(x)$ be polynomial bounded functions, and, for each $n$, $A_{n,1}, A_{n,2}, \ldots, A_{n,p(n)}$ be a sequence of complex-valued matrices of size less than $2^{q(n)}$. Then, if we have functions

$f(1^n, 1^k, x, y) = Re(A_{n,k}[x,y])$

$g(1^n, 1^k, x, y) = Im(A_{n,k}[x,y])$

in GapP, then there also exist functions $F$ and $G$ in GapP such that

$F(1^n, x, y) = Re((\prod_{i=1}^{p(n)} A_{n, i})[x,y])$

$G(1^n, x, y) = Im((\prod_{i=1}^{p(n)} A_{n, i})[x,y])$

Observe that, applying an appropriate topological ordering to our quantum circuit, we can serialize our quantum gates into a polynomial number of steps. Additionally, observe that we can take the tensor product of a gate's matrix with the identity matrix for the unaffected bits in order to come up with a complete transition matrix for each time step. We can now use this fact to show that there are functions $f$ and $g$ in GapP describing all of our quantum gates.

In order to do this, we need to take advantage of an alternate representation of our quantum register: its density matrix, $\rho$. Glossing over some details, this effectively linearizes our state and operations. With $2^k$ entries in the state vector, the corresponding density matrix is a $2^k \times 2^k$ matrix with trace 1. The $i$'th entry on the diagonal is simply the probability of finding the register in state $i$. If we then let our state be this matrix, flattened into a vector, $vec(\rho)$, the entries of the matrices describing our quantum gates fall in the set $\{-1, -1/2, 0, 1/2, 1\}$. By the fact that these matrices can be generated in polynomial time, we know that the corresponding $f$ and $g$ for each matrix (multiplied by 2, to deal with the factors of 1/2) must be in GapP. Then, by the fact noted above, there must exist $F$ and $G$ describing the entries of the transition matrix for the entire circuit (multiplied by $2^{p(x)}$).

We can assume that the circuit has only a single accepting state, so finding the acceptance probability is then simply a matter of looking up the single matrix entry that describes the transition from the starting state $|x\rangle$ to the accepting state, which consists of a single invocation of a GapP function.

To complete the proof, note that the function $a(x) = 2^{p(x)} (Pr[Q \textrm{ accepts } x] - 1/2)$ is positive when $Q$ accepts $x$, and negative otherwise. Therefore $Q$ can be simulated by a PP machine, and $BQP \subseteq PP$.

In fact, not only does PP contain BQP, but $PP^{BQP} = PP$.

It is unknown whether this inclusion is tight, but all signs seem to indicate that it is. We can define the class QMA analogously to MA, except that Arthur is a BQP machine, and Merlin sends him quantum advice. This class, which obviously contains BQP, is contained in PP (originally noted by Kitaev and Watrous). Furthermore, a theorem of Vyalyi states that if $QMA = PP$, then $PH \subseteq PP$.

Midterm correction

2009-04-09T19:56:00.005-04:00

Oops. I made a mistake in the grading of question 1(e): the problem of determining whether $#L = #P$ is open. To compensate for this error, I am adding +3 to everyone's grade on the midterm. If you have any other questions about the graded midterm (or Homework 4), please see me during my office hours next Tuesday. Thanks!

Details for the IKW Theorem

2009-04-09T15:26:00.003-04:00

The proof of the IKW Theorem I gave in class was a bit sketchy; let me discuss two points about it, raised by Or and Pranjal.

1. The first point, raised by Or, was about appealing to the Impagliazzo-Wigderson Theorem (or implicitly, the Nisan-Wigderson Theorem). Normally when one thinks about that theorem one thinks of the statement, "If there is a language $L \in E$ such that $L \not \in \bigcup_c \SIZE(n^c)$, then $BPP \subseteq \bigcap_{\epsilon} DTIME(2^{n^\epsilon})$.

However, this is not what the IKW Theorem appeals to; you should think of that as a corollary of the IW/NW Theorems. The Theorems themselves are input-length-specific; e.g., for Nisan-Wigderson, the statement we're using is of the form "Let $C$ be a circuit on $n$ bits of size $n^c$, and let $f : \{0,1\}^{n^{1/10c}} \to \{0,1\}$ be a function such that every size-$n^{2c}$ circuit has correlation at most $1/n^{2c}$. Then [some explicit PRG outputting $n$ bits based on $f$'s truth table and designs] $1/10$-fools $C$."

2. The second point, raised by Pranjal, was about the uncareful (indeed, possibly incorrect) way I explained the derandomization of $MA$ that comes out of assuming $NEXP \neq EXP$. The wrong way to say it is to start with a fixed language in $MA$ and then deduce that Arthur's $n^c$-time randomized part can be replaced by some other $NTIME(2^{n^a})$-time algorithm (with advice). That is, of course, pointless, if $a \geq c$, since Arthur could just enumerate all possible random strings. Rather, the key is to show that all of $MA$ can be done by a nondeterministic (advice-taking) Arthur who uses fixed-exponential nondeterministic time.

In other words, the correct key lemma is:

$NEXP \neq \EXP \Rightarrow \exists c, MA \subseteq io-[NTIME(2^{n^c})/n]$.

This is nontrivial because the same $c$ works for all languages in $MA$, regardless of their polytime complexity. And the proof of this uses the appeal to the length-specific IW Theorem described in Point 1 above.

Lecture 23

2009-04-09T15:25:00.000-04:00

Today we finished the proof of the IKW Theorem. We also showed fhe Kabanets-Impagliazzo Theorem: derandomizing Arithmetic Circuit Identity Testing implies $NEXP$ not in $P/poly$ or Permanent not in $AlgP/poly$ or both.

We then moved on to the definition of expander graphs, the definition of strongly explicit graph families, and saw the Lubotsky-Phillips-Sarnak and Margulis-Gabber-Galil expander families.

Why there isn't a simpler proof of IKW

2009-04-07T15:17:00.003-04:00

A question raised in class today was, Why can't we prove the IKW Lemma, $NEXP \subseteq P/poly \Rightarrow NEXP = EXP$, via techniques similar to Meyer's Lemma, $EXP \subseteq P/poly \Rightarrow EXP = PSPACE$?

(Recall, btw, that IKW actually get $NEXP = MA$ and Meyer actually gets $EXP = \Sigma_2$.)

In discussing it with Or and Pranjal after class, it seems the answer is the following. In the Meyer Lemma, for a fixed $EXP$ machine, we considered the map taking the index of tableau window into the tableau window contents. That map is in $EXP$, hence in $P/poly$. So there exists a circuit $C$ of some size $n^k$ computing the map. Given x, we enumerate all circuits of that size, and accept iff one of them implicitly describes an accepting tableau; this is doable in $PSPACE$.

Why doesn't this work for $NEXP$? For $NEXP$ computations, there may be multiple accepting tableaus. Not a problem so far. Certainly the $PSPACE$ algorithm still makes sense: enumerate all circuits of some fixed poly-size, and if one of them implicitly describes an accepting tableau, accept. The question is, if $x$ is in the language, will there be a fixed poly-size circuit describing an accepting tableau?

One has to be careful. There is no longer a clear meaning for "the map that takes a tableau window index to the tableau window contents", since there are multiple valid tableaus. Perhaps that's okay; perhaps we can allow for "multivalued functions". But still, there isn't a clear meaning for "this map is computable in $NEXP$ and hence in $P/poly$". The reason is, the usual meaning of an NTM computing a function is that some branches reject, and the ones that accept output valid answers. Such a model indeed computes a multi-valued function. However since it's not a decision problem (a language), it's not clear how we can get anything out of the assumption $NEXP \subseteq P/\poly$.

One way around this, as Or suggested, would be to make everything single-valued by looking at the lexicographically least accepting tableaus. Unfortunately, as we saw on Homework 2, this lexicographically least satisfying assignments characterize the lass $P^{NP}$, not $NP$. All is not lost, though; a paper of Bourke uses such ideas to show $EXP^{NP[t(n)]} \subseteq P/poly \Rightarrow EXP^{NP[t(n)]} = MA$ (where the notation indicates that the $EXP$ machine makes $t(n)$ queries to the oracle). This is related to Buhrman and Homer's old extension of Karp-Lipton: $EXP^{NP} \subseteq P/poly \Rightarrow EXP^{NP} = \Sigma_2$.

Lecture 22

2009-04-07T11:16:00.003-04:00

In this lecture we covered "derandomization implies circuit lower bounds" topics. In particular, we saw:

Kannan's Theorem, $\Sigma_2$ doesn't have fixed-polynomial size circuits.

The Babai-Fortnow-Lund Theorem, $EXP \subseteq P/poly \Rightarrow EXP = MA$, and its consequences: $MA$-$EXP$ does not have polynomial size circuits, derandomizing $MA$ to $NP$ implies showing $NEXP$ does not have polynomial size circuits.

Most of the Impagliazzo-Kabanets-Wigderson Theorem, $NEXP \subseteq P/poly \Rightarrow NEXP = EXP$ (and indeed $NEXP = MA$), along with Kabanets's "easy witness method". The remainder will be proved next time.

Homework 5

2009-04-07T11:15:00.001-04:00

Homework 5 is posted, due in 2 weeks as usual. It's long! Start early.

Lecture 21

2009-04-02T15:20:00.005-04:00

Today we saw the completion of Sudan-Trevisan-Vadhan's proof of the Impagliazzo-Wigderson Theorem: if there is a positive $\epsilon > 0$ such that $E$ contains a language not in $SIZE(2^{\epsilon n})$, then $P = BPP$. This included Sudan's algorithm for list-decoding Reed-Solomon codes.

Lecture 20

2009-03-31T14:48:00.001-04:00

Today we covered...

Reed-Muller code review. Local decoding with "random lines". Code concatenation. Beginning Sudan-Trevisan-Vadhan's hardness amplification.

Midterm correction

2009-03-30T12:44:00.001-04:00

On problem #4 on the midterm, assume $w \geq n$.

Thanks to Or for pointing out the necessity of this.

Lecture 19

2009-03-26T14:49:00.001-04:00

Today we covered...

Completion of proof of Impagliazzo's Hard-Core Set Theorem, Yao's XOR Lemma. Intro to error-correcting codes, list-decodable codes, locally decodable codes. Reed-Solomon codes, Hadamard codes, Reed-Muller codes. Connection between local list-decoding and hardness amplification.

Lecture 18

2009-03-24T14:35:00.001-04:00

Today we covered: Hardness vs. randomness corollaries of Nisan-Wigderson; Impagliazzo-Wigderson Theorem ($f \in \mathsf{E}$ requiring circuits of size $2^{\epsilon n}$ implies $\mathsf{P} = \mathsf{BPP}$); Hardness Amplification , $1 - 1/\mathrm{poly}(n)$ hardness to $1/2 + 1/\mathrm{poly}(n)$ hardness, with the XOR Lemma; Impagliazzo's proof via the Hard-Core Set Theorem (with Nisan's proof via the Minimax Theorem).

Midterm

2009-03-24T12:11:00.002-04:00

The take-home midterm is posted on the course home page. Please grab a copy now.

As a reminder, it is due next Tuesday, no collaboration is allowed, and no references to "outside" sources are allowed: just your course notes, the blog, the course homeworks, and the course homework solutions.

Lecture 17

2009-03-20T12:58:00.001-04:00

In this lecture we covered the Nisan-Wigderson Generator, which connects hardness to randomness. In the course of proving it we also saw designs and the Yao Next-Bit Predictor Theorem, which uses the "hybrid method".

Lecture 16

2009-03-17T15:16:00.004-04:00

In this lecture we covered Nisan's pseudorandom generator for log space.

One thing I had to rush over at the end was the actual definition of the generator, along with its seed length!

Here is an official inductive definition of the generator: Let $h_1, ... h_{\lg n} : \{0,1\}^k \to \{0,1\}^k$ be functions. We define $G_t : \{0,1\}^k \to \{0,1\}^{2^t k}$ inductively by $G_0(x) = x$, $G_{t}(x) = (G_{t-1}(x), G_{t-1}(h_t(x)))$.

Finally, Nisan's generator $G$ maps $\langle x, h_1, ... h_{\lg n} \rangle$ into $G_{\lg n}(x)$. Here the $h_i$'s are the "descriptions" of the hash functions.

Recall that we are using the simple "$a \circ x + b$" pairwise independent hash family; the "description" of such a function is just the $2k$-bit string $\langle a, b\rangle$. Conveniently, choosing this description uniformly at random coincides with choosing $h \sim \mathcal{H}_k$ uniformly at random.

So finally, the seed length is $\ell = k + (\lg n)(2k)$. Since $k = O(\log S)$, this is indeed $O(S \log n)$ seed-length, as claimed. The number of output bits is in fact $nk = O(n \log S)$ (which is, as we noted, slightly more than we need).

Fixed-polynomial circuit lower bounds for MA/1

2009-03-16T17:56:00.009-04:00

In this post, we look at a recent circuit lower bound result which shows that MA/1 is not contained in the class SIZE($n^k$). Some history and motivation first: A well studied fundamental problem in lowerbouds is in showing super-polynomial circuit lowerbounds for NP. This is natural to look at, since such a result would immediately separate P and NP, because P $\in$ P/poly has poly-sized circuit families deciding languages in it.

However, though people have been looking at this problem for quite some time, even getting super-linear lower bounds on the circuit size has been evasive. While the goal has been getting super polynomial lower bounds, the current best lower bound is just $4.5n - o(n)$.

Given this state, a natural thing to do is to look at showing results for larger classes, or in other words, attack NP from above. In this line of research, Kannan showed a promising result of this nature (we have seen this in one of the homeworks): $\Sigma_2 \cap \Pi_2$ is not contained in SIZE($n^k$). Getting closer to NP, Kobler and Watanabe have shown using the halving algorithm of BCGKT (seen in class), that $ZPP^{NP}$ has a circuit lower bound of $n^k$, for any fixed $k$. This is an improvement over the previous result of Kannan, as $ZPP^{NP}$ is "closer" to NP than $\Sigma_2 \cap \Pi_2$ is (i.e. $NP \subseteq ZPP^{NP} \subseteq \Sigma_2 \cap \Pi_2$).

In a recent result, Rahul Santhanam gets even closer to NP by showing an almost polynomial circuit lower bound for MA. He shows that for any fixed $k>0$, there are languages in the class MA/1 (MA with $1$ bit of advice) which are not decided by non-uniform circuit families of size $n^k$. Why is this result important ? Intuitively, MA is like the probabilistic version of NP, and therefore such lower bounds automatically gain much value, as it is widely believed that ''randomness'' to NP does not give much more power than the basic NP class (that is, MA $=$ NP is believed to hold). This therefore nearly implies polynomial circuit lower bounds for MA, which sits just above NP in the hierarchy. We say nearly because the class for which he shows a lower bound assumes $1$ additional bit of advice (MA/1).

Now let's look at the high level picture of proving such lower bounds. Imagine we want to show a lower bound for a class C, where NP $\subseteq$ C. If it is the case that NP is not contained in P/poly, then we are done because C is only larger than NP. On the other hand, if NP $\subseteq$ P/poly, then we \emph{use} this fact to show that the polynomial hierarchy collapses to C. But there are complete problems in PH which are not decided by SIZE($n^k$) --- recall this from HW1; because of the collapse, these problems are in $C$, and this completes the proof. If we recall, we did the exact same thing for showing such lower bounds for $\Sigma_2 \cap \Pi_2$: we showed that if NP $\subseteq$ P/poly, then PH collapses to $\Sigma_2 \cap \Pi_2$. Since we know that PH has problems which are not decided by SIZE($n^k$), we have that $\Sigma_2 \cap \Pi_2 $ is not contained in SIZE($n^k$).

In fact, the argument need not always be based on the two cases of whether or not NP is in P/poly. There are cases where it helps to consider a class which \emph{contains} C, and then argue depending on it's containment in P/poly. For instance, we have the result that if PSPACE $\subseteq$ P/poly, then PSPACE $=$ MA (this problem figures in HW4). Intuitively, the proof goes as follows: if PSPACE $\subseteq$ P/poly, then the prover of the IP protocol for QBF (a complete problem for PSPACE $\subseteq$ IP) can be represented by a poly-sized circuit. Merlin can therefore simply give Arthur the circuit for the correct input size and Arthur can use the circuit to simulate any query to the prover. Completeness is direct, and intuitively, soundness holds because we know no adaptive prover can cheat Arthur, so no fixed prover can! Therefore, QBF $\in$ MA.

Using the ideas defined above, we are now ready to show the main theorem that MA/1 is not in SIZE($n^k$).
We require the following lemma, whose proof is rather technical (using Shamir's proof for IP = PSPACE) and we omit.

There exists a PSPACE-complete problem $L$ and a probabilistic polynomial time turing machine $M$ such that for any input $x$,
1. $M$ asks only queries of length $|x|$.
2. If $M$ is given the language $L$ as oracle and if $x \in L$, then $M$ accepts $x$ with probability $1$.
3. If $x \notin L$, then no matter what oracle $M$ gets, it accepts with probability only at most $1/2$.

Such a complete problem is known to exist, and we shall make use of it. Just as an aside, this definition of $L$ seems similar to the notion of checkers in HW4.

If this language $L \in $ P/poly, then PSPACE $\in $ P/poly, meaning PSPACE $=$ MA, and this would give us the desired result since PSPACE is not contained in SIZE($n^k$). Therefore, we assume that $L \notin $ P/poly, and create the following \emph{padded} language $L'$. For what follows, let $s(n)$ denote the size of the smallest circuit which can decide $L$ on inputs of size $n$. Consider the following language $L'$:

$L' = \{ x1^{y} | x \in L, |x| = n, y \geq n, y$ is a power of $2, s(n) \in ((y + n)^{k+1}, (2y+n)^{k+1}] \}$.

We show that $L' \in $ MA/1 but $L' \notin $ SIZE($n^k$). We first show the latter result: In some sense, the magic is already done as the padding has sort of diagonalized the input.
Because $L \notin $ SIZE($n^k$) (we are in the case where $L \notin$ P/poly), there exists some input size $n_0$ such that $s(n_0) > (n_0+1)^k$, where $s(n)$ is the size of the smallest circuit deciding $L$ on inputs of size $n$. Define $y_0$ to be the power of $2$ such that $(n_0 + y_0)^k < s(n_0) \leq (n_0 + 2y_0)^k$. Notice that this is the same $y$ as defined in $L'$.

Now, suppose $L'$ has a circuit family of size $m^k$. We now create a "small" circuit for deciding $L$ on input size $n_0$: the circuit simply hardwires $y_0$ additional $1$'s to the input $x$ and subsequently mimics the circuit of $L'$ on inputs of size $n_0 + y$. However, the size of this circuit is at most $(n_0+y)^k$, which contradicts the definition of $s(n)$. This shows that $L' \notin $ SIZE($n^k$).

All that remains is to show that $L' \in $ MA/1. The key here is in knowing if the input size $m$ of a given $x1^y$ is \emph{valid}, in that it satisfies the circuit size condition. It would be difficult to have the MA protocol figure it out if the circuit size is large (which it probably is), but here is where we use the $1$ bit of advice. Given an input size of $m$, the advice is $1$ if and only if $m$ can be decomposed into $n$ and $y = 2^k$ such that $y \geq n$, and the smallest circuit size for deciding $L$ on inputs of size $n$ is between $(y+n)^{k+1}$ and $(2y + n)^{k+1}$. Notice that if such a valid $(n,y)$ decomposition exists, it is unique: if we try to increase $y$ to $2y$ and decrease $n$ accordingly, it would make the resulting decomposition infeasible as we have $y \geq n$.

Thus, given $x1^y$ for which we need to decide membership in $L'$, the MA protocol does the following: Merlin sends Arthur the circuit of size $s \in ((n+y)^{k+1}, (n+2y)^{k+1}]$ which solves $L$ on inputs of length $n$. Arthur checks if the advice is $1$, and rejects if it is not. If it is, then the $m$ is of a valid length, and Arthur looks at the circuit and identifies $n$ (which is the input size of the received circuit) and makes other necessary checks, like $y \geq n$, $y$ is a power of $2$, and $(y+n)^{k+1} < s \leq (2y+n)^{k+1}$. It then simulates $M$ (recall $M$, the probabilistic turing machine which decided $L$ with some oracle given), and accepts or rejects based on $M$.

It is easy to see that if $x1^y \in L'$, then Merlin could send the correct circuit, and Arthur would always accept. On the other hand, if $x1^y \notin L'$, then Merlin ``commits'' to an oracle by sending a circuit and by the properties of $L$ and $M$, Arthur accepts with only a small probability. This completes the proof.

On the power of membership queries in agnostic learning

2009-03-06T18:11:00.013-05:00

In class, the BCGKT theorem was introduced as an illustration of approximate sampling. It's also a complexity-theoretic result for query learning, wherein learning algorithms can draw examples of their choosing, not just those from a fixed dataset or a rigid oracle. Much as interactive proofs exploit the ability to ask (randomized) questions, query learning algorithms exploit the ability to perform experiments, ask users for feedback, and examine surroundings. These varying capabilities correspond to different models of query learning. In the BCGKT theorem, the NP oracle answers to equivalence querying: it either accepts the candidate hypothesis or returns a counterexample. Other interesting models include membership querying, which allows examples to be constructed from scratch and submitted to an oracle who labels it positive or negative, and active learning, in which artificial construction is disallowed but many unlabeled examples are available. Many positive results, such as exponential improvements in sample complexity, make query learning a topic of major interest in learning theory.

Query learners tend to work well because pivotal examples can falsify large swaths of the hypotheses under consideration. It's not surprising that they encounter difficulty when the true function is never a candidate and may not even exist. This impairs the ability to rule out hypotheses on the basis of a single inconsistency and often forces the learner to satisfy a conservative elimination criterion. This so-called agnostic setting is rife with hardness results, including a contribution by one of our wise masters.

The marginal distribution of the examples is often critical. Negative results for distribution-independent learning are often paired with positive results for distribution-specific learning; see, for example, the reply from our other wise master to his counterpart. This phenomenon is exemplified by Vitaly Feldman's recent work, which appeared in short at COLT '08 and in full a few days ago in JMLR.

The bad news comes first. When the examples come from an unknown distribution, membership queries don't offer any additional power. Much like boosting relies on a learner's ability to handle any marginal distribution on the examples, this proof relies on the learner's ability to find the best hypothesis regardless of how the joint example-label distribution changes. This robustness admits simulation of a membership query oracle: draw a sample, evaluate queries against the sample when possible, and return dummy answers for queries outside the sample. If error rates on the sample-conjured oracle are representative of those on the original distribution - something that can be ensured with Vapnik-Chervonenkis bounds - then the existence of a membership query learner implies the existence of a standard oracle learner. Feldman actually proves a stronger result involving finer details of agnostic learning, but those aren't of particular interest to this complexity class.

The juicier result, and the main topic of this post, is the separation proof: when the examples are uniformly distributed, some concept classes are learnable through membership queries but not through a standard oracle. Random samples may not reveal knowledge crucial to learning; since the distribution is fixed, this weakness can be systematically exploited. In the agnostic PAC model - noise free in the sense that the conditional expectation $\phi$ of the labels is a consistent boolean function of the examples - the exploit is very simple: carve out a small portion of the domain and therein hide a suitably short encoding of the target function. The encoding can be easily recovered by membership queries, but it is unlikely to be found by random examples due to the relatively large size of the entire domain.

This trick doesn't work in the agnostic setting, where such hiding places cannot be safe or small. Functions can be arbitrarily noisy on any part of the domain, so it's impossible to find a safe area to keep a brittle encoding. This issue is mitigated by the Hadamard code, which encodes an $n$-bit vector as all the $2^n$ values taken by the parity function $\chi$ for that vector. This approach seems suspicious, since all the values clearly can't be recovered, and learning parity functions in the agnostic setting is a major open problem. These worries are resolved by the Goldreich-Levin theorem, which was covered recently in Luca's class. For the purpose of this proof, the Goldreich-Levin theorem allows efficient recovery of the largest Fourier coefficients of $\phi$. We could stop here if we were happy to assume the intractibility of learning parities from a noisy standard oracle.

But we're not, so we're left to worry about how the Hadamard bloat might expose our secret to detection. Even an efficient coding scheme, like that described by Guruswami and Sudan, doesn't save us from a hefty lower bound on the size of the secret region. Assuming the concept class cannot be learned without the secret region, the region must occupy at least $(1-2\epsilon)2^n$ proportion of the domain.

The trick of sampling a fixed part of the domain is preserved by a technique from a 2007 paper by Elbaz et al. Instead of storing the Hadamard code in plain sight, it is obscured by a pseudorandom function. Recall that $\pi_y$ is a pseudorandom boolean function if its output cannot be distinguished from a completely random function with more than negligible probability in polynomial time. Such functions exist if one-way functions exist, which is the cryptographic assumption underlying the proof. Here they are used to build concepts of the following form (meaning will soon be given to the undefined variables; treat them as opaque for now):

$g_{\bar{d}}\left(k,z,\bar{x}\right)=\pi_{d_k}(z)\oplus \chi_{\bar{d}(k)}\left(\bar{x}\right)$

View the arguments as a single binary string of length $m$ and suppose $k$ is fixed. The value of $g$ on a random example $(z,\bar{x})$ is pseudorandom but, if $z$ is fixed, then $\{g(z,x)\}_x$ recovers the Hadamard encoding of $\bar{d}(k)$. Of course, this is possible only if $d_k$ is encoded and recovered; this will require another secret, and so forth. Thus a sequence of pseudorandom functions and secrets are used. There are $p-1$ such secrets $\bar{d}=\left(d_1,d_2,\ldots ,d_{p-1}\right)$, each indexing a family of pseudorandom boolean functions $\mathcal{F}_n=\left\{\pi_y\right\}_{y\in \{0,1\}^n}$. To combat adversarial noise, the sequence is highly redundant: each secret doesn't unlock one previous secret, but all previous secrets.

All the secrets except one can be recovered by membership queries, but doing the same from random examples would be akin to distinguishing a random function from a pseudorandom function. The proof details are a little hairy. I encourage you to read the original paper, but please don't be led astray by the figure; it's missing an arrow and it's labeled incorrectly. Vitaly says he'll post a corrected version on his site, most likely here.

In short, membership queries offer no advantage in the fully agnostic setting. Cryptographic evidence suggests that membership queries are more powerful than a standard oracle when the examples are uniformly distributed. I suggest Dana Angluin's survey to interested readers.

Factoring

2009-03-05T16:11:00.002-05:00

Sam asked me about the complexity of factoring, and the fastest known algorithms for it. Here is a very nice survey by Pomerance about the best known algorithms. Some light reading for you over Spring Break!

Lecture 15

2009-03-05T16:06:00.006-05:00

In this lecture we finished the proof of the Switching Lemma and showed how it implied Håstad's Theorem: Computing Parity by depth-$k$ circuits (unbounded fan-in) requires size $2^{\Omega(n^{1/(k-1)})}$.

We then stated and sketched the proof of the Linial-Mansour-Nisan (LMN) Theorem: If $f$ is computed by depth-$k$, size-$S$ circuits, then there is a multilinear real polynomial $p$ of degree at most $t = O(\log(S/\epsilon))^{k}$ which approximates $f$ in the following sense:

E${}_{x}[(f(x_1, ..., x_n) - p(x_1, ..., x_n))^2] \leq \epsilon$,

where $x = (x_1, ... x_n)$ is a uniformly random string.

By the way, Håstad subsequently slightly sharpened this; he improved $t$ to

$O(\log(S/\epsilon))^{k-1} \cdot min\{\log S, \log (1/\epsilon)\}$.

Lecture 14

2009-03-03T15:51:00.002-05:00

In this class we reviewed DNF/CNF size and width decision tree size and depth. We then began the proof of the Switching Lemma, which we will finish next time. If you want to read up on it, we are following Paul Beame's exposition.

Also, Homework #4 is out. It is due in 3 weeks, after which we will have the midterm. This midterm will occupy either 5 or 7 days.

Recognizing/printing real numbers in real time

2009-02-28T15:04:00.003-05:00

In the first blog post for the course, on the history of complexity, I saw mention of the question of whether the number $\sqrt{2}$ could be printed out by a Turing Machine at a rate of $O(1)$ time per digit. I had never heard of the problem before. Apparently one can ask similar questions about recognizing in "real time" whether a number is, say, $\sqrt{2}$; for more, see this post on Dick Lipton's blog.

Lecture 13

2009-02-26T15:09:00.000-05:00

Today we covered: Parity has unbounded fan-in circuits of depth-$d$ size-$2^{\Theta(n^{1/(d-1)})}$. Hastad's Theorem statement: This is also a lower bound for constant $d$. Proof in the case $d = 2$ (CNF, DNF). Razborov-Smolensky proof with $1/(4d)$ rather than $1/(d-1)$. Its main tool: For any $k$, $\epsilon$, there is a probability distribution on $k$-variable polynomials of degree $O(\log k \log(1/\epsilon))$ such that for every $k$-bit input $x$ we have $\Pr[p(x) = OR(x)] \geq 1 - \epsilon$ when $p$ is chosen from the distribution. Expanding functions $f : \{-1,1\}^n \to \mathbb{R}$ in the Fourier basis.

Homework 2 wrapup

2009-02-25T09:30:00.002-05:00

By the way: #4 is a theorem of Krentel; the class in #5 is actually called $S_2P$ (not $S$) and the problem is a theorem of Cai; #6 is a theorem of Mulmuley-Valiant-Vazirani.

Lecture 12

2009-02-24T14:48:00.000-05:00

Today we covered: Definitions of $AM[k]$ and $MA[k]$; $AM[k]$ and $MA[k]$ unchanged if perfect completeness required (statement); $MA = MA[2] \subseteq AM[2] = AM$; $AM[k] = AM[2]$ for all constant $k$; indeed, $AM[4r] \subseteq AM[2r+1]$ for any $r = r(n)$; $AM \subseteq \Pi_2$; Boppana-Hastad-Zachos Theorem, $coNP \subseteq AM \Rightarrow PH = AM$; Graph-Non-Isomorphism is not $NP$-complete unless the hierarchy collapses to $\Simga_2$; Goldwasser-Sipser Theorem, $k$-round private-coin interactive proofs are doable with $(k+10)$-round public-coin interactive proofs, hence $AM$ is unchanged if public coins are required; set size lower bound protocol in public coins $AM$.

Solutions to Homework 2

2009-02-24T13:12:00.003-05:00

I will be returning Homework 2 in class today. The class average on this homework is 79%. Solutions for the homework will once again be available upon request; please email me if you would like a copy.

Derandomization of space classes

2009-02-21T13:03:00.040-05:00

Understanding the exact computational power of randomness is an intriguing and very challenging problem in computer science. Although we are far away from an answer, a lot of nice results have emerged in the last two decades, particularly in the area of space bounded computations. In this post, we will look at a couple of such results. We will restrict our attention to randomized log-space machines, or the complexity class BPL, but the results we mentioned generalize to BSPACE($s(n)$) for any space constructible function $s(n) \ge \log n$. Recall that a BPL machine M
for a language L is a randomized machine running in log-space and satisfying the following conditions:
$x \in$ L $\Rightarrow$ Pr[M accepts $x$] $\ge \frac{2}{3}$
$x \notin$ L $\Rightarrow$ Pr[M accepts $x$] $\le \frac{1}{3}$
Also we know that, the computation of such a machine on input $x$ can be seen as a random walk on a graph $G$, called the ``configuration graph''. Each node in this graph represents a configuration of the machine and each edge represents a valid transition. Let us denote by $d$, the total number of nodes in this graph and let us assume that that the graph has a unique start state $c_{start}$ and unique accept and reject states $c_{accept}$ and $c_{reject}$. Since, the machine runs in log-space we know that $d$ is polynomial in the length of the input. We can also associate, with this graph, a matrix Q called the ``transition matrix''. The entry Q[i,j] in this matrix contains the probability that the machine M goes from configuration $i$ to configuration $j$ in one step. This way of looking at a BPL machine is very convenient since now simulating the machine is equivalent to computing the $p$ step transition probability $Q^p$[$c_{start}$ , $c_{accept}$], for any $p \ge d$. If this probability is more than $\frac{2}{3}$ we accept. If this probability is less than $\frac{1}{3}$, we reject. Savitch's idea of repeated matrix squaring computes this probability exactly giving us the following derandomization result $ BPL \subseteq L^2$. We would also be interested in the running time used by these simulations, hence we will rewrite the above result as BPL $\subseteq$ DTISP($n^{O(\log n)}$,$(\log n)^2$).

Further improvements to this result are all based on a very nice ``duality'' between hardness and randomness. This relationship was made concrete in a paper by Noam Nisan and Avi Wigderson. The high level idea is as follows: Suppose we have pseudo-random generator which takes as input a
short truly random seed and can produce a very long sequence of bits which look random to any probabilistic machine. We can then use these pseudo-random bits instead of truly random bits to simulate the machine thereby reducing the amount of randomness used. This in turn has the potential to lead to better deterministic simulations. Unfortunately, pseudo-random generators are known to exist only under the assumption that certain cryptographic objects called one way functions exist. However, it is possible to construct specialized unconditional pseudo-random
generators which can fool a particular class of machines C. Here is one way to do it, choose a class of functions, one for each input length, which is hard for the class C. In other words for every $n \ge 1$, for every machine M $ \in$ C, we must have |$Pr_{x \in U_n}$[M($x$) = f($x$)] $-$ $\frac{1}{2}$| $ \le \epsilon$, where $U_n$ is uniform distribution over $\{0,1\}^n$ and $\epsilon $ is very small(lets say $\frac{1}{n^2}$). What this means is that any machine in C can not do much better then random guessing when asked to predict the values of the hard functions. If we have such a class of functions, then here is a very simple pseudo-random generator which stretches its seed by 1 bit: $G_f : s \mapsto (s,f(s))$. Notice, that although we are only appending $f(s)$ at the end, no machine in C can distinguish that from a truly random bit with significant probability. This was roughly the idea behind the pseudo-random generator proposed by Nisan and Wigderson.

Later, in a breakthrough result, Noam Nisan gave a pseudo-random generator which can fool all probabilistic log-space machines and uses only $(\log n)^2$ bits of randomness. Notice, that this is an exponential improvement since a BPL machine can potentially use poly($n$) random bits, where $n$ is the length of the input. Virtually, every result in derandomizing space complexity classes has used some ideas from Nisan's paper. Before stating Nisan's result some definitions:

Definition 1:
For a vector $x \in {\Re}^d$, we define the $L_1$ norm of $x$ to be ||$x$|| = $\sum_i x_i$. For a $d \times d$ matrix over $\Re$, we define the norm of M, ||M||, to be the maximum over all the rows M[$i$,.] of ||M[$i$,.]||.

Definition 2:
If M and N are square matrices of the same dimension and $a$ is a positive real number, we say that M approximates N with accuracy a if ||M $-$ N|| $ \le 2^{-a}$.

Recall that simulating a BPL machine is equivalent to calculating the matrix $Q^p$, for some $p \ge d$. Hence, we now state and view Nisan's result as as randomized algorithm for approximating this matrix. We will call Nisan's algorithm PRS which stands for pseudorandom repeated squaring.

Theorem:
Let $a$ be an integer. Given as input a $d \times d$ transition matrix Q and an integer $r$, the PRS algorithm takes a random string $h$ of size $O(r(\log n))$ as input, runs in space $O(r + \log n)$ and computes another matrix $Q^\prime$, such that $Q^\prime$ approximates $Q^{2^{r}}$ with accuracy $a$ and error probability $2^{-2a}$.

Notice, that it is enough to approximate the entries in the matrix $Q^{2^r}$, since we only want to detect a significant gap in the acceptance probability of $\frac{2}{3}$ when $x \in $ L and the probability of $\frac{1}{3}$, when $x \notin$ L. For simulating BPL, we need to choose $r$ such that $2^r \ge d$. Choosing $r = O(\log n)$, gives us the desired log-space simulation which uses $O((\log n)^2)$ bits of randomness. A straightforward derandomization of this algorithm, i.e. enumerating through all the possible choices of the random seed, will not help us improve on the bound given by Savitch's theorem(WHY?). But, in a later paper Nisan observed that most of the bits in the random seed can actually be calculated deterministically, reducing the randomness used by the algorithm to $O(\log n)$. Derandomizing this new algorithm gives a deterministic simulation of BPL which uses $O((\log n)^2)$ space and $n^{O(1)}$ time! Hence, Nisan was able to show that BPL $\subseteq$ DTISP($n^{O(1)}$,$(\log n)^2$). In other words, Nisan showed that BPL $\subseteq SC$(``Steve's'' class). In a later work Nisan, Endre Szemer$\grave{\textrm{e}}$di, and Wigderson, in 1992, showed that undirected s-t connectivity(USTCONN) is in $L^{\frac{3}{2}}$. Of course, from Omar Reingold's result in 2004, we now know that USTCONN $\in$ L. But at that point the USTCONN $\in$ $L^{\frac{3}{2}}$ was a major indication that may be deterministic simulation of BPL could be done in $L^{\frac{3}{2}}$. This was achieved by Michael Saks and Shiyu Zhou and will be the last result covered in this post.

The main idea behind Saks and Zhou's result is to somehow balance the space usage and the randomness usage of the PRS algorithm. One way to do this is to try and combine Savitch's theorem and Nisan's PRS algorithm, i.e. try to do repeated matrix squaring but at each level of recursion, instead of calculating the matrix exactly, approximate it using the PRS algorithm. Lets see how it works in detail.
Consider the PRS algorithm again. Lets divide the input $r$ into two parts $r_1$ and $r_2$ such that $r = r_1r_2$. We can calculate $Q^{2^r}$ as a sequence matrices $Q_0$,$Q_1$,$\ldots$,$Q_{r_2}$, such that $Q_0$ = $Q^{2^{r_1}}$, $Q_{i+1}$ = ${Q_i}^{2^{r_1}}$ and $Q_{r_2}$ = $Q^{2^r}$. At each of the $r_2$ levels of the recursion we can use the PRS algorithm
to approximately calculate the matrices. We are going to use $O(\log n)$ space at each level for a total of $O(r_2 \log n)$ space. Also we are going to use $O(r_1 \log n)$ bits of randomness at each level for a total of $O(r \log n)$ bits of randomness. At present this does not seem very impressive, but what Saks and Zhou show is that we can actually use the same seed for the PRS algorithm at each level of recursion. This reduces the randomness complexity to $O(r_1 \log n)$. The reason why we can do that is the following: The analysis of the PRS algorithm shows that most of the seeds are good for a given fixed matrix. Hence, by union bound we must be able to show that most of the seeds are also good for a fixed set of matrices. If we can do that then we can set $r = O(\log n)$, and $r_1=r_2$, to get an algorithm with space complexity $O({(\log n }^{\frac{3}{2}})$ and randomness complexity $O({(\log n)}^{\frac{3}{2}})$. Then, a straightforward derandomization will give us the desired result that BPL $\subseteq L^{\frac{3}{2}}$. But there is a catch.

Notice that we cannot really apply the union bound argument to the matrices produced by the PRS algorithm since each of them depends on the seed used in the previous level of recursion. Saks and Zhou get around this problem by introducing the idea of random perturbations. The main observation is that we can apply the union bound argument to the sequence of matrices if they are not approximately calculated but exactly calculated as in Savitch's theorem. Now, the PRS algorithm guarantees that the matrices will be very close to the exact ones. Hence, if we just truncate the values in the matrices ignoring the lower order bits, we should be done. Except that we might have some bad roundings at boundary cases. Hence, what Saks and Zhou do is that they reduce the value of each entry in the matrix at each level by some random quantity and then truncate the values. In this way, the new matrices are independent of the seed used and we can then say that most of the seeds will be good for all these matrices. For random perturbations we increase the space usage at each level by $O(\log n)$. But the final space usage still is $O((\log n)^{\frac{3}{2}})$. That's it, we can now state Saks and Zhou's result that
$ BPL \subseteq DTISP(n^{O({(\log n)}^{.5})},{(\log n)}^{1.5}) $

Some follow-up work has been done after Saks and Zhou's result. For example, Jin-Yi Cai, Venkatesan Chakaravarthy and Dieter Van Melkebeek give a time-space tradeoff version of Saks and Zhou which says that, for any rational number $0 \le \alpha \le .5$, BPL $\subseteq$ DTISP($n^{O({(\log n)}^{.5-\alpha})}$,${(\log n)}^{1.5 + \alpha}$). Since then, Reingold's log-space algorithm for USTCONN has been a major result.

There is a general feeling in the community that we might be close to proving RL$=$L. In fact, Omar Reingold, Luca Trevisan and Salil Vadhan, in a paper in 2005, gave some strong evidence in favor of this.

Aside:
If you have read so far then a natural question to ask is: What about derandomization of time complexity classes. Can similar ideas be applied. Conceptually, Yes. Nisan's idea is pretty neat and generic. I have not done much survey but some initial reading seems to suggest that it is difficult to give unconditional pseudorandom generators which can fool time bounded complexity classes. May be the instructors can shed more light on this issue.

Lecture 11

2009-02-19T16:47:00.005-05:00

In Lecture 11, we covered:

Telling coke and pepsi apart: Interactive protocol for Graph nonisomorphism;
Interactive proof for Counting-SAT (and so PH is a subset of IP);
The precise power of interaction: IP = PSPACE ;
Perfect completeness and public coins don't change power of IP.

Graded problem set 1 was handed back.

Lecture 10

2009-02-17T15:27:00.003-05:00

Topics covered in Lecture 10:

Barrington's theorem: NC^1 has constant width branching programs (Ben-Or & Cleve's proof which showed width 7)
Lipton-Viglas theorem: SAT can't be solved in simultaneous n^{o(1)} space and n^{1.41} time.
Comments on relativization and limits of diagonalization
Introduction to Interactive proofs

Homework 2 -- CORRECTION

2009-02-16T13:46:00.001-05:00

A correction has been made to Problem (6c) on the homework. Thanks to Or for pointing out the mistake and giving the correction. The new statement (which is also in the file on the course home page) is:

c) Suppose we form $G'$ by blowing up each node $v$ in $G$ to a clique of size $2nk + w(v)$; we put either all possible edges or no possible edges between the "$u$-clique" and the "$v$-clique", depending on whether or not $(u,v)$ was an edge in $G$. Let $k' = 2nk^2 + r$, where $r \in [2nk]$ is chosen randomly. Show that if $G$'s maximum clique has size $< k$ then with probability $1$, $G'$ has no $k'$-clique; and, if $G$'s maximum clique has size $k$ then $G'$ has a unique $k'$-clique with probability at least $1/(4nk)$.

Solutions to Homework 1

2009-02-16T13:08:00.002-05:00

I have just added the solutions to Homework 1 to the course webpage. I am still marking the homeworks, but I hope to return them to you before the end of the week. Thanks for your patience!

UPDATE: I have removed the link to the solutions from the course webpage, but they are still available upon request. If you want a copy, please email me.

Homework 2

2009-02-16T09:03:00.002-05:00

Not that I imagine anyone worried about this, but for #4, it's okay to show completeness under poly-time many-one reductions. (I.e., don't bother about log-space reductions.)

A Quadratic Lower Bound for the Determinant and Permanent Problem

2009-02-14T16:52:00.017-05:00

Join me, fellow students, in a quest to discover Complexity-Theory's version of the 'Holy Grail': lower bounds on the size of circuits. This quest began at the 1970s, when the question of $P$ vs. $NP$ first arose. At those early ages, when people were naive, optimistic, and still new to the question $P \stackrel {?} {=} NP$, they sought to separate $NP$ from $P$. One direction, that initially seemed promising, was though circuit size. Clearly, $P \subset P/poly$. Furthermore, Karp showed that many functions belong to $NP$, and we know many functions with super-polynomial circuit-complexity do exist. So the hope was one would be able to show that some function in $NP$ must have large circuit-size, thus proving $P \neq NP$. In fact, one can show super-polynomial lower bound for some function in any level of the $PH$, and that will prove such a separation. And since Toda's theorem gives, $PH \subset P^{#P}$, the hope was that the Permanent, a $#P$-complete function, will have super-polynomial large circuits.

Recall that the Permanent is a function of numbers: $Perm = \sum_{\sigma \in S_n} \Pi_{i} M_{i, \sigma(i)}$, whereas circuits were defined over boolean values. So we introduce arithmetics circuits. Arithmetic circuits have $\oplus, \otimes$ gates (with fan-in 2), and $\ominus$ gates (with fan-in 1), representing the arithmetic $+, \times, -$ operations over some field $F$, and additionally uses constants in $F$. Clearly, every polynomial (and in particular the Permanent and the Determinant) can be represented as an arithmetic circuit, and furthermore, one can reduce any boolean circuit to an arithmetic circuit (representing NOT as $1 \ominus x$ and AND as $x\otimes y$). Using arithmetic circuits, Valiant defined in 1979 the arithmetics analogs of $P$ and $NP$:

Definition 1: A polynomial $p(\bar x)$ of degree $n^{O(1)}$ is in $VP$ if there exists a arithmetic circuit family of size $n^{O(1)}$ that computes it.
Definition 2: A polynomial $p(\bar x)$ of degree $n^{O(1)}$ is in $VNP$ if for some $m$ (polynomially bounded in $n$) there exists a family of polynomials $q_{n+m} \in VP$ s.t. $p(\bar x) = \sum_{\bar y \in \{0,1\}^m} q(\bar x, \bar y)$. For such $p$ and $q$, we say that $p$ is a projection of $q$.

Valiant showed that any polynomial in $VNP$ is a projection of the Permanent. He also showed a nice characterization of the functions of $VP$, which will take us back to linear algebra. Recall that an affine transformation of vector spaces is a combination of a linear transformation and a translation. We look at affine functions from the vector space $F[x_1, x_2, \ldots, x_d]$ of polynomials in $d$ variables over $F$, to the vector space $M_n(F)$ of all $n\times n$ matrices.

Definition 3: We say that a polynomial $p\in F[x_1, \ldots, x_d]$ has determinant complexity $n$ if any affine mapping $f:F[x_1, \ldots, x_d] \rightarrow M_n(F)$ s.t. $p \equiv \det\circ f$, must map $F[x_1, \ldots, x_d]$ to matrices of size $n\times n$ (or larger).

Valiant showed that if $p$ has circuit complexity $c$, then its determinant complexity is $\leq 2c$, so all functions in $VP$ have polynomially bounded determinant complexity. Hence, in order to separate $VNP$ from $VP$, one aspires to show that the determinant complexity of the Permanent is super-polynomial. Alas, until 2004, the best determinant-complexity lower bounds were linear in $n$. In 2004, Mignon and Ressayre showed a quadratic lower bound:

Theorem: If the characteristic of $F$ is $0$, then the determinant-complexity of the Permanent is at least $n^2/2$.

The proof of this theorem naturally involves some linear algebra, and requires the definition of a special linear operator. If $f:V\rightarrow F$ is a differentiable function, then we can define the tangent map $Tf: V\rightarrow V^*$, by: $Tf(v) = \langle \frac {\partial f}{\partial x_i}(v), \cdot \rangle$. I.e., we map every $v\in V$ to a linear functional $T_vf$, where $T_vf(w)$ is the scalar product of $\nabla f(v)$ and $w$. Using the tangent and the fact that the space of linear functionals is a vector space, we can now define a tangent to the tangent. Let $T^2f: V \rightarrow \textrm{Hom}(V, V^*)$ be defined by $T^2f(v) = (\cdot)^TH_f(v)(\cdot)$, where $H_f(v) = \left(\frac {\partial^2 f}{\partial x_i \partial x_j}(v)\right)_{i,j=1}$. I.e., we map every $v\in V$ to a bilinear function $A_v(\cdot, \cdot)$ where $A_v$ is constructed by the 2nd order partial derivatives of $f$ at $v$. Alternatively, one can think of $f(v)$ as a map $T_{v}^2f:V\rightarrow V^*$, where $(T_{v}^2f)(w)$ is the linear functional $\langle A_v w, \cdot\rangle$. Recall that any bilinear function (and in particular $A_v$) has a rank, which is the rank of the matrix.

Here is the proof of Mignon and Ressayre's theorem in a nutshell. Let $f:M_n(F)\rightarrow M_m(F)$ be an affine function s.t. $Perm_n = \det_m\circ f$. Then the following 3 claims hold:
Claim 1. $Perm_n$ is isomorphic to restricting $\det_m$ to the image of $f$, i.e. $Perm_n \simeq g$ where $g = \det_m |_{\textrm{Im}(f)}$. Since $g$ is a restriction of $\det_m$, we get $\textrm{rank}(T_{A}^{2} g) \leq \textrm{rank}(T_{A}^{2}\det_m)$.
Claim 2. There exists some non-invertible $A\in M_n(F)$, s.t. $T_{A}^{2} Perm_n$ has rank $= n^2$. (This is the most non-trivial part.)
Claim 3. For any non-invertible matrix $A$ it must hold that $\textrm{rank}(T_{A}^{2} \det_m) \leq 2m$.

Combining the 3 steps together, we deduce the inequalities $n^2 = \textrm{rank}(T_{A}^2Perm_n) = \textrm{rank}(T_A^2 g) \leq \textrm{rank}(T_A^2\det\_m) \leq 2m$

None of the proofs of 1,2 or 3 is hard, and they all boil down to looking at the matrix generated by the $T^2$ operator. If is our variable matrix, then we denote $P = Perm_n(X)$. For the minor $X_{i,j}$ (removing the $i$th row and the $j$th column of $X$), we denote $P_{i,j} = Perm_{n-1}(X_{i,j})$. For any $i\neq i', j\neq j'$, we denote $X_{\{i,i'\},\{j,j'\}}$ to be the minor of $X$ we get by removing both $i$ and $i'$ rows, and $j$ and $j'$ columns, and denote $P_{\{i,i'\},\{j,j'\}} = Perm_{n-2}(X_{\{i,i'\},\{j,j'\}})$. Then observe the following: $T^{2}Perm_n$ is the $n^2\times n^2$ matrix where for every $i \neq i'$, we have

Proving Claim 2 is the result of looking at . By sheer computation, they show that $T_A^{2}Perm_n$ is of the form , for two particular, invertible, $B$ and $C$, and show that this gives a $n^2 \times n^2$-matrix of full rank. We comment that the elements of $B$ and $C$ are multiplications of large factorials, so $B$ and $C$ are invertible because of the zero characteristic of $F$.

Proving Claim 3 uses a similar observation, based on the structure of $T^2$. If $X$ is a non-invertible matrix, then by changing basis, $X$ can be turned into $X'$, which is a diagonal matrix with some 0 entries on the main diagonal. $T_X^2\det$ and $T_{X'}^2\det$ will have the same rank. If we replace $Perm$ in $\det$, we get that $T_{X'}^2\det$ has the exact same structure as it had for the Permanent (replacing $P_{\{i,i'\},\{j,j'\}}$ with $D_{\{i,i'\},\{j,j'\}}$, the determinant of the same minor). However, since $X'$ is diagonal and non-invertible, then the determinant is $0$ for almost everywhere.

Proving Claim 1 boils down to showing the $f$ is injective, thus isomorphic over its image. If $f$ isn't injective, then exists a non-zero $v \in \textrm{Ker}(f)$. Hence, $\forall x, \forall \lambda \in F$ it holds that $Perm_n(x+\lambda v) = \det_m(f(x)+\lambda f(v)) = Perm_n(x)$, so the gradient of $Perm_n$ at $v$ must be $0$. Alternatively, every $T_xPerm_n$ maps $v$ into the $0$-functional. So for every $y$ it holds that $T_y^2Perm_n$ is a bilinear mapping, that maps every $x$ into a functional $\phi_x$ which is $0$ over $v$. Thus for every $y$ it holds that $T_y^2Perm_n$ is not of full rank. In particular, $T_A^2Perm_n$ has of rank strictly smaller than $n^2$, which contradicts Claim 2. The proof of the theorem is done.

SPOILER ALERT: The quest for lower bounds on circuits is (thus far) unsuccessful. Obviously, we still don't know how to show super-polynomial lower bounds on the determinant complexity of the Permanent. To this day, lower bounds are known only to a very restricted class of circuits (such as $AC^0$ or monotone circuits). In fact, Razborov and Rudich showed in 1995 that proving lower bounds using the currently known techniques is intrinsically difficult. However, there is some positive sign: in 2004, Kabanets and Impagliazzo showed that under the assumption $coRP = P$, either the Permanent or some function in $NEXP$ doesn't have polynomial-size circuits.

Combinatorial Complexity

2009-02-13T10:29:00.003-05:00

There is a certain broad area of complexity theory which does not have a proper name.

As far as it occurs to me at this instant, there are (at least) three big areas of complexity theory:

1. "Structural complexity theory". This refers to understanding the relationships between complexity classes, bounding and classifying time vs. space vs. randomness, understanding reductions, etc.

2. "Algorithmic complexity theory". I just made this name up, but I'm thinking here about the area of understanding the complexity of various specific problems; I think of proving NP-hardness results as falling into this area, so I would put inapproximability and PCPs into this category.

3. The mystery area I referred to at the beginning of this post. I guess my best attempt at naming this category would be either "Combinatorial complexity", or "Lower bounds". Here I mean the study of things like formula size/depth, constant-depth circuit size, branching program sizes, decision tree size, DNF size... roughly, the study of non-uniform classes of computation that are "small" enough that one can make reasonable progress on proving lower bounds.

The impetus for this post is to point you to a nice-looking graduate course on this 3rd area being taught by Rocco Servedio at Columbia this term. If the lecture notes continue, this should be a great resource for this huge area of complexity theory.

Lecture 9

2009-02-12T14:45:00.002-05:00

Topics covered in Lecture 9:

Randomized space: $RL \subseteq BPL \subseteq L^{3/2}$ (Saks-Zhou Theorem), USTCON $\in RL$. Circuits (as parallel computation): $NC$ vs. $P$, $NC^0$, $NC^1 \subseteq L \subseteq NL \subseteq NC^2$, matrix multiplication in $NC^1$, nonuniform $NC^1 = $ poly-size formulas. Branching programs: non-uniform $L = $ poly-size branching programs, small-width branching programs, statement of Barrington's Theorem (nonuniform $NC^1 = $ constant-width poly-size branching programs).

Office hours today

2009-02-10T08:46:00.003-05:00

Just a reminder that while class is canceled today, I will still be holding my office hours between 12:30pm and 1:30pm today, in Wean 3709.

Tuesday's class canceled

2009-02-09T12:01:00.000-05:00

Don't forget :)

Average Case Hardness

2009-02-06T19:04:00.009-05:00

In 1971, Stephen Cook showed that the boolean satisfiability problem is NP-Complete under polynomial time reductions. Soon afterward, Karp showed that many natural combinatorial problems (Vertex Cover, Clique, Hamiltonian Circuit etc..) were also NP-Complete. However, these results are often misinterpreted. Because most computer scientists believe $P \neq NP$ it is easy to assume that it is always hard to solve $3-SAT$. This is not true. In fact most randomly generated $3-SAT$ instances can be solved efficiently by algorithms like DPLL. Assuming that $P \neq NP$ then all we may conclude is that there is no efficient algorithm to solve these problems in the worst case. It is conceivable that $NP-Complete$ problems could still admit polynomial time algorithms for average instances.

Notice that problems which are not hard on average are poor candidates for cryptography and one-way functions. Protocols such as Diffie-Hellman would absolutely fail if it was easy to compute the discrete logarithm (given a multiplicative generator $g$ in a finite field mod p, and an integer $x$ compute $a$ such that $g^a \equiv x$ mod p) for average instances. Russel Impagliazzo (A Personal View of Average-Case Complexity) describes several possible worlds and their applications to cryptography.

World 1: Algorithmica $P = NP$ or $NP \subseteq BPP$. We all know that such a result would revolutionize computer science and machine learning. However, cryptography would be impossible in this world.

World 2: Heuristica $P \neq NP$, but, over any efficiently computable distribution, $NP-Complete$ problems are tractable on average. Intuitively, there are hard instances of $NP$ problems, but the problem of finding hard instances is itself intractable. Once again, crytography would most likely not be feasible in Heuristica because eavesdroppers could solve problems in a time comparable to the time it took to generate the problem.

World 3: Pessiland $P\neq NP$ AND there are problems which are hard in the average-case for efficiently computable distribution. However, there are no one way functions. This means that given $f(x)$ it is usually possible to find some $x'$ such that $f(x') = f(x)$ in time comparable to the ammount of time needed to compute $f(x)$. In Pessiland, it would be easy to generate hard instances of $NP$ problems, but there would be no way of generating hard (presolved) instances of $NP$ problems. Public key crytography would still not be possible. Thus, Average Case Hardness is a necessary (but not sufficient) condition for cryptography.

Worlds 4 and 5: Minicrypt and Cryptomania. In Cryptomania, almost any cryptographic task is possible. This is the world we typically assume we live in, because we assume protocols like RSA and Diffie-Hellman are secure. However, the only evidence that the Discrete Logarithm problem is hard is that fact that we don't know of an efficient algorithm to compute it. In reality, there is no theoretical reason why the problem should be hard. In fact, Peter Shor recently showed that Discrete Logarithms can be solved efficiently on a Quantum Computer.

Fortunately for cryptographers, the Discrete Logarithm problem is a beautiful example of self reducibility.

Lemma: Suppose that we had an algorithm $A$ which computes the the discrete logarithm efficiently (in time $poly(n)$, $n = \log p$) for at least $\frac{p}{poly(n)}$ values of $x$, then there is an efficient ZPP algorithm $A'$ to compute the discrete logarithm efficiently.

Proof (Sketch): We can pick $k$ such that $A$ solves at least $\frac{p}{n^k}$ instances in time $O(n^k)$, let $m = n^{2k}$.
Input: Generator g, Integer x, Prime p
Output: $a$ such that $g^a \equiv x$ mod p or FAIL

For $i = 1...m$
---$a_i \leftarrow Unif(0,p-2)$
--- $x_i = g^{a_i}$ mod p
---// Number Theory Fact: this is equivalent to picking $x_i\leftarrow Unif(1,...,p-2)$

---If $A(g,x\times x_i,p)$ returns $a'$ in $n^k$ steps then
------// Now we know the answer due to number theory:
------// $x \times x_i \equiv g^{a_i} g^{a}$ mod p
------// $ g^{a_i} g^{a} = g^{a_i + a} \equiv g^{a'} $ mod p
------// $a = a' - a_i$
------return $a = a' - a_i$
Output Failed

It is not too hard to verify that the algorithm takes polynomial time and with high probability computes the correct answer. QED

I am unaware of any NP-Complete problems which are self reducible in a similar sense as the Discrete Logarithm problem. If such a self reduction was found I suspect that this would be a very interesting result in complexity theory.

A more common approach to the problem of defining average case hardness is that of Leonid Levin. Levin (Average Case Complete Problems) defines the notion of a random NP problem and a complete random NP problem. His definitions are tedious and hard to follow at times, but they are worth the time and energy to understand.

Definition: A random problem is a pair $(\mu, R)$ where $R \subset \mathbb{N}^2$ is an instance witness and $\mu: \mathbb{N} \rightarrow [0,1]$ is a probability distribution function.

A problem instance is an integer $x$ is the problem instance. $x \in L$ if and only if there is $y$ such that $(x,y) \in R$. The a probability distribution function $\mu(x)$ gives the probability of all problem instances which do not exceed $x$.

Notation: $\mu'(x) = \mu(x)-\mu(x-1)$ is the probability density function.

Also, by convention

$|x| = \lceil \log x \rceil$

$R(x,y)$ is true if and only if $(x,y) \in R$.

Definition: A random problem is in NP if both $R$ and $\mu$ are both computable in polynomial time. We call such a problem a random NP Problem.

In other words, given a tuple $(x,y)$ (a problem instance and a verifier) we can decide whether or not $(x,y) \in R$ in polynomial time in $|x|$. We can also sample from the distribution $\mu$ in polynomial time.

Definition: A random problem $(\mu, R)$ is polynomial on average if there is a Turing Machine $M$, which runs in time $t(x)^k$ such that:

$M(x) \leftrightarrow \exists y R(x,y)$
$\Sigma_{x=1}^\infty \mu'(x) \frac{t(x)}{|x|}$ converges.

The first condition guarantees that $M$ actually decides the problem. The second condition guarantees that the Turing Machine must run quickly on average instances sampled from our distribution $\mu$.

Definition: We say that the probability distribution function $\mu_1$ dominates $\mu$ if $\exists k \forall x \frac{\mu'(x)}{\mu_1(x)} \leq |x|^k$. In such a case we write $\mu \prec \mu_1$.

Intuitively, this definition guarantees that all of the 'likely' instances of $\mu$ are also the 'likely' inputs of $\mu_1$

We are finally ready to define the notion of reduction between random NP problems.

Definition:A polynomial time computable function $f$ reduces a random NP problem $(\mu_1, R_1)$ to another random NP problem $(f(\mu_2), R_2)$ if the following conditions hold:

$f(\mu_2)(x) = \Sigma_{f(y) \leq x} \mu'(y)$
$\mu_1 \prec \mu_2$
$\exists y_1 R(x,y_1) \leftrightarrow \exists y_2 R(f(x),y_2)$

Condition 1 and 2 say that likely instances of problem 1 are mapped to likely instances of problem 2. Condition 3 guarantees that yes instances of problem 1 are mapped to yes instances problem (also no instances are mapped to no instances).

Levin shows that these reductions are closed under composition. If $A(x)$ is an algorithm that is fast on average for $(f(\mu_2), R_2)$ then $A(f(x))$ runs at most polynomially slower for $(\mu_1, R_1)$.

Definition: A random NP problem is complete if every random NP problem is reducible to it.

Levin proved that Tiling is an NP-complete random problem. Other natural combinatorial problems such as Graph Coloring and Matrix Decomposition have also been shown to be NP-complete random problems.

Lecture 8

2009-02-05T15:57:00.003-05:00

Today we proved the following five theorems:

1. $NSPACE(s(n)) \subseteq DTIME(2^{O(s(n))}).

2. ST-Connectivity is $NL$-complete.

3. Savitch's Theorem: $NSPACE(s(n)) \subseteq DSPACE(s(n)^2)$.

4. TQBF is $PSPACE$-complete.

5. Immerman-Szelepcsényi Theorem: $NSPACE(s(n)) \subseteq coNSPACE(s(n))$.

Here $s(n) \geq \log n$ is a space-constructible bound. (I believe that for most of these, if you want to get really really technical, you can even drop space-constructibility :)

Lecture 7

2009-02-03T15:28:00.002-05:00

Today we covered: Permanent is #P-complete (statement); Toda's Theorem; statements of basic space theorems (non-deterministic space $s$ in deterministic $2^{O(s)}$ time, Savitch's Theorem, Immerman-Szelepcsenyi Theorem).

Homework 2

2009-02-02T20:49:00.001-05:00

Homework 2 has been posted slightly early for your enjoyment! It's linked to on the course home page. Due Feb. 17.

I assume you all saw the hints for Homework 1 in the comments to the previous post.

Misc. Definitions

2009-01-31T12:55:00.006-05:00

In the lectures we've skipped some technical definitions so as to not get bogged down. But these are good things to know; they'll come up again and again if you study Complexity Theory.

1. Constructibility:A function $f : \mathbb{N} \to \mathbb{N}$ is time-constructible if there is a DTM which, on input $1^n$, outputs $1^{f(n)}$ in time $O(f(n))$. It is space-constructible if outputting $1^{f(n)}$ is doable in space exactly $f(n)$. As mentioned in class, we also invariably restrict attention to time bounds that are at least $n$ and space bounds that are at least $\log n$. In this case, every non-ridiculous time bound you would ever use is time-constructible, and similarly for space. The Time and Space Hierarchy Theorems require constructibility.

2. Promise problems: This is a generalization of a "language". A promise problem is a pair $(Y,N)$ of disjoint subsets of $\{0,1\}^*$. A TM "decides" the promise problem if it accepts all strings in $Y$ and rejects all strings in $N$. Note that a promise promise is a language iff $Y \cup N = \{0,1\}^*$. The name "promise" here refers to the fact that you can think of the TM as being "promised" that the input string is always in $Y \cup N$. Generally speaking, if there is an "efficient" algorithm for checking if $x \in Y \cup N$ then the promise problem is not much different from a language (one can put the "easily decidable" strings in $\{0,1\}^* \setminus (Y \cup N)$ into either $Y$ or $N$, say).

3. Syntactic/semantic classes: This is not a 100% rigorous definition; we illustrate it via examples. A complexity class defined via time-bounded machines (TMs, NTMs, counting TMs, etc.) is said to be syntactic if there is an "effective enumeration" of the machines defining the class. For example, if $f(n)$ is a time-constructible function, the class $DTIME(f(n))$ is a syntactic class, since you can effectively enumerate the TMs running in time at most $O(f(n))$. Similarly for $NTIME(f(n))$ -- the NTMs running in time at most $O(f(n))$ are effectively enumerable. Classes like $P$, $NP$, $PSPACE$ are "syntactic". Syntactic class have Hierarchy Theorems and they also tend to have "generic complete problems". A semantic class is one which is not syntactic; generally, this means it is defined by a machine class "with a promise". The classic example is $BPP$: Here there is no way to effectively enumerate randomized TMs with the property that for each $x$ they either accept with probability at least $3/4$ or reject with probability at least $3/4$. (Indeed, checking whether an RTM has this property is undecidable.) Instead, languages in $BPP$ are defined only by machines $M$ that satisfy the promise "$M$ is a BPP machine".

4. Promise classes: For semantic classes like $RP$ and $BPP$ there is an associated "promise class" of promise problems, denoted $prRP$, $prBPP$, etc. For example, $prRP$ is the class of all promise problems $(Y,N)$ such that there is a polynomial-time RTM which accepts all strings $x \in Y$ with probability at least $1/2$ and accepts all strings $x \in N$ with probability $0$. The RTM may have any behavior on strings not in $Y \cup N$.

5. Uniformity: Again, this is not 100% well-defined, but a complexity class is said to be uniform if it is defined by one machine that operates for all input lengths. It is said to be nonuniform if there is a different machine defining it for each input lengths. Roughly, classes with TM-based definitions are "uniform", and classes with circuit-based definitions are "nonuniform".

6. Reductions: We've talked about how it is important to specify the complexity of reductions (poly-time, log-space, even $AC^0$), but there's also another distinction. A many-one (or Karp) reduction $R$ from $L$ to $L'$ is one which maps $x$ to $R(x)$ such that $x \in L \iff R(x) \in L'$. An oracle (or Cook) reduction $R$ is one which solves $L$ by using an algorithm for $L'$ as an oracle. Having a Karp reduction is "stronger" than having a Cook reduction, and we generally define completeness for complexity classes in terms of having a Karp reduction because we can: e.g., all textbook $NP$-completeness reductions are many-one. But sometimes it's better to define completeness in terms of Cook reductions; for example, as we saw in class with $\#\P$.

7. -hard: For a class $C$ we said that $L$ is $C$-complete if: (a) $L \in C$; (b) every problem in $C$ reduces to $L$. We say that $L$ is $C$-hard when (b) holds.

8. Self-reducibility: A language $L$ is said to be downward self-reducible if one can decide $x \in L$ efficiently using an oracle for $L$ on instances of size $< |x|$. This sounds funny, but it makes sense. The classic example is $SAT$: If you have a black box which can solve any $SAT$ instance of size at most $n$, you can use it to efficiently solve any instance of size at most $n+1$; you use the classic trick of setting $x_1$ to $0$ and checking satisfiability, and setting $x_1$ to $1$ and checking satisfiability. A language $L$ is said to be randomly self-reducible if one can decide $x \in L$ efficiently with high probability using an oracle for $L$ which works with high probability on randomly chosen instances. An example (as we'll see at some point in class) is the 0-1 PERMANENT problem: If you can solve randomly chosen 0-1 PERMANENT instances with high probability, you can actually solve all 0-1 PERMANENT instances with high probability.

9. Padding: Padding is the general idea of taking a language $L$ and considering the language $L' = \{ x\#1^{f(|x|)} : x \in L \}$, where $f$ is some fast-growing functions. I.e., it's the idea of "padding" all inputs with a large number of "blanks". It is used for classic upward collapse results such as "$NP = P \Rightarrow NEXP = EXP$". To see this, suppose $NP = P$. Let $L$ be a language in $NEXP$; say it's in $NTIME(2^{n^c})$. Let $L'$ be the padded version of $L$, where $f(x) = 2^{n^c}$. Now it's easy to see that $L'$ is in $NP$: just run the $NTIME(2^{n^c})$ algorithm for $L$, which is now "polynomial time" because the input length in $L'$ has been padded. Hence by assumption, $L'$ is in $P$. But then clearly $L$ is in $EXP$: to decide $x \in L$ in exponential time, just pad $x$ and then run the $P$-algorithm for $L'$.

10. Succinctness: This is the spiritual opposite of padding. For some languages $L$, there is a version $L'$ where the inputs for $L$ are succinctly described. The classic example is where $L$ is CIRCUIT-VALUE, and $L'$ is SUCCINCT-CIRCUIT-VALUE. Here, an input $E$ for $L'$ is a "succinct encoding" of an (exponentially large) circuit $C$: The input $E$ itself is a circuit, which on input $i$ "outputs the $i$th gate in $C$" -- its type (AND, OR, NOT, input, output), and the indices of the gates that feed into it. Typically, the "succinct" version of a complete language is itself complete for the "exponentially larger" class. For example, you can check that since CIRCUIT-VALUE is $P$-complete, SUCCINCT-CIRCUIT-VALUE is $EXP$-complete. And since SAT is $NP$-complete, SUCCINCT-SAT (where the input is a circuit describing an exponentially long formula) is $NEXP$-complete.

Partial Derandomization of Polynomial Identity Checking (II)

2009-01-30T16:06:00.020-05:00

Given the blackbox model, a direct way to test whether there's a zero polynomial inside is just to try (maybe a lot of) inputs. Then if it is a zero polynomial you'll always get the right answer; but if it isn't, you need to have a reasonable bound on the number of tests you need to make. Hence the key observation that makes an efficient randomized algorithm possible is the following:

(Schwartz-Zippel) Let $P(x_1,...,x_n)\in F[x_1,...,x_n]$ be a nonzero polynomial and $d=\sum d_i$. Pick points in some set $S^n\subseteq\bar F^n$ ($\bar F$ denotes the algebraic closure of $F$, which is just a technicality, since sometimes you need to go into extensions of $F$) and feed them to the blackbox, then you get at most $d|S|^{n-1}$ zeros as output.

An inductive argument (on the number of variables) easily shows its validity. This is saying: if you choose a reasonably big $S$, say $|S|>cd$ for some constant $c$, then the possibility of getting zero as output is at most $c^{-1}$. The number of random bits used is $n\log cd$. Evidently the algorithm can be boosted to arbitrary precision at the cost of using more random bits (bigger $S$ or repetitive runs).

This is a practical enough algorithm, but can we possibly have some magic inputs to try on the blackboxes, so that zero polynomials can be deterministically detected from the output? Consider, for example, when you know the polynomial only has integer coefficients, maybe you can feed it with some numbers whose weirdness will not be affected by the integer coefficients, and the whole polynomial evaluates to zero iff all the coefficients are zero! This is the idea of Chen-Kao: use irrational numbers.

Suppose we feed $P(x_1,...,x_n)$ (which contains only integer coefficients) with an input $(\pi_1,...,\pi_n)$ satisfying $\pi_i=\sum_{j=1}^{\log (d_i+1)} \sqrt p_{ij}$ where $p_{ij}$s are arbitrary (different) prime numbers. Then, $P(x_1,...,x_n)\neq 0$ iff $P(\pi_1,...,\pi_n)\neq 0$. (Proof: In the inductive step, first evaluate $P$ on $\pi_1,...,\pi_{n-1}$, which results in a univariate polynomial $P'(x_n)$, with coefficients in the extension field $F'=F[\pi_1,...,\pi_{n-1}]$. But notice that the dimension of $F'[\pi_n]$ over $F'$ is $2^{\log(d_n+1)}$, which is bigger than the degree $d_n$, implying that $\pi_n$ can never be a root of $P'(x_n)$.)

But isn't that saying we have a deterministic algorithm already? No - you can never evaluate irrational numbers at infinite precision! We can only truncate the binary expansion of the irrationals at certain decimal positions, say $l$, and randomly choose the signs of $p_{ij}$s -the error probability then drops proportionally to $l^{-1}$ (calculation is needed and contained in Chen-Kao's original paper (Lemma2.2)). Rethink about this: the precision of the algorithm depends on $l$, which is not in the random bits! So arbitrarily precision can be achieved without changing the number of random bits (which is $\sum_{i=1}^n \log (d_i+1)$), the number of different signs we picked).

Chen-Kao's ingenious method has one drawback - it's dependent on the properties of numbers (coefficients need to be integers; prime numbers need to exist - not the case for, say, finite fields). This is where Lewin-Vadhan came in, with an abstraction of the method applicable to arbitrary field.

The idea of Lewin-Vadhan is to find a substitute notion of irrationals in arbitrary fields. Note that the underlying strategy of Chen-Kao is to find some evaluation points that are provably non-vanishable for nonzero polynomials. Lewin-Vadhan carefully showed that the following analogy works: let prime numbers be abstracted to irreducible polynomials in $F[x]$; binary expansion of the square roots be abstracted to power series (in $F[[x]]$) of the square roots of the irreducible polynomials, which are approximated by truncating modulo some $x^l$.

For the whole scheme to work, two things need to be affirmed:

1. The irreducible polynomials indeed work as prime numbers, i.e., when any nonzero polynomials $P(x_1,...,x_n)$, let $\pi_i=\sum_{j=1}^{\log (d_i+1)} \sqrt f_{ij}$ ($f_{ij}$s are now univariate polynomials) then $P(\pi_1,...,\pi_n)$ is never zero (in $F[x]$!). The proof for this goes similarly as the simpler proof above for prime numbers.

2. The irreducible polynomials that have square root expansions (this is not always the case since the constant term has to be quadratic residue) need to be easy enough to find. In fact, it is proved using Hensel's Lemma that polynomials have a power series expansion in $F[[x]]$ iff the constant term is a quadratic residue (except for finite fields of characteristic 2, which are handled independently). Also, the number of irreducible polynomials in $F[x]$ of degree less than $n$ is at least $(|F|^n-1)/n$. Please refer to the original paper for the full proofs (actually the extended version of it).

Finally, the approximation using power series needs to give the desirable error probability. For any given error $\epsilon$, the power series can be truncated at $x^l$ where $l=0.5 \epsilon^{-1} d \max (\deg (f_{ij}))$. This is technically more complicated than just probability calculation as for the prime number case. But, (very "luckily", which is a word used multiple times in the paper), everything works out. The random bits are, still, only used for choosing signs of $\sqrt f_{ij}$, and the number of them is $\sum_i\log (d_i+1)$.

In a sense, the problem is solved after Lewin-Vadhan's construction. It is provable that under the given model (i.e., only $n$ and $d_i$ are known as parameters), the number of random bits used is already optimal - since any deterministic algorithm requests at least $\prod_i (d_i+1)$ queries to decide the polynomial (if the number of queries is smaller than $\prod_i (d_i+1)$ which is the number of possible monomials, you'll get polynomials indistinguishable from the zero polynomial), any random algorithm necessarily needs $r=(1-O(1))\sum_i \log(d_i+1)$ bits (a trivial derandomization is to try out all the $2^r$ possibilities which shouldn't be smaller than the deterministic queries needed).

This should be a good success story in randomized algorithm design, had there not been the tragic death of Daniel Lewin on 9-11, 2001.

Lecture 6

2009-01-29T22:42:00.003-05:00

In this class we finished the proof of the Approximate Counting/Sampling and the Bshouty-Cleve-Gavalda-Kannan-Tamon Theorem. We also introduced #P.

Partial Derandomization of Polynomial Identity Checking (I)

2009-01-29T21:48:00.009-05:00

(To Ryan and Venkat: my post is getting too long so I'm breaking it into two (hopefully not three) parts and the second part will come out tomorrow...)

Checking multivariate polynomial identities is a problem central to algorithm design and complexity theory.

I didn't inline a formal definition in the previous sentence, because there's a catch in defining the problem. A polynomial $P(x_1,...,x_n)$ (say, in $F[x_1,...,x_n]$ for some field $F$) can be viewed as, at least, two things: syntactically, it is just a formal expression recursively built up from variables, coefficients from $F$, arithmetic operators and parentheses; semantically, it is a function from $F^n$ to $F$. Correspondingly, when we say a polynomial is identical to zero, we can have two different meanings:

1. It is indeed the zero element in the ring $F[x_1,...,x_n]$. Namely, when written in sparse form (that is, when parentheses are no longer needed), all coefficients turn out to be zero.
2. It is a constant function that maps all the points in $F^n$ to $0\in F$.

The two definitions coincide only over an infinite field $F$ (reason: a syntactically non-zero polynomial can not vanish on all the points in $F^n$ (but note that it can definitely vanish on an infinite number of points, some online notes are wrong about this), since you can fix values to $n-1$ variables and get a univariate polynomial which can only have finitely many roots (less or equal than its degree). For a finite field of size $q$, the polynomial $(x^q-x)\in F[x]$ vanishes on every point in $F$ (reason: the nonzero elements are in a cyclic group under multiplication, obeying Lagrange's theorem).

We fix definition #1. If you need, two reasons can be provided:
1. For definition #2, the problem is coNP-complete over finite fields. It's in coNP since you can decide its complement language by checking certificates for their nonzero-ness. It's complete since Boolean tautologies are just polynomials that are always evaluated to 1 over the finite field of size 2.
2. Applications: Biparitite matching, IP=PSPACE, etc.

Now the problem is clear: given a multivariate polynomial $P(x_1,...,x_n)\in F[x_1,...,x_n]$, we would like to decide whether $P(x_1,...,x_n)=0\in F[x_1,...,x_n]$. Next we need to decide the description format of the input polynomials. In the trivial case, polynomials can be given in sparse form and you just take a look at the coefficients. Of course that shouldn't be what we are concerned about here, since expanding polynomials easily takes exponential time. Rather, we take the black-box model of the polynomials, which is just something that efficiently evaluates the polynomial given any point in $F^n$. The only parameters of the polynomial that we have access are: the number of variables $n$, and the highest degree on each variable $d_i, i\in \{1,...,n\}$. Note that if we are allowed to know other parameters, the problem can be different.

So (Too) much for the preparation. The problem was given a randomized polynomial time algorithm first by Schwartz-Zippel. Twenty years after that, Chen-Kao gave a partial derandomization of Schwartz-Zippel's algorithm (i.e., reduced the number of random bits needed in the algorithm) for polynomials with integer coefficients. Later, Lewin-Vadhan, which will be the focus of (the coming second part of) my post, generalized Chen-Kao's method to the problem in its full generality, and proved the optimality of the number of random bits used under the given model (blackbox, same parameters). As mentioned in class, whether the algorithm can be fully derandomized is open.

Trivial lemma => powerful circuit lower bounds

2009-01-28T13:27:00.005-05:00

Remember the very first lemma we used in the proof of the Valiant-Vazirani Theorem? Though simple, it's actually extremely useful. Here is an equivalent way to state it:

Lemma: There is a degree-2 "randomized $F_2$-polynomial" for the OR function. Precisely, the degree-2 polynomial

$p(x,r) = \sum_{i=1}^n r_i x_i$ mod 2

computes the function OR($x$) with one-sided error $1/2$ when its "random bits" $r$ are chosen uniformly.

It's an easy exercise to show from this that there is a degree-$O(\log n)$ "randomized $F_2$-polynomial" which computes the OR function with one-sided error $1/n^{100}$. Of course, there is similarly one for AND. By combining these, you can get a polylog$(n)$-degree randomized polynomial for any "$AC^0$" circuit.

Definition: A circuit is in "$AC^0$" if it is of polynomial size and constant depth. Here we allow AND and OR gates of unbounded fan-in (otherwise you couldn't even compute the AND of all bits in constant depth!).

But for some basic functions -- e.g., the function

$f(x_1, ... , x_n) = \sum_{i=1}^n x_i$ mod 3

-- it's not too hard to show that they can't have a polylog$(n)$-degree randomized polynomial. Hence we get a rare circuit lower bound: this $f$ cannot be computed in $AC^0$.

We will probably do this more explicitly later in the course. This idea is also used crucially in Braverman's remarkable paper, discussed in an earlier blog post.

Lecture 5

2009-01-27T14:57:00.000-05:00

The topics in Lecture 5 were: Why having an algorithm for SAT is different from having an oracle for SAT; the Valiant-Vazirani theorem ("Unique-SAT $\in P \Rightarrow$ SAT $\in RP$"); pairwise-independent hash families; most of the Approximate Counting Theorem.

If pigs could whistle, then horses could fly

2009-01-26T13:12:00.005-05:00

Sometimes a result in Complexity Theory is described (or disparaged?) with the phrase, "If pigs could whistle, then horses could fly". (I can't figure out how this got started; the earliest online example I could find was from Dan Spielman's lecture notes but I'm pretty sure I heard it well before this. Can someone antedate this reference?)

The meaning is that the result is of the form "(something probably false) implies (something probably false)". An example is the Karp-Lipton Theorem:

$NP \subseteq P/poly \Rightarrow$ the Hierarchy collapses.

If you really believe "$NP \subseteq P/poly$" is false, then in some sense the statement is vacuous. If you somehow intuitively feel that "the Hierarchy collapses" is even more probably false than "$NP \subseteq P/poly$" then the statement has value; its contrapositive is that "assuming the Hierarchy doesn't collapse" (which you strongly believe), $NP$ does not have polynomial-size circuits (which maybe you believed less)?

In this particular case, I don't know what your intuition is, but I suppose mine is that I feel $NP \subseteq P/poly$ is more false-seeming than that the Hierarchy collapse. So does the Karp-Lipton tell me anything?! Or is it just, "If pigs could whistle, then horses could fly"?

In this case, the theorem is very meaningful -- but for another reason. As Scott Aaronson once wrote in a blog comment on this subject, "It gives one of the few known bridges between [TM-based complexity classes] and [circuits] -- and thereby lets us prove interesting circuit lower bounds." By this he means the fact that $\Sigma_2$ does not have polynomial-size circuits -- Problem 4c on your homework!

The many characterizations of NP

2009-01-23T21:10:00.009-05:00

When I first heard of nondeterministic Turing machines and the complexity class NP, I thought the idea was somewhat contrived. Alan Turing’s original work laid out a computational model which Turing believed captured all of the important artifacts of a person performing a computation. If you want to take a look at Turing’s paper (it’s a good read!), you can find a copy of it here: http://www.thocp.net/biographies/papers/turing_oncomputablenumbers_1936.pdf. Today, we are taught to think of Turing machines like specific computer programs or computers (universal TMs). Most programmers would be aghast at the thought of a computer being able to guess inputs to functions or take different courses of action in the middle of a computation. It turns out that despite some of the strangeness of thinking about nondeterministic machines, the complexity class NP has many interesting equivalent definitions without the use of nondeterminism. The goal of this blog post is to explore these various equivalences in more detail.

We first saw robustness in our definitions when we showed that polytime multi-tape TMs have equivalent polytime single-tape TMs. Thus, the class P is robust in the sense that it doesn’t matter whether we use a single or multi-tape TM to solve problems in P, EXP, etc. In a somewhat similar looking result, Savatch’s theorem relates the amount of space required by a deterministic simulation of a nondeterministic machine as follows: $NSPACE(f(n)) \subseteq DSPACE(f^2(n))$. Hence, the class PSPACE is robust to whether we use deterministic or nondeterministic machines. In the area of low space complexity, we still don’t know whether L = NL. However, Immerman and Szelepcsenyi independently showed that NL = co-NL. We’ll return back to this later when we mention descriptive complexity theory.

Of course, one of the most important question about nondeterministic TMs is whether P = NP. While it’s straightforward to go about simulating a nondeterministic TM using only a quadratic space blowup, it’s not at all clear whether one can avoid doing an exhaustive search of computation paths in the simulation. Steve Cook has an excellent overview of the P vs. NP problem on the Clay Mathematics website that you should check out here.Overall, the study of complexity started early on when von Neumann, Cobham and Edmonds took interest in problems which have polytime solutions. Over time, there have been proofs that certain theories are difficult to decide (look at Presberger arithmetic or type-checking in ML for example). Whether we should consider polynomial run time feasible is questionable (consider an O(n^100) algorithm and doubling the input size). Alas, this argument seems like one best left to people actually implementing systems, where constant factors matter. :-)

The P = NP is important from a theoretical and practical viewpoint. It deserves a better response than "not unless P = 0 or N = 1." I want to argue why NP is 'natural' in the sense that even without strange nondeterministic machines we still define NP in many different ways. So with that, let's take a look at a few different characterizations of NP!

Characterization 1: You only need to easily verify a 'solution'.

As we saw in class, NP is exactly those languages for which there’s a polynomial time ‘verifier’ V for the language. We showed that for a language L in NP there’s some polytime TM V(.,.) and constant c such that V verifies x’s membership in L given the existence of some certificate string y, where |y| < |x|^c. If you don't have such a certificate, then x isn't in L. The most basic and intuitive example we saw was SAT: given a propositional formula and truth assignment, you can easily check whether the assignment satisfies the formula. If there is no such satisfying assignment, then the formula is not in SAT. Sometimes it’s much more tangible to work with this characterization of NP- come up with an appropriate notion of a certificate and simply write a reasonably fast program which checks certificate validity. Furthermore, this definition of NP doesn’t require the machinery of nondeterministic TMs. A consequence of P = NP and this characterization of NP would be that finding solutions (certificates) is no harder (up to polynomial factors) than verifying solutions. Alternatively, if P != NP, then there is some language for which it’s hard to find solutions. As SAT is NP-complete, SAT would need to be one such difficult language and we couldn't quickly find satisfying assignments for Boolean formulas.

Characterization 2: Probabilistic Checkable Proofs

For the sake of this blog post, I'll provide a high-level view of PCPs without going into details about the formalities. Arora’s and Barak’s complexity book provide nice coverage of interactive proof systems and PCPs. In the case of SAT we can determine whether a formula A is in SAT by verifying some satisfying assignment to the variables. An incredible result known as the PCP Theorem tells us that each NP languages has a probabilistic certificate verifier which only looks at a constant number of bits in the certificate w, and is allowed O(log(n)) random bits to perform the check. Like we did in the case of BPP and RP, we'll look at a probability distribution over random input strings r. In the case that the certificate is valid, the verifier must always accept (x,w,r). In the case that the certificate is actually incorrect, the probability that the verifier incorrectly accepts (x,w,r) must be less than 1 /2.

What implications does this have in practice? One example is that you can be arbitrarily certain of the correctness of a supposed satisfying assignment A to a 3-CNF formula Phi while checking only a constant number of variable assignments and using a small number of random bits.M athematicians trying to verify that a long (but still polynomial length) proof of a theorem is correct can do so with great certainty without reading the whole thing! Since theorems with polynomial length proofs are a language in NP, reviewers would only need to spot check the proof in order to confident of the proof’s correctness. That sure cuts down on the amount of work a reviewer has to perform, but surely doesn’t satisfy a mathematician’s desire for 100% certainty that a proof holds. The PCP theorem provides an interesting probabilistic definition for NP.

Characterization 3: Descriptive Complexity Theory and doing away with machines

Up to this point we’ve focused on looking at NP languages in terms of computational models. So far we’ve seen two verifier-based approaches, but what about a view of NP which makes no reference to Turing at all? Immerman’s “Descriptive Complexity: a Logician’s Approach to Computation” provides a nice introduction to the topic of descriptive complexity. In general, NP languages characterize some property of strings. For example, the language SAT contains those formulas which satisfy the property “This formula is satisfiable.” Descriptive complexity theory attempts to characterize the hardness of defining these properties in a logical framework.

Immerman says that “we view inputs as finite logical structures, e.g., a binary string w” which can be encoded as an element in structure that encodes all n-bit strings, functions to test whether a particular bit i is set, and an order relation over all of the binary strings. We've done this sort of thing before when arguing that we only need to consider TMs over the alphabet {0,1}. Let’s look at how we can express the language of 3-colorable graphs in this context using these structures, unary ‘color’ relations, a binary edge relation, and existential quantification. The structure contains an encoding of the graph vertices and edges, and the relationship Edge(.,.) determines whether two vertices are adjacent or not. A graph is 3-colorable iff there’s an assignment of one of three colors to every vertex and no two adjacent vertices are colored the same. Logically, this is expressed as

Exists unary relations R, G, and B such that for all x [ (R(x) or G(x) or B(x)) and [for all y Edge(x,y) implies {not (R(x) and R(y)) and not (G(x) and G(y)) and not (B(x) and B(y)) } ]]

The unary relationships assign colors to all of the vertices and the second part makes sure that no two adjacent vertices are colored the same. This formula is an example of a second order existential formula; a 2nd order existential formula begins with a second order existential quantification and the rest of the formula is a first order statement. These formulas look like “Exists relations R, S, T, … such that (first order formula over the universe).” The first result in descriptive complexity theory happened when Ronald Fagin showed that a set of structures (collections of binary strings) Q is in NP if and only if Q is the set of structures which satisfy some second order existential formula. Notice that this definition makes no mention of Turing machines *or* time! Earlier I made a comment about NL = co-NL, and I will finish commenting on it here. Immerman proves that NL is equivalent to “the set of problems describable in first-order logic with the addition of a transitive closure operation.” After playing around with the logic and properties of transitive closure operations, Immerman is able to show that for s(n) >= log(n), NSPACE[s(n)] is closed under complement. Describing complexity classes in terms of logical formulas provides a different perspective on computation and introduces an interesting set of tools for approaching various problems in complexity theory.

Hopefully this post gives you some perspective about all kinds of interesting characterizations of NP. Based on some of the logic I've studied, I'm interested in looking more at descriptive complexity theory. If you're interested in exploring this approach to complexity theory in more detail, please get in touch with me.

Note to future bloggers: DO NOT write your post in MS Word and copy it into the rich text edit box. It ends up copying over a bunch of wacky HTML that you have to edit out by hand in order to get your post to work... :-(

Polylog-wise independence fools constant-depth circuits

2009-01-23T09:46:00.002-05:00

Well, the big buzz around the blogosphere, occasioned by an anonymous comment on Luca's blog Wednesday night is a new preprint by the mighty Mark Braverman, currently a postdoc at Microsoft Research, soon a faculty member at the University of Toronto.

Mark paper proves a conjecture of Linial and Nisan from 1990; namely, that no $n$-input circuit with constant depth and polynomial size can distinguish truly random inputs from inputs that are $k$-wise independent for $k = polylog(n)$.

The preprint is discussed in some detail on Scott's blog and also on Lance/Bill's blog.

There is a good chance we'll have the tools to cover this paper toward the end of the course. :)

Lecture 4

2009-01-22T14:41:00.003-05:00

The topics covered in Lecture 4 were: Adleman's Theorem, $BPP \in P/poly$; Poly-time hierarchy; Min-Circuit; Infinite Hierarchy Assumption, Collapse Lemma; $PSPACE =$ Alternating Poly Time statement; Oracles, $\Sigma_2 = NP^{NP}$, etc; Sipser-Gacs-Lautemann Theorem, $BPP \in \Sigma_2$; Karp-Lipton(-Sipser) Theorem, $NP \subseteq P/poly \Rightarrow PH = \Sigma_2$; Valiant-Vazirani Theorem statement, UniqueSat $\in P \Rightarrow NP = RP$.

Lecture 3

2009-01-20T20:51:00.001-05:00

Lecture 3 covered the following topics: NP vs. coNP and the theme of proof complexity; nondeterministic time hierarchy via lazy diagonalization; Ladner's Theorem statement; Randomized TMs, BPP, RP, ZPP; problems in BPP but not known to be in P (Berlekamp's algorithm vs. factoring cubics mod p) and primality; lack of hierarchy and complete problems for BPP; polynomial identity testing; error amplification for BPP (and statement about randomness reduction); poly-size circuit families; Adleman's Theorem BPP in P/poly.

Tentative syllabus

2009-01-15T22:27:00.002-05:00

Here is a very rough guideline for the list of topics we might cover in the course. This is almost certainly an ambitious plan and is subject to change based on time constraints. We will probably only be able to discuss a subset of these topics, and may not cover the topics necessarily in the order listed.

-------------------

Introducton: the big questions, Turing machines, Basic time and space
classes (P,NP,L,PSPACE,NL), Universal Turing machines, Hierarchy
theorems, Nondeterminism, NP-completeness and Cook-Levin theorem,
P-completeness;

Randomized complexity classes, Polynomial identity testing, Polynomial
time hierarchy, Non-uniform (circuit) classes, Karp-Lipton theorem.

Complexity of Unique-SAT, Approximate counting in the
hierarchy, Exact learning of circuits with oracles.

Space complexity: PSPACE and NL-completeness, Savitch's theorem, NL =
coNL, Relationship to parallel computation and NC circuit classes.

Counting classes, #P-completeness, The power of counting (Toda's
theorem).

The power of interaction: Graph nonisomorphism protocoal, Interactive
proofs for #SAT, IP=PSPACE, coNP unlikely to have short interactive
proofs.

Lower bounds and concrete complexity:
Parity doesn't have small depth circuits.
Some frontiers in circuit complexity:
- ACC_0 and multiparty communication complexity
- Log depth and rigidity
Time space trade-offs: Lower bounds for SAT;
Non-uniform model: Branching programs. Barrington's theorem.

Derandomization:
- Nisan's generator for low space machines
- Nisan-Wigderson: hardness vs randomness
- Hardness amplification and average-case hardness

Some vignettes:
- Cryptography in constant parallel time
- Natural proofs: a barrier to proving stronger circuit lower bounds
- Derandomization needs circuit lower bounds
- Quantum computing

Lecture 2

2009-01-15T14:30:00.002-05:00

The topics covered in Lecture 2 were Universal Turing Machines, the Time and Space Hierarchy Theorems, Nondeterminism and NP as poly-time verification, poly-time reductions and NP-completeness, the Cook-Levin Theorem and Circuit-Sat being NP-complete, Circuit-Val is P-complete under log-space reductions, coNP.

Lecture 1

2009-01-13T15:14:00.004-05:00

The topics covered in Lecture 1 were: the "big questions" like "P ?= NP", "P ?= PSPACE", "P ?= LOGSPACE", "SC ?= NL", "P ?= NC", "EXP ?$\subseteq$ P/poly", and "P ?= BPP"; search vs. decision problems and languages; the multitape Turing Machine model; the Extended Church-Turing Thesis; Linear Speedup Theorem; and the classes TIME($f(n)$), SPACE($f(n)$), P, PSPACE, and L (aka LOGSPACE).

If you need a refresher on basic stuff such as the Turing Machine Model (the details of which are as finicky as they are ultimately boring) you might look at Chapter 1 of the Arora-Barak book.

Homework Template

2009-01-12T16:45:00.003-05:00

Hello everyone, and welcome to the Complexity class!

I just wanted to let you know that I have added a sample homework solution to the class website. The source files for the homework can be found here (.tex), here (.bib), and here (.sty). Downloading all three files into a common directory and compiling with Latex, you should obtain this output.

For the homeworks, you should only have to rename and modify the "sample" files as needed. If you have any problems with the files or if you have any other questions, please don't hesitate to ask me.

History of Complexity

2009-01-12T15:51:00.006-05:00

For an early blog post, I was planning on reading a little about the history of complexity, checking out the original sources, and writing a little about "who first thought of measuring running time in terms of input string length?" and "what were Cobham and Edmonds thinking when they suggested P as a good class to study?"

But after a bunch of research I found this article by Stephen Cook on the very subject, on the occasion of him winning the Turing Award. And it seemed hard to imagine how I could write anything more authentic or instructive.

So I encourage you to read the article. But as you do so, let me add a few random comments that spring to my mind. Also, please post any questions or comments that you might have...

. Cook's article was written five years before the discovery of the famous 1956 letter from Gödel to von Neumann -- in which Gödel quite explicitly asks whether NP could be in P. Bear in mind that the notions of P and NP didn't even exist in 1956!

. I've never heard of Cook's problem about printing out $\sqrt{2}$ at a linear rate -- anyone got a reference for it? Is it still open?

. As Cook himself notes, much of the key development of computational complexity took place among the graduate students at Princeton in the early-to-mid 1960's. I suppose this shouldn't be too surprising, given that it was at Princeton and the Institute for Advanced Studies in the '30s and '40s that you had all the folks working on foundations of mathematics but with a "computer science" slant (Gödel, von Neumann, Church, Turing), plus other folks like Kuhn, Tucker, and Minsky. This is the gang that begat the complexity-theory founders Cook mentions -- Rabin, Stearns, Bennett, and Ritchie, as well as Aho, Hopcroft and Ullman, and CMU's own Turing Award winners Manuel Blum and Dana Scott. The only original complexity theory folks from this era I could find not out of Princeton or Princetonians were Hartmanis (from Caltech) and the very mysterious Alan Cobham, who appears to have no PhD and to hail from parts unknown. Anyone got any information on him?

. These are all men, by the way; of course, Princeton didn't even have women undergraduates until the end of the '60s. Harvard, where Cook was, seems to have been the only non-backwards place of the time, producing several female complexity-theory folks, most notably Greibach.

. The "right" definition of how to define a RAM (random access machine) is not so controversial today as I guess it was when Cook was writing. I think everyone agrees that most sensible definitions are okay and about equal, up to log factors. I think the "random access Turing Machine" (see here) is a reasonable standard.

. Cook writes "The identification of P with the tractable (or feasible) problems has been generally accepted in the field since the early 1970's." I'm not completely sure about this today. Certainly everyone agrees that P is the most reasonable, natural, and best class to study, but there is a great deal of interest these days in linear, quasilinear (linear times log factors), and even sublinear time algorithms. In fact, it's not so unreasonable to argue that an algorithm is truly efficient in practice only if it is quasilinear time. Perhaps more on this in a future post...

. Regarding Cook's list of the most interesting and important problems in P...

- 35 years after the Schönhage-Strassen algorithm Cook mentions, a faster multiplication algorithm was found. It runs in time $n \log n 2^{O(\log^* n)}$ (!!) and was given in an award-winning 2007 paper of Fürer over at Penn State.

- Coppersmith and Winograd soon thereafter improved the matrix multiplication time to roughly $n^{2.38}$. This has stood for 20 years.

- Primes is in P, thanks to Agrawal, Kayal, and Saxena in 2004.

- Linear Programming being in P has subsequently proven to be of enormous importance.

- To be honest, there aren't so many additional notable polynomial-time algorithms discovered since then. I might point to the Convex Programming work due to Grötschel, Lovász and Schrijver (1981), the theory of Markov Chain Monte Carlo due to Jerrum-Sinclair and Dyer-Frieze-Kannan (1988), and recognizing minor-closed graph families due to Robinson and Seymour (1983--2004). Any other candidates?

. Cook devotes a lot more space to #P-completeness than NP-completeness (probably out of modesty), but the latter continues to be much more important and influential, though we will certainly study the former in our class.

. Similarly, the study of parallel complexity and the class NC has not proven quite so influential as it looked in the '80s, but we will certainly study it too.

. Re lower bounds: "Structured lower bounds" we're pretty good at. But genuine lower bounds? We still have absolutely no clue; people feel even less enthusiastic about the prospect of proving good time lower bounds than they did when Cook wrote. Cook's speculation about separating P from L at the end of the article looks overly optimistic today.

. That said, and on the Section 4.3 topic of time-space product lower bounds, there has been a lot of good work done recently in this area, especially by recent CMU complexity grad Ryan Williams. We plan to cover some of this in our course.

Read this blog

2008-12-18T17:26:00.000-05:00

This is the class blog for CMU's Spring 2009 graduate CS course 15-855*, "An intensive introduction to computational complexity".

The instructors for this course are Venkat Guruswami and Ryan O'Donnell. The TA is Eric Blais.

The course homepage is http://www.cs.cmu.edu/~odonnell/complexity/. That page will be mostly static, except for postings of the homeworks and midterm. Please read this blog regularly, or add it to your RSS feed. We will use the blog to post announcements (e.g., "There is a correction to problem 3 on the homework..."), lecture corrigenda and updates, homework hints, etc.

Students in the class will also be required to make one significant blog post, for credit. This will be discussed in Lecture 1.

Finally, we will use MathML in these posts; if it is working correctly for you, the following statements should look basically the same:

A set system L is "laminar" if for all A, B ∈ L, either A∩B = Ø, A ⊆ B, or B ⊆ A.

A set system $L$ is "laminar" if for all $A$, $B$ $\in$ $L$, either $A \cap B = \emptyset$, $A \subseteq B$, or $B \subseteq A$.

To get this to work, on IE I believe you download an ActiveX control here:
http://www.dessci.com/en/products/mathplayer/download.htm

If you use Firefox, try going here:
http://www.mozilla.org/projects/mathml/fonts

15-855: Intensive Intro to Computational Complexity

Wrapup

Parameterized Complexity and ETH

Lower bounds for locally decodable codes

Kolmogorov Complexity and derandomization

Lecture 28

Game theory complexity and computing Nash Equilibrium

Last lecture

Course evaluations

Lecture 27

Lecture 26

Blogging

Lecture 25

Homework 5 Correction

Easy Witnesses

THURSDAY'S CLASS CANCELED

Lecture 24

Bounds on BQP

Midterm correction

Details for the IKW Theorem

Lecture 23

Why there isn't a simpler proof of IKW

Lecture 22

Homework 5

Lecture 21

Lecture 20

Midterm correction

Lecture 19

Lecture 18

Midterm

Lecture 17

Lecture 16

Fixed-polynomial circuit lower bounds for MA/1

On the power of membership queries in agnostic learning

Factoring

Lecture 15

Lecture 14

Recognizing/printing real numbers in real time

Lecture 13

Homework 2 wrapup

Lecture 12

Solutions to Homework 2

Derandomization of space classes

Lecture 11

Lecture 10

Homework 2 -- CORRECTION

Solutions to Homework 1

Homework 2

A Quadratic Lower Bound for the Determinant and Permanent Problem

Combinatorial Complexity

Lecture 9

Office hours today

Tuesday's class canceled

Average Case Hardness

Lecture 8

Lecture 7

Homework 2

Misc. Definitions

Partial Derandomization of Polynomial Identity Checking (II)

Lecture 6

Partial Derandomization of Polynomial Identity Checking (I)

Trivial lemma => powerful circuit lower bounds

Lecture 5

If pigs could whistle, then horses could fly

The many characterizations of NP

Polylog-wise independence fools constant-depth circuits

Lecture 4

Lecture 3

Blogroll

Tentative syllabus

Lecture 2

Lecture 1

Homework Template

History of Complexity

Read this blog