Codes and Expansions (CodEx) Seminar

Dmitriy Kunisky (Johns Hopkins University):
Computational hardness of testing for graph lifts and certifying properties of random regular graphs

Certification tasks ask an algorithm to output a quantity that is guaranteed to be a bound on an optimization problem. I will present a new form of evidence that certification tasks over random regular graphs—say, certifying bounds on the chromatic number, maximum cut, or expansion of a graph—are computationally hard. Rather than proving lower bounds against concrete certification algorithms like convex relaxations, this argument will draw a connection with computational statistics, showing that a good certification algorithm could solve a hypothesis testing task that we believe to be difficult.

The key innovation will be a means of “quietly planting” unusual structures in regular graphs in a way that is hard to detect by taking random lifts of a suitable base graph. For regular graphs of fixed degree, I will give evidence that random lifts are hard to distinguish from uniformly random graphs provided that the base graph is Ramanujan. This gives a surprising connection between certification and the extremal properties of Ramanujan graphs, and allows for simple “proofs by example&rduo; of the hardness of certification by merely exhibiting specific finite Ramanujan graphs with various properties. I will show how this approach gives the first evidence for the hardness of certification of many properties of random regular graphs and will present numerous intriguing open problems that it suggests.

Based on recent joint work with Xifan Yu.