Representations of monotone Boolean functions by linear programs

DOI10.1145/3337787MaRDI QIDQ5205818zbMATH OpenOpenAlexFDO

Authors Mateus de Oliveira Oliveira, Pavel Pudlák

Publication date 16 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/7520/

zbMATH Keywords

feasible interpolationLovász-Schrijver proof systemsmonotone linear programming circuits

Mathematics Subject Classification ID

Complexity of proofs (03F20) Networks and circuits as models of computation; circuit complexity (68Q06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Representations of monotone Boolean functions by linear programs
• Superpolynomial lower bounds for monotone span programs
• On \(\epsilon\)-sensitive monotone computations
• scientific article; zbMATH DE number 3877103
• Monotone real circuits are more powerful than monotone Boolean circuits

Cited in

(8)

• Joint realizability of monotone Boolean functions
• scientific article; zbMATH DE number 3877103 (Why is no real title available?)
• Shattered sets and the Hilbert function
• Representations of monotone Boolean functions by linear programs
• On the complexity of computing a random Boolean function over the reals
• scientific article; zbMATH DE number 7300360 (Why is no real title available?)
• On protocols for monotone feasible interpolation
• Replaceability and computational equivalence for monotone boolean functions

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 Q5205818)