A note on the power of threshold circuits
Eric Allender · 1989
The author presents a very simple proof of the fact that any language accepted by polynomial-size depth-k unbounded-fan-in circuits of AND and OR gates is accepted by depth-three threshold circuits of size n raised to the power O(log/sup k/n). The proof uses much of the intuition of S. Toda's result that the polynomial hierarchy is contained in P/sup Hash P/ (30th Ann. Symp. Foundations Comput. Sci., p.514-519, 1989).>