Theory Seminar

— 4:00pm

In Person Only - Gates Hillman 8102

JESS BANKS , Ph.D. Candidate

Refutation and Computationally Quiet Planting of Cuts and Colorings in Random Graphs

Random d-regular graphs are k-colorable with high probability when k >~ d/(2 log d), but polynomial-time *refutation* of k-colorings in random d-regular graphs has only been achieved when k <~ sqrt(d)/2. I'll give some evidence that threshold is a fundamental feature of the problem — and conjecture that no polynomial time refutation algorithm can improve on it.

The main observation is that refuting k-colorings in uniformly random d-regular graphs is at least as hard as distinguishing such graphs from any "planted" distribution over k-colorable, d-regular graphs. So motivated, I'll introduce a particular "quietly planted" distribution and give evidence that, for infinitely many d and k, this quiet model is indistinguishable in polynomial time from uniformly random d-regular graphs whenever k >~ sqrt(d)/2. I'll also talk about a surprising connection to Ramanujan graphs.

Joint work with Afonso Bandeira, Cris Moore, Tim Kunisky, and Alex Wein.

Jess Banks is a PhD student in the mathematics department, working with Nikhil Srivastava. Her research spans theoretical computer science, probability, and statistical physics, with particular focus on non-backtracking walks, semidefinite programming, and the use of randomness in numerical linear algebra.

Event Website:

For More Information: