Borders, Debordering, and Algebraic Complexity

Speaker 

Pranjal Dutta November 7, 2025. 

Abstract

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. For a detailed survey, refer to the recent article: https://arxiv.org/abs/2510.13049 No prior knowledge of algebraic complexity, or advanced mathematics is required.