ECCC-Report TR10-174https://eccc.weizmann.ac.il/report/2010/174Comments and Revisions published for TR10-174en-usFri, 12 Nov 2010 23:03:44 +0200
Paper TR10-174
| A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games |
Scott Aaronson,
Baris Aydinlioglu,
Harry Buhrman,
John Hitchcock,
Dieter van Melkebeek
https://eccc.weizmann.ac.il/report/2010/174We present an alternate proof of the recent result by Gutfreund and Kawachi that derandomizing Arthur-Merlin games into $P^{NP}$ implies linear-exponential circuit lower bounds for $E^{NP}$. Our proof is simpler and yields stronger results. In particular, consider the promise-$AM$ problem of distinguishing between the case where a given Boolean circuit $C$ accepts at least a given number $b$ of inputs, and the case where $C$ accepts less than $\delta \cdot b$ inputs for some positive constant $\delta$. If $P^{NP}$ contains a solution for this promise problem then $E^{NP}$ requires circuits of size $\Omega(2^n/n)$ almost everywhere.
Fri, 12 Nov 2010 23:03:44 +0200https://eccc.weizmann.ac.il/report/2010/174