Uniform proofs of ACC representations (Q2402964)

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.