Majority gates vs. general weighted threshold gates
Tóm tắt
In this paper we study small depth circuits that contain threshold gates (with or without weights) and parity gates. All circuits we consider are of polynomial size. We prove several results which complete the work on characterizing possible inclusions between many classes defined by small depth circuits. These results are the following:
Tài liệu tham khảo
E. Allender, A note on the power of threshold circuts, inProceedings of the 30th IEEE Symposium on Foundations of Computer Science, 1989, 580–584.
J. Bruck, Harmonic analysis of polynomial threshold functions,SIAM Journal on Discrete Mathematics 3(2) (1990), 168–177.
J. Bruck and R. Smolensky, Polynomial threshold functions,AC 0 functions and spectral norms, inProceedings of the 31st IEEE Symposium on Foundations of Computer Science, 1990, 632–641.
Y. Freund, Boosting a weak learning algorithm by majority, inWorkshop on Computational Learning Theory, Morgan Kaufmann, 1990, 202–216.
M. Goldmann and M. Karpinski, Constructing depthd+1 majority circuits that simulate depthd threshold circuits, manuscript, 1992.
A. Hajnal, W. Maass, P. Pudlák, M. Szegedy, and G. Turán, Threshold circuits of bounded depth, inProceedings of 28 IEEE Symposium on Foundations of Computer Science, 1987, 99–110.
J. Håstad and M. Goldmann, On the power of small-depth threshold circuits, inProceedings of the 31st IEEE Symposium on Foundations of Computer Science, 1990, 610–618.
J. Hertz, R. Krogh, and A. Palmer,An Introduction to the Theory of Neural Computation, Addison-Wesley, 1991.
M. Hofri,Probabilistic Analysis of Algorithms, Springer-Verlag, 1987.
M. Krause, Geometric arguments yield better bounds for threshold circuits and distributed computing, inProceedings of the 6th Structure in Complexity Theory Conference, 1991, 314–322.
M. Krause and S. Waack, Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fanin, inProceedings of the 32nd IEEE Symposium on Foundations of Computer Science, 1991, 777–782.
W. Maass, G. Schnitger, and E. Sontag, On the computational power of sigmoid versus boolean threshold circuits, inProceedings of the 32nd IEEE Symposium on Foundations of Computer Science, 1991, 767–776.
S. Muroga,Threshold logic and its applications, Wiley-Interscience, 1971.
J. Myhill andW. H. Kautz, On the size of weights required for linear-input switching functions,IRE Trans. on Electronic Computers EC10(2) (1961), 288–290.
G. Owen,Game theory, Academic press, second edition, 1982.
K.-Y. Siu andJ. Bruck, On the power of threshold circuits with small weights,SIAM Journal on Discrete Mathematics 4(3) (1991) 423–435.
K.-Y. Siu and V. Roychowdhury, On optimal depth threshold circuits for multiplication and related problems, manuscript, 1992.
S. Toda, On the computational power ofPP and ⊗P, inProceedings of the 30th IEEE Symposium on Foundations of Computer Science, 1989, 514–519.
A. Yao, Some complexity questions related to distributive computing, inProceedings of the 11th ACM Symposium on Theory of Computing, 1979, 209–213.
A. Yao, Lower bounds by probabilistic arguments, inProceedings of the 24th IEEE Symposium on Foundations of Computer Science, 1983, 420–428.
A. Yao, Circuits and local computation, inProceedings of the 21st ACM Symposium on Theory of Computing, 1989, 186–196.
A. Yao, OnACC and threshold circuits, inProceedings of the 31st IEEE Symposium on Foundations of Computer Science, 1990, 619–627.