Grochow, Joshua A. ;
Mulmuley, Ketan D. ;
Qiao, Youming
Boundaries of VP and VNP
Abstract
One fundamental question in the context of the geometric complexity theory approach to the VP vs. VNP conjecture is whether VP = !VP, where VP is the class of families of polynomials that can be computed by arithmetic circuits of polynomial degree and size, and VP is the class of families of polynomials that can be approximated infinitesimally closely by arithmetic circuits of polynomial degree and size. The goal of this article is to study the conjecture in (Mulmuley, FOCS 2012) that !VP is not contained in VP.
Towards that end, we introduce three degenerations of VP (i.e., sets of points in VP), namely the stable degeneration StableVP, the Newton degeneration NewtonVP, and the pdefinable oneparameter degeneration VP*. We also introduce analogous degenerations of VNP. We show that StableVP subseteq NewtonVP subseteq VP* subseteq VNP, and StableVNP = NewtonVNP = VNP* = VNP. The three notions of degenerations and the proof of this result shed light on the problem of separating VP from VP.
Although we do not yet construct explicit candidates for the polynomial families in !VP\VP, we prove results which tell us where not to look for such families. Specifically, we demonstrate that the families in NewtonVP \VP based on semiinvariants of quivers would have to be nongeneric by showing that, for many finite quivers (including some wild ones), Newton degeneration of any generic semiinvariant can be computed by a circuit of polynomial size. We also show that the Newton degenerations of perfect matching Pfaffians, monotone arithmetic circuits over the reals, and Schur polynomials have polynomialsize circuits.
BibTeX  Entry
@InProceedings{grochow_et_al:LIPIcs:2016:6314,
author = {Joshua A. Grochow and Ketan D. Mulmuley and Youming Qiao},
title = {{Boundaries of VP and VNP}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {34:134:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6314},
URN = {urn:nbn:de:0030drops63147},
doi = {10.4230/LIPIcs.ICALP.2016.34},
annote = {Keywords: geometric complexity theory, arithmetic circuit, border complexity}
}
2016
Keywords: 

geometric complexity theory, arithmetic circuit, border complexity 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

2016 