Pfaffians and Valiant's holographic algorithms
If one computed the determinant of an n by n matirx
using the naive formula, it would involve performing a
number of arithmetic operations that is exponential in $n$.
Gaussian elimination enables us
to compute determinants in less than $n^4$ operations. There are many
classes of problems and sequences of polynomials which naively require
performing a number of arithmetic operations that is exponential in the
input data to solve. Some, like the determinant, also admit fast
algorithms. Valiant has obtained a class of such algorithms,
which he calls ``holographic'' algorithms, which, from his
perspective,
allow one to simulate a quantum computer on a classical computer.
I'll explain Valiant's algorithms, their potential applicability,
how they relate to Pfaffians (as well as some identites regarding Pfaffians of
interest in their own right), and what light they shed on the
P vs NP problem.