Borders, Debordering, and Algebraic Complexity,

I will briefly introduce Valiant’s framework for algebraic complexity—VP vs. VNP (determinant vs. permanent)—and the associated border variants. Border complexity -- central to algebraic complexity and to Geometric Complexity Theory (GCT) -- captures polynomials lying in the Zariski closure of low-complexity classes; equivalently, those obtainable as limits (degenerations) of efficient computations. Notably, the best upper bounds on the matrix-multiplication exponent come via low border tensor rank. Debordering is the task of proving an upper bound on some non-border complexity measure in terms of a border complexity measure, thereby eliminating limits.

The talk will focus on two concrete toy models defined by Waring rank and Chow rank, as well as their border versions. I will survey recent qualitative debordering results, compare structural behaviors of border vs. non-border measures in these models, and outline some open problems.

This seminar is part of the Problems in Algebraic Geometry Coming from Complexity Theory series.