Počet záznamů: 1
Representations of monotone Boolean functions by linear programs
- 1.
SYSNO ASEP 0511322 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Representations of monotone Boolean functions by linear programs Tvůrce(i) de Oliveira Oliveira, M. (NO)
Pudlák, Pavel (MU-W) RID, SAIČíslo článku 22 Zdroj.dok. ACM Transactions on Computation Theory. - : Association for Computing Machinery - ISSN 1942-3454
Roč. 11, č. 4 (2019)Poč.str. 31 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova monotone linear programming circuits ; Lovász-Schrijver proof systems ; feasible interpolation Vědní obor RIV BA - Obecná matematika Obor OECD Pure mathematics Způsob publikování Open access Institucionální podpora MU-W - RVO:67985840 UT WOS 000496750000004 EID SCOPUS 85075615893 DOI 10.1145/3337787 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2020 Elektronická adresa http://dx.doi.org/10.1145/3337787
Počet záznamů: 1