We discovered a serious error in one of our previous submissions to ECCC and wish to make sure that this mistake is publicly known. The main argument of the report TR06-133 is in error. The paper claims to prove the result of the title by reduction from the (Exists,k)-pebble game, ... more >>>

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 of refutations, and ... more >>>

This paper gives two distinct proofs of an exponential separation between regular resolution and unrestricted resolution. The previous best known separation between these systems was quasi-polynomial. more >>>