Seminars

View all Seminars  |  Download ICal for this event

Monotone Arithmetic Lower Bounds Via Communication Complexity.

Series: Theory Seminar

Speaker: Dr. Arkadev Chattopadhyay Associate Professor School of Technology and Computer Science TIFR Mumbai

Date/Time: Sep 24 16:00:00

Location: Microsoft Teams - ON-LINE

Abstract:
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="Link
<br>
For more details about the seminar please visit the website at Link

Host Faculty: Dr. Anand Louis