Loading Events

« All Events

  • This event has passed.

MALOTEC Seminar

April 23 @ 11:00 am - 12:00 pm

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.

For more information

Details

Date:
April 23
Time:
11:00 am - 12:00 pm
Event Category:

Logo du CNRS

Logo d'Inria

Logo Université de Lorraine