Monomial-size vs. Bit-complexity in Sums-of-Squares and Polynomial Calculus

Tuomas Hakoniemi

In this paper we consider the relationship between monomial-size and bit-complexity in Sums-of-Squares (SOS) in Polynomial Calculus Resolution over rationals (PCR/$\mathbb{Q}$). We…