Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR13-037 | 3rd December 2014 14:08

Circuit Lower Bounds for Average MA

RSS-Feed




Revision #2
Authors: Alexander Knop
Accepted on: 3rd December 2014 14:08
Downloads: 446
Keywords: 


Abstract:

Santhanam (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.


Revision #1 to TR13-037 | 3rd December 2014 05:34

Circuit Lower Bounds for Average MA





Revision #1
Authors: Alexander Knop
Accepted on: 3rd December 2014 05:34
Downloads: 302
Keywords: 


Abstract:

Santhanam (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.



Changes to previous version:

Translate result to average setting.


Paper:

TR13-037 | 15th March 2013 11:54

Circuit Lower Bounds for Heuristic MA





TR13-037
Authors: Alexander Knop
Publication: 15th March 2013 15:31
Downloads: 1118
Keywords: 


Abstract:

Santhanam (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.



ISSN 1433-8092 | Imprint