Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Res(k):
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 >>>

TR23-068 | 10th May 2023
Ben Davis, Robert Robere

Colourful TFNP and Propositional Proofs

Recent work has shown that many of the standard TFNP classes — such as PLS, PPADS, PPAD, SOPL, and EOPL — have corresponding proof systems in propositional proof complexity, in the sense that a total search problem is in the class if and only if the totality of the problem ... more >>>

ISSN 1433-8092 | Imprint