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



REPORTS > KEYWORD > READ-ONCE BRANCHING PROGRAM:
Reports tagged with read-once branching program:
TR98-018 | 27th March 1998
Martin Sauerhoff

Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs

Comments: 1
We extend the tools for proving lower bounds for randomized branching programs by presenting a new technique for the read-once case which is applicable to a large class of functions. This technique fills the gap between simple methods only applicable for OBDDs and the well-known "rectangle technique" of Borodin, Razborov ... more >>>



ISSN 1433-8092 | Imprint