Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RESOLUTION WIDTH:
Reports tagged with Resolution Width:
TR02-035 | 27th May 2002
Albert Atserias, VĂ­ctor Dalmau

A Combinatorial Characterization of Resolution Width

We provide a characterization of the resolution
width introduced in the context of Propositional Proof Complexity
in terms of the existential pebble game introduced
in the context of Finite Model Theory. The characterization
is tight and purely combinatorial. Our
first application of this result is a surprising
proof that the ... more >>>


TR06-133 | 14th October 2006
Alex Hertel, Alasdair Urquhart

The Resolution Width Problem is EXPTIME-Complete

The importance of {\em width} as a resource in resolution theorem proving
has been emphasized in work of Ben-Sasson and Wigderson. Their results show that lower
bounds on the size of resolution refutations can be proved in a uniform manner by
demonstrating lower bounds on the width ... more >>>


TR24-128 | 27th August 2024
Yaroslav Alekseev, Dmitry Itsykson

Lifting to regular resolution over parities via games

Revisions: 1

The propositional proof system resolution over parities (Res($\oplus$)) combines resolution and the linear algebra over GF(2). It is a challenging open question to prove a superpolynomial lower bound on the proof size in this system. For many years, superpolynomial lower bounds were known only in tree-like cases. Recently, Efremenko, Garlik, ... more >>>




ISSN 1433-8092 | Imprint