The Unreasonable Power of the Sum-Check Protocol

At this point in the post, we have our hammer in hand: the sum-check protocol, which allows a verifier to offload the computation expressions of the form of Equation (1) to an untrusted prover. However, wielding this hammer to solve problems people care about can require a good deal of cleverness. The goal of the rest of this post is give a flavor of how this typically works.

The general challenge is the following: suppose the verifier has an input $x$ and asks the prover to compute some function $F$ of $x$. To apply the sum-check protocol to compute $F$, we need to be able to express $F(x)$ as an instance of Equation (1). This means that we need to identify some $v$-variate polynomial $g$ of degree 2 in each variable such that $F(x)$ can be inferred from the sum of $g$’s values over all inputs in $\{0, 1\}^{v}$. Moreover, the verifier needs to be able to evaluate $g(r)$ at any desired input $r \in \mathbf{F}^v$ in linear time.

I will explain one illustrative example of this paradigm, in which the input $x$ is the adjacency matrix of a graph, and $F(x)$ is the number of triangles in that graph. To accomplish this, I have no choice but to introduce one technical notion, called multilinear extensions, defined in the lemma below. To avoid unnecessary details, I do not prove the lemma, but it follows readily from Lagrange interpolation.

Let $f \colon \{0, 1\}^n \to \mathbf{F}$. Then there is a unique multilinear polynomial $\tilde{f}$ over $\mathbf{F}$ such that $\tilde{f}(x) = f(x)$ for all $x \in \{0,1\}^n$. Here, a polynomial is said to be multilinear if it has degree at most 1 in each variable. $\tilde{f}$ is called the multilinear extension (MLE) of $f$. Given as input a list of all $2^n$ evaluations of $f$, and an arbitrary point $r \in \mathbf{F}^n$, there is an algorithm that can evaluate $\tilde{f}(r)$ in $O(2^n)$ time.

Let $G$ be an undirected graph on $n$ vertices with edge set $E$. Let $A \in \{0, 1\}^{n \times n}$ be the adjacency matrix of $G$, i.e., $A_{i,j}=1$ if and only if $(i, j) \in E$. In the counting triangles problem, the input is the adjacency matrix $A$, and the goal is to determine the number of vertex triples $(i, j, k)$ that are all connected to each other by edges.

At first blush, it is totally unclear how to express the number of triangles in $G$ as the sum of the evaluations of a degree-2 polynomial $g$ over all inputs in $\{0, 1\}^v$. After all, the counting triangles problem itself makes no reference to any low-degree polynomial $g$, so where will $g$ come from? This is where multilinear extensions come to the rescue.

For it to make sense to talk about multilinear extensions, we need to view the adjacency matrix $A$ not as a matrix, but rather as a function $f_A$ mapping $\{0, 1\}^{\log n} \times \{0, 1\}^{\log n}$ to $\{0, 1\}$. The natural way to do this is to define $f_A(x, y)$ so that it interprets $x$ and $y$ as the binary representations of some integers $i$ and $j$ between $1$ and $n$, and outputs $A_{i, j}$.

Then the number of triangles in $G$ is simply: $$ \Delta := \frac{1}{6} \sum_{x, y, z \in \{0, 1\}^{\log n}} f_A(x, y) \cdot f_A(y, z) \cdot f_A(x, z) \textit{ } (2)$$
To see that this equality is true, observe that the term for $x, y, z$ in the above sum is 1 if edges $(x, y)$, $(y, z)$, and $(x, z)$ all appear in $G$, and is 0 otherwise. The factor $1/6$ comes in because the sum over unordered node triples $(i, j, k)$ counts each triangle 6 times, once for each permutation of $i$, $j$, and $k$.

Let $\mathbf{F}$ be a finite field of size $p \geq n^3$, where $p$ is a prime, and let us view all entries of $A$ as elements of $\mathbf{F}$. Here, we are choosing $p$ large enough so that $6\Delta$ is guaranteed to be in $\{0, 1, \dots, p\}$. This ensures that, if we associate elements of $\mathbf{F}$ with integers in $\{0, 1, \dots, p\}$ in the natural way, then Equation (2) holds even when all additions and multiplications are done in $\mathbf{F}$ rather than over the integers. (Choosing a large field to work over has the added benefit of ensuring good soundness error, as the soundness error of the sum-check protocol decreases linearly with field size.)

