Theory of Computing
-------------------
Title     : Polynomial Calculus Space and Resolution Width
Authors   : Nicola Galesi, Leszek A. Kolodziejczyk, and Neil Thapen
Volume    : 21
Number    : 6
Pages     : 1-29
URL       : https://theoryofcomputing.org/articles/v021a006

Abstract
--------

We show that if a $k$-CNF requires width $w$ to refute in resolution,
then it requires space $\sqrt w$ to refute in polynomial calculus,
where the _space_ of a polynomial calculus refutation is the number of
monomials that must be kept in memory when working through the proof.
This is the first analogue, in polynomial calculus, of Atserias and
Dalmau's result that, in resolution, width is a lower bound on clause
space.

As a by-product of our new approach to space lower bounds we give a
simple proof of Bonacina's recent result that total space in
resolution (the total number of variable occurrences that must be kept
in memory) is at least the width squared.

As corollaries of the main result we obtain some new lower bounds on
the PCR space needed to refute specific formulas, as well as partial
answers to some open problems about relations between space, size, and
degree for polynomial calculus.


--------------

A conference version of this paper appeared in the Proceedings of the
60th Annual Symposium on Foundations of Computer Science (FOCS'19).