MA/1∉SIZE[nk]
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∈N, MA/1⊈SIZE[nk].
Proof for the main theorem
We consider the following two cases: (i) PSPACE⊆P/poly and (ii) PSPACE⊈P/poly. 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⊈SIZE[nk] for all k∈N and thus MA⊆SIZE[nk]. Note that here we actually prover lower bound for a smaller class than MA/1. To show PSPACE⊈SIZE[nk], one simply enumerate all the circuit family in SIZE[nK] (since SIZE[nk] 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∈P/poly. 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′∈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 (|x|+y)k+1≤s(n)<(|x|+2y)k+1 given input (x,1y). 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′∈MA/1.
With some more effort, one can also easily shows that L′ does not have size nk circuit. Thus, we conclude that MA/1⊈SIZE(nk).
A natural question here could be: why this only works for fixed polynomial size lower bound? A quick answer is: we only know PSPACE⊈SIZE[nk] for all k∈N. As the first step reduce the lower bound for MA to PSPACE, this is the best this approach can get.