Télécom ParisTech

Actualité

Illustration de l'actualité : PhD defense Mikaël Monet : Combined complexity of queries over probabilistic data

PhD defense Mikaël Monet : Combined complexity of queries over probabilistic data

vendredi
12
octobre
2018

PhD Comics : I'm defending my thesis, Mom !

Jury

  • Antoine Amarilli, Télécom ParisTech (co-supervisor)
  • Florent Capelli, Université de Lille (examiner)
  • Georg Gottlob, University of Oxford (reviewer)
  • Benny Kimelfeld, Technion (reviewer)
  • Dan Olteanu, University of Oxford (examiner)
  • Pierre Senellart, ENS (co-supervisor)
  • Cristina Sirangelo, Université Paris-Diderot (examiner)
  • Emmanuel Waller, Université Paris-Sud (examiner)

Abstract

Query evaluation over probabilistic databases (probabilistic query evaluation, or PQE) is known to be intractable in many cases, even in data complexity, i.e., when the query is fixed. Although some restrictions of the queries and instances have been proposed to lower the complexity, these known tractable cases usually do not apply to combined complexity, i.e., when the query is not fixed.  My thesis investigates the question of which queries and instances ensure the tractability of PQE in combined complexity. [Read more ]