Daniel Lokshtanov is a Professor at the Department of Computer Science at the University of California Santa Barbara, before which he was a Professor at the Department of Informatics at the University of Bergen. He received his PhD in Computer Science (2009), from the University of Bergen. He spent two years (2010- 2012) as a Simons Postdoctoral Fellow at University of California at San Diego.
His research interests span a wide area of algorithms, and he has made several fundamental contributions in the areas of exact exponential algorithms, parameterized and fine-grained algorithms and approximation algorithms. He has been awarded the Meltzer Prize for Young Researchers for his work at the University of Bergen. He is a recipient of the Bergen Research Foundation young researcher grant and of an ERC starting grant on parameterized algorithms. He is a co-author of two recently published texts — Kernelization (Cambridge University Press, 2019) and Parameterized Algorithms (Springer, 2015).
Lectures will be recorded. Tutorials are planned as interactive problem-solving sessions.
Address by Prof. Rajat Moona (Director, IITGN) • Address by Prof. Anirban Dasgupta (Discipline Coordinator, Computer Science and Engineering, IITGN and Local GIAN Coordinator for IITGN) • Address by Prof. Saket Saurabh (IMSc)
Introduction to randomized methods in algorithms, an overview of approaches to coping with NP-hardness (approximation and parameterization). Analyze randomized algorithms (e.g, min-cut, polynomial identity testing).
Concentration bounds (Chernoff and Hoeffding).
Review of discrete probability spaces (events, expectation, variance, Chebyshev inequality).
Randomized algorithms for Feedback Vertex Set and generalization to Planar F-Deletion
Color Coding (k-Path) and Chromatic Coding (Feedback Arc Set on Tournaments and d-Clustering)
Introduction to LPs and SDPs and deterministic rounding schemes (Vertex Cover, Feedback Vertex Set)
Randomized rounding of LPs (PTAS for Closest String)
Randomized rounding of SDPs (0.87 Goeman and Williamson approximation for Max Cut)
Introduction to Tree Decompositions and Dynamic Programming over Graphs of Bounded Treewidth
Cut and Count for improved dynamic programming over tree decompositions.
Derandomization: k-wise independence and near k-wise independence; splitters
Introduction to Representative Sets
Constructions of near k-wise independent sample spaces, constructions of universal sets
Constructions of universal coloring families
Efficient computation of representative sets
The lectures will be streamed on YouTube and will be available for free. However, registration and attendance is mandatory for those who need a certificate. Registration is now closed. If you missed registering, you can catch up on the YouTube livestream instead. Watch this space!**.