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"
}