Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > STEFAN DANTCHEV:
All reports by Author Stefan Dantchev:

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 >>>


TR18-024 | 1st February 2018
Olaf Beyersdorff, Judith Clymo, Stefan Dantchev, Barnaby Martin

The Riis Complexity Gap for QBF Resolution

We give an analogue of the Riis Complexity Gap Theorem for Quanti fied Boolean Formulas (QBFs). Every fi rst-order sentence $\phi$ without finite models gives rise to a sequence of QBFs whose minimal refutations in tree-like Q-Resolution are either of polynomial size (if $\phi$ has no models) or at least ... more >>>




ISSN 1433-8092 | Imprint