For the next MALOTEC seminar, Valia Mitsou, who is a candidate for the position of associate professor in CentraleSupelec will give a presentation at LORIA on Tuesday April 23 at 11am in room A008
Presentation of the speaker :
Valia Mitsou
Université Paris Diderot
Institut de Recherche en Informatique Fondamentale (IRIF)
Title: Limitation of treewidth for problems beyond NP
Abstract: In this seminar, we take a closer look at the parameterized complexity of problems belonging in Σ^p_2 and Π^p_2, the second level of the polynomial hierarchy. We provide tight fine-grained bounds on their complexity with respect to the most important structural graph parameter, the treewidth. We observe that these problems exhibit similar behavior: we show that a variety of diverse problems including ∃∀SAT, Choosability, as well as various problems from AI such as Abduction and Abstract Argumentation, while they admit a $2^{2^{O(tw)}}$ algorithm, they cannot be solved in time $2^{2^{o(tw)}}$ under the Exponential Time Hypothesis.
