Flattenings and Koszul Young flattenings arising in complexity theory

ABSTRACT

I find new equations for Chow varieties, their secant varieties, and an additional variety that arises in the study of complexity theory by flattenings and Koszul Young flattenings. This enables a new lower bound for symmetric border rank of $x_1{x}_2\cdots x_d$ when d is odd, and a new lower complexity bound for the permanent.

KEYWORDS:

• Chow variety
• flattenings
• Koszul Young flattenings
• permanent
• secant variety
• symmetric border rank

MATHEMATICS SUBJECT CLASSIFICATION:

• 14Q20
• 68Q15
• 68Q17

Acknowledgments

I thank my advisor J. M. Landsberg for discussing all the details throughout this article. I thank Y. Qi for discussing the second part of this article. I thank Iarrobino for providing references for Theorem 2.7. Part of this work was done while the author was visiting the Simons Institute for the Theory of Computing, UC Berkeley for the Algorithms and Complexity in Algebraic Geometry program in 2014, I thank Simons Institute for providing a good research environment.