14
$\begingroup$

I am reading the appendix about ACC lower bounds for NEXP in Arora and Barak's Computational Complexity book. http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf One of the key lemmas is a transformation from $ACC^{0}$ circuits to multilinear polynomials over the integers with polylogarithmic degree and quasipolynomial coefficients, or equivalently, the circuit class $SYM^{+}$, which is the class of depth two circuits with quasipolynomially many AND gates at its bottom level with polylogarithmic fan-in, and a symmetric gate at the top level.

In the appendix to the textbook, this transformation has three steps, assuming that the gate set consists of OR, mod $2$, mod $3$, and the constant $1$. The first step is to reduce the fan-in of the OR gates to polylogarithmic order.

Using the Valiant–Vazirani Isolation Lemma, the authors obtain that given an OR gate over $2^{k}$ inputs of the form $OR (x_{1},...,x_{2^{k}})$, , if we pick $h$ to be a pairwise independent hash function, from $[2^{k}]$ to $\{ 0,1 \}$, then for any nonzero $x \in \{0,1\}^{2^{k}}$,with probability at least $1/(10k)$ it will hold that $\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2$.

Isn't the probability of $\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2$ at least $1/2$ ? It seems that $1/10k$ is a weak lower bound.

The second step is moving to arithmetic gates and pushing multiplications down. In this step, we will transform Boolean circuits with a given binary input string to an arithmetic circuit with an integer input.

Here they note that $OR(x_{1},...,x_{k})$ is replaced with $1-x_{1}x_{2}\cdots x_{k}$, and $MOD_{p}(x_{1},...,x_{k})$ is replaced with $(\Sigma_{i=1,...,k} x_{i})^{p-1}$ using Fermat's Little Theorem.

Why does this replacement give an equivalent $SYM^{+}$ circuit ?

$\endgroup$
  • 3
    $\begingroup$ I don't understand the expression that follows "with probability at least 1/(10k) it will hold that ...." Are you missing an equals sign? Also, could you cite the page number where this proof appears? $\endgroup$ – Robin Kothari Aug 12 '13 at 21:48
10
$\begingroup$

Isn't the probability of $\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2 = 1$ at least 1/2 ? It seems that $1/(10k)$ is a weak lower bound.

In fact the answer is no. (It would be that $\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2 = 1$ holds with probability at least $1/2-\varepsilon$, if we were working with an $\varepsilon$-biased hash family, and indeed using $\varepsilon$-biased hash functions gives a way to improve the parameters of the construction. But pairwise independence is not necessarily $\varepsilon$-biased.)

It seems they are missing one additional step here. To apply Valiant-Vazirani directly, you would need to also randomly choose the range of the hash function. Rather than picking random pairwise-independent $h : [2^k]\rightarrow\{0,1\}$, it seems you should pick random $\ell \in \{2,\ldots,k+1\}$ and then pick random pairwise-independent $h : [2^k]\rightarrow \{0,1\}^{\ell}$. (Here I am deliberately using Arora-Barak's statement of Valiant-Vazirani, found on page 354.) Let $s$ be the number of $x_i=1$. Valiant-Vazirani says that when you have chosen $\ell$ such that $2^{\ell-2} \leq s \leq 2^{\ell-1}$, then the probability that $\Sigma_{i:h (i) =1} x_{i} = 1$ (over the integers!) is at least $1/8$.

So by picking random $\ell$ and picking random pairwise independent $h: [2^k]\rightarrow\{0,1\}^{\ell}$, then you have probability at least $1/(8k)$ that $\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2 = 1$. To simulate the random choice of $\ell$ in the circuit, you could simply take the $OR$ over all possible $\ell$ (their number is logarithmic in $2^k$, after all), so the probability of success becomes at least $1/8$ again. So rather than having $O(k\log s)$ hash functions with range $\{0,1\}$, you'll want $O(k)$ different sets of hash functions (each set having a different range), with $O(\log s)$ hash functions in each set.

Why does this replacement give an equivalent SYM+ circuit ?

A SYM of AND (i.e, SYM+) circuit of size $K$ is essentially equivalent to having a multivariate polynomial $h : \{0,1\}^n \rightarrow \{0,\ldots,K\}$ with at most $K$ monomials, a lookup table $g : \{0,\ldots,K\}\rightarrow \{0,1\}$, and computing $g(h(x_1,\ldots,x_n))$. (For instance, a proof can be found in Beigel-Tarui.) The intuition is that each monomial in $f$ is an AND gate, and $g$ is the SYM gate. I say "essentially equivalent" because the multilinear polynomial $h$ could also have negative coefficients for some terms, and negative coefficents are not obviously implementable in SYM of AND. But I claim (and Beigel and Tarui claim) that this is not a problem. Think about it :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.