Liana Khazaliya "Tractability Barriers for Parameterized (Geo)Metric Graph Problems"

HIIT Special Seminars
This talk is part of the HIIT Special Seminar series. The talks in this series are provided by candidates who have applied to our HIIT Fellowship recruitment call and are highly considered for the position. All talks are virtual, open to the public, and recorded for the future
HIIT Special Seminar

When

–

Where

Online

Event language(s)

English
Join via zoom

This talk can be viewed via zoom. (Note: this talk will be recorded)

Title: Tractability Barriers for Parameterized (Geo)Metric Graph Problems

Abstract: In this talk, we investigate computational problems that are intractable in the classical sense, in particular those that are NP-hard.

Such problems have been studied extensively, and a wide range of approaches has been proposed to cope with their inherent difficulty.
Not only seeking new algorithms to overcome this intractability, we also adopt a complementary perspective and focus on the following question: what are the fundamental barriers that prevent them from being efficiently solvable?

We specifically focus on problems where the previously developed techniques and results did not provide comprehensive answers; and the framework of parameterized complexity provides a more refined understanding of the sources and limits of algorithmic intractability

  • Updated:
  • Published:
Share
URL copied!