An introduction to boolean function complexity
Journées algorithmiques, Astérisque, no. 38-39 (1976), p. 183-201
@incollection{AST_1976__38-39__183_0,
author = {Paterson, Michael S.},
title = {An introduction to boolean function complexity},
booktitle = {Journ\'ees algorithmiques},
author = {Collectif},
series = {Ast\'erisque},
publisher = {Soci\'et\'e math\'ematique de France},
number = {38-39},
year = {1976},
pages = {183-201},
zbl = {0348.94043},
mrnumber = {443433},
language = {en},
url = {http://www.numdam.org/item/AST_1976__38-39__183_0}
}

Paterson, Michael S. An introduction to boolean function complexity, in Journées algorithmiques, Astérisque, no. 38-39 (1976), pp. 183-201. http://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 135213

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

[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 0381.94028

[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. | Article | MR 416108 | Zbl 0322.68027

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

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

[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 238668 | Zbl 0191.28502

[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. | Article | MR 378476 | Zbl 0366.68041

[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 | MR 208813 | Zbl 0208.40102

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

[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 0301.02016

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

[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 126385

[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 453331 | Zbl 0361.94051

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

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

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

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

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

[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 433982 | Zbl 0363.68067

[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 462795 | Zbl 0364.94031

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

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

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

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

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

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

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

[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. | Article | Zbl 0217.53802

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

[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).