Tight Lower Bounds for Parameterized Algorithms under ETH

Add to your list(s) Download to your calendar using vCal

• Rajesh Chitnis, Birmingham
• Thursday 01 December 2022, 15:00-16:00
• LTC.

If you have a question about this talk, please contact Johannes Carmesin.

Parameterized (time) complexity attempts to give a more fine-grained analysis of the complexity of problems: instead of measuring the running time as a function of only the input size, we analyze the running time with respect to additional parameters. This approach has proven to be highly successful in delineating our understanding of NP-hard problems.

Recently, the Exponential Time Hypothesis (ETH) has proven to be quite useful in showing (almost) tight lower bounds on the running time of parameterized algorithms for several problems. In this talk, I will give a survey of these lower bounds (including a few of my results) and conclude with an open problem.

This talk is part of the Combinatorics and Probability seminar series.

This talk is included in these lists:

• Combinatorics and Probability seminar
• LTC
• School of Mathematics events

Note that ex-directory lists are not shown.