An introduction to boolean function complexity
Journées algorithmiques, Astérisque, no. 38-39 (1976), pp. 183-201 
@incollection{AST_1976__38-39__183_0,
     author = {Paterson, Michael S.},
     title = {An introduction to boolean function complexity},
     booktitle = {Journ\'ees algorithmiques},
     series = {Ast\'erisque},
     pages = {183--201},
     year = {1976},
     publisher = {Soci\'et\'e math\'ematique de France},
     number = {38-39},
     mrnumber = {443433},
     zbl = {0348.94043},
     language = {en},
     url = {https://www.numdam.org/item/AST_1976__38-39__183_0/}
}
TY  - CHAP
AU  - Paterson, Michael S.
TI  - An introduction to boolean function complexity
BT  - Journées algorithmiques
AU  - Collectif
T3  - Astérisque
PY  - 1976
SP  - 183
EP  - 201
IS  - 38-39
PB  - Société mathématique de France
UR  - https://www.numdam.org/item/AST_1976__38-39__183_0/
LA  - en
ID  - AST_1976__38-39__183_0
ER  - 
%0 Book Section
%A Paterson, Michael S.
%T An introduction to boolean function complexity
%B Journées algorithmiques
%A Collectif
%S Astérisque
%D 1976
%P 183-201
%N 38-39
%I Société mathématique de France
%U https://www.numdam.org/item/AST_1976__38-39__183_0/
%G en
%F AST_1976__38-39__183_0
Paterson, Michael S. An introduction to boolean function complexity, dans Journées algorithmiques, Astérisque, no. 38-39 (1976), pp. 183-201. https://www.numdam.org/item/AST_1976__38-39__183_0/

[1] A. Avizienis. "Signed-digit number representation for fast parallel arithmetic," IRE Trans EC-10, 9, 389-400. | MR

[2] A. Ehrenfeucht. "Practical decidability," Report CU-CS-008-72 University of Colorado (1972). | Zbl

[3] M. J. Fischer, A. R. Meyer and M. S. Paterson. "Lower bounds on the size of Boolean formulas : preliminary report," Proc. 7th Ann. ACM Symp. on Th. of Computing (1975), 45-49. | Zbl

[4] L. H. Harper, W. N. Hsieh and J. E. Savage. "A class of Boolean functions with linear combinational complexity," Theoretical Computer Science, 1, 2, 161-183. | MR | Zbl | DOI

[5] L. H. Harper and J. E. Savage. "On the complexity of the marriage problem," Advances in Mathematics 9, 3 (1972), 299-312. | MR | Zbl | DOI

[6] L. Hodes. "The logical complexity of geometric properties in the plane," J. ACM 17, 2 (1970), 339-347. | MR | Zbl | DOI

[7] L. Hodes and E. Specker. "Lengths of formulas and elimination of quantifiers I," in Contributions to Mathematical Logic, K. Schutte, ed., North Holland Publ. Co., (1968), 175-188. | MR | Zbl

[8] R. M. Karp. "Reducibility among combinatorial problems," in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York (1972), 85-103. | MR | Zbl | DOI

[9] B. M. Kloss. "Estimates of the complexity of solutions of systems of linear equations," Eng. trans. in Soviet Math Dokl. 7, 6 (1966), 1537-1540 | Zbl | MR

B. M. Kloss. "Estimates of the complexity of solutions of systems of linear equations," orig. Dokl. Akad. Nauk SSSR, 171, 4, 781-783. | MR | Zbl

[10] V. M. Krapchenko. "The complexity of the realization of symmetrical functions by formulae," English translation in Math. Notes of the Academy of Sciences of the USSR (1972), 70-76 | Zbl

V. M. Krapchenko. "The complexity of the realization of symmetrical functions by formulae," orig. in Matem. Zametki 11, 1, 109-120. | MR | Zbl

[11] O. B. Lupanov. "Ob odnom metode sinteza skhem," Izv. VUZ (Radiofizika)1, 1 (1958), 120-140.

[12] O. B. Lupanov. "Complexity of formula realization of functions of logical algebra," Prob. Cyb. 3, (1962), 782-811

O. B. Lupanov. "Complexity of formula realization of functions of logical algebra," orig. Prob. Kibernetiki 3, 61-80. | MR

[13] W. F. Mccoll and M. S. Paterson. "The depth of all Boolean functions," Th. of Computation Report 7, Univ. of Warwick (1975). To appear in SIAM J. on Computing. | MR | Zbl

[14] D. E. Muller and F. P. Preparata. "Bounds to complexities of networks for sorting and switching," J. ACM22, 2 (1975), 195-201. | MR | Zbl

[15] E. I. Neciporuk. "A Boolean function," Soviet Math. Dokl. 7, 4 (1966), 999-1000 | Zbl

[15] E. I. Neciporuk. "A Boolean function", orig. Dokl. Akad. Nauk SSSR 169, 4, 765-766. | MR | Zbl

[16] M. S. Paterson and L. G. Valiant. "Circuit size is nonlinear in depth," Th. of Computation Report 8, Univ. of Warwick (1975). | Zbl | MR

M. S. Paterson and L. G. Valiant. "Circuit size is nonlinear in depth," To appear in Theoretical Computer Science. | MR | Zbl

[17] W. Paul. "A 2.5 N lower bound for the combinational complexity of Boolean functions," Proc. 7th Ann. ACM Symp. on Th. of Comp. Albuquerque (1975), 27-36. | MR | Zbl

[18] N. Pippenger. "Short formulae for symmetric functions," IBM Research Report RC-5143, (1974), 15 pp.

[19] N. Pippenger. "Information theory and the complexity of Boolean functions," submitted to Math. Systems Theory, (1976). | MR | Zbl

[20] N. Pippenger and M. J. Fischer. "Relations among complexity measures," in preparation. | Zbl | DOI

[21] J. Riordan and C. E. Shannon. "The number of two-terminal seriesparallel networks," J. Math. and Physics 21 (1942), 83-93. | MR | DOI

[22] J. E. Savage. The Complexity of Computing (manuscript). | Zbl

[23] J. E. Savage. "Computational work and time on finite machines", J. ACM 19, 4 (1972), 660-674. | MR | Zbl | DOI

[24] C. P. Schnorr. "Zwei lineare untere Schranken fuer die Komplexitaet Boolescher Funktionen," Computing 13 (1974), 155-171. | MR | Zbl | DOI

[25] C. P. Schnorr. "The combinational complexity of equivalence," to appear in Theoretical Computer Science 2. | Zbl | MR

[26] C. E. Shannon. "The synthesis of two-terminal switching circuits," Bell System Technical Journal 28 (1949), 59-98. | MR | DOI

[27] P. M. Spira. "On time-hardware complexity tradeoffs for Boolean functions," Proc. 4th Hawaii Int. Symp. on System Sciences (1971), 525-527.

[28] P. M. Spira. "On the time necessary to compute switching functions," IEEE Trans. Computers C-20 (1971), 104-105. | Zbl | DOI

[29] L. J. Stockmeyer. "On the combinational complexity of certain symmetric Boolean functions," IBM Research RC 5829 Math. (1976). | Zbl | MR | DOI

[30] L. J. Stockmeyer and A. R. Meyer. "Inherent computational complexity of decision problems in logic and automata Theory." To appear in the series : Lecture Notes in Computer Science, Springer (1977)

[30] L. J. Stockmeyer and A. R. Meyer An earlier version of this appears as : "The complexity of decision problems in automata theory and logic," by L. J. Stockmeyer, MAC TR 133, M.I.T. (1974).