Public defence in Computer Science, M.Sc. Sorrachai Yingchareonthawornchai

Title of the thesis: Vertex Connectivity via Local Computation: Breaking Quadratic Time, Poly-logarithmic Max-flows, and Derandomization

Doctoral student: Sorrachai Yingchareonthawornchai
Opponent: Prof. Robert Krauthgamer, The Weizmann Institute of Science, Israel
Custos: Assist.Prof. Parinya Chalermsook, Aalto University School of Science, Department of Computer Science

On Local Computation and Fast Algorithms for Vertex Connectivity 

This thesis is about designing algorithms for computing vertex connectivity of a network. The main result is a blazingly fast algorithm for computing vertex connectivity. Vertex connectivity is one of the oldest problems in computer science which has been studied since the 1960s. Vertex connectivity measures the robustness of a network against node failures. For example, low vertex connectivity in a cloud network means an attacker can disrupt or disconnect the network by disabling a few nodes. The problem remains active and open for decades. Prior to this thesis, the fastest known algorithm takes a very long time on a large network. In this thesis, we revisit the problem through the lens of local computation– the algorithmic paradigm that can detect a small artifact without seeing the entire network. We develop a series of algorithms from detecting small to large connectivity, and finally culminating in an “almost linear time” algorithm for vertex connectivity. Roughly speaking, almost linear time means the algorithm’s running time to compute the vertex connectivity is proportional to the time to read the network as an input. This running time is essentially the best possible. Therefore, this thesis resolves a long-standing open problem in vertex connectivity.

Thesis available for public display 10 days prior to the defence at: https://aaltodoc.aalto.fi/doc_public/eonly/riiputus/

Doctoral theses in the School of Science: https://aaltodoc.aalto.fi/handle/123456789/52