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