Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable

Sasank Mouli

For every $n>0$, we show the existence of a CNF tautology over $O(n^2)$ variables of width $O(\log n)$ such that it has a Polynomial Calculus Resolution refutation over $\{0,1\}$…