<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=windows-1256">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:0 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Aptos;
panose-1:2 11 0 4 2 2 2 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:12.0pt;
font-family:"Aptos",sans-serif;}
span.apple-converted-space
{mso-style-name:apple-converted-space;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
mso-ligatures:none;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="#467886" vlink="#96607D" style="word-wrap:break-word">
<div class="WordSection1">
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><span style="color:black"> </span><o:p></o:p></p>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<p class="MsoNormal"><i><span style="font-family:Helvetica;color:#8B0102">UNIVERSITY OF CHICAGO</span></i><o:p></o:p></p>
<p class="MsoNormal" style="font-variant-caps:normal;orphans:auto;text-align:start;widows:auto;word-spacing:0px">
<i><span style="font-family:Helvetica;color:#8B0102">COMPUTER SCIENCE DEPARTMENT</span></i><o:p></o:p></p>
<p class="MsoNormal" style="font-variant-caps:normal;orphans:auto;text-align:start;widows:auto;word-spacing:0px">
<i><span style="font-family:Helvetica;color:#8B0102">PRESENTS</span></i><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal" style="font-variant-caps:normal;orphans:auto;text-align:start;widows:auto;word-spacing:0px">
<b><span style="font-family:Helvetica">Dmitriy (Tim) Kunisky<span style="color:#212121">, PhD</span></span></b><o:p></o:p></p>
<p class="MsoNormal"><b>Yale<span style="color:#212121"> University</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#212121"> </span><o:p></o:p></p>
<p class="MsoNormal" style="font-variant-caps:normal;orphans:auto;text-align:start;widows:auto;word-spacing:0px">
<span style="font-size:10.0pt;font-family:"Calibri",sans-serif;color:#212121"> </span><span style="font-size:10.0pt;font-family:"Calibri",sans-serif"><img width="231" height="180" style="width:2.4062in;height:1.875in" id="Picture_x0020_1" src="cid:image001.jpg@01DA958C.B5F7B1C0" alt="Dmitriy (Tim) Kunisky Talk -- Spring ..."></span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:black;background:yellow">Tuesday, May 7, 2024 at 3:30pm</span></b><o:p></o:p></p>
<p class="MsoNormal" style="font-variant-caps:normal;orphans:auto;text-align:start;widows:auto;word-spacing:0px">
<b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:black;background:yellow">Room – Kent 107</span></b><o:p></o:p></p>
<p class="MsoNormal" style="font-variant-caps:normal;orphans:auto;text-align:start;widows:auto;word-spacing:0px">
<span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:11.0pt;color:#212121">Title:</span></i></b><span class="apple-converted-space"><span style="font-size:11.0pt;color:#212121"> </span></span><b><span style="font-size:14.0pt;font-family:"Calibri",sans-serif;color:#212121">Computational
hardness of testing for graph lifts and certifying properties of random regular graphs</span></b><o:p></o:p></p>
<p class="MsoNormal" style="font-variant-caps:normal;orphans:auto;text-align:start;widows:auto;word-spacing:0px">
<span style="font-size:11.0pt;color:#212121"> </span><o:p></o:p></p>
<p class="MsoNormal" style="font-variant-caps:normal;orphans:auto;text-align:start;widows:auto;word-spacing:0px">
<b><i><span style="font-size:11.0pt;color:#212121">Abstract:</span></i></b><span class="apple-converted-space"><b><span style="font-size:11.0pt;color:#212121"> </span></b></span><span style="font-family:"Calibri",sans-serif;color:#212121">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.<br>
<br>
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.<br>
<br>
Based on recent joint work with Xifan Yu.</span><o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:11.0pt"> </span></i></b><o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:11.0pt"> </span></i></b><o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:11.0pt;color:#212121">Bio</span></i></b><span style="font-size:11.0pt;color:#212121">:<span class="apple-converted-space"> </span></span><span style="font-family:"Calibri",sans-serif;color:#212121">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.</span><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal" style="font-variant-caps:normal;orphans:auto;text-align:start;widows:auto;word-spacing:0px">
<span style="color:#212121"> </span><o:p></o:p></p>
<p class="MsoNormal" style="font-variant-caps:normal;orphans:auto;text-align:start;widows:auto;word-spacing:0px">
<span style="font-size:10.0pt;font-family:"Calibri",sans-serif;color:#212121"> </span><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><b>Host: Aaron Potechin</b><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>