A method for obtaining efficient lower bounds for monotone complexity

A. A. Markov, "On the minimal contact-valve two-terminal networks for monotone symmetric functions," Probl. Kibern.,8, 117–112 (1962).

E. I. Nechiporuk, "On a certain Boolean matrix," Probl. Kibern.,21, 237–240 (1969).

E. I. Nechiporuk, "On the realization of disjunction and conjunction in certain monotone bases," Probl. Kibern.,23, 291–293 (1970).

M. S. Paterson, "Complexity of monotone networks for Boolean matrix product," Theor. Comput. Sci.,1, 13–20 (1975).

V. R. Pratt, "The effect of basis on size of Boolean expressions," in: Proc. 16th Annual Symposium on Foundations of Computer Science (Berkeley, Calif., 1975), IEEE Computer Society, Long Beach, Calif. (1975), pp. 119–121.

N. Pippenger, On Another Boolean Matrix. IBM Research Report RC-6914 (1977).

K. Mehlhorn and Z. Galil, "Monotone switching circuits and Boolean matrix product," Computing,16, 99–111 (1976).

K. Mehlhorn, "Some remarks on Boolean sums," Acta Inform.,12, 371–375 (1979).

I. Wegener, "Switching functions whose monotone complexity is nearly quadratic," Theor. Comput. Sci.,9, 83–97 (1979).

E. A. Okol'nishnikova, "A monotone Boolean system with quadratic complexity of realization in the basis {&, V,0, 1}," Diskretnyi Abaliz,41, 81–98 (1984).

A. E. Andreev, "On a method for obtaining lower bounds for the complexity of individual monotone functions," Preprint No. 248, Inst. Probl. Mekh. Akad. Nauk SSSR and Moskov. Gos. Univ. (1985).

A. E. Andreev, "On a method for obtaining lower bounds for the complexity of individual monotone functions," Dokl. Akad. Nauk SSSR,282, No. 5, 1033–1037 (1985).

A. A. Razborov, "Lower bounds for the monotone complexity of certain Boolean functions," Dokl. Akad. Nauk SSSR,281, No. 4, 798–801 (1985).

A. A. Razborov, "Lower bounds on the monotone complexity of the logical permanent," Mat. Zametki,37, No. 6, 877–900 (1985).

O. B. Lupanov, "On the synthesis of certain classes of control systems," Probl. Kibern.,10, 63–97 (1963).

O. B. Lupanov, "On methods for obtaining estimates of the complexity of defining and computing individual functions," Diskretnyi Analiz, No. 25, 3–18 (1974).

S. V. Yablonskii and O. B. Lupanov (eds.), Discrete Mathematics and Mathematical Questions of Cybernetics [in Russian], Nauka, Moscow (1974).