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

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

TR97-057 | 3rd November 1997
Petr Savicky

Complexity and Probability of some Boolean Formulas

For any Boolean function $f$ let $L(f)$ be its formula size
complexity in the basis $\{\land,\oplus,1\}$. For every $n$ and
every $k\le n/2$, we describe a probabilistic distribution
on formulas in the basis $\{\land,\oplus,1\}$ in some given set of
$n$ variables and of the ... more >>>


TR97-056 | 1st December 1997
Oded Goldreich

Combinatorial Property Testing (a survey).

Comments: 1

We consider the question of determining whether
a given object has a predetermined property or is ``far'' from any
object having the property.
Specifically, objects are modeled by functions,
and distance between functions is measured as the fraction
of the domain on which the functions differ.
We ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint