Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with cutting plane proofs:
TR12-039 | 17th April 2012
Stasys Jukna

Clique Problem, Cutting Plane Proofs, and Communication Complexity

Motivated by its relation to the length of cutting plane proofs for the Maximum Biclique problem, here we consider the following communication game on a given graph G, known to both players. Let K be the maximal number of vertices in a complete bipartite subgraph of G (which is not ... more >>>

TR17-042 | 6th March 2017
Pavel Hrubes, Pavel Pudlak

Random formulas, monotone circuits, and interpolation

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

ISSN 1433-8092 | Imprint