[Theory] Reading group talk: Sorrachai Yingchareonthawornchai on January 16

[Madhur Tulsiani]

Hi all,

If you were there for Thatchaphol’s talk on Friday last week (or even if you missed it) and want to know more about testing k-connectivity, please do come for Sorrachai’s talk on Thursday to hear about the state of the art! He will give a talk at the TTIC in the theory reading group slot at 4 pm on Thursday, January 16. The title and abstract for the talk are included below.

Best,

Madhur 

===

Title: Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms. 

Abstract: Consider the following "local" cut-detection problem in a directed graph: We are given a seed vertex x and need to remove at most k edges so that at most ν edges can be reached from x (a "local" cut) or output ⊥ to indicate that no such cut exists. If we are given query access to the input graph, then this problem can in principle be solved without reading the whole graph and with query complexity depending on k and ν.  
In this talk, I will present a simple randomized algorithm spending O(νk^2) time and O(kν) queries for the slight variant of the above problem, improving in particular a previous time bound of O(k^O(k) ν) by Chechik et al. [SODA '17]. I will then present two key applications of the local cut algorithm. First application is a fast randomized algorithm for the classic k-vertex connectivity problem that takes near-linear time when k = O(polylog(n)). Second is property testing algorithms for k-edge and -vertex connectivity with query complexities that are near-linear in k, exponentially improving the state-of-the-art. This resolves two open problems, one by Goldreich and Ron [STOC '97] and one by Orenstein and Ron [Theor. Comput Sci. '11].

This talk is based on joint work with Sebastian Forster, Danupon Nanongkai, Thatchaphol Saranurak, and Liu Yang.

Bio: Sorrachai Yingchareonthawornchai is currently a Ph.D. student in computer science at Aalto University, Finland. He obtained MS degree in computer science at Michigan State University in 2019. He is the recipient of the best poster award of ICNP 2016. His research interest includes graph algorithms, approximation algorithms.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20200114/4f23c451/attachment.html>