  It has often been claimed in recent papers that one can find a degree d
Sum-of-Squares proof if one exists via the Ellipsoid algorithm. In [O17], Ryan
O'Donnell notes this widely quoted claim is not necessarily true. He presents
an example of a polynomial system with bounded coeffcients that admits
low-degree proofs of non-negativity, but these proofs necessarily involve
numbers with an exponential number of bits, causing the Ellipsoid algorithm to
take exponential time. In this paper we obtain both positive and negative
results on the bit complexity of SoS proofs. First, we propose a suffcient
condition on a polynomial system that implies a bound on the coefficients in an
SoS proof. We demonstrate that this sufficient condition is applicable for
common use-cases of the SoS algorithm, such as Max-CSP, Balanced Separator,
Max- Clique, Max-Bisection, and Unit-Vector constraints. On the negative side,
O'Donnell asked whether every polynomial system containing Boolean constraints
admits proofs of polynomial bit complexity. We answer this question in the
negative, giving a counterexample system and non-negative polynomial which has
degree two SoS proofs, but no SoS proof with small coefficients until degree
Omega(sqrt(n))
