Random formulas, monotone circuits, and interpolation
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F17%3A00483703" target="_blank" >RIV/67985840:_____/17:00483703 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1109/FOCS.2017.20" target="_blank" >http://dx.doi.org/10.1109/FOCS.2017.20</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/FOCS.2017.20" target="_blank" >10.1109/FOCS.2017.20</a>
Alternative languages
Result language
angličtina
Original language name
Random formulas, monotone circuits, and interpolation
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
2017 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS)
ISBN
978-1-5386-3464-6
ISSN
0272-5428
e-ISSN
—
Number of pages
11
Pages from-to
121-131
Publisher name
IEEE
Place of publication
New York
Event location
Berkeley
Event date
Oct 15, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000417425300011