DIKU Bits: The vertex connectivity problem

On 14 September, Danupon Nanongkai from the Algorithms and Complexity (AC) section at Department of Computer Science, University of Copenhagen, will give a DIKU Bits lecture. 

Speaker

Danupon Nanongkai, professor in Algorithms and Complexity (AC) section, Department of Computer Science, University of Copenhagen

Title 

The vertex connectivity problem

Abstract

The vertex connectivity of a network G is the minimum number k of nodes whose removal disconnects G. Computing k=1 is a textbook exercise and requires linear time (hint: DFS). Solving k=2 also requires linear time using the SPQR tree data structure. However, for larger k we have been stuck with quadratic time from the 1950s. I will present a simple algorithm that makes the first progress in many decades and highlights a new paradigm in algorithms design called "local algorithms". 

Bio

Which courses do you teach? (BSc and MSc) I am co-teaching "Advanced algorithms and data structures" and "Topics in Algorithms and Data Structures (TADS)". I will also be co-teaching "Approximation Algorithms". 

Which technology/research/projects/startup are you excited to see the evolution of? As a person working with algorithms and complexity, I am excited with the recent tremendous progress on fundamental algorithmic questions that we have been stuck with for many decades, such as max-flow and matching, and how seemingly unrelated techniques are put together to achieve this. Beyond my own field, decades ago I was interested in making computers competent in the game of Go, so I am very impressed by how this has been achieved.

What is your favorite sketch from the DIKUrevy? I haven't watched the DIKUrevy yet.