On -sensitive monotone computations
DOI10.1007/S00037-020-00196-6zbMATH Open1461.68084OpenAlexW3044232313MaRDI QIDQ2198153FDOQ2198153
Authors: Pavel Hrubeš 
Publication date: 9 September 2020
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-020-00196-6
Recommendations
- Strongly exponential lower bounds for monotone computation
- scientific article; zbMATH DE number 3999837
- scientific article; zbMATH DE number 4045141
- Lower bounds on the depth of monotone arithmetic computations
- scientific article; zbMATH DE number 1256664
- scientific article; zbMATH DE number 4217938
- scientific article; zbMATH DE number 609922
- scientific article; zbMATH DE number 4049557
- scientific article; zbMATH DE number 3974158
- A method for obtaining efficient lower bounds for monotone complexity
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20) Networks and circuits as models of computation; circuit complexity (68Q06)
Cites Work
- On the complexity of nonnegative matrix factorization
- Title not available (Why is that?)
- Real rank versus nonnegative rank
- Expressing combinatorial optimization problems by linear programs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Linear vs. semidefinite extended formulations
- Algorithms in real algebraic geometry
- Negation can be exponentially powerful
- Title not available (Why is that?)
- On the nonnegative rank of distance matrices
- Some \(0/1\) polytopes need exponential size extended formulations
- Arithmetic circuits: a survey of recent results and open questions
- Depth-3 arithmetic circuits over fields of characteristic zero
- On the depth complexity of formulas
- Negation is Powerless for Boolean Slice Functions
- Homogeneous formulas and symmetric polynomials
- Title not available (Why is that?)
- Reducibility by algebraic projections
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Monotone simulations of non-monotone proofs.
- Extension complexity of independent set polytopes
- Representations of monotone Boolean functions by linear programs
- Separating monotone VP and VNP
Cited In (5)
- Representations of monotone Boolean functions by linear programs
- A note on monotone complexity and the rank of matrices
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- A note on the monotonicity of the ES algorithm
- On the extension complexity of polytopes separating subsets of the Boolean cube
This page was built for publication: On \(\epsilon\)-sensitive monotone computations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2198153)
