<p>The circuit characterization are by Kannan, Venkateswaran, Vinay, and Yao given in the paper:</p>

<p><a href="http://dx.doi.org/10.1006/inco.1993.1033" rel="nofollow">A Circuit-Based Proof of Toda′s Theorem</a></p>

CC BY-SA 3.0
2014-05-05T14:38:28.497Z
2014-05-05T14:38:28.497Z
Kristoffer Arnsfelt Hansen
<p>This is a question from the lecture about Toda's theorem:</p>

<p><a href="http://www.cs.princeton.edu/courses/archive/spring01/cs522/lecnotes/lec8.ps" rel="nofollow">http://www.cs.princeton.edu/courses/archive/spring01/cs522/lecnotes/lec8.ps</a></p>

<p>The lecture uses theorem 1 and theorem 2 but not include proof. My question is how to proof?</p>

<p>Theorem 2:</p>

<p>$L \in \oplus P$ iff $L$ can be computed by a DC uniform circuit $\{D_n\}$ that</p>

<p>use $AND$, $OR$, $NOT$, $XOR$ gates.</p>

<p>has size $2^{n^{O(1)}}$ and constant depth</p>

<p>$XOR$ gates can have unbounded (exponential) fanin, but $AND$, $OR$ gates have fanin at most $n^{O(1)}$</p>

<p>$NOT$ gates can appear anywhere in the circuit.</p>

<p>This question may not be a research level question, but I really want to know the answer. If someone can give me a detailed reference, I will appreciate that.</p>

<circuit-families>
DC uniform circuit and parity-P
Tian
# DC uniform circuit and parity-P

(Asked by: username_0 on 2014-05-05)

This is a question from the lecture about Toda's theorem:

<http://www.cs.princeton.edu/courses/archive/spring01/cs522/lecnotes/lec8.ps>

The lecture uses theorem 1 and theorem 2 but not include proof. My question is how to proof?

Theorem 2:

$L \in \oplus P$ iff $L$ can be computed by a DC uniform circuit $\{D\_n\}$ that

use $AND$, $OR$, $NOT$, $XOR$ gates.

has size $2^{n^{O(1)}}$ and constant depth

$XOR$ gates can have unbounded (exponential) fanin, but $AND$, $OR$ gates have fanin at most $n^{O(1)}$

$NOT$ gates can appear anywhere in the circuit.

This question may not be a research level question, but I really want to know the answer. If someone can give me a detailed reference, I will appreciate that.

**Tags:** circuit-families

---

## 1 answers

### Answer by username_1 on 2014-05-05. Score: 2 | Accepted answer

The circuit characterization are by Kannan, Venkateswaran, Vinay, and Yao given in the paper:

[A Circuit-Based Proof of Toda′s Theorem](http://dx.doi.org/10.1006/inco.1993.1033)


---

