[Theory] UC Theory Seminar

[Alexander Razborov]

Dmitriy (Tim) Kunisky, PhD
Yale University
 
 
Tuesday, May 7, 2024 at 3:30pm
Room – Kent 107
 
 
Title: Computational hardness of testing for graph lifts and certifying properties of random regular graphs
 
Abstract: 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" 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.
Bio: Dmitriy (Tim) Kunisky is a postdoctoral associate at Yale University’s Department of Computer Science.  He received his PhD at the Courant Institute of Mathematical Sciences at New York University advised by Afonso Bandeira and Gerard Ben Arous.  Recently, He has taught survey topics courses for graduate students on Modern Probability for Theoretical Computer Science and Sum-of-Squares Optimization.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20240430/cdf414a5/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 5513 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20240430/cdf414a5/attachment.jpg>