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

Bookmarks Report an error
Multi angle
Authors : Durand, Arnaud (Author of the conference)
CIRM (Publisher )

Loading the player...

Abstract : 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

MSC Codes :

    Information on the Video

    Film maker : Petit, Jean
    Language : English
    Available date : 13/02/2023
    Conference Date : 19/01/2023
    Subseries : Research talks
    arXiv category : Logic ; Computational Complexity
    Mathematical Area(s) : Computer Science ; Logic and Foundations
    Format : MP4 (.mp4) - HD
    Video Time : 01:01:13
    Targeted Audience : Researchers ; Graduate Students ; Doctoral Students, Post-Doctoral Students
    Download : https://videos.cirm-math.fr/2023-01-19_Durand.mp4

Information on the Event

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

Citation Data

DOI : 10.24350/CIRM.V.19994503
Cite this video as: 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

See Also

Bibliography



Bookmarks Report an error