Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOWER BONDS:
Reports tagged with lower bonds:
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 >>>




ISSN 1433-8092 | Imprint