On \(\epsilon\)-sensitive monotone computations

DOI10.1007/s00037-020-00196-6zbMath1461.68084OpenAlexW3044232313MaRDI QIDQ2198153

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)

Related Items (1)

On the extension complexity of polytopes separating subsets of the Boolean cube

Cites Work

• On the nonnegative rank of distance matrices
• Homogeneous formulas and symmetric polynomials
• Real rank versus nonnegative rank
• Negation can be exponentially powerful
• Reducibility by algebraic projections
• Expressing combinatorial optimization problems by linear programs
• Monotone simulations of non-monotone proofs.
• Some \(0/1\) polytopes need exponential size extended formulations
• Arithmetic Circuits: A survey of recent results and open questions
• On the Complexity of Nonnegative Matrix Factorization
• On the depth complexity of formulas
• Extension Complexity of Independent Set Polytopes
• The Matching Polytope has Exponential Extension Complexity
• Negation is Powerless for Boolean Slice Functions
• Separating monotone VP and VNP
• Linear vs. semidefinite extended formulations
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Algorithms in real algebraic geometry
• Depth-3 arithmetic circuits over fields of characteristic zero
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On \(\epsilon\)-sensitive monotone computations