ECCC-Report TR17-042https://eccc.weizmann.ac.il/report/2017/042Comments and Revisions published for TR17-042en-usMon, 06 Mar 2017 12:08:12 +0200
Paper TR17-042
| Random formulas, monotone circuits, and interpolation |
Pavel Pudlak,
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2017/042We 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$ 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. We give a superpolynomial lower bound on monotone real circuits that approximately decide the satisfiability of $k$-CNFs, where $k=\omega(1)$. For $k\approx\log n$, the lower bound is exponential.Mon, 06 Mar 2017 12:08:12 +0200https://eccc.weizmann.ac.il/report/2017/042