Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction

(2021) Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction.

Preview

Text marx.pdf Download (642kB) | Preview

Abstract

Conditional lower bounds based on $\textup{P}\neq \textup{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.

Item Type:	Conference or Workshop Item (A Paper) (Lecture)
Divisions:	Dániel Marx (DM)
Conference:	PODS ACM SIGMOD-SIGACT-SIGART Conference on Principles of Database Systems
Depositing User:	Dániel Marx
Date Deposited:	29 Apr 2022 08:25
Last Modified:	29 Apr 2022 08:30
Primary Research Area:	NRA1: Trustworthy Information Processing
URI:	https://publications.cispa.saarland/id/eprint/3621

Actions

Actions (login required)

View Item