BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Resolution and the binary encodings of combinatorial principles Galesi, Nicola


We compare the complexity of refuting the binary and unary versions of large classes of combinatorial principles in Resolution and its extension Res(s) to s-DNFs. In particular we prove size lower bonds in Res(s) for the binary versions of the weak pigeonhole principle and the k-clique principle. The talk is based on a joint work with Stefan Dantchev and Barnaby Martin.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International