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

DOI10.1070/SM2012V203N10ABEH004270MaRDI QIDQ4907594zbMATH OpenOpenAlexFDO

Authors S. B. Gashkov, I. 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

arithmetic circuitscomplexity classeslower bounds for complexitymonotone complexitypermanentthin sets

Mathematics Subject Classification ID

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

Recommendations

• Lower bounds on monotone arithmetic circuits with restricted depths
• scientific article; zbMATH DE number 3960990
• Lower bounds for monotone counting circuits
• Lower bounds for the complexity of polynomials
• An exponential lower bound for the size of monotone real circuits

Cited in

(16)

• An exponential lower bound for the size of monotone real circuits
• Tropical complexity, Sidon sets, and dynamic programming
• Log-concavity and lower bounds for arithmetic circuits
• Lower bounds for monotone counting circuits
• scientific article; zbMATH DE number 3960990 (Why is no real title available?)
• scientific article; zbMATH DE number 4045141 (Why is no real title available?)
• scientific article; zbMATH DE number 4068271 (Why is no real title available?)
• Minkowski complexity of sets: an easy lower bound
• Lower bounds for tropical circuits and dynamic programs
• Approximation limitations of pure dynamic programming
• Monotone circuit lower bounds from robust sunflowers
• Monotone classes beyond VNP
• Notes on Boolean read-k and multilinear circuits
• Lower bounds for additive complexity of linear operators and bilinear algorithms for matrix and polynomial multiplication over GF(2)
• Monotone classes beyond VNP
• Monotone bounded-depth complexity of homomorphism polynomials

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

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