[Proof Complexity] Seminar Monday Oct 4 at 14:00 CEST with Arkadev Chattopadhyay: Monotone arithmetic lower bounds via communication complexity

[Jakob Nordström]

Dear all,

On Monday October 4 at 14:00 CEST we are having a MIAO video seminar with Arkadev Chattopadhyay from the Tata Institute of Fundamental Research, Mumbai titled "Monotone arithmetic lower bounds via communication complexity". See below for the abstract.

We will meet virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://www.youtube.com/channel/UCN0G2Wfl9-sAKrVLVza7z4A for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners an overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming video seminars can be found at http://www.jakobnordstrom.se/videoseminars/ . If you do not wish to receive these announcements, or receive several copies of them, please send a message to jakob.nordstrom at cs.lth.se.

Best regards,
Jakob Nordström

**********

Monday Oct 4 at 14:00 CEST
Monotone arithmetic lower bounds via communication complexity
(Arkadev Chattopadhyay, Tata Institute of Fundamental Research, Mumbai)

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).


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98
http://www.jakobnordstrom.se