TY - JOUR
T1 - Holographic algorithms without matchgates
AU - Landsberg, J. M.
AU - Morton, Jason
AU - Norine, Serguei
N1 - Funding Information:
This paper is an outgrowth of the AIM workshop Geometry and representation theory of tensors for computer science, statistics and other areas July 21–25, 2008, and authors gratefully thank AIM and the other participants of the workshop. We especially thank J. Cai, P. Lu, and L. Valiant for their significant efforts to explain their theory to us during the workshop. J. Cai is also to be thanked for continuing to answer our questions with extraordinary patience for months afterwards. We thank R. Thomas for his help with the graph-theoretical part of the argument. J.M. Landsberg was supported by NSF grant DMS-1006353. Jason Morton was supported by the Defense Advanced Research Projects Agency under Award No. N66001-10-1-4040. Serguei Norine was supported by NSF grant DMS-0803214.
PY - 2013/1/15
Y1 - 2013/1/15
N2 - The theory of holographic algorithms, which are polynomial time algorithms for certain combinatorial counting problems, surprised the complexity community by showing certain problems, very similar to #P complete problems, were in fact in the class P. In particular, the theory produces algebraic tests for a problem to be in P. In this article we describe the geometric basis of these algorithms by (i) replacing the construction of graph fragments in the procedure by the direct construction of a skew symmetric matrix, and (ii) replacing the computation of weighted perfect matchings of an auxiliary graph by computing the Pfaffian of the directly constructed skew-symmetric matrix. This procedure indicates a more geometric approach to complexity classes. It also leads to more general constructions where one replaces the "Grassmann-Plücker identities" which test for admissibility by other algebraic tests. Natural problems treatable by these methods have been previously considered in a different context, and we present one such example.
AB - The theory of holographic algorithms, which are polynomial time algorithms for certain combinatorial counting problems, surprised the complexity community by showing certain problems, very similar to #P complete problems, were in fact in the class P. In particular, the theory produces algebraic tests for a problem to be in P. In this article we describe the geometric basis of these algorithms by (i) replacing the construction of graph fragments in the procedure by the direct construction of a skew symmetric matrix, and (ii) replacing the computation of weighted perfect matchings of an auxiliary graph by computing the Pfaffian of the directly constructed skew-symmetric matrix. This procedure indicates a more geometric approach to complexity classes. It also leads to more general constructions where one replaces the "Grassmann-Plücker identities" which test for admissibility by other algebraic tests. Natural problems treatable by these methods have been previously considered in a different context, and we present one such example.
UR - http://www.scopus.com/inward/record.url?scp=84869426367&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84869426367&partnerID=8YFLogxK
U2 - 10.1016/j.laa.2012.01.010
DO - 10.1016/j.laa.2012.01.010
M3 - Article
AN - SCOPUS:84869426367
SN - 0024-3795
VL - 438
SP - 782
EP - 795
JO - Linear Algebra and Its Applications
JF - Linear Algebra and Its Applications
IS - 2
ER -