Abstract:
For many high dimensional inference problems—such as planted clique, sparse PCA, matching problems, or certain Stochastic Block Model (SBM) variants—there is a long track record of best-known polynomial-time methods (e.g., spectral, Sum of Squares, iterative) being well-characterized or matched by low-degree polynomial tests. In this context, "low-degree" means algorithms represented as polynomials of the input data of degree O(log(N)), where N is the data size. Consequently, the failure of all low-degree polynomial methods in these settings has been widely regarded as strong heuristic evidence that no polynomial-time algorithm can succeed.
In this talk, we examine low-degree polynomial hardness specifically for broadcasting on tree models: A random label assigned to the root of a tree and propagates downward, with each child node independently adopting a label conditioned only on its parent's label according to a Markov transition matrix. The tree reconstruction problem ask when it is possible to infer the root label from observations at the leaves labels. Although this model is known to admit efficient algorithms—most notably Belief Propagation—below the celebrated Kesten-Stigum bound, our recent work demonstrates that all polynomials of leaf labels with degree smaller than N^c exhibit vanishing correlation with the root labels. This result presents a natural counterexample to the prevailing heuristic and perhaps gives a better understanding on relations between low-degree hardness and computational hardness.
This is a joint work with Elchanan Mossel.
Bio：
Han Huang is currently an assistant professor at the University of Missouri. Previously, he was a postdoctoral researcher at MIT, mentored by Elchanan Mossel in 2023, and before that, he was a postdoc at Georgia Tech, working with Konstantin Tikhomirov. Han completed his Ph.D. at the University of Michigan in 2019 under the supervision of Mark Rudelson. His research interests include convex geometry, high-dimensional probability, and discrete inference problems.
