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 Previous

TR94-021 | 12th December 1994
Lance Fortnow

My Favorite Ten Complexity Theorems of the Past Decade

We review the past ten years in computational complexity theory by
focusing on ten theorems that the author enjoyed the most. We use
each of the theorems as a springboard to discuss work done in
various areas of complexity theory.

more >>>

TR94-020 | 12th December 1994

Agnostic PAC-Learning of Functions on Analog Neural Nets

We consider learning on multi-layer neural nets with piecewise polynomial
activation functions and a fixed number k of numerical inputs. We exhibit
arbitrarily large network architectures for which efficient and provably
successful learning algorithms exist in the rather realistic refinement of
Valiant's model for probably approximately correct learning ("PAC-learning")
where ... more >>>


TR94-008 | 12th December 1994
Oded Goldreich

Probabilistic Proof Systems (A Survey)

Various types of probabilistic proof systems have played
a central role in the development of computer science in the last decade.
In this exposition, we concentrate on three such proof systems ---
interactive proofs, zero-knowledge proofs,
and probabilistic checkable proofs --- stressing the essential
role of randomness in each ... more >>>



previous Previous


ISSN 1433-8092 | Imprint