Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction

2021/06/18 by Dániel Marx · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Artificial intelligence #Complexity and Algorithms in Graphs #Computer science #Constraint (computer-aided design) #Constraint satisfaction #Constraint satisfaction problem #Data Management and Algorithms #Mathematics #Theoretical computer science #Upper and lower bounds #cs.CC #cs.DB

paper · pdf · doi:10.1145/3452021.3458814

PODS 2021 Tutorial

openalex publication_date 2021/06/18 · openalex created_date 2021/07/05 · arxiv created 2022/03/15 · arxiv updated 2022/03/16 · openalex updated_date 2026/08/05

Abstract

Conditional lower bounds based on P≠ 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.

Citations

• Computational Complexity
• Parameterized Complexity Theory
• Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
• On the complexity of fixed parameter clique and dominating set
• Canonical labeling of graphs
• Which Problems Have Strongly Exponential Complexity?
• Graph minors. III. Planar tree-width
• S-functions for graphs
• The complexity of theorem-proving procedures
• A rigorous time bound for factoring integers
• General context-free recognition in less than cubic time
• On the Structure of Polynomial Time Reducibility
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Tight Hardness Results for LCS and Other Sequence Similarity Measures
• On Problems as Hard as CNF-SAT
• Graph isomorphism in quasipolynomial time [extended abstract]
• Parameterized Algorithms
• A Refined Laser Method and Faster Matrix Multiplication