Cubic lower bounds hold for permanent and pfaffian computations in odd characteristic
Cubic lower bounds for the permanent in odd characteristic, for Pfaffian representations, and for polynomial entries
Computational Complexity
Summary
Calculating the permanent of a matrix is known to be harder than calculating its determinant. The authors show that a certain measure of difficulty, called determinantal complexity, for the permanent cannot be smaller than a value that grows cubically with the matrix size, even in mathematical settings beyond complex numbers. They extend this cubic lower bound to related calculations called Pfaffians and to matrices whose entries are more complicated polynomials. Their proof uses counting special points on geometric shapes called hypersurfaces in various mathematical fields.
What this means in practice
- •For complexity theorists: Clarify limits on simplifying permanent computations in various algebraic settings, informing theoretical computational complexity boundaries.
- •For algebraic geometers: Use geometric methods involving hypersurface intersections to understand polynomial representation complexities.
A theory result. No direct application yet.
Authors
Karthik Sheshadri
Abstract
The determinantal complexity of a polynomial is the order of the smallest matrix whose entries are polynomials of degree at most one and whose determinant equals the polynomial. A lower bound for the permanent in this measure is the algebraic form of the question whether the permanent is harder to compute than the determinant. Over the complex numbers, the best known lower bound grows cubically in the size of the permanent. It holds even when the permanent only has to be a limit of such determinants. I prove that the cubic lower bound holds over every algebraically closed field of odd characteristic $p$, with a constant that depends on $p$. Hence the cubic bound does not depend on characteristic zero. I also prove the bound for Pfaffians, which are square roots of determinants of skew symmetric matrices. Lower bounds for Pfaffians imply the same bounds for determinants. Further, I prove the bound, divided by $a$, for matrices whose entries are polynomials of degree at most $a$. All three results come from one lower bound for smooth hypersurfaces. I prove it in every characteristic by counting intersection points together with their multiplicities.