Log-concavity and lower bounds for arithmetic circuits

DOI10.1007/978-3-662-48054-0_30MaRDI QIDQ2946406zbMATH OpenOpenAlexFDO

Authors Ignacio García Marco, Sébastien Tavenas, Pascal Koiran

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.07705

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: One question that we investigate in this paper is, how can we build log-concave polynomials using sparse polynomials as building blocks? More precisely, let $f=su{m}_{i=0}^d{a}_i{X}^{i}inmathbb{R}^{+}[X]$ be a polynomial satisfying the log-concavity condition $a_i^{2}extgreaterau{a}_{i-1}{a}_{i+1}$ for every $iin1,ldots,d-1,$ where $auextgreater0$. Whenever $f$ can be written under the form $f=su{m}_{i=1}^{k}pro{d}_{j=1}^m{f}_{i,j}$ where the polynomials $f_{i,j}$ have at most $t$ monomials, it is clear that $dleqk{t}^m$. Assuming that the $f_{i,j}$ have only non-negative coefficients, we improve this degree bound to $d=mathcalO(k{m}^{2/3}{t}^{2m/3}mlo{g}^{2/3}(kt))$ if $auextgreater1$, and to $dleqkmt$ if $au=d^{2d}$. This investigation has a complexity-theoretic motivation: we show that a suitable strengthening of the above results would imply a separation of the algebraic complexity classes VP and VNP. As they currently stand, these results are strong enough to provide a new example of a family of polynomials in VNP which cannot be computed by monotone arithmetic circuits of polynomial size.

Recommendations

• Strongly Exponential Separation between Monotone VP and Monotone VNP
• A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
• Lower bounds on monotone arithmetic circuits with restricted depths
• Monotone separations for constant degree polynomials
• The limited power of powering: polynomial identity testing and a depth-four lower bound for the permanent

Cites work

• A \(\tau \)-conjecture for Newton polygons
• A Sufficient Condition for All the Roots of a Polynomial To Be Real
• Arithmetic circuits: the chasm at depth four gets wider
• Completeness and reduction in algebraic complexity theory
• Convexly independent subsets of the Minkowski sum of planar point sets
• scientific article; zbMATH DE number 193053 (Why is no real title available?)
• Improved Bounds for Reduction to Depth 4 and Depth 3
• Negation can be exponentially powerful
• On the real -conjecture and the distribution of complex roots
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Valiant's model and the cost of computing integers

Cited in

(2)

• Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
• On Lower Bounds for Constant Width Arithmetic Circuits

This page was built for publication: Log-concavity and lower bounds for arithmetic circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946406)