[Theory] UC Theory Seminar: a reminder

[Alexander Razborov]

Begin forwarded message:

> From: Jose J Fragoso <jfragoso at uchicago.edu>
> Date: October 10, 2022 at 9:13:54 AM CDT
> To: colloquium at cs.uchicago.edu
> Subject: [prof] [faculty-monday] [Colloquium] CS Theory Seminar - Sorrachai Yingchareonthawornchai, Tuesday, October 11, 2022
> 
> 
>  
> UNIVERSITY OF CHICAGO
> COMPUTER SCIENCE DEPARTMENT
> PRESENTS
>  
>                                  
>  
> Sorrachai Yingchareonthawornchai
> Aalto University, Espoo, Finland
>  
>  
> 
>  
>  
>  
>  
> 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 Doctoral Researcher at Aalto University in Espoo, Finland.
> 
>  
> 
> Host: Janos Simon
> 
> 
> 
> 
> 
> _______________________________________________
> Colloquium mailing list  -  Colloquium at mailman.cs.uchicago.edu
> https://mailman.cs.uchicago.edu/mailman/listinfo/colloquium
> _______________________________________________
> Facultylunch mailing list
> Facultylunch at mailman.cs.uchicago.edu
> https://mailman.cs.uchicago.edu/cgi-bin/mailman/listinfo/facultylunch_______________________________________________
> Full-professor mailing list
> Full-professor at mailman.cs.uchicago.edu
> https://mailman.cs.uchicago.edu/cgi-bin/mailman/listinfo/full-professor
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20221010/5c3d4a84/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 184824 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20221010/5c3d4a84/attachment-0001.jpg>