Geodesic
On the linear classification of even and odd permutation matrices and the complexity of computing the permanent
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 57 (2017) no. 2, pp. 362-372 
A. V. Babenko; M. N. Vyalyi. On the linear classification of even and odd permutation matrices and the complexity of computing the permanent. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 57 (2017) no. 2, pp. 362-372. http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_2_a11/
@article{ZVMMF_2017_57_2_a11,
     author = {A. V. Babenko and M. N. Vyalyi},
     title = {On the linear classification of even and odd permutation matrices and the complexity of computing the permanent},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {362--372},
     year = {2017},
     volume = {57},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_2_a11/}
}
TY  - JOUR
AU  - A. V. Babenko
AU  - M. N. Vyalyi
TI  - On the linear classification of even and odd permutation matrices and the complexity of computing the permanent
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2017
SP  - 362
EP  - 372
VL  - 57
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_2_a11/
LA  - ru
ID  - ZVMMF_2017_57_2_a11
ER  - 
%0 Journal Article
%A A. V. Babenko
%A M. N. Vyalyi
%T On the linear classification of even and odd permutation matrices and the complexity of computing the permanent
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2017
%P 362-372
%V 57
%N 2
%U http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_2_a11/
%G ru
%F ZVMMF_2017_57_2_a11

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

The problem of linear classification of the parity of permutation matrices is studied. This problem is related to the analysis of complexity of a class of algorithms designed for computing the permanent of a matrix that generalizes the Kasteleyn algorithm. Exponential lower bounds on the magnitude of the coefficients of the functional that classifies the even and odd permutation matrices in the case of the field of real numbers and similar linear lower bounds on the rank of the classifying map for the case of the field of characteristic 2 are obtained.

[1] Abbe E., Alon N., Bandeira A. S., Linear Boolean classification, coding and “the critical problem”, 2014, arXiv: 1401.6528v2 | MR

[2] Crapo H. H., Rota G. C., On the foundations of combinatorial theory: Combinatorial geometries, MIT Press, Cambridge, MA, 1970 | MR

[3] Aigner M., Kombinatornaya teoriya, Mir, M., 1982

[4] Arora S., Barak B., Computational complexity: a modern approach, Cambridge Univ. Press, Cambridge, UK, 2009 | MR | Zbl

[5] Valiant L. G., “The complexity of computing the permanent”, Theoretical computer science, 8:2 (1979), 189–201 | DOI | MR | Zbl

[6] Ryser H. J., Combinatorial mathematics, Carus Math. Monographs, 14, Math. Assoc. of America, Washington, DC, 1963 | Zbl

[7] Mahajan M., Vinay V., “Determinant: old algorithms, new insights”, SIAM J. Discrete Math., 12:4 (1999), 474–490 | DOI | MR | Zbl

[8] Kasteleyn P. W., “Graph theory and crystal physics”, Graph Theory and Theoretical Physics, ed. F. Harary, Academic Press, London–New York, 1967, 43–110 | MR

[9] Smetanin Yu. G., Khachiyan L. G., “Primenenie psevdopolinomialnykh algoritmov dlya nekotorykh zadach kombinatornoi optimizatsii s ogranicheniyami”, Izv. AN SSSR. Tekh. Kibernetika, 1986, no. 6, 139–144

[10] Lovasz L., “Semidefinite programs and combinatorial optimization”, Recent advances in algorithms and combinatorics, eds. B. A. Reed, C. L. Sales, Springer, Berlin, 2003, 137–194 | MR | Zbl