Title: Borders, Debordering, and Algebraic Complexity
Speaker: Pranjal Dutta (Assistant Professor, CCDS, NTU, Singapore)
Invited by: Bruno Loff (LASIGE, DM/FCUL)
When: June 09, 2026, 14:00
Where: Ciências ULisboa, C6.2.33

Abstract: The talk introduces Valiant’s framework for algebraic complexity—VP vs. VNP (determinant vs. permanent)—and its border variants. Border complexity underlies the best-known bounds on matrix multiplication. The talk focuses on two toy models defined by Waring and Chow ranks, surveys recent debordering results, compares structural behaviours of border and non-border measures, and outlines open problems. A longer survey can be found at arxiv.org/abs/2510.13049 (Invited and accepted in Text and Monographs in Symbolic Computation (TMSC) 2026).
*No prior knowledge of algebraic complexity, or advanced mathematics is required*.

Bio: Pranjal Dutta is currently an Assistant Professor in the College of Computing and Data Science (CCDS) at Nanyang Technological University (NTU) Singapore. He spent Fall 2025 at Simons Institute as a Simons-Berkeley Fellow as well as Jane Street Research Fellow. Before joining NTU, he was a postdoc at NUS Singapore, advised by Prof. Divesh Aggarwal. He obtained his PhD from Chennai Mathematical Institute, advised by Prof. Nitin Saxena and he was supported by Google PhD Fellowship. His PhD work won the ACM India Doctoral Dissertation Award 2023. He is broadly interested in Theoretical Computer Science, with a focus on algebraic complexity theory, and geometric complexity theory (GCT), learning theory, and related areas of mathematics.