The Power of the Middle Bit of a #P Function

This paper studies the class MP of languages which can be solved in polynomial time with the additional information of one bit from a #P function f{hook}. The middle bit of f{hook}(x) is shown to be as powerful as any other bit, whereas the O(log n) bits at either end are apparently weaker. The polynomial hierarchy and the classes Mod_k P, k ≥ 2, are shown to be low for MP. They are also low far a class we call AmpMP which is defined by abstracting the "amplification" methods of Toda (SIAM J, Comput.20 ( 1991), 865-877). Consequences of these results for circuit complexity are obtained using the concept of a MidBit gate, which is defined to take binary inputs x₁, ...,x_w and output the ⌊log₂(w)/2⌋th hit in the binary representation of the number Σ^w_i=1x_i . Every language in ACC can be computed by a family of depth-2 deterministic circuits of size 2^{log nO(1)} with a Mid Bit gate at the root and AND-gates of fan-in (log n)^O(1) at the leaves. This result improves the known upper bounds for the class ACC.