[Colloquium] U of C - CS Theory Seminar, Tuesday, May 7

[Jose J Fragoso]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS


Dmitriy (Tim) Kunisky, PhD
Yale University

 [Dmitriy (Tim) Kunisky Talk -- Spring ...]
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.

Based on recent joint work with Xifan Yu.


Bio: Tim Kunisky is a postdoctoral associate at Yale University, hosted by Dan Spielman in the Department of Computer Science. He previously graduated with a bachelor's degree in mathematics from Princeton University, worked on machine learning for ranking problems and natural language processing at Google, and received his PhD in mathematics from the Courant Institute of Mathematical Sciences at New York University, where he was advised by Afonso Bandeira and G‌érard Ben Arous. His main research interests concern how probability theory and mathematical statistics interact with computational complexity and the theory of algorithms.




Host: Aaron Potechin

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240425/9ca2ea20/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 5513 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240425/9ca2ea20/attachment-0001.jpg>