# How is the MA version of SETH proven to be false?

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.

• Could you post the document if you get a response?
– user34945
Nov 10 '15 at 16:45
• A paper is coming soon. Thanks for your patience. Nov 10 '15 at 17:11
• Actually I will say that what I prove is much stronger than: "there is a $1.9^n$ time Merlin-Arthur protocol for refuting k-TAUT", i.e., unsatisfiable k-CNF formulas. You can get about $2^{n/2}$ time for refuting any UNSAT circuit of sublinear depth, as far as I can tell. But as I said, the paper is coming soon. Nov 10 '15 at 22:14
• Possibly silly question, is that result (essentially) moving towards the idea: the conjectures "NSETH" and "k-TAUT requires exponential size circuits" are mutually exclusive? Or does the PRG construction easily eat up any potential gap between the MA and NP complexity of k-TAUT? Nov 11 '15 at 9:42
• Not a silly question! Short answer is that I don't know yet. Nov 12 '15 at 1:48

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.

• In the centered portion (near the top) of part 2 on page 6, it looks like R(x) should be replaced with R(r). ​ ​
– user6973
Jan 20 '16 at 5:46
• Please send comments on the manuscript to me directly; I don't check stackexchange every day. Thanks. Jan 20 '16 at 8:06
• Could you summarize the main idea of the paper, in order to provide a more self contained answer, and possibly protect against bit-rot?
– cody
Jan 21 '16 at 23:15