Abstract:
For any given Boolean formula $\phi(x_1,\dots,x_n)$, one can efficiently construct (using \emph{arithmetization}) a low-degree polynomial $p(x_1,\dots,x_n)$ that agrees with $\phi$ over all points in the Boolean cube $\{0,1\}^n$; the constructed polynomial $p$ can be interpreted as a polynomial over an arbitrary field $\mathbb{F}$. The problem $\#SAT$ (of counting the number of satisfying assignments of $\phi$) thus reduces to the polynomial summation $\sum_{x\in\{0,1\}^n} p(x)$. Motivated by this connection, we study the \emph{query complexity} of the polynomial summation problem: Given (oracle access to) a polynomial $p(x_1,\dots,x_n)$, compute $\sum_{x\in\{0,1\}^n} p(x)$. Obviously, querying $p$ at all $2^n$ points in $\{0,1\}^n$ suffices. Is there a field $\mathbb{F}$ such that, for every polynomial $p\in\mathbb{F}[x_1,\dots,x_n]$, the sum $\sum_{x\in\{0,1\}^n} p(x)$ can be computed using fewer than $2^n$ queries from $\mathbb{F}^n$? We show that the simple upper bound $2^n$ is in fact \emph{tight} for \emph{any} field $\mathbb{F}$ in the \emph{black-box model} where one has only oracle access to the polynomial $p$. We prove these lower bounds for the \emph{adaptive} query model where the next query can depend on the values of $p$ at previously queried points. Our lower bounds hold even for polynomials that have degree at most $2$ in each variable. In contrast, for polynomials that have degree at most $1$ in each variable (i.e., multilinear polynomials), we observe that a \emph{single} query is sufficient over any field of characteristic other than $2$. We also give query lower bounds for certain extensions of the polynomial summation problem.