Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
According to this paper, which discusses a nondeterministic extension of the Strong Exponential Time Hypothesis (SETH), "[…] Williams has recently shown related hypotheses about Merlin-Arthur complexity of k-TAUT are false". However, that paper only cites a personal communication.
How is the MA version of SETH proven to be false?
I suspect that it involves algebrizing the formula, but do not have any further idea.
You can find a preprint by following this link http://eccc.hpi-web.de/report/2016/002/
EDIT (1/24) By request, here is a quick summary, taken from the paper itself, but glossing over many things. Suppose Merlin can prove to Arthur that for a $k$-variable arithmetic circuit $C$, its value on all points in $\{0,1\}^k$ is a certain table of $2^k$ field elements, in time about $(s + 2^k) \cdot d$, where $s$ is the size of $C$ and $d$ is the degree of the polynomial computed by $C$. (We call this a "short non-interactive proof of batch evaluation" --- evaluating $C$ on many assignments.)
Then Merlin can solve $\#$SAT for Arthur as follows. Given a CNF $F$ on $n$ variables and $m$ clauses, Merlin and Arthur first construct an arithmetic circuit $C$ on $n/2$ variables of degree at most $mn$, size about $mn \cdot 2^{n/2}$, which takes a sum over all assignments to the first $n/2$ variables of the CNF $F$ (adding a $1$ to the sum when $F$ is true, and $0$ when it's false). Using the batch evaluation protocol, Merlin can then prove that $C$ takes on $2^{n/2}$ particular values on all its $2^{n/2}$ Boolean assignments, in about $2^{n/2} poly(n,m)$ time. Summing up all those values, we get the count of the SAT assignments to $F$.
Now we say at a high level how to do the batch evaluation protocol. We want the proof to be a succinct representation of the circuit $C$ that is both easy to evaluate on all of the $2^k$ given inputs, and also easy to verify with randomness. We set the proof to be a univariate polynomial $Q(x)$ defined over a sufficiently large extension field of the base field $K$ (of characteristic at least $2^n$ for our application), where $Q(x)$ has degree about $2^k \cdot d$, and $Q$ ``sketches'' the evaluation of the degree-$d$ arithmetic circuit $C$ over all $2^k$ assignments. The polynomial $Q$ satisfies two conflicting conditions:
The verifier can use the sketch $Q$ to efficiently produce the truth table of $C$. In particular, for some explicitly known $\alpha_i$ from the extension of $K$, we want $(Q(\alpha_0), Q(\alpha_1),\ldots,Q(\alpha_K)) = (C(a_1),\ldots,C(a_{2^K}))$, where $a_i$ is the $i$th Boolean assignment to the $k$ variables of $C$ (under some ordering on assignments).
The verifier can check that $Q$ is a faithful representation of $C$'s behavior on all $2^k$ Boolean assignments, in about $2^k + s$ time, with randomness. This basically becomes a univariate polynomial identity test.
The construction of $Q$ uses an interpolation trick originating from the holographic proofs, where multivariate expressions can be efficiently ``expressed'' as univariate ones. Both of the two items utilize fast algorithms for manipulating univariate polynomials.
