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