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

__
TR00-034
| 5th June 2000
__

Valentine Kabanets, Charles Rackoff, Stephen Cook#### Efficiently Approximable Real-Valued Functions

Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka

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

Valentine Kabanets, Charles Rackoff, Stephen Cook

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