  Consider a system of $m$ polynomial equations $\{p_i(x) = b_i\}_{i \leq m}$
of degree $D\geq 2$ in $n$-dimensional variable $x \in \mathbb{R}^n$ such that
each coefficient of every $p_i$ and $b_i$s are chosen at random and
independently from some continuous distribution. We study the basic question of
determining the smallest $m$ -- the algorithmic threshold -- for which
efficient algorithms can find refutations (i.e. certificates of
unsatisfiability) for such systems. This setting generalizes problems such as
refuting random SAT instances, low-rank matrix sensing and certifying
pseudo-randomness of Goldreich's candidate generators and generalizations.
  We show that for every $d \in \mathbb{N}$, the $(n+m)^{O(d)}$-time canonical
sum-of-squares (SoS) relaxation refutes such a system with high probability
whenever $m \geq O(n) \cdot (\frac{n}{d})^{D-1}$. We prove a lower bound in the
restricted low-degree polynomial model of computation which suggests that this
trade-off between SoS degree and the number of equations is nearly tight for
all $d$. We also confirm the predictions of this lower bound in a limited
setting by showing a lower bound on the canonical degree-$4$ sum-of-squares
relaxation for refuting random quadratic polynomials. Together, our results
provide evidence for an algorithmic threshold for the problem at $m \gtrsim
\widetilde{O}(n) \cdot n^{(1-\delta)(D-1)}$ for $2^{n^{\delta}}$-time
algorithms for all $\delta$.
