Revision #1 Authors: Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

Accepted on: 30th November 2020 00:19

Downloads: 67

Keywords:

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

Minor changes made in section 6. Proof of Lemma 6.1

TR20-166 Authors: Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

Publication: 9th November 2020 15:42

Downloads: 230

Keywords:

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