<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=us-ascii">
<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;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:10.0pt;
font-family:"Calibri",sans-serif;}
span.apple-converted-space
{mso-style-name:apple-converted-space;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@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="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">UNIVERSITY OF CHICAGO</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">COMPUTER SCIENCE DEPARTMENT</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">PRESENTS</span></i><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica;color:black">Sorrachai Yingchareonthawornchai
</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica">Aalto
<span style="color:black">University</span>, Espoo, Finland</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica;color:black"> </span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica;color:black"> </span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><img width="185" height="176" style="width:1.927in;height:1.8333in" id="Picture_x0020_2" src="cid:image001.jpg@01D8D7D0.96623EA0" alt="images"></span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica;color:black"> </span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica;color:black"> </span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;color:black">Tuesday, October 11, 2022 at 3:30pm</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;color:black;background:yellow">Kent Chemical Laboratory, Room 107</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p><b><i><span style="font-size:12.0pt">Title:</span></i></b><span style="font-size:12.0pt">
</span><b><span style="font-size:14.0pt">Deterministic Small Vertex Connectivity in Almost Linear Time</span></b><span style="font-size:12.0pt">
</span><o:p></o:p></p>
<p><span style="font-size:12.0pt"><br>
<b><i>Abstract:</i> </b> In the vertex connectivity problem, given an undirected n-vertex<br>
m-edge graph, we need to compute the minimum number of vertices<br>
that can disconnect the graph after removing them. This problem is one<br>
of the most well-studied graph problems. From 2019, a new line of<br>
work [Nanongkai et al. STOC'19;SODA'20;STOC'21] has used<br>
randomized techniques to break the quadratic-time barrier and, very<br>
recently, culminated in an almost-linear time algorithm via the recently<br>
announced maxflow algorithm by Chen et al. In contrast, all known deterministic algorithms are much slower. The fastest algorithm [Gabow<br>
FOCS'00] takes O(m(n+\min\{c^{5/2},cn^{3/4}\})) time where c<br>
is the vertex connectivity. It remains open whether there exists a subquadratic-time deterministic algorithm for any constant<br>
c>3.<br>
<br>
In this talk, we present the first deterministic almost-linear time<br>
vertex connectivity algorithm for all constants c. Our<br>
running time is m^{1+o(1)}2^{O(c^{2})} time, which is almost-linear<br>
for all c=o(\sqrt{\log n}). This is the first deterministic algorithm<br>
that breaks the O(n^{2})-time bound on sparse graphs where m=O(n), which is known for more<br>
than 50 years ago [Kleitman'69].<br>
<br>
Towards our result, we give a new reduction framework to vertex<br>
expanders which in turn exploits our new almost-linear time construction<br>
of mimicking network for vertex connectivity. The<br>
previous construction by Kratsch and Wahlstr\"{o}m [FOCS'12]<br>
requires large polynomial time and is randomized.<br>
An interesting aspect that allows our overall algorithm to be efficient is to ``lift'' several graph problems to hypergraphs and work directly on hypergraphs.</span><o:p></o:p></p>
<p><b><i><span style="font-size:12.0pt">Bio:</span></i></b><span style="font-size:12.0pt">
<span style="color:black;background:#FDFDFD">I am a Doctoral Researcher at Aalto University in Espoo, Finland.</span></span>
<o:p></o:p></p>
<p><span style="color:black"> </span><o:p></o:p></p>
<p style="margin-bottom:12.0pt"><b><span style="font-size:12.0pt;font-family:Helvetica;color:black">Host:<span class="apple-converted-space"> </span></span></b><b><span style="font-size:14.0pt;color:black">Janos Simon</span></b><br>
<br>
<br>
<br>
<o:p></o:p></p>
</div>
</body>
</html>