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-050 | 23rd September 1996
Petr Savicky, Stanislav Zak

A hierarchy for (1,+k)-branching programs with respect to k

Branching programs (b.p.'s) or decision diagrams are a general
graph-based model of sequential computation. The 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 $k$-b.p.'s,
where each computation reads each input ... more >>>


TR96-049 | 9th September 1996
Per Enflo, Meera Sitharam

Stable basis families and complexity lower bounds

--
Scalar product estimates have so far been used in
proving several unweighted threshold lower bounds.
We show that if a basis set of Boolean functions satisfies
certain weak stability conditions, then
scalar product estimates
yield lower bounds for the size of weighted thresholds
of these basis functions.
Stable ... more >>>


TR96-048 | 12th September 1996
Eric Allender, Klaus-Joern Lange

StUSPACE(log n) is Contained in DSPACE((log^2 n)/loglog n)

We present a deterministic algorithm running in space
O((log^2 n)/loglog n) solving the connectivity problem
on strongly unambiguous graphs. In addition, we present
an O(log n) time-bounded algorithm for this problem
running on a parallel pointer machine.

more >>>


previous PreviousNext next


ISSN 1433-8092 | Imprint