BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20210924T120000Z
UID:13d33582b1e92e8cc4b577237f70e031-201
DTSTAMP:19700101T120016Z
DESCRIPTION:Monotone Arithmetic Lower Bounds Via Communication Complexity.
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/201/monotone-arithmetic-lower-bounds-via-communication-complexity/
SUMMARY:How much power does negation or cancellation provide to computation?
<br>
This is a fundamental question in theoretical computer science that
<br>
appears in various parts: in Boolean circuits, Arithmetic circuits and
<br>
also in communication complexity. I will talk about some new connections
<br>
between the latter two fields and their applications to extend two
<br>
classical results from four decades ago:  Valiant (1979) showed that
<br>
monotone arithmetic circuits are exponentially weaker than general
<br>
circuits for computing monotone polynomials. Our first result gives a
<br>
qualitatively more powerful separation by showing an exponential
<br>
separation between general monotone circuits and constant-depth
<br>
multi-linear formulas. Neither such a separation between general
<br>
formulas and monotone circuits, nor a separation between multi-linear
<br>
circuits and monotone circuits were known before. Our result uses the
<br>
recent counter-example to the Log-Approximate-Rank Conjecture in
<br>
communication complexity.
<br>
 <br>
<br>
Jerrum and Snir (1982) also obtained a separation between the powers of
<br>
general circuits and monotone ones via a different polynomial, i.e. the
<br>
spanning tree polynomial (STP), a polynomial that is well known to be in
<br>
VP, using non-multi-linear cancellations of determinantal computation.
<br>
We provide the first extension of this result to show that the STP
<br>
remains `robustly hard` for monotone circuits  in the sense of Hrubes
<br>
recent notion of epsilon-sensitivity. The latter result is proved via
<br>
formulating a discrepancy method for monotone arithmetic circuits that
<br>
seems independently interesting.
<br>
<br>
We will discuss several open problems arising from these results.
<br>
 <br>
(These are based on joint works with Rajit Datta, Utsab Ghosal and
<br>
Partha Mukhopadhyay).
<br>
<br>
Microsoft Teams Link:
<br>
<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>
<br>
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/
DTSTART:20210924T120000Z
END:VEVENT
END:VCALENDAR