Abstract: I will discuss the complexity classes VP and VNP of families of polynomials. While VNP contains complete problems (like the permanent) that are natural, the class VP was now known to have any complete problems beyond those that can be based on circuit-related problems based on the definition of VP. I will discuss a natural VP-complete family based on 'graph homomorphism polynomials'.
This talk is based on a paper by Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, and Nitin Saurabh.