Alladi Ramakrishnan Hall

Enumerator polynomials: Completeness and Intermediate Complexity

Meena Mahajan

IMSc

The partition functions count homomorphisms from an input graph G to a
fixed graph H. In the setting of algebraic complexity (which
generalises exact counting complexity), probing "from the left" turns
out to be more useful. We show that enumerating monomials that are in
bijection with homomorphisms from a fixed graph G to an input graph H
naturally gives rise to polynomial families complete for VP and VNP,
the algebraic analogues of P and NP defined by Valiant in 1979. These
provide the first example of a family that is defined independent of a
circuit model and that is complete for VP.

The cut enumerator polynomial Cut$_q$ (for a natural number q >1),
defined by Burgisser in 2000, is known to have "intermediate" status
as follows: Over any finite field of size q, it is in VNP, and
unless PH collapses, is neither in VP nor VNP-complete. Till recently
this was the only known family with these properties. Abstracting this
technique, we show that a host of other similar polynomials based on a
generalised version of enumerations of satisfying assignments, vertex
covers, cliques, 3-dimensional matchings, and closed walks, all have
the same properties. Furthermore, augmenting recent results due to
Grochow using extension complexity bounds in polyhedral theory, we
show that two of these polynomials are provably not obtainable as
monotone affine polynomial-size projections of the permanent.

This is joint work with Nitin Saurabh.