Geodesic
Complexity of the realization of a~linear Boolean function in the class of $\pi$-schemes
Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 3, pp. 36-94.

Voir la notice de l'article provenant de la source Math-Net.Ru

Using Khrapchenko's method, we obtain the exact lower bound of 40 for the complexity in the class of $\pi$-schemes of a linear Boolean function depending substantially on 6 variables. We give a simplified proof of several lower bounds for the complexity of linear Boolean functions which are previously obtained on the basis of the same method. Bibliogr. 18.
Keywords: Boolean function, $\pi$-scheme, lower complexity bound. 
@article{DA_2018_25_3_a2,
     author = {K. L. Rychkov},
     title = {Complexity of the realization of a~linear {Boolean} function in the class of $\pi$-schemes},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {36--94},
     publisher = {mathdoc},
     volume = {25},
     number = {3},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2018_25_3_a2/}
}
TY  - JOUR
AU  - K. L. Rychkov
TI  - Complexity of the realization of a~linear Boolean function in the class of $\pi$-schemes
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2018
SP  - 36
EP  - 94
VL  - 25
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2018_25_3_a2/
LA  - ru
ID  - DA_2018_25_3_a2
ER  - 
%0 Journal Article
%A K. L. Rychkov
%T Complexity of the realization of a~linear Boolean function in the class of $\pi$-schemes
%J Diskretnyj analiz i issledovanie operacij
%D 2018
%P 36-94
%V 25
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2018_25_3_a2/
%G ru
%F DA_2018_25_3_a2
K. L. Rychkov. Complexity of the realization of a~linear Boolean function in the class of $\pi$-schemes. Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 3, pp. 36-94. http://geodesic.mathdoc.fr/item/DA_2018_25_3_a2/

[1] S. V. Avgustinovich, Yu. L. Vasil'ev, K. L. Rychkov, “The computation complexity in the class of formulas”, J. Appl. Ind. Math., 6:4 (2012), 403–409 | DOI | MR | Zbl

[2] Yu. L. Vasil'ev, K. L. Rychkov, “A lower bound on formula size of a ternary linear function”, J. Appl. Ind. Math., 7:4 (2013), 490–499 | MR | Zbl

[3] K. L. Rychkov, “A modification of Khrapchenko's method and its application to estimation of complexity of $\pi$-schemes for code functions”, Methods of Discrete Analysis in Theory of Graphs and Schemes, 42, Izd. Inst. Mat., Novosibirsk, 1985, 91–98 (Russian) | Zbl

[4] K. L. Rychkov, “On the lower bounds for the complexity of serial-parallel contact circuits realizing linear Boolean functions”, Discrete Analysis and Operations Research, Math. Its Appl., 355, Kluwer Acad. Publ., Dordrecht, 1996, 217–234 | MR | Zbl

[5] K. L. Rychkov, “Lower bounds on the formula complexity of a linear Boolean function”, Sib. Elektron. Mat. Izv., 11 (2014), 165–184 (Russian) | Zbl

[6] K. L. Rychkov, “Sufficient conditions for the minimal $\pi$-schemes for linear Boolean functions to be locally non-repeating”, Diskretn. Anal. Issled. Oper., 22:5 (2015), 71–85 (Russian) | DOI | MR | Zbl

[7] B. A. Subbotovskaya, “Realization of linear functions by formulas using $\vee,\,^-$”, Sov. Math. Dokl., 2 (1961), 110–112 | MR | Zbl

[8] V. M. Khrapchenko, “Complexity of the realization of a linear function in the class of $\Pi$-circuits”, Math. Notes Acad. Sci. USSR, 9:1 (1971), 21–23 | MR | Zbl | Zbl

[9] V. M. Khrapchenko, “A method of determining lower bounds for the complexity of $\Pi$-schemes”, Math. Notes Acad. Sci. USSR, 10:1 (1971), 474–479 | MR | Zbl

[10] D. Yu. Cherukhin, “To the question of a logical representation for the parity counter”, Neform. Nauka, 2009, no. 2, 14–23 (Russian)

[11] S. V. Yablonskii, “Realization of a linear function in the class of $\Pi$-circuits”, Dokl. Akad. Nauk SSSR Nov. Ser., 94:5 (1954), 805–806 (Russian) | MR

[12] Harary F., Graph theory, Addison-Wesley, Reading, MA, 1969, 273 pp. | MR | Zbl

[13] Håstad J., “The shrinkage exponent of de Morgan formulae is 2”, SIAM J. Comput., 27:1 (1998), 48–64 | DOI | MR

[14] Karchmer M., Wigderson A., “Monotone circuits for connectivity require super-logarithmics depth”, SIAM J. Discrete Math., 3:2 (1990), 255–265 | DOI | MR | Zbl

[15] Lee T., “A new rank technique for formula size lower bounds”, Proc. 24th Annu. Symp. Theoretical Aspects of Computer Science (Aachen, Germany, Feb. 22–24, 2007), Lect. Notes Comput. Sci., 4393, Springer-Verl., Heidelberg, 2007, 145–156 | DOI | MR | Zbl

[16] Razborov A., “Applications of matrix methods to the theory of lower bounds in computational complexity”, Combinatorica, 10:1 (1990), 81–93 | DOI | MR | Zbl

[17] Turán P., “Eine Extremalaufgabe aus der Graphentheorie”, Mat. Fiz. Lapok, 48:1 (1941), 436–452 | MR | Zbl

[18] Wegener I., The complexity of Boolean functions, Wiley, Chichester, UK, 1987 | MR | Zbl