Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### Circuit Lower Bounds for Average MA

Revision #2
Authors: Alexander Knop
Accepted on: 3rd December 2014 14:08
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
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
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.