Seminar Announcement Speaker: Bhargav C S, IIT Kanpur Date: Friday, 05 April 2024 Time: 11:00 AM Venue: Seminar Hall Learning the coefficients: A presentable version of border complexity and applications to circuit factoring Bhargav C S IIT Kanpur. 05-04-24 Abstract Valiant's conjecture, or the VP vs VNP question, is the holy grail of Algebraic Complexity, akin to the P vs NP problem in Boolean complexity. The ambitious Geometric Complexity Theory (GCT) program attempts to attack the conjecture using tools from representation theory and algebraic geometry to prove (the possibly stronger statement) that VNP is not contained in VP's closure or _border_. The definition of the border is inherently existential, and it is unknown whether the closure of VP is explicit, i.e., whether it is in VNP. In this talk, I will describe a recent work that defines a new notion of the border that we term _presentable_. We will show that the presentable border of VP is in VNP over finite fields. We further apply the techniques to Circuit Factorization. We show that polynomial degree irreducible factors of a polynomial size (exponential degree) circuit are in VNP. This makes progress towards the Factor Conjecture of Burgisser. We also show that VNP is closed under factoring over finite fields. This was previously only known for fields of large characteristic or characteristic 0. This is joint work with Prateek Dwivedi and Nitin Saxena from IIT Kanpur.
|