Lower bounds for monotone counting circuits
From MaRDI portal
Publication:313809
DOI10.1016/J.DAM.2016.04.024zbMATH Open1350.68149arXiv1502.01865OpenAlexW2949346951MaRDI QIDQ313809FDOQ313809
Publication date: 12 September 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Abstract: A {+,x}-circuit counts a given multivariate polynomial f, if its values on 0-1 inputs are the same as those of f; on other inputs the circuit may output arbitrary values. Such a circuit counts the number of monomials of f evaluated to 1 by a given 0-1 input vector (with multiplicities given by their coefficients). A circuit decides if it has the same 0-1 roots as f. We first show that some multilinear polynomials can be exponentially easier to count than to compute them, and can be exponentially easier to decide than to count them. Then we give general lower bounds on the size of counting circuits.
Full work available at URL: https://arxiv.org/abs/1502.01865
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- On a routing problem
- Lower bounds for tropical circuits and dynamic programs
- Combinatorial Nullstellensatz
- Negation can be exponentially powerful
- A lower bound on the number of additions in monotone computations
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Lower bounds for resolution and cutting plane proofs and monotone computations
- The monotone circuit complexity of Boolean functions
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- On the depth complexity of formulas
- An inequality for the weights of two families of sets, their unions and intersections
- On the Parallel Evaluation of Multivariate Polynomials
- A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- Homogeneous formulas and symmetric polynomials
- Size-depth trade-offs for monotone arithmetic circuits
Cited In (9)
- Lower bounds for monotonic list labeling
- Regular expression length via arithmetic formula complexity
- Monotone circuit lower bounds from robust sunflowers
- Monotone arithmetic complexity of graph homomorphism polynomials
- Arithmetic Circuits and Polynomial Replacement Systems
- Notes on Boolean read-\(k\) and multilinear circuits
- Lower bounds for modular counting by circuits with modular gates
- An exponential lower bound for the size of monotone real circuits
- Title not available (Why is that?)
Recommendations
- Lower bounds on monotone arithmetic circuits with restricted depths 👍 👎
- A lower bound for monotone arithmetic circuits computing \(0-1\) permanent 👍 👎
- Lower bounds for monotone arithmetic circuits via communication complexity 👍 👎
- Lower bounds for modular counting by circuits with modular gates 👍 👎
- Lower bounds for modular counting by circuits with modular gates 👍 👎
- Monotone circuit lower bounds from resolution 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Lower Bounds for (Non-Monotone) Comparator Circuits 👍 👎
- Title not available (Why is that?) 👍 👎
This page was built for publication: Lower bounds for monotone counting circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313809)
