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.
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
- Monotone circuit lower bounds from resolution
- scientific article; zbMATH DE number 4193610
- Lower Bounds for (Non-Monotone) Comparator Circuits
- scientific article; zbMATH DE number 4008289
Cites work
- scientific article; zbMATH DE number 4008289 (Why is no real title available?)
- scientific article; zbMATH DE number 4045141 (Why is no real title available?)
- A direct version of Shamir and Snir's lower bounds on monotone circuit depth
- A lower bound for monotone arithmetic circuits computing \(0-1\) permanent
- A lower bound on the number of additions in monotone computations
- A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
- An inequality for the weights of two families of sets, their unions and intersections
- Combinatorial Nullstellensatz
- Homogeneous formulas and symmetric polynomials
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Lower bounds for tropical circuits and dynamic programs
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- Negation can be exponentially powerful
- On a routing problem
- On the Parallel Evaluation of Multivariate Polynomials
- On the depth complexity of formulas
- Size-depth trade-offs for monotone arithmetic circuits
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- The monotone circuit complexity of Boolean functions
Cited in
(15)- Lower bounds for monotonic list labeling
- Fast monotone summation over disjoint sets
- Regular expression length via arithmetic formula complexity
- Monotone circuit lower bounds from robust sunflowers
- A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
- Monomials in arithmetic circuits: complete problems in the counting hierarchy
- Monomials in arithmetic circuits: complete problems in the counting hierarchy
- Monotone arithmetic complexity of graph homomorphism polynomials
- Lower bounds on monotone arithmetic circuits with restricted depths
- 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
- scientific article; zbMATH DE number 2080200 (Why is no real title available?)
- scientific article; zbMATH DE number 3960990 (Why is no real title available?)
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)
