Skip to main content

Pfaffian Circuits

Date:
-
Location:
University of Kentucky, Whitehall Classroom Building room 346
Speaker(s) / Presenter(s):
Jason Morton, Pennsylvania State University

 

Pfaffian circuits are a new, simplified construction of Valiant's holographic algorithms.  These algorithms provide in general O(n^r) time solutions to certain counting problems, where 1.19<r<3 is the order of Pfaffian evaluation in the ring of interest. Examples include fast algorithms for lattice path problems and a new O(n^r) algorithm for evaluation of Tutte polynomials of lattice path matroids. Finally, I'll comment on some of the geometric considerations in analyzing other potential applications of Pfaffi an circuits.

Event Series: