Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with arithmetization:
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 ... more >>>

TR08-005 | 15th January 2008
Scott Aaronson, Avi Wigderson

Algebrization: A New Barrier in Complexity Theory

Any proof of P!=NP will have to overcome two barriers: relativization
and natural proofs. Yet over the last decade, we have seen circuit
lower bounds (for example, that PP does not have linear-size circuits)
that overcome both barriers simultaneously. So the question arises of
whether there ... more >>>

ISSN 1433-8092 | Imprint