Campus Event Calendar
Event Entry
What and Who
Power and limitation of border depth-3 algebraic circuits
Pranjal Dutta
Incoming Postdoc at Oxford
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 27 September 2022
13:00
45 Minutes
E1 4
024
Saarbrücken
Abstract
Border complexity of polynomials plays an integral role in the GCT (Geometric complexity theory) approach to prove P != NP. GCT was proposed by Mulmuley and Sohoni in 2001 where the idea is to prove the P!=NP (and its algebraic versions) using algebraic geometry and representation theory. Even the restricted setting of algebraic circuits in the border is not well-understood. Surprisingly, (Kumar ToCT'20) proved the universality of the border of top-fanin 2 depth-3 circuits (Σ^[2]ΠΣ-bar), which is in contrast with its classical model.
In this talk, we will discuss some advancements in this area. We will discuss an upper bound result which states that the bounded top-fanin border depth-3 circuits (Σ^[k]ΠΣ-bar for constant k) can be computed by a polynomial-size algebraic branching program (ABP). We will also discuss a strong exponential separation between any two consecutive border classes, Σ^[k]ΠΣ-bar and Σ^[k+1]ΠΣ-bar, establishing an optimal hierarchy of constant top-fanin border depth-3 circuits.
This is based on two works -- (i) the upper bound result is a joint work with Prateek Dwivedi and Nitin Saxena, FOCS'21 and (ii) the lower bound result is a joint work with Nitin Saxena, FOCS'22.
Contact
Virtual Meeting Details
Zoom
527 278 8807
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
The talk will take place in the hybrid format. If you wish to attend online but do not have the password for the zoom room, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.
Roohani Sharma, 09/15/2022 23:57
Roohani Sharma, 09/12/2022 12:07 -- Created document.
Roohani Sharma, 09/12/2022 12:07 -- Created document.