Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BINARY ENCODINGS:
Reports tagged with Binary Encodings:
TR18-165 | 20th September 2018
Stefan Dantchev, Nicola Galesi, Barnaby Martin

Resolution and the binary encoding of combinatorial principles

We investigate the size complexity of proofs in $RES(s)$ -- an extension of Resolution working on $s$-DNFs instead of clauses -- for families of contradictions given in the {\em unusual binary} encoding. A motivation of our work is size lower bounds of refutations in Resolution for families of contradictions in ... more >>>




ISSN 1433-8092 | Imprint