[Colloquium] CS Theory Seminar - Sorrachai Yingchareonthawornchai, Tuesday, October 11, 2022

[Jose J Fragoso]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS



Sorrachai Yingchareonthawornchai
Michigan State University


[images]




Tuesday, October 11, 2022 at 3:30pm
Kent Chemical Laboratory, Room 107



Title: Deterministic Small Vertex Connectivity in Almost Linear Time

Abstract:  In the vertex connectivity problem, given an undirected n-vertex
m-edge graph, we need to compute the minimum number of vertices
that can disconnect the graph after removing them. This problem is one
of the most well-studied graph problems. From 2019, a new line of
work [Nanongkai et al. STOC'19;SODA'20;STOC'21] has used
randomized techniques to break the quadratic-time barrier and, very
recently, culminated in an almost-linear time algorithm via the recently
announced maxflow algorithm by Chen et al. In contrast, all known deterministic algorithms are much slower. The fastest algorithm [Gabow
FOCS'00] takes O(m(n+\min\{c^{5/2},cn^{3/4}\})) time where c
is the vertex connectivity. It remains open whether there exists a subquadratic-time deterministic algorithm for any constant
c>3.

In this talk, we present the first deterministic almost-linear time
vertex connectivity algorithm for all constants c. Our
running time is m^{1+o(1)}2^{O(c^{2})} time, which is almost-linear
for all c=o(\sqrt{\log n}). This is the first deterministic algorithm
that breaks the O(n^{2})-time bound on sparse graphs where m=O(n), which is known for more
than 50 years ago [Kleitman'69].

Towards our result, we give a new reduction framework to vertex
expanders which in turn exploits our new almost-linear time construction
of mimicking network for vertex connectivity. The
previous construction by Kratsch and Wahlstr\"{o}m [FOCS'12]
requires large polynomial time and is randomized.
An interesting aspect that allows our overall algorithm to be efficient is to ``lift'' several graph problems to hypergraphs and work directly on hypergraphs.

Bio:  I am a third-year Ph.D. student in Computer Science at Michigan State University <http://www.cse.msu.edu> . My advisor is Prof.Eric Torng<http://www.cse.msu.edu/~torng/>. I received Bachelor of Engineering (B.Eng 2012) with Second-class Honour and Master of Engineering (M.Eng 2013) in Computer Engineering from Chulalongkorn University<http://www.chula.ac.th/en/>, Thailand.



Host: Janos Simon


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