×

zbMATH — the first resource for mathematics

Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. (English. Russian original) Zbl 0632.94030
Math. Notes 41, 333-338 (1987); translation from Mat. Zametki 41, No. 4, 598-607 (1987).
Lower bounds for bounded depth circuits over \(\{\) &,\(\vee,\oplus \}\) are given using a special structure of families of Boolean functions called regular models. The construction of bounded degree is described. These models are then used to deduce exponential lower bounds in the basis \(\{\) &,\(\oplus \}\), and it is shown that they also hold in the basis \(\{\) &,\(\vee,\oplus \}\).
Reviewer: L.Livovschi

MSC:
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] N. Blum, ?Boolean functions requiring 3n network size,? Theor. Comput. Sci.,28, 337-345 (1984). · Zbl 0539.94036
[2] M. Furst, J. B. Saxe, and M. Sipser, ?Parity, circuits, and the polynomial time hierarchy,? Proc. 22nd Ann. IEEE Symp. on Foundations of Computer Sci. (1981), pp. 260-270. · Zbl 0534.94008
[3] M. Furst, J. B. Saxe, and M. Sipser, ?Parity, circuits, and the polynomial time hierarchy,? Math. Syst. Theory,17, 13-27 (1984). · Zbl 0534.94008
[4] M. Ajtai, ??1 1 formulas on finite structures,? Ann. Pure Appl. Logic,24, 1-48 (1983). · Zbl 0519.03021
[5] L. G. Valiant, ?Exponential lower bounds for restricted monotone circuits,? Proc. 15th Ann. ACM Symp. on Theory of Comp. (1983), pp. 110-187.
[6] R. Boppana, ?Threshold functions and bounded depth monotone circuits,? Proc. 16th Ann. ACM Symp. on Theory of Comp. (1984), pp. 475-479.
[7] M. Klaw, W. Paul, N. Pippenger, and M. Yannakakis, ?On monotone formulas with restricted depth,? Proc. 16th Ann. ACM Symp. on Theory of Comp. (1984), pp. 475-479.
[8] A. Yao, ?Separating the polynomial-time hierarchy by oracles,? Proc. 26th Ann. IEEE Symp. on Foundations of Computer Science (1985), pp. 1-10.
[9] J. Hastad, ?Almost-optimal lower bounds for small depth circuits,? Preprint (1985).
[10] A. A. Razborov, ?Lower bounds on monotone complexity of some Boolean functions,? Dokl. Akad. Nauk SSSR,281, No. 4, 789-801 (1985). · Zbl 0621.94027
[11] A. A. Razborov, ?Lower bounds on monotone complexity of a logical permanent,? Mat. Zametki,37, No. 6, 887-900 (1985).
[12] A. E. Andreev, ?On a method of obtaining lower complexity bounds of individual monotone functions,? Dokl. Akad. Nauk SSSR,282, No. 5, 1033-1037 (1985). · Zbl 0616.94019
[13] N. Alon and R. B. Boppana, ?The monotone circuit complexity of Boolean functions,? Preprint (1985). · Zbl 0631.68041
[14] D. Yu. Grigor’ev, ?Lower bounds for algebraic complexity of computations,? Computational Complexity Theory, I [in Russian], Zapiski LOMI, Vol. 188, Nauka, Leningrad (1982).
[15] A. A. Razborov, ?Lower bounds on the size of bounded depth circuits over the basis { &, ?, ?},? Usp. Math. Nauk,41, No.4, 219-220 (1986). · Zbl 0615.94012
[16] R. Smolensky, ?Algebraic methods in the theory of lower bounds for Boolean circuit complexity,? Preprint, Univ. of California, Berkeley (1986).
[17] M. Paterson, ?Bounded depth circuits over {+, ?},? Preprint, Univ. of Warwick (1986).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.