Previous slide Next slide Back to the first slide View text version


Notes:

- Allender shows how to use Toda's proof to show that every constant depth circuit has an equivalent depth-three quasipolynomial-size threshold circuit.

- The class $\ACC$ consists of those circuits accepted by bounded depth circuits with $\AND$, $\OR$ and $\MOD_q$ gates where $q$ is a fixed integer not necessarily prime. Yao and Beigel and Tarui extend Toda’s ideas to show that every language in $\ACC$ is recognized by depth-two circuits with a symmetric (independent of input order) gate at the root and quasipolynomial $\AND$ gates of polylog fan-in at the leaves.

- Toda and Ogiwara extend part of Toda's work to show that every function in $\GapP^\PH$ probabilistically reduces to a $\GapP$ function. Their result shows that in addition to $\parityp$, $\PH$ probabilistically reduces to many other counting classes such as $\PP$

- Open: Can counting simulate polynomial alternations.