Number of the records: 1
Random formulas, monotone circuits, and interpolation
- 1.0483703 - MÚ 2018 RIV US eng C - Conference Paper (international conference)
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]
EU Projects: European Commission(XE) 339691 - FEALORA
Institutional support: RVO:67985840
Keywords : Cutting Planes * random formulas * interpolation
OECD category: 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.
Permanent Link: http://hdl.handle.net/11104/0278908
File Download Size Commentary Version Access Hrubes.pdf 11 296.4 KB Publisher’s postprint require
Number of the records: 1