The power of the middle bit of a #P function
FakultätFakultät für Ingenieurwissenschaften und Informatik
Ressourcen- / MedientypWissenschaftlicher Beitrag, Text
Datum der Freischaltung2009-08-09
We study the class of languages which can be solved in polynomial time with the additional information of one bit from a #P function. In particular we show that the polynomial hierarchy and the classes ModkP are low for this class. We translate these results to the area of circuit complexity using the concept of a MidBit gate, which is defined to take binary inputs x_1,...,x_n and output the middle bit in the binary representation of the sum over the inputs. We show that every language in ACC can be computed by a family of depth-2 deterministic circuits of quasi-polynomial size with a MidBit gate at the root and AND-gates of poly-logarithmic fan-in at the leaves. This result improves the known upper bounds for the class ACC.
LizenzStandard (Fassung vom 01.10.2008)