Theory Seminar

# Holographic algorithms without matchgates

## Jason Morton

Assistant Professor of Mathematics and Statistics
Department of Mathematics, Pennsylvania State University

Friday, June 04, 2010
10:30am - 11:30am
Beyster Bldg. 3941

Combinatorial (weighted) counting problems, such as counting the number of satisfying assignments of a Boolean satisfiability problem or computing the partition function of a graphical model, can be expressed as tensor contractions diagrammed by a bipartite graph $\Gamma=(V,U,E)$. Many algorithms for solving these problems efficiently use tree structure and factorization over a semiring (the "sum-product algorithm"). Over a proper ring, cancellation can be exploited as well. This requires a change of basis so that certain algebraic conditions are locally satisfied, and the addition of orientation or ordering information. Recently, this Pfaffian-based approach has been used by Valiant and Cai to provide unexpected, polynomial-time "accidental" algorithms for certain counting problems including simulating quantum computation. Their method expands the vertices of $\Gamma$ into graph fragments called matchgates and applies the FKT algorithm to find a Pfaffian orientation and compute the perfect matching polynomial. We demonstrate a geometrically-motivated simplification of this approach using only a $|E| \times |E|$ matrix and give some generalizations.