Representations of monotone Boolean functions by linear programs

DOI10.4230/LIPICS.CCC.2017.3MaRDI QIDQ5111133zbMATH OpenFDO

Authors Mateus de Oliveira Oliveira, Pavel Pudlák

Publication date 26 May 2020

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2017.3

zbMATH Keywords

lower boundsfeasible interpolationLovász-Schrijver proof systemcutting-planes proof systemmonotone linear programming circuits

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

• Representations of monotone Boolean functions by linear programs
• Lower bounds for resolution and cutting plane proofs and monotone computations
• scientific article; zbMATH DE number 3877103
• Monotone projection lower bounds from extended formulation lower bounds
• On the Power of Symmetric Linear Programs

Cited in

(7)

• Representations of monotone Boolean functions by linear programs
• Shattered sets and the Hilbert function
• scientific article; zbMATH DE number 3877103 (Why is no real title available?)
• Monotone projection lower bounds from extended formulation lower bounds
• Joint realizability of monotone Boolean functions
• Replaceability and computational equivalence for monotone boolean functions
• On \(\epsilon\)-sensitive monotone computations

This page was built for publication: Representations of monotone Boolean functions by linear programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111133)