Theory Seminar

Friday, October 29, 2021 - 3:00pm to 4:00pm

Location:

In Person Only Gates Hillman 8102

Speaker:

JESS BANKS, Ph.D. Candidate https://math.berkeley.edu/~jbanks/

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:

http://theory.cs.cmu.edu/

For More Information, Contact:

Keywords:

Seminar Series