IMSc Webinar

Lower Bounds for Monotone Arithmetic Circuits via Communication Complexity

Partha Mukhopadhyay

CMI

Webinar: join at https://zoom.us/j/99018916192?pwd=Vnd3YW1RbisxNlVhZGN5RXYvMVZ5Zz09 Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first qualitative improvement to this classical result: we construct a family of monotone polynomials which can be computed by polynomial-size depth-three formulas but require exponential size monotone circuits. The polynomial family embeds a boolean function devised recently by Chattopadhyay, Mande and Sherif (2020) to refute the Log Approximate-Rank Conjecture in communication complexity. To prove our lower bound, we develop a general connection between corruption of combinatorial rectangles and corruption of product polynomials in arithmetic settings. This connection could be of independent interest. Recently Hrubes (2020) has introduced a new method to attack general VP vs VNP question by proving a certain type of lower bound for monotone circuits. We take a first step in this direction via arithmetization of discrepancy based techniques which are studied in communication complexity. Joint work with Arkadev Chattopadhyay (TIFR) and Rajit Datta (CMI)