<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body dir="auto">
<div><br>
</div>
<div align="left" dir="auto" style="font-size:100%;color:#000000"><br>
</div>
<div class="WordSection1" dir="auto">
<p class="MsoNormal"><i><span style="font-size:12.0pt; font-family:Helvetica; color:#8B0102">UNIVERSITY OF CHICAGO</span></i></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt; font-family:Helvetica; color:#8B0102">COMPUTER SCIENCE DEPARTMENT</span></i></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt; font-family:Helvetica; color:#8B0102">PRESENTS</span></i></p>
<p class="MsoNormal"><span style="font-size:11.0pt; color:black"> </span></p>
<p class="MsoNormal"><span style="font-size:11.0pt; color:black"> </span></p>
<p class="MsoNormal"><span style="font-size:11.0pt; color:black"> </span></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt; font-family:Helvetica; color:black">Sorrachai Yingchareonthawornchai
</span></b></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></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt; font-family:Helvetica; color:black"> </span></b></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt; font-family:Helvetica; color:black"> </span></b></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><img width="185" height="176" style="width: 1.927in; height: 1.8333in;" alt="images" src="cid:image001.jpg@01D8D7D0.96623EA0" id="Picture_x0020_2" onmouseover="imageMousePointerUpdate(true)" onmouseout="imageMousePointerUpdate(false)"></span></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt; font-family:Helvetica; color:black"> </span></b></p>
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt; font-family:Helvetica; color:black"> </span></b></p>
<p class="MsoNormal"><span style="font-size:11.0pt; color:black"> </span></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt; color:black">Tuesday, October 11, 2022 at 3:30pm</span></b></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt; color:black; background:yellow">Kent Chemical Laboratory, Room 107</span></b></p>
<p class="MsoNormal"><span style="font-size:11.0pt; color:black"> </span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span></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></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></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>
</p>
<p><span style="color:black"> </span></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>
<br>
<br>
</p>
</div>
</body>
</html>