Back to Boolean Circuits
Back to notes

# $\MA/1\notin\SIZE[n^k]$

90%

Santhanam showed super polynomial circuit lower bound for the Merlin-Arthur class with one bit advice , i.e., $\MA/1$. This is one of the state-of-the-art circuit lower bounds against fixed polynomial size circuit. The main idea is using collapse theorem for a complete language of $\PSPACE$ and a special translation argument. Here, we sketch the proof for the main theorem and state the corollaries. For the interested reader, we strongly recommend reading Santhanam’s paper which gave a very comprehensive introduction.

For any $k\in\N$, $\MA/1\not\subseteq\SIZE[n^k]$.

## Proof for the main theorem

We consider the following two cases: (i) $\PSPACE\subseteq\Ppoly$ and (ii) $\PSPACE\not\subseteq\Ppoly$. Note that consider $\PSPACE$ is quite interesting here since we are actually proving lower bounds for a smaller class.

Note that the first case is easy because $\PSPACE$ will collapse into $\MA$ (see this note). By the following diagonal argument, we show that $\PSPACE\not\subseteq\SIZE[n^k]$ for all $k\in\N$ and thus $\MA\subseteq\SIZE[n^k]$. Note that here we actually prover lower bound for a smaller class than $\MA/1$. To show $\PSPACE\not\subseteq\SIZE[n^k]$, one simply enumerate all the circuit family in $\SIZE[n^K]$ (since $\SIZE[n^k]$ is countable, it is enumerable) and then negate one output for each circuit family on one input length.

As for the second case, now we know that any complete language of $\PSPACE$ requires super-polynomial size circuit. The idea is then to put one of them (or its varient) into lower complexity classes (such as $\MA$ or $\MA/1$) while keeping the hardness.

Let us first recall how $\PSPACE$ collapses to $\MA$ when one assume $\PSPACE\in\Ppoly$. The main idea there is to send the circuits that computes the prover’s answers to Arthur so that he can efficiently simulate the verifier. However, here we know that a complete language of $\PSPACE$ might not have polynomial size circuit and thus this approach does not work. Santhanam elegantly used the translation technique to transform a $\PSPACE$-complete language $L$ to a languge $L’$ such the input length-$m(n)$ of $L’$ corresponds to the length-$n$ input of $L$ and $s(n)=\poly(m(n))$ where $s(n)$ is the size of the minimum circuit for $L$ on length-$n$ input. If this happened, then there is an $\AM$ protocol for $L’$.

However, this is not straightforward and we need two ingredients:

• A special $\PSPACE$-complete language $L$ with the following properties. There is an $\IP$ protocol for $L$ such that the queries sent by the verifier are of the same length as that of the input.
• Translating $L$ into another language $L’$ such that $L’\in\MA/1$.

With the $\PSPACE$-complete language $L$ above, for each input length $n$, one then only need to worry about one possible query length to the prover in the $\IP$ protocol. That is, in the future $\MA$ protocol, Merlin only needs to send one circuit to Arthur. This will much simplify the proof.

Next, we want to design language $L’$ such that (i) the input length-$m(n)$ of $L’$ corresponds to the length-$n$ input of $L$ and $s(n)=\poly(m(n))$ (ii) $L’$ does not have polynomial size circuit. Santhanam designed the following $L’$.

$L' = \{(x,1^y):\ x\in L,\ y=2^t,\ (\card{x}+y)^{k+1}\leq s(n)<(\card{x}+2y)^{k+1}\}.$

First, note that such construction of $L’$ achieves what we hoped for and it is straightforward to have a $\MA$ protocol with perfect completeness. However, it is not clear about the soundness since we have no control on the input where $y$ does not satify the desired properties.

The trick here is to use one bit of advice to indicate whether $y$ satisfies $(\card{x}+y)^{k+1}\leq s(n)<(\card{x}+2y)^{k+1}$ given input $(x,1^y)$. Note that for length-$n$ input, different $y$ gives a different input length $n+y$ and thus one bit of advice suffices. As a result, with some effort, one can then show that $L’\in\MA/1$.

With some more effort, one can also easily shows that $L’$ does not have size $n^k$ circuit. Thus, we conclude that $\MA/1\not\subseteq\SIZE(n^k)$.

A natural question here could be: why this only works for fixed polynomial size lower bound? A quick answer is: we only know $\PSPACE\not\subseteq\SIZE[n^k]$ for all $k\in\N$. As the first step reduce the lower bound for $\MA$ to $\PSPACE$, this is the best this approach can get.