Counterexamples to the Low-Degree Conjecture

A primary goal of computer science is to understand which problems can be solved by efficient algorithms. Given the formidable difficulty of proving unconditional computational hardness, stateof-the-art results typically rely on unproven conjectures. While many such results rely only upon the widely-believed conjecture P NP, other results have only been proven under stronger assumptions such as the unique games conjecture [Kho02, Kho05], the exponential time hypothesis [IP01], the learning with errors assumption [Reg09], or the planted clique hypothesis [Jer92, BR13]. It has also been fruitful to conjecture that a specific algorithm (or limited class of algorithms) is optimal for a suitable class of problems. This viewpoint has been particularly prominent in the study of average-case noisy statistical inference problems, where it appears that optimal performance over a large class of problems can be achieved by methods such as the sum-of-squares hierarchy (see [RSS18]), statistical query algorithms [Kea93, BFJ 94], the approximate message passing framework [DMM09, LKZ15], and low-degree polynomials [HS17, HKP 17, Hop18]. It is helpful to have such a conjectured-optimal meta-algorithm because this often admits a systematic analysis of hardness.