ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > POLYNOMIAL SUMMATION:
Reports tagged with polynomial summation:
TR07-125 | 11th October 2007
Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka

The black-box query complexity of polynomial summation

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 ... more >>>



ISSN 1433-8092 | Imprint