Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR97-023 | 3rd June 1997
S. Jukna, A. Razborov, Petr Savicky, Ingo Wegener

On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs

It is known that if a Boolean function f in n variables
has a DNF and a CNF of size at most N then f also has a
(deterministic) decision tree of size $\exp(O(\log n\log^2 N)$.
We show that this simulation {\em cannot} be ... more >>>


TR97-021 | 16th May 1997
Farid Ablayev

Randomization and nondeterminsm are incomparable for ordered read-once branching programs


In the manuscript F. Ablayev and M. Karpinski, On the power of
randomized branching programs (generalization of ICALP'96 paper
results for the case of pure boolean function, available at
http://www.ksu.ru/~ablayev) we exhibited a simple boolean functions
$f_n$ in $n$ variables such that:

1) $f_{n}$ can be computed ... more >>>


TR97-020 | 15th May 1997
Oded Goldreich

A Sample of Samplers -- A Computational Perspective on Sampling (survey).


We consider the problem of estimating the average of a huge set of values.
That is,
given oracle access to an arbitrary function $f:\{0,1\}^n\mapsto[0,1]$,
we need to estimate $2^{-n} \sum_{x\in\{0,1\}^n} f(x)$
upto an additive error of $\epsilon$.
We are allowed to employ a randomized algorithm which may ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint