(with Ulrich Hertrampf),
Information and Computation Vol. 112
1994, pp. 217-238. (This material appeared in preliminary form in
the papers A Note on the Power of Threshold Circuits
1989, pp. 580-584), and On the Power of Uniform Families of
Constant-Depth Threshold Circuits
(MFCS 1990, LNCS 452, pp. 158-164.))
in Kolmogorov Complexity and
editor, EATCS Monograph Series, Springer-Verlag, 1992, pp. 4-22.
Earlier versions of this work appeared in
Proc. AAAI Spring Symposium on the Theory and Application
of Minimal-Length Encoding, and in a paper entitled The Generalized
Kolmogorov Complexity of Sets, in
4th IEEE Structure in Complexity Theory Conference, 1989.
Journal of Computer and System Sciences Vol. 39, 1989, 101-124.
Special issue on IEEE Structure in Complexity Theory Conference 1987
(whose proceedings contain an abstract of this paper).
An earlier version
appeared in Proc. 19th
STOC, 1987, pp.