On -sensitive monotone computations

DOI10.1007/S00037-020-00196-6MaRDI QIDQ2198153zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

extension complexitynonnegative rankarithmetic circuit complexity

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 3781471 (Why is no real title available?)
• scientific article; zbMATH DE number 176870 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• Algorithms in real algebraic geometry
• Arithmetic circuits: a survey of recent results and open questions
• Depth-3 arithmetic circuits over fields of characteristic zero
• Expressing combinatorial optimization problems by linear programs
• Extension complexity of independent set polytopes
• Homogeneous formulas and symmetric polynomials
• Linear vs. semidefinite extended formulations
• Monotone simulations of non-monotone proofs.
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Negation can be exponentially powerful
• Negation is Powerless for Boolean Slice Functions
• On the complexity of nonnegative matrix factorization
• On the depth complexity of formulas
• On the nonnegative rank of distance matrices
• Real rank versus nonnegative rank
• Reducibility by algebraic projections
• Representations of monotone Boolean functions by linear programs
• Separating monotone VP and VNP
• Some \(0/1\) polytopes need exponential size extended formulations

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)