Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Zh. Vychisl. Mat. Mat. Fiz.:
Year:
Volume:
Issue:
Page:
Find




Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register

Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, 2017, Volume 57, Number 2, Pages 362–372
DOI: https://doi.org/10.7868/S004446691702003X (Mi zvmmf10527) 		 
This article is cited in 1 scientific paper (total in 1 paper)

On the linear classification of even and odd permutation matrices and the complexity of computing the permanent

A. V. Babenkoa, M. N. Vyalyibc

a Moscow Institute of Physics and Technology, Dolgopudnyi, Moscow oblast, Russia
b Dorodnicyn Computing Center, Federal Research Center “Computer Science and Control”, Russian Academy of Sciences, Moscow, Russia
c National Research University “Higher School of Economics” (HSE), Moscow
Full-text PDF (218 kB) Citations (1)
References:
PDF
HTML
DOI: https://doi.org/10.7868/S004446691702003X
Abstract: 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.
Key words: permutation matrix, parity, permanent, linear classification, theta function, independence number.
Funding agency Grant number
Russian Foundation for Basic Research 14-01-00641_а
Ministry of Education and Science of the Russian Federation
Received: 15.05.2015
Revised: 27.07.2016
English version:
Computational Mathematics and Mathematical Physics, 2017, Volume 57, Issue 2, Pages 362–371
DOI: https://doi.org/10.1134/S0965542517020038
Bibliographic databases:
Document Type: Article
UDC: 519.7
Language: Russian
Citation: A. V. Babenko, M. N. Vyalyi, “On the linear classification of even and odd permutation matrices and the complexity of computing the permanent”, Zh. Vychisl. Mat. Mat. Fiz., 57:2 (2017), 362–372; Comput. Math. Math. Phys., 57:2 (2017), 362–371
Citation in format AMSBIB
\Bibitem{BabVya17}
\by A.~V.~Babenko, M.~N.~Vyalyi
\paper On the linear classification of even and odd permutation matrices and the complexity of computing the permanent
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2017
\vol 57
\issue 2
\pages 362--372
\mathnet{http://mi.mathnet.ru/zvmmf10527}
\crossref{https://doi.org/10.7868/S004446691702003X}
\elib{https://elibrary.ru/item.asp?id=28918679}
\transl
\jour Comput. Math. Math. Phys.
\yr 2017
\vol 57
\issue 2
\pages 362--371
\crossref{https://doi.org/10.1134/S0965542517020038}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000397983100012}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85032900304}
Linking options:
  • https://www.mathnet.ru/eng/zvmmf10527
  • https://www.mathnet.ru/eng/zvmmf/v57/i2/p362
    • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025