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

TR95-022 | 2nd May 1995
Marek Karpinski, Wojciech Rytter, Ayumi Shinohara

Pattern-Matching for Strings with Short Descriptions

We consider strings which are succinctly described. The description
is in terms of straight-line programs in which the constants are
symbols and the only operation is the concatenation. Such
descriptions correspond to the systems of recurrences or to
context-free grammars generating single words. The descriptive ... more >>>


TR95-021 | 20th April 1995
Marek Karpinski, Rutger Verbeek

On Randomized Versus Deterministic Computation

In contrast to deterministic or nondeterministic computation, it is
a fundamental open problem in randomized computation how to separate
different randomized time classes (at this point we do not even know
how to separate linear randomized time from ${\mathcal O}(n^{\log n})$
randomized time) or how to ... more >>>


TR95-020 | 8th March 1995
William Hurwood

Dynamic Fault Diagnosis

We consider a dynamic fault diagnosis problem: There are n
processors, to be tested in a series of rounds. In every
testing round we use a directed matching to have some
processors report on the status (good or faulty) of other
processors. Also in each round ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint