Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-005 | 17th January 2007 00:00

Circuit Lower Bounds for Merlin-Arthur Classes


Authors: Rahul Santhanam
Publication: 18th January 2007 02:02
Downloads: 4006


We show that for each k > 0, MA/1 (MA with 1 bit of advice) does not have circuits of size n^k. This implies the first superlinear circuit lower bounds for the promise versions of the classes MA, AM and ZPP_{||}^{NP}.

We extend our main result in several ways. For each k, we give an explicit language in (MA /cap coMA)/1 which doesn't have circuits of size n^k. We also adapt our lower bound to the average-case setting, i.e., we give languages L_{k} in MA/1 such that for infinitely many n, no circuit of size n^k solves L_{k} correctly on more than a 1/2+1/n^k fraction of inputs of length n. Furthermore, we prove that for any k, MA does not have arithmetic circuits of size n^k.

As a corollary to our main result, we obtain that derandomization of MA with O(1) bits of advice implies the existence of pseudo-random generators computable efficiently using O(1) bits of advice.

ISSN 1433-8092 | Imprint