Computer Science

Document Type

Conference Paper


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


First Page


Last Page




APA Citation

Green, F., Köbler, J., & Torán Romero, J. (1991). The power of the middle bit.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.