Equations for Chow Varieties, Their Secant Varieties and Other Varieties Arising in Complexity Theory
Loading...
Date
2016-05-24
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The Chow variety of polynomials that decompose as a product of linear forms has been studied for more than 100 years. Brill, Gordon, and others obtained set-theoretic equations for the Chow variety. I compute Brill's equations as a GL (V )-module. I find new equations for Chow varieties, their secant varieties, and an additional variety by flattenings and Koszul Young flattenings. This enables a new lower bound for the symmetric border rank of x1x2 ยทยทยท xd when d is odd and a new complexity lower bound for the permanent. I use the method of prolongation to obtain equations for secant varieties of Chow varieties as GL(V )-modules. The goal of studying these varieties arising in complexity theory is to separate VP from VNP, which is an algebraic analog of the famous P versus NP problem.
Description
Keywords
Chow variety, Brill's equations, secant variety, flattening, Koszul Young flattening, permanent, VP and VNP