Log-Concavity and Lower Bounds for Arithmetic Circuits

DOI10.1007/978-3-662-48054-0_30zbMath1465.68077arXiv1503.07705OpenAlexW2951405814MaRDI QIDQ2946406

Sébastien Tavenas, Ignacio García-Marco, 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

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

Related Items (1)

Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization

Cites Work

• Unnamed Item
• Unnamed Item
• The maximum number of faces of the Minkowski sum of two convex polytopes
• Arithmetic circuits: the chasm at depth four gets wider
• Convexly independent subsets of the Minkowski sum of planar point sets
• Negation can be exponentially powerful
• Completeness and reduction in algebraic complexity theory
• Valiant's model and the cost of computing integers
• A \(\tau \)-conjecture for Newton polygons
• Improved Bounds for Reduction to Depth 4 and Depth 3
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• A Sufficient Condition for All the Roots of a Polynomial To Be Real

This page was built for publication: Log-Concavity and Lower Bounds for Arithmetic Circuits