Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Charles Rackoff:

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

TR00-034 | 5th June 2000
Valentine Kabanets, Charles Rackoff, Stephen Cook

Efficiently Approximable Real-Valued Functions

We consider a class, denoted APP, of real-valued functions
f:{0,1}^n\rightarrow [0,1] such that f can be approximated, to
within any epsilon>0, by a probabilistic Turing machine running in
time poly(n,1/epsilon). We argue that APP can be viewed as a
generalization of BPP, and show that APP contains a natural
complete ... more >>>

ISSN 1433-8092 | Imprint