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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International