Computational lower bounds via almost orthonormal polynomials

The thesis is at [this link].

Slides are at [this link].

Image credits

Gemini. The exact prompt was the thesis title.

Abstract

Low-degree lower bounds are an established method to claim average-case hardness for algorithms. When the null hypothesis is simple, an explicit orthonormal basis suffices to start the derivation. When it is not, advanced proof methods rely on a complex matrix inversion via recursive relations. In this work, we present a new proof technique to find low-degree lower bounds for any type of null distribution. It relies on finding an “almost orthonormal” basis. Specifically, we exploit symmetries in the distributions and the graphical structure to adjust orthogonal polynomials for simple null hypotheses. With the right fixes, correlations decay fast enough to reproduce the classical proof. We present the steps for a motivating example: the planted sub-matrix model. The observation is a binary matrix such that the entries are more likely to be positive if they belong to a latent clique of vertices of random size. After establishing a low-degree lower bound for this model, we argue that our method works for many others. The progression is adaptive, with sections for readers not familiar with low-degree polynomials and average-case hardness in general.