<p>This result is presented in the Web Addendum of Arora-Barak, which can be found <a href="http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf" rel="nofollow">here</a>.</p>

CC BY-SA 3.0
2014-03-08T17:05:33.120Z
2014-03-08T17:05:33.120Z
Bart Jansen
<p><a href="http://cvs.cs.umd.edu/~gasarch/ryan/acc.pdf" rel="noreferrer">Beigel and Tarui</a>'s transformation of $\mathsf{ACC}^0$ circuits to depth 2 circuits with a polylog symmetric function on top is one of important results in the circuit complexity. For example, the recent breakthrough separation between $\mathsf{NEXP}$  and $\mathsf{ACC}^0$ by Ryan Williams uses this transformation to design a fast $\mathsf{ACC}^0$-CircuitSAT algorithm. </p>

<p>I think the proof in their paper is a little complicated and too technical for me. Is there a simpler proof of their result?</p>

<cc.complexity-theory><complexity-classes><circuit-complexity>
Is there a simpler proof of Beigel and Tarui's transformaion of ACC0 circuits
poul
# Is there a simpler proof of Beigel and Tarui's transformaion of ACC0 circuits

(Asked by: username_0 on 2013-05-07)

[Beigel and Tarui](http://cvs.cs.umd.edu/~gasarch/ryan/acc.pdf)'s transformation of $\mathsf{ACC}^0$ circuits to depth 2 circuits with a polylog symmetric function on top is one of important results in the circuit complexity. For example, the recent breakthrough separation between $\mathsf{NEXP}$ and $\mathsf{ACC}^0$ by Ryan Williams uses this transformation to design a fast $\mathsf{ACC}^0$-CircuitSAT algorithm.

I think the proof in their paper is a little complicated and too technical for me. Is there a simpler proof of their result?

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity

---

## 1 answers

### Answer by username_1 on 2014-03-08. Score: 3

This result is presented in the Web Addendum of Arora-Barak, which can be found [here](http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf).


---

