Seminars

View all Seminars  |  Download ICal for this event

Lower Bounds for Sums of Ordered Set-Multilinear ABPs

Series: Department Seminar

Speaker: Prerona Chatterjee, Postdoc at Tel Aviv university, Israel

Date/Time: Jan 30 11:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Abstract:
In a recent work, Bhargav, Dwivedi, and Saxena (2023), showed that super-polynomial lower bounds against a sum of ordered set-multilinear branching programs �?? for a polynomial over n variables of degree O(log n/ log log n) �?? would imply super-polynomial lower bounds against general ABPs. Following up on their work, in a joint work with Kush, Saraf and Shpilka, we prove an exponential lower bound against this model but for a polynomial over n^2 variables of degree n. In fact, even though our lower bound does not remain super-polynomial when the polynomial has degree O(log n/ log log n), it does remain so for a polynomial with degree as low as omega(log n). Moreover, the hard polynomial is computable by an ABP, thereby suggesting that our approach would not work if one wanted to prove lower bounds against general ABPs.

In this talk, we will see a proof overview of both the structural statement of Bhargav, Dwivedi and Saxena, as well as the lower bound against Sums of Ordered Set-Multilinear ABPs. The talk is based on joint work with Deepanshu Kush, Shubhangi Saraf and Amir Shpilka (Link

Host Faculty: Prof. Chandan Saha