Geodesic
On the Kräuter–Seifter theorem on permanent divisibility
Zapiski Nauchnykh Seminarov POMI, Computational methods and algorithms. Part XXX, Tome 463 (2017), pp. 25-35 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The paper investigates the divisibility of the permanent function of $(1,-1)$-matrices by different powers of 2. It is shown that the Kräuter–Seifter bound is the best possible for generic $(1,-1)$-matrices. 
@article{ZNSL_2017_463_a2,
     author = {M. V. Budrevich and A. E. Guterman and K. A. Taranin},
     title = {On the {Kr\"auter{\textendash}Seifter} theorem on permanent divisibility},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {25--35},
     year = {2017},
     volume = {463},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2017_463_a2/}
}
TY  - JOUR
AU  - M. V. Budrevich
AU  - A. E. Guterman
AU  - K. A. Taranin
TI  - On the Kräuter–Seifter theorem on permanent divisibility
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2017
SP  - 25
EP  - 35
VL  - 463
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2017_463_a2/
LA  - ru
ID  - ZNSL_2017_463_a2
ER  - 
%0 Journal Article
%A M. V. Budrevich
%A A. E. Guterman
%A K. A. Taranin
%T On the Kräuter–Seifter theorem on permanent divisibility
%J Zapiski Nauchnykh Seminarov POMI
%D 2017
%P 25-35
%V 463
%U http://geodesic.mathdoc.fr/item/ZNSL_2017_463_a2/
%G ru
%F ZNSL_2017_463_a2
M. V. Budrevich; A. E. Guterman; K. A. Taranin. On the Kräuter–Seifter theorem on permanent divisibility. Zapiski Nauchnykh Seminarov POMI, Computational methods and algorithms. Part XXX, Tome 463 (2017), pp. 25-35. http://geodesic.mathdoc.fr/item/ZNSL_2017_463_a2/

[1] M. V. Budrevich, A. E. Guterman, K. A. Taranin, “O delimosti parmanenta $(\pm1)$-matritsy”, Zap. nauchn. semin. POMI, 439, 2015, 26–37 | MR

[2] S. A. Cook, “The complexity of theorem proving procedures”, Proc. 3rd Ann. ACM Symp. Theory Comput., 1971, 151–158 | Zbl

[3] D. K. Faddeev, I. S. Sominskii, Sbornik zadach po vysshei algebre, Izdanie 9, Nauka, M., 1968 | MR

[4] R. A. Brualdi, H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1991 | MR | Zbl

[5] R. A. Brualdi, M. Newman, “Some theorems on the permanent”, J. Res. Nat. Bur. Stand., 69B:3 (1965), 159–163 | DOI | MR | Zbl

[6] N. Fine, “Binomial coefficients modulo a prime”, Amer. Math. Monthly, 54 (1947), 589–592 | DOI | MR | Zbl

[7] M. R. Garey, D. S. Johnson, Computers and Intractability: a Guide to the Theory of $NP$-Completness, W. H. Freeman, San Francisco, 1979 | MR

[8] Ph. Hall, “On representatives of subsets”, J. London Math. Soc., 10:1 (1935), 26–30 | DOI | Zbl

[9] R. M. Karp, “Reducibility among combinatorial problems”, Complexity of Computer Computations, Plenum Press, New York, 1972, 85–104 | DOI | MR

[10] A. R. Kräuter, N. Seifter, “On some questions concerning permanents of $(1,-1)$-matrices”, Israel J. Math., 45:1 (1983), 53–62 | DOI | MR | Zbl

[11] H. Perfect, “Positive diagonals of $\pm1$-matrices”, Monatsh. Math., 77 (1973), 225–240 | DOI | MR | Zbl

[12] L. G. Valiant, “The complexity of computing the permanent”, Theor. Comput. Sci., 8 (1979), 189–201 | DOI | MR | Zbl

[13] E. T. H. Wang, “On permanents of $(1,-1)$-matrices”, Israel J. Math., 18 (1974), 353–361 | DOI | MR