Maria Luisa Bonet, Juan Luis Esteban, Jan Johannsen

We prove an exponential lower bound for tree-like Cutting Planes

refutations of a set of clauses which has polynomial size resolution

refutations. This implies an exponential separation between tree-like

and dag-like proofs for both Cutting Planes and resolution; in both

cases only superpolynomial separations were known before.

In order to ...
more >>>

Dmitry Itsykson, Artur Riazanov

A canonical communication problem ${\rm Search}(\phi)$ is defined for every unsatisfiable CNF $\phi$: an assignment to the variables of $\phi$ is distributed among the communicating parties, they are to find a clause of $\phi$ falsified by this assignment. Lower bounds on the randomized $k$-party communication complexity of ${\rm Search}(\phi)$ in ... more >>>