[Proof Complexity] New preprint

[Neil Thapen]

Dear colleagues,

A new preprint, "A trade-off between length and width in resolution" is 
available at http://users.math.cas.cz/~thapen/length_width.pdf
Any comments or corrections are welcome.

The abstract is: We describe a family of CNF formulas in n variables, with
small initial width, which have polynomial length resolution refutations.
By a result of Ben-Sasson and Wigderson it follows that they must also
have narrow resolution refutations, of width O(\sqrt{nlogn}). We show 
that, for our formulas, this decrease in width comes at the expense of an 
increase in size, and any such narrow refutations must have exponential 
length.


Best,

Neil