University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Tight Lower Bounds for Parameterized Algorithms under ETH

Tight Lower Bounds for Parameterized Algorithms under ETH

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

  • UserRajesh Chitnis, Birmingham
  • ClockThursday 01 December 2022, 15:00-16:00
  • HouseLTC.

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on talks.cam from the University of Cambridge.