Codes and Expansions (CodEx) Seminar

Afonso S. Bandeira (ETH Zurich)
Hardness of refuting coloring in random graphs and quiet computational planting

In this talk we will address the problem of refuting the existence of rare structure in random data. We will focus on vertex colorings of random d regular graphs and show how to plant a coloring with far fewer colors than it is typical of a random graph while giving evidence that this construction is computationally indistinguishable from a uniformly drawn graph. Time permitting, we will also discuss lower bounds on the SK Hamiltonian, Sparse PCA, and Matrix RIP certification. Joint work with: Jess Banks (Berkeley), Tim Kunisky (NYU), Cris Moore (Santa Fe), and Alex Wein (NYU).