Computer Science/Discrete Mathematics Seminar I

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 polynomials P-n in n variables, each of its monomials has positive coefficient, such that P-n can be computed by a polynomial-size *depth-three* formula but every monotone circuit computing it has size exp(n^{1/4}/log(n)).

The polynomial P-n embeds the SINK o XOR function devised recently by Chattopadhyay, Mande and Sherif (2019) to refute the Log-Approximate-Rank Conjecture in communication complexity. To prove our lower bound for P-n, we develop a general connection between corruption of combinatorial rectangles by any function f o XOR and corruption of product polynomials by a certain polynomial P-f that is an arithmetic embedding of f. This connection should be of independent interest.

Using further ideas from communication complexity, we construct another family of set-multilinear polynomials f(n,m) such that both F(n,m) − eps. f(n,m) and F(n,m) + eps.f(n,m) have monotone circuit complexity exp(n/log(n))  if eps >= exp−(Omega(m)) and F(n,m) is the full set-multilinear polynomial over n blocks each of size m, with m=O(nlogn). The polynomials f(n,m) have 0/1 coefficients and are in VNP.  Proving such lower bounds for monotone circuits has been advocated recently by Hrubeš (2020) as a first step towards proving lower bounds against general circuits via his new approach.

(This is joint work with Rajit Datta and Partha Mukhopadhyay and is accessible at: https://eccc.weizmann.ac.il/report/2020/166/)