ECCC-Report TR07-005https://eccc.weizmann.ac.il/report/2007/005Comments and Revisions published for TR07-005en-usThu, 18 Jan 2007 02:02:36 +0200
Paper TR07-005
| Circuit Lower Bounds for Merlin-Arthur Classes |
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2007/005We 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.
Thu, 18 Jan 2007 02:02:36 +0200https://eccc.weizmann.ac.il/report/2007/005