Seminars

View all Seminars  |  Download ICal for this event

Border ranks, and de-bordering paradigms in Geometric Complexity Theory

Series: Bangalore Theory Seminars

Speaker: Pranjal Dutta, National University of Singapore,

Date/Time: Feb 01 14:00:00

Location: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract:
Border (or approximative) complexity of multivariate polynomials plays an integral role in GCT (Geometric Complexity Theory) approach to P!=NP. De-bordering is the task of proving an upper bound on some non-border complexity measure in terms of a border complexity measure, thus getting rid of limits. The de-bordering of matrix multiplication tensors by Bini played a pivotal role in the development of efficient matrix multiplication algorithms. Consequently, de-bordering finds applications in both establishing computational complexity lower bounds and facilitating algorithm design. Currently, very few de-bordering results are known.

Restricted algebraic circuits, therefore, are a good testing ground for these de-bordering questions. Recently, Kumar (ToCT 20) proved that *any* polynomial f can be approximated arbitrarily well by linear projections of the polynomial x_1*...* x_N - 1, a special depth-2 circuit for an exponentially large N. In this talk, we will go introduce some more border rank measures, for e.g.,~border Waring rank, border Chow rank. We will discuss the recent developments relating to them.

This is based on multiple joint works with Prateek Dwivedi, Nitin Saxena, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal and Vladimir Lysikov..


Microsoft teams link:
Link

We are grateful to the Kirani family for generously supporting the theory seminar series

Hosts: Rameesh Paul, Rahul Madhavan, Rachana Gusain, KVN Sreenivas