Danupon Nanongkai

Danupon Nanongkai is currently a scientific director at Max Planck Institute for Informatics in Saarbrücken, Germany. His research interest is generally on graph algorithms and complexity, where the current focus is on algorithmic techniques that work across various models of computation. He was awarded the Principles of Distributed Computing Doctoral Dissertation Award in 2013, the ERC Starting Grant in 2016, and the best paper award from FOCS 2022. He received a Ph.D. in Algorithms, Combinatorics, and Optimization (ACO) from Georgia Tech in 2011 and a docent (aka habilitation) in Computer Science from KTH Royal Institute of Technology, Sweden, in 2017.

RESEARCH INTERESTS

Our long-term vision is to develop cross-paradigm techniques for designing algorithms that work across many models of computation, such as dynamic, distributed, streaming, parallel, and quantum algorithms. Our philosophy is to simultaneously study the same question from the perspectives of many computing paradigms to find new insights that may not emerge from the isolated viewpoint of a single model. We aim to achieve two goals simultaneously: (i) solutions for notorious long-standing open problems and (ii) efficient algorithms that can fully exploit the characteristics of modern computing devices and data.

Our current focus is on basic questions about graph data, such as connectivity, shortest paths, and matching. The aim is to develop provably fast algorithms and complexity theory, using tools such as sketching, spectral techniques, fast matrix multiplication, approximation algorithms, communication complexity and fine-grained complexity.

Although we focus on long-standing open problems and mathematical proofs, we are open to new problems arising from applications and to collaborations with experimentalists.

Keywords:

• Graph algorithms, Modern computational models, Distributed algorithms, Dynamic algorithms, Approximation algorithms, Sublinear algorithms, Lower bounds, Fine-grained Complexity, Hardness of approximation.

Education

• Docent (aka habilitation) KTH Royal Institute of Technology
• Bachelor of Engineering - BE Kasetsart University
• High School Triam Udom Suksa School

SELECTED HONORS

• Best paper award at FOCS 2022
• For the paper "Negative-Weight Single-Source Shortest Paths in Near-linear Time" co-authored with Aaron Bernstein and Christian Wulff-Nilsen
• ERC Starting Grant 2017
• ERC Starting Grants award up to 1.5€ million for 5 years to support up-and-coming research leaders who are about to establish a proper research team and to start conducting independent research in Europe.
• Principles of Distributed Computing Doctoral Dissertation Award 2013
• The award was created in 2012 to acknowledge and promote outstanding research by doctoral (Ph.D.) students on the principles of Distributed Computing.