Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Average-Case Analysis:
TR97-058 | 2nd December 1997
Oded Goldreich

Notes on Levin's Theory of Average-Case Complexity.

In 1984, Leonid Levin has initiated a theory of average-case complexity.
We provide an exposition of the basic definitions suggested by Levin,
and discuss some of the considerations underlying these definitions.

more >>>

TR04-038 | 27th April 2004
John Case, Sanjay Jain, RĂ¼diger Reischuk, Frank Stephan, Thomas Zeugmann

A Polynomial Time Learner for a Subclass of Regular Patterns

Presented is an algorithm (for learning a subclass of erasing regular
pattern languages) which
can be made to run with arbitrarily high probability of
success on extended regular languages generated by patterns
$\pi$ of the form $x_0 \alpha_1 x_1 ... \alpha_m x_m$
for unknown $m$ but known $c$,
more >>>

ISSN 1433-8092 | Imprint