Countdown
to the start of the workshop

Professor, University of California Santa Barbara

Daniel Lokshtanov

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).

schedule

5-Day Course

Lectures will be recorded. Tutorials are planned as interactive problem-solving sessions.

  • 9.00am

    Registration

  • 9.30am

    Coffee

  • 10.00am

    Inaugaration

    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)

  • 10.45am

    Lecture 1

    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).

    Daniel Lokshtanov
  • 12.30pm

    Lunch Break

  • 2.30pm

    Lecture 2

    Concentration bounds (Chernoff and Hoeffding).

    Daniel Lokshtanov
  • 4.00pm

    Coffee Break

  • 4.30pm

    Tutorial

    Review of discrete probability spaces (events, expectation, variance, Chebyshev inequality).

    Neeldhara Misra
  • 10.30am

    Coffee

  • 11.00am

    Lecture 3

    Randomized algorithms for Feedback Vertex Set and generalization to Planar F-Deletion

    Daniel Lokshtanov
  • 12.30pm

    Lunch Break

  • 2.30pm

    Lecture 4

    Color Coding (k-Path) and Chromatic Coding (Feedback Arc Set on Tournaments and d-Clustering)

    Daniel Lokshtanov
  • 4.00pm

    Coffee Break

  • 4.30pm

    Tutorial

    Introduction to LPs and SDPs and deterministic rounding schemes (Vertex Cover, Feedback Vertex Set)

    Daniel Lokshtanov
  • 10.30am

    Coffee

  • 11.00am

    Lecture 5

    Randomized rounding of LPs (PTAS for Closest String)

    Daniel Lokshtanov
  • 12.30pm

    Lunch Break

  • 2.30pm

    Lecture 6

    Randomized rounding of SDPs (0.87 Goeman and Williamson approximation for Max Cut)

    Daniel Lokshtanov
  • 4.00pm

    Coffee Break

  • 4.30pm

    Tutorial

    Introduction to Tree Decompositions and Dynamic Programming over Graphs of Bounded Treewidth

    Neeldhara Misra
  • 10.30am

    Coffee

  • 11.00am

    Lecture 7

    Cut and Count for improved dynamic programming over tree decompositions.

    Daniel Lokshtanov
  • 12.30pm

    Lunch Break

  • 2.30pm

    Lecture 8

    Derandomization: k-wise independence and near k-wise independence; splitters

    Daniel Lokshtanov
  • 4.00pm

    Coffee Break

  • 4.30pm

    Tutorial

    Introduction to Representative Sets

    Daniel Lokshtanov
  • 10.30am

    Coffee

  • 11.00am

    Lecture 9

    Constructions of near k-wise independent sample spaces, constructions of universal sets

    Daniel Lokshtanov
  • 12.30pm

    Lunch Break

  • 2.30pm

    Lecture 10

    Constructions of universal coloring families

    Daniel Lokshtanov
  • 4.00pm

    Coffee Break

  • 4.30pm

    Tutorial

    Efficient computation of representative sets

    Daniel Lokshtanov
Sign Up

Registration

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!**.

1500 INR

Virtual
  • Welcome Kit
  • Join over Zoom
  • Participate in Q&A
  • Bring your own food and drink :)
Sign Up

5000 INR

Local
  • Welcome Kit
  • Lunch and Coffee
  • In-person interactions
  • No accommodation
Sign Up

10000 INR

Outstation
  • Welcome Kit
  • Lunch and Coffee
  • In-person interactions
  • Shared hostel accommodation on campus
Sign Up
Sponsors

We are grateful for support from:

Venue location
5 - 9 December, 2022

Indian Institute of Technology, Gandhinagar
near GIFT City
Palaj, Gandhinagar
382355

More Information