LOWER BOUNDS FOR COMPLEXITY OF PERCEPTRONS AND OTHER THRESHOLD CIRCUITS OF BOUNDED DEPTH
Professor Nikolai Vereshchagin, Moscow State University
(present address: LIP, ENS Lyon)

Abstract: First lower bounds for complexity of perceptrons were obtained by Minsky and Papert in the sixties. The recent interest in perceptrons is aroused by the fact that lower bounds for perceptrons help in constructing oracles separating different complexity classes from PP (probabilistic polynomial time). Threshold circuits of bounded depth form the smallest natural class for which there are no non-trivial lower bounds. The only known lower bounds are those for circuits of depth 2 and circuits with n^{o(1)} of majority gates.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 28 January 1998.

back