Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-042 | 6th March 2017 12:07

Random formulas, monotone circuits, and interpolation

RSS-Feed




TR17-042
Authors: Pavel Hrubes, Pavel Pudlak
Publication: 6th March 2017 12:08
Downloads: 313
Keywords: 


Abstract:

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$ 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.



ISSN 1433-8092 | Imprint