Easy Witnesses

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:

1. 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.
2. $\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:

1. 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.
2. $\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:

1. 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.
2. $\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:

1. 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.
2. $\mathrm{BPP}\subseteq \mathrm{NP}$.

THURSDAY'S CLASS CANCELED

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

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

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

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

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

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

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

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

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

Lecture 21

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

Today we covered...

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

Midterm correction

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

Thanks to Or for pointing out the necessity of this.

Lecture 19

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

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

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

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

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

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

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.