The celebrated notion of NP-completeness provides a framework to identify computational problems that are unlikely to be solvable in time polynomial in the input size. Further research has shown that not all NP-complete problems have the same complexity, and many of them behave vastly differently, in terms of their exact exponential time complexity. Several recent developments have helped us understand this behaviour better.

Exponential Time Hypothesis (ETH), that asserts that the classical problem of boolean satisfiability on n variables (SAT) can not be solved in 2^{o(n)} time, and Strong Exponential Time Hypothesis (SETH), that asserts that SAT can not be solved in 2^{cn} time for any constant c < 1, have provided frameworks to show lower bounds and pinpoint the complexity of not just NP-complete problems, but even problems that have well-known polynomial time algorithms. The notion of parameterized complexity has extended the realm of feasible algorithms beyond polynomial time algorithms (by allowing running times that are exponential in small parameters associated with the input). The related notions of kernelization and instance compression have provided a framework to show problems whose instances can not be compressed beyond a point.

The speakers of the workshop will dwell on some of these developments. There will also be talks on recent developments on exact algorithms for specific problems, including graph isomorphism, steiner tree problems and deletion problems. Deletion problems are (graph or SAT) problems on instances that are `not far' from instances that are efficiently solvable.

A tentative program is [here]

• Nikhil Bansal (TU Eindhoven)
  Approximating Maximum Independent Set problem in Sparse Graphs using Hierarchies [slides]

• Neeldhara Misra (IISc Bangalore)
  Parameterized Graph Modification: A Modern Perspective [slides]

• Fahad Panolan (IMSc Chennai)
  Representative Sets and Kernels [slides]

• Geevarghese Philip (MPI Germany)
  Kernelization Lower Bounds: A Brief History [slides]

• Michał Pilipczuk (University of Warsaw, Poland)
  1. Graph Isomorphism is FPT Parameterized by Treewidth; [slides]
  2. Algorithmic Lower Bounds based on ETH and SETH [slides]

• M. S. Ramanujan (University of Bergen, Norway)
  Backdoors to Satisfiability [slides]

• Gaurav Rattan (IMSc Chennai)
  Parameterized Complexity of Geometric Graph Isomorphism [slides]

• Rahul Santhanam (University of Edinburgh, UK)
  Models of Exact Algorithms for NP-hard Problems [slides]

• Ondrej Suchy (Czech Technical University, Prague)
  Exact Algorithms for the Steiner Tree Problem and its Variants [slides]

• Ryan Williams (Stanford University, USA)
  On the Strong Exponential Time Hypothesis [slides]

Abstract of the talks are [here]

• Venkatesh Raman (IMSc Chennai)

• Saket Saurabh (IMSc Chennai)