Geodesic
On irreduceability of Boolean functions with respect to commutative associative operation
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 4 (2020), pp. 51-53 
G. V. Safonov; G. V. Bokov; V. B. Kudryavtsev. On irreduceability of Boolean functions with respect to commutative associative operation. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 4 (2020), pp. 51-53. http://geodesic.mathdoc.fr/item/VMUMM_2020_4_a6/
@article{VMUMM_2020_4_a6,
     author = {G. V. Safonov and G. V. Bokov and V. B. Kudryavtsev},
     title = {On irreduceability of {Boolean} functions with respect to commutative associative operation},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {51--53},
     year = {2020},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2020_4_a6/}
}
TY  - JOUR
AU  - G. V. Safonov
AU  - G. V. Bokov
AU  - V. B. Kudryavtsev
TI  - On irreduceability of Boolean functions with respect to commutative associative operation
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2020
SP  - 51
EP  - 53
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2020_4_a6/
LA  - ru
ID  - VMUMM_2020_4_a6
ER  - 
%0 Journal Article
%A G. V. Safonov
%A G. V. Bokov
%A V. B. Kudryavtsev
%T On irreduceability of Boolean functions with respect to commutative associative operation
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2020
%P 51-53
%N 4
%U http://geodesic.mathdoc.fr/item/VMUMM_2020_4_a6/
%G ru
%F VMUMM_2020_4_a6

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

The paper is focused on decomposition of Boolean functions on the form $f_1\circ\ldots\circ f_m$, where $\circ$ is a commutative associative operation and $f_1,\ldots,f_m$ are Boolean functions with fewer arguments. For each commutative associative operation, we define necessary and sufficient conditions for the absence of such a decomposition and find the related complexity class.

[1] Brzozowski J. A., Luba T., “Decomposition of Boolean functions specified by cubes”, J. Multiple Valued Logic and Soft Comput., 9 (2003), 377–417 | MR | Zbl

[2] Meier W., Pasalic E., Carlet C., “Algebraic attacks and decomposition of Boolean functions”, Advances in Cryptology — EUROCRYPT 2004, Lect. Notes Comput. Sci., 3027, Springer, Berlin, 2004, 474–491 | DOI | MR | Zbl

[3] Zhuk D. N., “Predikatnyi metod postroeniya reshetki Posta”, Diskretn. matem., 23:2 (2011), 115–128 | Zbl

[4] Cook S. A., “The complexity of theorem proving procedures”, Proc. Third Annual ACM Symposium on Theory of Computing, STOC'71, Association Comput. Machinery, N.Y., 1971, 151–158 | DOI | MR

[5] Levin L. A., “Universalnye zadachi perebora”, Probl. peredachi inform., 9:3 (1973), 115–116 | MR | Zbl

[6] Climent J. J., Garcia F. J., Requena V., “The degree of a Boolean function and some algebraic properties of its support”, Trans. Inform. and Commun. Technol., 45 (2013), 25–36

[7] Alon N., “Combinatorial Nullstellensatz”, Combin. Probab. and Comput., 8:1–2 (1999), 7–29 | DOI | MR | Zbl

[8] Chevalley C., “Démonstration d'une hypothèse de M. Artin”, Abh. Math. Semin. Univ. Hamburg, 11 (1936), 73–75 | DOI | MR

[9] Warning E., “Bemerkung zur vorstehenden Arbeit von Herrn Chevalley”, Abh. Math. Semin. Univ. Hamburg, 11 (1936), 76–83 | MR

[10] Papadimitriou C. H., Zachos S., “Two remarks on the power of counting”, Proc. 6th Conf. Theor. Comput. Sci., Lect. Notes Comput. Sci., 145, Springer, Berlin, 1983, 269–276 | DOI | MR

[11] Belovs A., Ivanyos G., Qiao Y., Santha M., Yang S., “On the polynomial parity argument complexity of the combinatorial Nullstellensatz”, Proc. 32nd Comput. Complex. Conf., CCC'17, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 30, Dagstuhl, 2017, 1–24 | MR