Lecture Announcement
Date: 21 December 2022
Time: 2.30 pm
Venue: Lecture Hall 802
Approximative closure of symbolic determinant under rank-1 restriction
Rohit Gurjar
IIT Mumbai.
21-12-22

---

Abstract

An interesting question in algebraic complexity theory is to understand the approximative closure of various classes of polynomials. Some algebraic models of computation like depth-2 circuits and read-once ABPs are known to be closed under approximation. That is, any polynomial that can be approximately computed in these models can also be exactly computed. We show such a closure result for another algebraic model: det(sum_i A_i x_i) under the restriction that each A_i is of rank one. The proof is based on some LP duality kind of results in combinatorial optimization