Random formulas, monotone circuits, and interpolation

0483703 - MÚ 2018 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
Hrubeš, Pavel - Pudlák, Pavel
Random formulas, monotone circuits, and interpolation.
2017 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS). New York: IEEE, 2017, s. 121-131. Annual IEEE Symposium on Foundations of Computer Science. ISBN 978-1-5386-3464-6. ISSN 0272-5428.
[58th IEEE Annual Symposium on Foundations of Computer Science (FOCS). Berkeley (US), 15.10.2017-17.10.2017]
GRANT EU: European Commission(XE) 339691 - FEALORA
Institucionální podpora: RVO:67985840
Klíčová slova: Cutting Planes * random formulas * interpolation
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
http://ieeexplore.ieee.org/document/8104052/

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.
Trvalý link: http://hdl.handle.net/11104/0278908