### Revision(s):

__
Revision #2 to TR13-037 | 3rd December 2014 14:08
__
#### Circuit Lower Bounds for Average MA

**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

**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

**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.