Number of the records: 1
Representations of monotone Boolean functions by linear programs
- 1.
SYSNO ASEP 0511322 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title Representations of monotone Boolean functions by linear programs Author(s) de Oliveira Oliveira, M. (NO)
Pudlák, Pavel (MU-W) RID, SAIArticle number 22 Source Title ACM Transactions on Computation Theory. - : Association for Computing Machinery - ISSN 1942-3454
Roč. 11, č. 4 (2019)Number of pages 31 s. Language eng - English Country US - United States Keywords monotone linear programming circuits ; Lovász-Schrijver proof systems ; feasible interpolation Subject RIV BA - General Mathematics OECD category Pure mathematics Method of publishing Open access Institutional support MU-W - RVO:67985840 UT WOS 000496750000004 EID SCOPUS 85075615893 DOI 10.1145/3337787 Annotation 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 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2020 Electronic address http://dx.doi.org/10.1145/3337787
Number of the records: 1