__Preprint:__

**
Sam Buss
Uniform Proofs of ACC Representations
Archive for Mathematical Logic 56, 5-6 (2017) 639-669.
**

**
Download manuscript: PDF.
**

**Abstract:**
We give a uniform proof of the theorems of Yao and Beigel-Tarui
representing ACC predicates as constant depth circuits
with MOD *m* gates and a symmetric gate.
The proof is based on a relativized,
generalized form of Toda's theorem expressed
in terms of closure properties of formulas under
bounded universal, existential and modular counting quantifiers.
This allows the main proofs to be expressed in terms
of formula classes instead of Boolean circuits.
The uniform version of the Beigel-Tarui theorem
is then obtained automatically via the
Furst-Saxe-Sipser and Paris-Wilkie translations.
As a special case, we obtain a uniform version of Razborov
and Smolensky's representation of AC^{0}[p] circuits.
The paper is partly expository, but is also motivated
by the desire to recast
Toda's theorem, the Beigel-Tarui theorem, and their proofs
into the language of bounded arithmetic. However,
no knowledge of bounded arithmetic is needed.