A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials

DOI10.1070/SM2012v203n10ABEH004270zbMath1270.68113OpenAlexW2157358149MaRDI QIDQ4907594

Sergey B. Gashkov, Igor S. Sergeev

Publication date: 4 February 2013

Published in: Sbornik: Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1070/sm2012v203n10abeh004270

zbMATH Keywords

thin setspermanentcomplexity classesarithmetic circuitsmonotone complexitylower bounds for complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Lower bounds for monotone counting circuits ⋮ Minkowski Complexity of Sets: An Easy Lower Bound ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ Approximation Limitations of Pure Dynamic Programming ⋮ Tropical Complexity, Sidon Sets, and Dynamic Programming ⋮ Monotone circuit lower bounds from robust sunflowers

This page was built for publication: A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials