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

TR96-037 | 14th June 1996
Stasys Jukna, Alexander Razborov

Neither Reading Few Bits Twice nor Reading Illegally Helps Much

We first consider so-called {\em $(1,+s)$-branching programs}
in which along every consistent path at most $s$ variables are tested
more than once. We prove that any such program computing a
characteristic function of a linear code $C$ has size at least
more >>>


TR96-036 | 28th May 1996
Petr Savicky, Stanislav Zak

A large lower bound for 1-branching programs

Revisions: 1

Branching programs (b.p.'s) or decision diagrams are a general
graph-based model of sequential computation. B.p.'s of polynomial
size are a nonuniform counterpart of LOG. Lower bounds for
different kinds of restricted b.p.'s are intensively investigated.
An important restriction are so called 1-b.p.'s, where each
computation reads each input bit at ... more >>>


TR96-035 | 27th March 1996
Ronald V. Book, Heribert Vollmer, Klaus W. Wagner

Probabilistic Type-2 Operators and ``Almost''-Classes


We define and examine several probabilistic operators ranging over sets
(i.e., operators of type 2), among them the formerly studied
ALMOST-operator. We compare their power and prove that they all coincide
for a wide variety of classes. As a consequence, we characterize the
ALMOST-operator which ranges over infinite objects ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint