<blockquote>
  <p>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. </p>
</blockquote>

<p>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.)</p>

<p>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$. </p>

<p>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.</p>

<blockquote>
  <p>Why does this replacement give an equivalent SYM+ circuit ?</p>
</blockquote>

<p>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 :) </p>

CC BY-SA 3.0
2013-08-22T11:08:45.723Z
2013-08-22T11:59:49.233Z
2013-08-22T11:59:49.233Z
Ryan Williams
<p>I am reading the appendix about ACC lower bounds for NEXP in Arora and Barak's <em>Computational Complexity</em> book.
<a href="http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf">http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf</a>
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. </p>

<p>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. </p>

<p>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$.</p>

<blockquote>
  <p>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. </p>
</blockquote>

<p>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.</p>

<p>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. </p>

<blockquote>
  <p>Why does this replacement give an equivalent $SYM^{+}$ circuit ?</p>
</blockquote>

CC BY-SA 3.0
2013-08-12T21:48:48.223Z
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?
Robin Kothari
<cc.complexity-theory><co.combinatorics><complexity-classes><circuit-complexity><boolean-functions>
Beigel-Tarui transformation of ACC cricuits
echuly
# Beigel-Tarui transformation of ACC cricuits

(Asked by: username_0 on 2013-08-11)

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 ?

**Tags:** cc.complexity-theory, co.combinatorics, complexity-classes, circuit-complexity, boolean-functions
> **Comments:**
> **username_1**: 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?  

---

## 1 answers

### Answer by username_2 on 2013-08-22. Score: 10

> 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 :)


---

