Determinant, Permanent and their Planar Restrictions
Raghav Kulkarni
University of Chicago.
25-08-06

---

Abstract

We study the complexities of computing determinant and permanent when restricted to adjacency matrices of directed planar graphs. In particular, we show that planarity does not help getting down the complexities in either case. In contrast, we show that permanent of adjacency matrix of directed bipartite planar graph can be computed in GapL, infact, it is complete for GapL.

The main technique used in reducing arbitrary permanent or determinant to respective planar case is replacing each crossing by a suitable planarity gadget while preserving the quantity that we are computing.

This is joint work with Samir Datta, Nutan Limaye and Meena Mahajan when the speaker was visiting Chennai Mathematical Institute in summer 2006.