Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction

Summary: Tutorial survey of modern conditional lower-bound techniques (P≠NP, ETH, fine-grained) for database theory and constraint satisfaction. Demonstrates how these frameworks and reductions yield tight, often near-optimal, barriers for core DB/CSP algorithms. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1831
Venue: PODS
Year: 2021
Pagerank: 4.3146507e-05
Overall Rank: 9,627 | 33.03%
DOI: 10.1145/3452021.3458814

Incoming Non-self Citations Over Time

Authors

1. Dániel Marx

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,166	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.8124491e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,778	Dense-Order Constraint Databases (Extended Abstract)	1995	PODS	5.9290535e-05
12,792	Combinatorial Games in Database Theory	1995	PODS	4.1945683e-05
8,323	Towards Practical Constraint Databases (Extended Abstract)	1996	PODS	4.5435639e-05
4,986	Specification, Semantics, And Enforcement Of Dynamic Database Constraints	1984	VLDB	5.7846051e-05
4,793	Toward Practical Constraint Databases	1993	VLDB	5.9164359e-05
9,843	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	4.2721228e-05
4,546	Bounded Conjunctive Queries	2014	VLDB	6.0987778e-05
5,709	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	5.3602702e-05
7,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05
4,977	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.7881576e-05