CISPA
Browse

Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction

Download (1.06 MB)
conference contribution
posted on 2024-10-30, 16:58 authored by Dániel MarxDániel Marx
Conditional lower bounds based on $P
eq NP$, the Exponential-Time Hypothesis (ETH), or similar complexity assumptions can provide very useful information about what type of algorithms are likely to be possible. Ideally, such lower bounds would be able to demonstrate that the best known algorithms are essentially optimal and cannot be improved further. In this tutorial, we overview different types of lower bounds, and see how they can be applied to problems in database theory and constraint satisfaction.

History

Editor

Libkin L ; Pichler R ; Guagliardo P

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

ACM SIGMOD-SIGACT-SIGART Conference on Principles of Database Systems (PODS)

Journal

PODS

Page Range

19-29

Publisher

Association for Computing Machinery (ACM)

Open Access Type

  • Green

BibTeX

@conference{Marx:2021, title = "Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction", author = "Marx, Dániel", editor = "Libkin, Leonid" AND "Pichler, Reinhard" AND "Guagliardo, Paolo", year = 2021, month = 6, journal = "PODS", pages = "19--29", publisher = "Association for Computing Machinery (ACM)", doi = "10.1145/3452021.3458814" }