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.
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.
Translate result to average setting.
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.
