On the Linear Classification of Even and Odd Permutation Matrices and the Complexity of Computing the Permanent

被引：1

作者：

Babenko, A. V. ^{[1
]}

Vyalyi, M. N. ^{[2
]}

机构：

[1] Moscow Inst Phys & Technol, Dolgopudnyi 141701, Moscow Oblast, Russia

[2] Russian Acad Sci, Fed Res Ctr Comp Sci & Control, Dorodnicyn Comp Ctr, Moscow 119333, Russia

来源：

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS | 2017年 / 57卷 / 02期

基金：

俄罗斯基础研究基金会;

关键词：

permutation matrix; parity; permanent; linear classification; theta function; independence number;

D O I：

10.1134/S0965542517020038

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：362 / 371

页数：10

共 10 条

[1]

Abbe E., 2014, ARXIV14016528V2

[2]

[Anonymous], 1997, Combinatorial Theory

[3]

Arora S, 2009, COMPUTATIONAL COMPLEXITY: A MODERN APPROACH, P1, DOI 10.1017/CBO9780511804090

[4]

Crapo H.H., 1970, On the foundations of combinatorial theory: Combinatorial geometries

[5]

Kasteleyn P. W., 1967, Graph theory and theoretical physics, P43

[6]

Lovasz L., 2003, RECENT ADV ALGORITHM, P137, DOI DOI 10.1007/0-387-22444-0_6

[7] Determinant: Old algorithms, new insights [J].

Mahajan, M ;

Vinay, V .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (04) :474-490

[8]

Ryser H. J., 1963, CARUS MATH MONOGRAPH, pxiv+154

[9]

Smetanin Yu. G., 1986, IZV AKADEMII NAUK SS, P139

[10]

Valiant L. G., 1979, Theoretical Computer Science, V8, P189, DOI 10.1016/0304-3975(79)90044-6

← 1 →