6th Conference on Computability in Europe (CiE 2010),
Centre for Applied Mathematics and Information Technology,
Dept. of Mathematics, University of Azores, pp. 1--5, 2010.
(with Jia Jiao, Meena
Mahajan, and
V. Vinay),
Theoretical Computer Science Vol. 209, 1998, 47-86.
[NOTE:The proof of Theorem 7.12 is incorrect. See the discussion
of this here.]
This is a
revision and extension of
the paper Depth reduction for noncommutative arithmetic
circuits (with Jia Jiao), in Proc. 25th
STOC 1993, pp.
515-522.
(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
(FOCS
1989, pp. 580-584), and On the Power of Uniform Families of
Constant-Depth Threshold Circuits
(MFCS 1990, Lecture
Notes in Computer Science 452, pp. 158-164.))
in Kolmogorov Complexity and
Computational Complexity,
Osamu Watanabe,
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
Proc.
4th IEEE Structure in Complexity Theory Conference, 1989.
(with Osamu
Watanabe),
Information and Computation Vol. 86
1990, pp. 160-178.
An earlier version appeared in
Proc. 3rd IEEE Structure in Complexity Theory Conference, 1988.
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.
151-159.