The Complexity of the Fermionant and Immanants of Constant Width

by Stephan Mertens and Cristopher Moore

Theory of Computing, Volume 9(6), pp. 273-282, 2013

Bibliography with links to cited articles

[1]   Richard Arratia, Béla Bollobás, and Gregory B. Sorkin: The interlace polynomial of a graph. J. Combin. Theory Ser. B, 92(2):199–233, 2004. Preliminary version in SODA’00. [doi:10.1016/j.jctb.2004.03.003]

[2]   Andrea Austin: The circuit partition polynomial with applications and relation to the Tutte and interlace polynomials. Rose-Hulman Undergraduate Mathematics Journal, 8(2):1:1–19, 2007.

[3]   Alexander I. Barvinok: Computational complexity of immanents and representations of the full linear group. Functional Analysis and its Applications, 24(2):144–145, 1990. [doi:10.1007/BF01077707]

[4]   Béla Bollobás: Evaluations of the circuit partition polynomial. J. Combin. Theory Ser. B, 85(2):261–268, 2002. [doi:10.1006/jctb.2001.2102]

[5]   André Bouchet: Tutte-Martin polynomials and orienting vectors of isotropic systems. Graphs and Combinatorics, 7(3):235–252, 1991. [doi:10.1007/BF01787630]

[6]   Graham Brightwell and Peter Winkler: Counting Eulerian circuits is #P-complete. In Proc. 7th Workshop on Algorithm Engineering and Experiments and 2nd Workshop on Analytic Algorithmics and Combinatorics (ALENEX/ANALCO’05), pp. 259–262. SIAM Press, 2005. Available from SIAM.

[7]   Jean-Luc Brylinski and Ranee Brylinski: Complexity and completeness of immanants. Technical report, 2003. [arXiv:cs/0301024]

[8]   Peter Bürgisser: The computational complexity of immanants. SIAM J. Comput., 30(3):1023–1040, 2000. Preliminary version in FPSAC’98. [doi:10.1137/S0097539798367880]

[9]   Peter Bürgisser: The computational complexity to evaluate representations of general linear groups. SIAM J. Comput., 30(3):1010–1022, 2000. Preliminary version in FPSAC’98. [doi:10.1137/S0097539798367892]

[10]   Shailesh Chandrasekharan and Uwe-Jens Wiese: Partition functions of strongly correlated electron systems as “fermionants”. Technical report, 2011. [arXiv:1108.2461]

[11]   Joanna A. Ellis-Monaghan: New results for the Martin polynomial. J. Combin. Theory Ser. B, 74(2):326–352, 1998. [doi:10.1006/jctb.1998.1853]

[12]   Joanna A. Ellis-Monaghan and Irasema Sarmiento: Distance hereditary graphs and the interlace polynomial. Combinatorics, Probability & Computing, 16(6):947–973, 2007. [doi:10.1017/S0963548307008723]

[13]   William Fulton and Joe Harris: Representation Theory: A First Course. Springer, 2004. Available from Springer.

[14]   Leslie Ann Goldberg and Mark Jerrum: Inapproximability of the Tutte polynomial of a planar graph. Comput. Complexity, 21(4):605–642, 2012. [doi:10.1007/s00037-012-0046-4]

[15]   Werner Hartmann: On the complexity of immanants. Linear and Multilinear Algebra, 18(2):127–140, 1985. [doi:10.1080/03081088508817680]

[16]   François Jaeger: On Tutte polynomials and cycles of plane graphs. J. Combin. Theory Ser. B, 44(2):127–146, 1988. [doi:10.1016/0095-8956(88)90083-4]

[17]   Michel Las Vergnas: On Eulerian partitions of graphs. Research Notes in Mathematics, 34:62–75, 1979.

[18]   Michel Las Vergnas: On the evaluation at (3,3) of the Tutte polynomial of a graph. J. Combin. Theory Ser. B, 45(3):367–372, 1988. [doi:10.1016/0095-8956(88)90079-2]

[19]   Pierre Martin: Enumérations eulériennes dans les multigraphes et invariants de Tutte-Grothendieck. Thesis, Université Scientifique et Médicale de Grenoble, 1977. Available in Archives Ouvertes.

[20]   Cristopher Moore and Stephan Mertens: The Nature of Computation. Oxford University Press, 2011. [ACM:2086753]

[21]   Seinosuke Toda: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865–877, 1991. Preliminary version in FOCS’89. [doi:10.1137/0220053]

[22]    Leslie G. Valiant: The complexity of computing the permanent. Theoret. Comput. Sci., 8(2):189–201, 1979. [doi:10.1016/0304-3975(79)90044-6]

[23]   Leslie G. Valiant: Completeness for parity problems. In Proc. 11th Ann. Internat. Computing and Combinatorics Conf. (COCOON’05), pp. 1–8. Springer, 2005. [doi:10.1007/11533719_1]

[24]   Dirk L. Vertigan: The computational complexity of Tutte invariants for planar graphs. SIAM J. Comput., 35(3):690–712, 2005. [doi:10.1137/S0097539704446797]