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

Faculty Advisor:

How much power does negation or cancellation provide to computation?
This is a fundamental question in theoretical computer science that
appears in various parts: in Boolean circuits, Arithmetic circuits and
also in communication complexity. I will talk about some new connections
between the latter two fields and their applications to extend two
classical results from four decades ago: Valiant (1979) showed that
monotone arithmetic circuits are exponentially weaker than general
circuits for computing monotone polynomials. Our first result gives a
qualitatively more powerful separation by showing an exponential
separation between general monotone circuits and constant-depth
multi-linear formulas. Neither such a separation between general
formulas and monotone circuits, nor a separation between multi-linear
circuits and monotone circuits were known before. Our result uses the
recent counter-example to the Log-Approximate-Rank Conjecture in
communication complexity.

Jerrum and Snir (1982) also obtained a separation between the powers of
general circuits and monotone ones via a different polynomial, i.e. the
spanning tree polynomial (STP), a polynomial that is well known to be in
VP, using non-multi-linear cancellations of determinantal computation.
We provide the first extension of this result to show that the STP
remains `robustly hard` for monotone circuits in the sense of Hrubes
recent notion of epsilon-sensitivity. The latter result is proved via
formulating a discrepancy method for monotone arithmetic circuits that
seems independently interesting.

We will discuss several open problems arising from these results.

(These are based on joint works with Rajit Datta, Utsab Ghosal and
Partha Mukhopadhyay).

Microsoft Teams Link:
For more details about the seminar please visit the website at

Speaker Bio:

Host Faculty: Dr. Anand Louis