Lower bounds for monotone counting circuits

DOI10.1016/j.dam.2016.04.024zbMath1350.68149arXiv1502.01865OpenAlexW2949346951MaRDI QIDQ313809

Stasys P. Jukna

Publication date: 12 September 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsarithmetic circuitsBoolean circuitscounting complexity

Mathematics Subject Classification ID

Related Items (2)

Monotone arithmetic complexity of graph homomorphism polynomials ⋮ Regular expression length via arithmetic formula complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Lower bounds for tropical circuits and dynamic programs
• Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
• Homogeneous formulas and symmetric polynomials
• Size-depth trade-offs for monotone arithmetic circuits
• The monotone circuit complexity of Boolean functions
• Negation can be exponentially powerful
• A lower bound on the number of additions in monotone computations
• A lower bound for monotone arithmetic circuits computing \(0-1\) permanent
• A direct version of Shamir and Snir's lower bounds on monotone circuit depth
• On a routing problem
• On the depth complexity of formulas
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• An inequality for the weights of two families of sets, their unions and intersections
• On the Parallel Evaluation of Multivariate Polynomials
• Combinatorial Nullstellensatz
• Lower bounds for resolution and cutting plane proofs and monotone computations
• A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials

This page was built for publication: Lower bounds for monotone counting circuits