Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FOURIER BASIS:
Reports tagged with Fourier basis:
TR24-046 | 6th March 2024
Sasank Mouli

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 ... more >>>




ISSN 1433-8092 | Imprint