At last we are ready to describe the polynomial $g$ to which we will apply the sum-check protocol to compute $6 \Delta$. Recalling that $\tilde{f}_A$ is the MLE of $f_A$ over $\mathbf{F}$, define the $(3 \log n)$-variate polynomial $g$ to be: $$g(X, Y, Z) = \tilde{f}_A(X, Y) \cdot \tilde{f}_A(Y, Z) \cdot \tilde{f}_A(X, Z)$$

It is easy to see that $$6 \Delta = \sum_{x, y, z \in \{0, 1\}^{\log n}} g(x, y, z),$$ so applying the sum-check protocol to $g$ yields an IP computing $6\Delta$. This IP requires $3 \log n$ rounds, with the prover sending 3 field elements in each round. The verifier’s runtime is dominated by the time required to evaluate $g$ at a single input $(r_1, r_2, r_3) \in \mathbf{F}^{3 \log n}$, for which it suffices to evaluate $\tilde{f}_A$ at the three inputs $(r_1, r_2)$, $(r_2, r_3)$, and $(r_1, r_3)$. This can be done in $O(n^2)$ time using the Multilinear Extension Lemma. This is much faster than the fastest known algorithm for counting triangles, which runs in matrix multiplication time (superlinear in the input size).

It turns out that the prover in this IP can compute all of its prescribed messages in $O(n^3)$ time. This is not obvious, and for brevity, I’ll omit the details of how to accomplish this. Note that this runtime for the prover matches that of the the naive algorithm for counting triangles that iterates over all triples of vertices in $G$ and checks if they are all connected to each other.

Hopefully the above gives a sense of how problems that people care about can be expressed as instances of Equation (1) in non-obvious ways. The general paradigm works as follows. An input $x$ of length $n$ is viewed as a function $f_x$ mapping $\{0, 1\}^{\log n}$ to some field $\mathbf{F}$. And then the multilinear extension $\tilde{f}_x$ of $f_x$ is used in some way to construct a low-degree polynomial $g$ such that, as per Equation (1), the desired answer equals the sum of the evaluations of $g$ over the Boolean hypercube.

The full version of this post covers some additional examples of this paradigm. In the hopes of enticing you to check it out, here is a summary of the examples covered there.

First, it gives a more sophisticated IP for counting triangles in which the prover is much more efficient than the above. Specifically, the prover runs the best-known algorithm to solve the triangles problem, and then does a low-order amount of extra work to prove the answer is correct. I don’t know of any other IPs or argument systems that achieve this super-efficiency for the prover while keeping the proof length sublinear in the input size.

Second, it gives a similarly super-efficient IP for matrix-powering. Given any $n \times n$ matrix $A$ over field $\mathbf{F}$, this IP is capable of computing any desired entry of the powered matrix $A^k$. The number of rounds and communication cost of the IP are $O(\log(k) \cdot \log n)$, and the verifier’s runtime is $O(n^2 + \log(k) \cdot \log n)$.

Finally, it uses this matrix-powering protocol to re-prove the following important result of Goldwasser, Kalai, and Rothblum (GKR): all problems solvable in logarithmic space have an IP with a quasilinear-time verifier, polynomial time prover, and polylogarithmic proof length. The basic idea of the proof is that executing any Turing Machine $M$ that uses $s$ bits of space can be reduced to the problem of computing a single entry of $A^{2^s}$ for a certain matrix $A$ ($A$ is in fact the configuration graph of $M$). So one can just apply the matrix-powering IP to $A$ to determine the output of $M$. While $A$ is a huge matrix (it has at least $2^s$ rows and columns), configuration graphs have a ton of structure, and this enables the verifier to evaluate $\tilde{f}_A$ at a single input in $O(s \cdot n)$ time. If $s$ is logarithmic in the input size, then this means that the verifier in the IP runs in $O(n \log n)$ time.

The original paper of GKR proved the same result by constructing an arithmetic circuit for computing $A^{2^s}$ and then applying a sophisticated IP for arithmetic circuit evaluation to that circuit. The approach described above is simpler, in that it directly applies a simple IP for matrix-powering, rather than a more complicated IP for the general circuit-evaluation problem.