Počet záznamů: 1
Random formulas, monotone circuits, and interpolation
- 1.
SYSNO ASEP 0483703 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název Random formulas, monotone circuits, and interpolation Tvůrce(i) Hrubeš, Pavel (MU-W) RID, SAI, ORCID
Pudlák, Pavel (MU-W) RID, SAIZdroj.dok. 2017 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS). - New York : IEEE, 2017 - ISSN 0272-5428 - ISBN 978-1-5386-3464-6 Rozsah stran s. 121-131 Poč.str. 11 s. Forma vydání Tištěná - P Akce 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS) Datum konání 15.10.2017 - 17.10.2017 Místo konání Berkeley Země US - Spojené státy americké Typ akce WRD Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova Cutting Planes ; random formulas ; interpolation Vědní obor RIV BA - Obecná matematika Obor OECD Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) Institucionální podpora MU-W - RVO:67985840 UT WOS 000417425300011 EID SCOPUS 85041112630 DOI 10.1109/FOCS.2017.20 Anotace We prove new lower bounds on the sizes of proofs in the Cutting Plane proof system, using a concept that we call unsatisfiability certificate. This approach is, essentially, equivalent to the well-known feasible interpolation method, but is applicable to CNF formulas that do not seem suitable for interpolation. Specifically, we prove exponential lower bounds for random k-CNFs, where k is the logarithm of the number of variables, and for the Weak Bit Pigeon Hole Principle. Furthermore, we prove a monotone variant of a hypothesis of Feige [12]. We give a superpolynomial lower bound on monotone real circuits that approximately decide the satisfiability of k-CNFs, where k =omega(1). For k approximate to log n, the lower bound is exponential. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2018
Počet záznamů: 1