ECCC-Report TR13-037https://eccc.weizmann.ac.il/report/2013/037Comments and Revisions published for TR13-037en-usWed, 03 Dec 2014 14:08:52 +0200
Revision 2
| Circuit Lower Bounds for Average MA |
Alexander Knop
https://eccc.weizmann.ac.il/report/2013/037#revision2Santhanam (2007) proved that MA/1 does not have circuits of size $n^k$. We translate his result to the heuristic setting by proving that there is a constant $a$ such that for any $k$, there is a language in AvgMA that cannot be solved by circuits of size $n^k$ on more than the $1 - \frac{1}{n^a}$ fraction of inputs.
In order to get rid of the non-uniform advice, we supply the inputs with the probability hreshold that
we use to determine the acceptance. This technique was used by Pervyshev (2007) for proving a time hierarchy for heuristic computations.Wed, 03 Dec 2014 14:08:52 +0200https://eccc.weizmann.ac.il/report/2013/037#revision2
Revision 1
| Circuit Lower Bounds for Average MA |
Alexander Knop
https://eccc.weizmann.ac.il/report/2013/037#revision1Santhanam (2007) proved that MA/1 does not have circuits of size $n^k$. We translate his result to the heuristic setting by proving that there is a constant $a$ such that for any $k$, there is a language in AvgMA that cannot be solved by circuits of size $n^k$ on more than the $1 - \frac{1}{n^a}$ fraction of inputs.
In order to get rid of the non-uniform advice, we supply the inputs with the probability hreshold that
we use to determine the acceptance. This technique was used by Pervyshev (2007) for proving a time hierarchy for heuristic computations.Wed, 03 Dec 2014 05:34:53 +0200https://eccc.weizmann.ac.il/report/2013/037#revision1
Paper TR13-037
| Circuit Lower Bounds for Heuristic MA |
Alexander Knop
https://eccc.weizmann.ac.il/report/2013/037Santhanam (2007) proved that MA/1 does not have circuits of size $n^k$. We translate his result to the heuristic setting by proving that there is a constant $a$ such that for any $k$, there is a language in HeurMA that cannot be solved by circuits of size $n^k$ on more than the $1 - \frac{1}{n^a}$ fraction of inputs.
In order to get rid of the non-uniform advice, we supply the inputs with the probability hreshold that
we use to determine the acceptance. This technique was used by Pervyshev (2007) for proving a time hierarchy for heuristic computations.Fri, 15 Mar 2013 15:31:14 +0200https://eccc.weizmann.ac.il/report/2013/037