Michael Forbes: Some Concrete Questions on the Border Complexity of Polynomials

Algebraic Complexity Theory traditionally studies the size of algebraic circuits required to compute a polynomial p(x1,...,xn). However, from the perspective of algebraic geometry it is more natural to consider the "border size" required to compute a polynomial, which is smallest size of circuits needed to arbitrarily approximate p(x1,...,xn) in some sense. While most existing methods for proving circuit size lower bounds readily extend to proving lower bounds for border-size, we lack a robust understanding of how the notions of circuit-size and border-circuit-size compare. In this talk I will discuss some concrete challenges surrounding border-complexity. I will start with the basic setup of border tensor-rank, and comment on its relation to the matrix multiplication exponent. I will then discuss the natural extension to VP and its border. I will then highlight open questions on the "circuit-size and border-circuit-size " question, even for restricted models of computation, as well as discussing recent challenges posed by Mulmuley. צילום הרצאה שלומי חיון צילום הרצאות סטודיו האנה בי