Oded Goldreich

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.

John Case, Sanjay Jain, RĂ¼diger Reischuk, Frank Stephan, Thomas Zeugmann

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 >>>