ECCC-Report TR20-166https://eccc.weizmann.ac.il/report/2020/166Comments and Revisions published for TR20-166en-usMon, 09 Nov 2020 15:42:48 +0200
Paper TR20-166
| Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity |
Arkadev Chattopadhyay,
Rajit Datta,
Partha Mukhopadhyay
https://eccc.weizmann.ac.il/report/2020/166Valiant (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 \emph{depth-three formula} but every monotone circuit computing it has size $2^{\Omega(n^{1/4}/\log(n))}$.
The polynomial $P_n$ embeds the $\text{SINK}\circ \text{XOR}$ function devised recently by Chattopadhyay, Mande and Sherif (2020) 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 \circ \text{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} - \epsilon\cdot f_{n,m}$ and $F_{n,m} + \epsilon\cdot f_{n,m}$ have monotone circuit complexity $2^{\Omega(n/\log(n))}$ if $\epsilon \geq 2^{- \Omega( m )}$ and $F_{n,m} = \prod_{i=1}^n \big(x_{i,1} +\cdots+x_{i,m}\big)$, with $m = O( n/\log n )$. 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.Mon, 09 Nov 2020 15:42:48 +0200https://eccc.weizmann.ac.il/report/2020/166