BARC talk by Prateek Dwivedi

Friday, November 15, 2024, Prateek Dwivedi, Postdoc at IT University of Copenhagen, Denmark, will give a talk on "Presentable Version of Border Complexity and Applications to Circuit Factoring".

Please note that this particular BARC talk will be held at ITU, Rued Langgaards Vej 7, 2300 Copenhagen.

Abstract:
Valiant's conjecture, or the VP vs. VNP question, is a central open problem in Algebraic Complexity, comparable to the P vs. NP problem in Boolean complexity. The ambitious Geometric Complexity Theory (GCT) program aims to tackle this conjecture, leveraging representation theory and algebraic geometry to show (a possibly stronger statement) that VNP is not contained in border of VP. This further raises the question on the importance of approximation, and if the border circuits can always be easily simulated by exact computation ("debordering"). However, the inherently existential definition of border complexity makes the problem challenging.

In this talk, Prateek will describe a recent work that defines a new notion of the border that we call presentable. He will show that the presentable border of VP is in VNP over finite fields. Such a strong de-bordering results is unsolved with the vanilla definition. He further applies the techniques to Circuit Factorization. He shows that polynomial degree irreducible factors of a polynomial size (exponential degree) circuit are in VNP. This makes progress towards the Factor Conjecture of Burgisser. He also shows 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 C.S. Bhargav and Nitin Saxena from IIT Kanpur (STOC 2024 https://doi.org/10.1145/3618260.364974).

Bio:
Prateek Dwivedi is a Postdoctoral Researcher at the IT University of Copenhagen, working with Prof. Nutan Limaye. Before this he was a PhD student at IIT Kanpur with Prof. Nitin Saxena. His research interests include computational complexity theory, algebra, and graph theory.

Host:
Nutan Limaye