Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with computation complexity:
TR01-037 | 21st February 2001
Rustam Mubarakzjanov

Bounded-Width Probabilistic OBDDs and Read-Once Branching Programs are Incomparable

Restricted branching programs are considered by the investigation
of relationships between complexity classes of Boolean functions.
Read-once ordered branching programs (or OBDDs) form the most restricted class
of this computation model.
Since the problem of proving exponential lower bounds on the complexity
for general probabilistic OBDDs is open so ... more >>>

TR22-134 | 23rd September 2022
Greg McLellan, Alexey Milovanov

Some Games on Turing Machines and Power from Random Strings

Revisions: 1

Denote by $R$ the set of strings with high Kolmogorov complexity. In [E. Allender, H. Buhrman, M. Kouck\'y, D. van Melkebeek, and D. Ronneburger.
Power from random strings.
\emph{SIAM Journal on Computing}, 35:1467--1493, 2006.] the idea of using $R$ as an oracle for resource-bounded computation models was presented. This idea ... more >>>

ISSN 1433-8092 | Imprint