Circuit Lower Bounds for Merlin-Arthur Classes

Rahul Santhanam

Research output: Contribution to journalArticlepeer-review

Abstract

We show that for each k > 0, MA/1 (MA with 1 bit of advice) doesn’t have circuits of size nk. This implies the first superlinear circuit lower bounds for the promise versions of the classes MA,AM and ZPPNP.

We extend our main result in several ways. For each k, we give an explicit language in (MA ∩ coMA)/1 which doesn’t have circuits of size nk. We also adapt our lower bound to the average-case setting, i.e., we show that MA/1 cannot be
solved on more than 1/2+1/nk fraction of inputs of length n by circuits of size nk. Furthermore, we prove that MA does not have arithmetic circuits of size nk for any k.

As a corollary to our main result, we obtain that derandomization
of MA with O(1) advice implies the existence of pseudo-random generators computable using O(1) bits of advice.
Original languageEnglish
Number of pages23
JournalSIAM Journal on Computing
Volume39
Issue number3
DOIs
Publication statusPublished - 2009

Fingerprint

Dive into the research topics of 'Circuit Lower Bounds for Merlin-Arthur Classes'. Together they form a unique fingerprint.

Cite this