TR07-125 Authors: Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka

Publication: 7th December 2007 11:57

Downloads: 1073

Keywords:

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.