Talks
Fall 2014

Degenerations of VP and VNP

Monday, December 14th, 2015 2:00 pm2:45 pm

Add to Calendar

One fundamental question in the geometric complexity theory approach to the VPws vs.
VNP conjecture is whether \bar{VPws}=VPws, where VPws is the class of families of polynomials that computed by symbolic determinants of polynomial size, and \bar{VPws} denotes the class of families of polynomials that can be approximated infinitesimally closely by symbolic determinants of polynomial size. We demonstrate nontriviality of this question by constructing an explicit family of polynomials that can be approximated infinitesimally closely by symbolic determinants of O(n) size but conjecturally cannot be computed exactly by symbolic determinants of (n^{2+δ}) size, for a small enough positive constant δ.
 
To study the question further, we introduce three degenerations of VPws, within \bar{VPws},
namely the stable degeneration Stable-VPws, the Newton degeneration Newton-VPws and the
p-definable one parameter degenerations VP*ws. The degenerations of VP and VNP are similar.
 
We show that (1) Stable-VPws ⊆ Newton-VPws ⊆ VP*ws ⊆ VNP, (2) Stable-VP ⊆ Newton-VP ⊆
VP* ⊆ VNP, and (3) Stable-VNP = Newton-VNP = VNP* = VNP.
 
This investigation supports the conjecture in GCT V that \bar{VPws} and \bar{VP} are not contained in VP (or even VNP). In fact, we are led to a refined conjecture that VPws ⊂ Newton-VPws ⊂
VP*ws ⊂ \bar{VPws}, and an analogous conjecture for VP.
 
Finally, we demonstrate that the families in Newton-VPws \ VPws would have to be very
special by showing that, for any finite quiver, Newton degeneration of any generic semi-invariant
has a small circuit.
 
Joint work with Ketan Mulmuley and Joshua A. Grochow.