Uniform proofs of ACC representations
Since the nineteens, it is known that both non-uniform [\textit{A. C.-C. Yao}, ``On ACC and threshold circuits, in: Proceedings 31st IEEE symposium on foundations of computer science, FOCS'90. Los Alamitos, CA: IEEE Computer Society. 619--627 (1990; \url{doi:10.1109/FSCS.1990.89583})] and uniform [\textit{R. Beigel} and \textit{J. Tarui}, Comput. Complexity 4, No. 4, 350--366 (1994; Zbl 0835.68040)] ACC0 circuits can be represented by constant-depth circuits with MOD gates and a symmetric gate. Interestingly, the proofs are quite different, the uniform case requiring to use the Valiant-Vazirani theorem [\textit{L. G. Valiant} and \textit{V. V. Vazirani}, Theor. Comput. Sci. 47, 85--95 (1986; Zbl 0621.68030)], but both results had a tremendous impact on the complexity theory community. The current paper offers an interpretation of this famous result from the point of view of bounded arithmetic. It succeeds in offering an interesting relation between computational complexity and bounded arithmetic, and does it, surprisingly, without using any (pre-existing) constructions from bounded arithmetic. After a short and to-the-point introduction, the author introduces the modular polynomial time hierarchy ModPH and its probabilistic version BP\(\cdot\oplus\)-ptime (Section 2). ModPH can be seen as a uniform version of ACC, and is equivalent to expressibility in the language of bounded arithmetic endowed with modular counting quantifiers and the smash function. Several closure properties are then proven and speculated (Section 3). Once everything is in place, the proof of the two main theorems (Section 4) are relatively short: oracles are used to convert the circuit description and inputs, so that the circuit value problem becomes a ModPH with oracles predicate. This predicate can then be rewritten as a constant-depth formula of the desired form, which in its turn is converted into a circuit of the desired form thanks to the Paris-Wilkie, Furst-Saxe-Sipser translation. The paper explores an interesting pathway, inventing new objects based on pre-existing results by porting them into another field. It re-enforces the connexions between circuit complexity and bounded arithmetic without bringing anything new to the former, except another evidence of the solidity and interest of the exploited result. The paper is nicely written and connects multiple fundamental areas of computer science, without being encumbered with elaborated technical details.
- A circuit-based proof of Toda's theorem
- A new characterization of \(\text{ACC}^{0}\) and probabilistic \(\text{CC}^{0}\)
- A note on \(\mathbf{MOD}_{p}\)-\(\mathbf{MOD}_{m}\) circuits
- A simple proof of Toda's theorem
- A Uniform Circuit Lower Bound for the Permanent
- Approximate counting by hashing in bounded arithmetic
- Approximate counting in bounded arithmetic
- BPP and the polynomial hierarchy
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Computational Complexity
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Depth reduction for circuits of unbounded fan-in
- scientific article; zbMATH DE number 1301088 (Why is no real title available?)
- scientific article; zbMATH DE number 1351078 (Why is no real title available?)
- scientific article; zbMATH DE number 1114025 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- NP is as easy as detecting unique solutions
- On ACC
- On uniform circuit complexity
- Parity, circuits, and the polynomial-time hierarchy
- PP is as Hard as the Polynomial-Time Hierarchy
- Probabilistic complexity classes and lowness
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- The power of the middle bit of a \(\#\)P function
This page was built for publication: Uniform proofs of ACC representations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2402964)
