Name
Abstract | ||
|---|---|---|
ABSTRACTValiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first improvement to this classical result: we construct a family of polynomials Pn in n variables, each of its monomials has non-negative coefficient, such that Pn can be computed by a polynomial-size depth-three formula but every monotone circuit computing it has size 2Ω(n1/4/log(n)). The polynomial Pn embeds the SINK∘ 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 Pn, we develop a general connection between corruption of combinatorial rectangles by any function f ∘ XOR and corruption of product polynomials by a certain polynomial Pf 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 fn,m such that both Fn,m − є· fn,m and Fn,m + є· fn,m have monotone circuit complexity 2Ω(n/log(n)) if є ≥ 2− Ω( m ) and Fn,m ∏i=1n (xi,1 +⋯+xi,m), with m = O( n/logn ). The polynomials fn,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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1145/3406325.3451069 | ACM Symposium on Theory of Computing |
DocType | Volume | Citations |
Conference | 27 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arkadev Chattopadhyay | 1 | 150 | 19.93 |
| Rajit Datta | 2 | 1 | 3.75 |
| Partha Mukhopadhyay | 3 | 91 | 12.71 |