Theory Seminar
— 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 dregular graphs are kcolorable with high probability when k >~ d/(2 log d), but polynomialtime *refutation* of kcolorings in random dregular 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 kcolorings in uniformly random dregular graphs is at least as hard as distinguishing such graphs from any "planted" distribution over kcolorable, dregular 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 dregular 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 nonbacktracking walks, semidefinite programming, and the use of randomness in numerical linear algebra.
Event Website:
http://theory.cs.cmu.edu/
For More Information:
praveshk@andrew.cmu.edu