Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Representations of Monotone Boolean Functions by Linear Programs

Representations of Monotone Boolean Functions by Linear Programs We introduce the notion of monotone linear programming circuits (MLP circuits), a model of computation for partial Boolean functions. Using this model, we prove the following results.1 (1) MLP circuits are superpolynomially stronger than monotone Boolean circuits. (2) MLP circuits are exponentially stronger than monotone span programs over the reals. (3) MLP circuits can be used to provide monotone feasibility interpolation theorems for Lovász-Schrijver proof systems and for mixed Lovász-Schrijver proof systems. (4) The Lovász-Schrijver proof system cannot be polynomially simulated by the cutting planes proof system. Finally, we establish connections between the problem of proving lower bounds for the size of MLP circuits and the field of extension complexity of polytopes. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Representations of Monotone Boolean Functions by Linear Programs

Download PDF
31 pages

Loading next page...
 
/lp/association-for-computing-machinery/representations-of-monotone-boolean-functions-by-linear-programs-v3IkZAU68V
Publisher
Association for Computing Machinery
Copyright
Copyright © 2019 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3337787
Publisher site
See Article on Publisher Site

Abstract

We introduce the notion of monotone linear programming circuits (MLP circuits), a model of computation for partial Boolean functions. Using this model, we prove the following results.1 (1) MLP circuits are superpolynomially stronger than monotone Boolean circuits. (2) MLP circuits are exponentially stronger than monotone span programs over the reals. (3) MLP circuits can be used to provide monotone feasibility interpolation theorems for Lovász-Schrijver proof systems and for mixed Lovász-Schrijver proof systems. (4) The Lovász-Schrijver proof system cannot be polynomially simulated by the cutting planes proof system. Finally, we establish connections between the problem of proving lower bounds for the size of MLP circuits and the field of extension complexity of polytopes.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Jul 20, 2019

Keywords: Lovász-Schrijver proof systems

References

  • Satisfiability, branch-width and Tseitin tautologies
    Alekhnovich, Michael; Razborov, Alexander A.
  • Superpolynomial lower bounds for monotone span programs
    Babai, László; Gál, Anna; Wigderson, Avi
  • Lower bounds on Hilbert’s Nullstellensatz and propositional proofs
    Beame, Paul; Impagliazzo, Russell; Krajíček, Jan; Pitassi, Toniann; Pudlák, Pavel
  • Lower bounds for cutting planes proofs with small coefficients
    Bonet, Maria Luisa; Pitassi, Toniann; Raz, Ran
  • Approximation limits of linear programs (beyond hierarchies)
    Braun, Gábor; Fiorini, Samuel; Pokutta, Sebastian; Steurer, David
  • An information complexity approach to extended formulations
    Braverman, Mark; Moitra, Ankur
  • Good degree bounds on Nullstellensatz refutations of the induction principle
    Buss, Samuel R.; Pitassi, Toniann
  • Representations of monotone Boolean functions by linear programs
    de Oliveira Oliveira, Mateus; Pudlák, Pavel
  • Exponential lower bounds for polytopes in combinatorial optimization
    Fiorini, Samuel; Massar, Serge; Pokutta, Sebastian; Tiwary, Hans Raj; De Wolf, Ronald
  • Lower bounds on sizes of cutting planes proofs for modular coloring principles
    Fu, Xudong
  • A characterization of span program size and improved lower bounds for monotone span programs
    Gál, Anna
  • A note on monotone complexity and the rank of matrices
    Gál, Anna; Pudlák, Pavel
  • Smallest compact formulation for the permutahedron
    Goemans, Michel X.
  • Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
    Grigoriev, Dima
  • Complexity of semi-algebraic proofs
    Grigoriev, Dima; Hirsch, Edward A; Pasechnik, Dmitrii V
  • The intractability of resolution
    Haken, Armin
  • An exponential lower bound for the size of monotone real circuits
    Haken, Armin; Cook, Stephen A
  • Lower bounds for the polynomial calculus and the Gröbner basis algorithm
    Impagliazzo, Russell; Pudlák, Pavel; Sgall, Jiri
  • On span programs
    Karchmer, M.; Wigderson, A.
  • Lower bounds of static Lovász-Schrijver calculus proofs for tseitin tautologies
    Kojevnikov, Arist; Itsykson, Dmitry
  • Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
    Krajíček, Jan
  • Interpolation and approximate semantic derivations
    Krajíček, Jan
  • Cones of matrices and set-functions and 0-1 optimization
    Lovász, László; Schrijver, Alexander
  • Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures
    Pitassi, Toniann; Segerlind, Nathan
  • Lower bounds for resolution and cutting plane proofs and monotone computations
    Pudlák, Pavel
  • On the complexity of the propositional calculus
    Pudlák, Pavel
  • Algebraic models of computation and interpolation for algebraic proof systems
    Pudlák, Pavel; Sgall, Jiri
  • Monotone circuits for matching require linear depth
    Raz, Ran; Wigderson, Avi
  • Lower bounds on monotone complexity of the logical permanent
    Razborov, Alexander A.
  • Lower bounds for monotone complexity of boolean functions
    Razborov, Alexander A.
  • Unprovability of circuit size lower bounds in certain fragments of bounded arithmetic
    Razborov, Alexander A.
  • Proof complexity and beyond
    Razborov, Alexander A.
  • Exponential lower bounds for monotone span programs
    Robere, Robert; Pitassi, Toniann; Rossman, Benjamin; Cook, Stephen A
  • The matching polytope has exponential extension complexity
    Rothvoß, Thomas
  • Combinatorial Optimization: Polyhedra and Efficiency
    Schrijver, Alexander