Geodesic
Multiaffine polynomials over a finite field
Diskretnaya Matematika, Tome 32 (2020) no. 3, pp. 85-97.

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

We consider polynomials $f(x_1, \ldots, x_n)$ over a finite field that possess the following property: for some element $b$ of the field the set of solutions of the equation $f(x_1, \ldots, x_n) = b$ coincides with the set of solutions of some system of linear equations over this field. Such polynomials are said to be multiaffine with respect to the right-hand side $b$. We obtain the properties of multiaffine polynomials over a finite field. Then we show that checking the multiaffinity with respect to a given right-hand side may be done by an algorithm with polynomial (in terms of the number of variables and summands of the input polynomial) complexity. Besides that, we prove that in case of the positive decision a corresponding system of linear equations may be recovered with complexity which is also polynomial in terms of the same parameters.
Keywords: finite field, polynomial, multiaffinity, system of linear equations over a finite field, algorithm, complexity, polynomial algorithm. 
@article{DM_2020_32_3_a6,
     author = {S. N. Selezneva},
     title = {Multiaffine polynomials over a finite field},
     journal = {Diskretnaya Matematika},
     pages = {85--97},
     publisher = {mathdoc},
     volume = {32},
     number = {3},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2020_32_3_a6/}
}
TY  - JOUR
AU  - S. N. Selezneva
TI  - Multiaffine polynomials over a finite field
JO  - Diskretnaya Matematika
PY  - 2020
SP  - 85
EP  - 97
VL  - 32
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2020_32_3_a6/
LA  - ru
ID  - DM_2020_32_3_a6
ER  - 
%0 Journal Article
%A S. N. Selezneva
%T Multiaffine polynomials over a finite field
%J Diskretnaya Matematika
%D 2020
%P 85-97
%V 32
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2020_32_3_a6/
%G ru
%F DM_2020_32_3_a6
S. N. Selezneva. Multiaffine polynomials over a finite field. Diskretnaya Matematika, Tome 32 (2020) no. 3, pp. 85-97. http://geodesic.mathdoc.fr/item/DM_2020_32_3_a6/

[1] Gorshkov S. P., “O slozhnosti raspoznavaniya multiaffinnosti, biyunktivnosti, slaboi polozhitelnosti i slaboi otritsatelnosti”, Obozr. promyshl. i prikl. matem., 4:2 (1997), 216–237

[2] Creignou N., Khanna S., Sudan M., Complexity classifications of Boolean constraint satisfaction problems, SIAM, 2001, xii+100 pp. | MR | Zbl

[3] Gorshkov S. P., Tarasov A. V., Slozhnost resheniya sistem bulevykh uravnenii, Kurs, M., 2017, 192 pp.

[4] Logachev O. A., Sukaev A. A., Fedorov S. N., “Ob odnom metode resheniya sistem kvadratichnykh bulevykh uravnenii, ispolzuyuschem lokalnye affinnosti”, Informatika i ee primen., 13:2 (2019), 37–46 | MR

[5] Lidl R., Niederreiter H., Finite Fields, Addison-Wesley Publ. Inc., 1983, 755 pp. | MR | MR | Zbl

[6] Baev V. V., “On some algorithms for constructing low-degree annihilators for Boolean functions”, Discrete Math. Appl., 16:5 (2006), 439–452 | DOI | MR | Zbl

[7] Baev V. V., “An enhanced algorithm to search for low-degree annihilators for a Zhegalkin polynomial”, Discrete Math. Appl., 17:5 (2007), 533–538 | DOI | DOI | MR | Zbl | Zbl