Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-106 | 16th June 2017 15:29

Representations of Monotone Boolean Functions by Linear Programs


Authors: Mateus de Oliveira Oliveira, Pavel Pudlak
Publication: 16th June 2017 15:30
Downloads: 2542


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. MLP circuits are superpolynomially stronger than monotone Boolean circuits.
2. MLP circuits are exponentially stronger than monotone span programs.
3. MLP circuits can be used to provide monotone feasibility interpolation theorems for Lovasz-Schrijver proof systems, and for mixed Lovasz-Schrijver proof systems.
4. The Lovasz-Schrijver proof system cannot be polynomially simulated by the cutting planes proof system. This is the first result showing a separation between these two proof systems.

Finally, we discuss connections between the problem of proving lower bounds on the size of MLPs and the problem of proving lower bounds on extended formulations of polytopes.

ISSN 1433-8092 | Imprint