Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable
<|reference_start|>Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable: 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\}$ variables of size $O(n^3polylog(n))$ but any Polynomial Calculus refutation over $\{+1,-1\}$ variables requires size $2^{\Omega(n)}$. This shows that Polynomial Calculus sizes over the $\{0,1\}$ and $\{+1,-1\}$ bases are incomparable (since Tseitin tautologies show a separation in the other direction) and answers an open problem posed by Sokolov [Sok20] and Razborov.<|reference_end|>
@article{mouli2024polynomial,
    title={Polynomial Calculus sizes over the Boolean and Fourier bases are
  incomparable},
    author={Sasank Mouli},
    journal={arXiv preprint arXiv:2403.03933},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.03933},
    primaryClass={cs.CC math.LO}
}