ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > PROBABILISTIC COMPUTATION:
Reports tagged with probabilistic computation:
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 far, ... more >>>

TR02-058 | 25th September 2002
Philippe Moser

A generalization of Lutz's measure to probabilistic classes

We extend Lutz's measure to probabilistic classes, and obtain notions of measure on probabilistic complexity classes C such as BPP , BPE and BPEXP. Unlike former attempts, all our measure notions satisfy all three Lutz's measure axioms, that is every singleton {L} has measure zero in C, the whole space ... more >>>



ISSN 1433-8092 | Imprint