En poursuivant votre navigation sur ce site, vous acceptez l'utilisation d'un simple cookie d'identification. Aucune autre exploitation n'est faite de ce cookie. OK
1

A quick and partial survey on the complexity of query answering

Sélection Signaler une erreur
Multi angle
Auteurs : Durand, Arnaud (Auteur de la Conférence)
CIRM (Editeur )

Loading the player...

Résumé : In this talk we will survey questions in logic and complexity at the interface between finite model theory, algorithms and database theory. The focus will be on the complexity of the many tasks related to query answering such as deciding if a Boolean query (for example a restricted first-order formula) is true or not in a finite model, counting the size of the answer set or enumerating the results. It will be a survey of some of the tools from complexity measures trough algorithmic methods to conditional lower bounds that have been designed in the domain over the last years.

Keywords : finite model theory; database theory; complexity

Codes MSC :

    Informations sur la Vidéo

    Réalisateur : Petit, Jean
    Langue : Anglais
    Date de publication : 13/02/2023
    Date de captation : 19/01/2023
    Sous collection : Research talks
    arXiv category : Logic ; Computational Complexity
    Domaine : Computer Science ; Logic and Foundations
    Format : MP4 (.mp4) - HD
    Durée : 01:01:13
    Audience : Researchers ; Graduate Students ; Doctoral Students, Post-Doctoral Students
    Download : https://videos.cirm-math.fr/2023-01-19_Durand.mp4

Informations sur la Rencontre

Nom de la rencontre : Discrete mathematics and logic : between mathematics and the computer science / Les mathématiques discrètes et la logique: des mathématiques à l'informatique
Organisateurs de la rencontre : Dzamonja, Mirna ; Schmitz, Sylvain ; Schnoebelen, Philippe ; Vaananen, Jouko
Dates : 16/01/2023 - 20/01/2023
Année de la rencontre : 2023
URL Congrès : https://conferences.cirm-math.fr/2758.html

Données de citation

DOI : 10.24350/CIRM.V.19994503
Citer cette vidéo: Durand, Arnaud (2023). A quick and partial survey on the complexity of query answering. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19994503
URI : http://dx.doi.org/10.24350/CIRM.V.19994503

Voir aussi

Bibliographie



Sélection Signaler une erreur