  A conjecture of Hopkins (2018) posits that for certain high-dimensional
hypothesis testing problems, no polynomial-time algorithm can outperform
so-called "simple statistics", which are low-degree polynomials in the data.
This conjecture formalizes the beliefs surrounding a line of recent work that
seeks to understand statistical-versus-computational tradeoffs via the
low-degree likelihood ratio. In this work, we refute the conjecture of Hopkins.
However, our counterexample crucially exploits the specifics of the noise
operator used in the conjecture, and we point out a simple way to modify the
conjecture to rule out our counterexample. We also give an example illustrating
that (even after the above modification), the symmetry assumption in the
conjecture is necessary. These results do not undermine the low-degree
framework for computational lower bounds, but rather aim to better understand
what class of problems it is applicable to.
