Geodesic
Sufficient conditions for the minimal $\pi$-schemes for linear Boolean functions to be locally non-repeating
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 5, pp. 71-85.

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

We formulate sufficient conditions for the minimal $\pi$-schemes for linear Boolean functions to be locally non-repeating. The validity of these conditions gives a description of the classes of all minimal $\pi$-schemes for linear Boolean functions which depend essentially on n variables. Ill. 2, bibliogr. 12.
Keywords: formula size, $\pi$-scheme, lower bound on the complexity. 
@article{DA_2015_22_5_a3,
     author = {K. L. Rychkov},
     title = {Sufficient conditions for the minimal $\pi$-schemes for linear {Boolean} functions to be locally non-repeating},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {71--85},
     publisher = {mathdoc},
     volume = {22},
     number = {5},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_5_a3/}
}
TY  - JOUR
AU  - K. L. Rychkov
TI  - Sufficient conditions for the minimal $\pi$-schemes for linear Boolean functions to be locally non-repeating
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 71
EP  - 85
VL  - 22
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_5_a3/
LA  - ru
ID  - DA_2015_22_5_a3
ER  - 
%0 Journal Article
%A K. L. Rychkov
%T Sufficient conditions for the minimal $\pi$-schemes for linear Boolean functions to be locally non-repeating
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 71-85
%V 22
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_5_a3/
%G ru
%F DA_2015_22_5_a3
K. L. Rychkov. Sufficient conditions for the minimal $\pi$-schemes for linear Boolean functions to be locally non-repeating. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 5, pp. 71-85. http://geodesic.mathdoc.fr/item/DA_2015_22_5_a3/

[1] 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, Discrete Analysis, 42, Izd. Inst. Mat., Novosibirsk, 1985, 91–98 | MR | Zbl

[2] K. L. Rychkov, “On minimal $\pi$-schemes for linear Boolean functions”, Sib. Adv. Math., 3:3 (1993), 172–185 | MR | MR | Zbl | Zbl

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

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

[5] 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 | DOI | MR | Zbl | Zbl

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

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

[8] 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 | MR

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

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

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

[12] Wegener I., The complexity of Boolean functions, Wiley, Chichester, 1987, 458 pp. | MR | Zbl