<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div dir="ltr"></div><div dir="ltr"><br><br><br>Begin forwarded message:<br><br></div><blockquote type="cite"><div dir="ltr"><b>From:</b> Jose J Fragoso <jfragoso@uchicago.edu><br><b>Date:</b> October 10, 2022 at 9:13:54 AM CDT<br><b>To:</b> colloquium@cs.uchicago.edu<br><b>Subject:</b> <b>[prof] [faculty-monday] [Colloquium] CS Theory Seminar - Sorrachai Yingchareonthawornchai, Tuesday, October 11, 2022</b><br><br></div></blockquote><blockquote type="cite"><div dir="ltr">
<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-face { font-family: Helvetica; }
@font-face { font-family: "Cambria Math"; }
@font-face { font-family: Calibri; }
p.MsoNormal, li.MsoNormal, div.MsoNormal { margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif; }
span.apple-converted-space { }
.MsoChpDefault { font-size: 10pt; }
@page WordSection1 { size: 8.5in 11in; margin: 1in; }
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]-->
<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" alt="image001.jpg" src="cid:image001.jpg@01D8D7D0.96623EA0"></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>
<br>
<o:p></o:p></p>
</div>
<span>_______________________________________________</span><br><span>Colloquium mailing list - Colloquium@mailman.cs.uchicago.edu</span><br><span>https://mailman.cs.uchicago.edu/mailman/listinfo/colloquium</span><br><span>_______________________________________________</span><br><span>Facultylunch mailing list</span><br><span>Facultylunch@mailman.cs.uchicago.edu</span><br><span>https://mailman.cs.uchicago.edu/cgi-bin/mailman/listinfo/facultylunch<span>_______________________________________________</span><br><span>Full-professor mailing list</span><br><span>Full-professor@mailman.cs.uchicago.edu</span><br><span>https://mailman.cs.uchicago.edu/cgi-bin/mailman/listinfo/full-professor</span><br></span></div></blockquote></body></html>