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]

Abstract of the talks are [here]