[Proof Complexity] New paper

[Neil Thapen]

Dear colleagues,

A new preprint by Ilario Bonacina, Nicola Galesi and myself,
"Total space in resolution", is available on ECCC at 
http://eccc.hpi-web.de/report/2014/038/
Comments, corrections and suggestions are appreciated.

The abstract is:
We show Omega(n^2) lower bounds on the total space used in resolution 
refutations of random k-CNFs over n variables, and of the graph pigeonhole 
principle and the bit pigeonhole principle for n holes. This answers the 
long-standing open problem of whether there are families of k-CNF formulas 
of size O(n) requiring total space Omega(n^2) in resolution, and gives the 
first truly quadratic lower bounds on total space. The results follow from a 
more general theorem showing that, for formulas satisfying certain 
conditions, in every resolution refutation there is a memory configuration 
containing many clauses of large width.

Regards,

Neil