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., 2017, Volume 57, Number 2,Pages <nobr>362

This article is cited in 1 paper

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

A. V. Babenko^a, M. N. Vyalyi^bc

^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

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.

UDC: 519.7

Received: 15.05.2015
Revised: 27.07.2016

DOI: 10.7868/S004446691702003X