BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20210730T120000Z
UID:1926a4477be6b260f79220ed136b854b-181
DTSTAMP:19700101T120016Z
DESCRIPTION:Superpolynomial lower bounds against low-depth algebraic circuits
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/181/superpolynomial-lower-bounds-against-low-depth-algebraic-circuits/
SUMMARY:An algebraic circuit computes a polynomial using addition and multiplication operators. Understanding the power of algebraic circuits has close connections to understanding general computation. It is known that proving lower bounds for algebraic circuits can serve as a stepping stone towards proving general Boolean circuit lower bounds.
<br>
Despite this, not many lower bounds are known for even simple Sigma Pi Sigma (product-depth 1) circuits. Before our work, the best known lower bound for product-depth 1 circuit was (slightly less than) cubic. No lower bounds were known for general product-depth 2 circuits.
<br>
In this work, we show the first superpolynomial lower bound for low-product-depth algebraic circuits.
<br>
In the talk, we discuss the main results and present the proof ideas used in the proof of the superpolynomial lower bound for product-depth 1 circuits.
<br>
This talk is based on joint work with Srikanth Srinivasan and Sébastien Tavenas.
<br>
Microsoft Teams Link:
<a href="https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d">https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d</a>
DTSTART:20210730T120000Z
END:VEVENT
END:VCALENDAR