Computer Science
Document Type
Conference Paper
Abstract
The class of languages that can be recognized in polynomial time with the additional information of one bit from a #P function is studied. In particular, it is shown that every ModkP class and every class contained in PH are low for this class. These results are translated to the area of circuit complexity using MidBit (middle bit) gates. It is shown that every language in ACC can be computed by a family of depth-2 deterministic circuits of size 2 to the (log n)c power with a MidBit gate at the root and AND-gates of fan-in (log n)c at the leaves. This result improves the known upper bounds for the class ACC.
Publication Title
Proceedings of the Seventh Annual Structure in Complexity Theory Conference
Publication Date
1992
First Page
111
Last Page
117
ISBN
081862955X
Repository Citation
Green, Frederic; Kobler, Johannes; and Toran, Jacobo, "The power of the middle bit" (1992). Computer Science. 75.
https://commons.clarku.edu/faculty_computer_sciences/75
APA Citation
Green, F., Köbler, J., & Torán Romero, J. (1991). The power of the middle bit.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.