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.3105158e-05
Overall Rank: 9,627 | 33.10%
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,165	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.807833e-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
12,801	Combinatorial Games in Database Theory	1995	PODS	4.1905499e-05
4,782	Dense-Order Constraint Databases (Extended Abstract)	1995	PODS	5.9233349e-05
8,317	Towards Practical Constraint Databases (Extended Abstract)	1996	PODS	4.5392079e-05
4,985	Specification, Semantics, And Enforcement Of Dynamic Database Constraints	1984	VLDB	5.7790376e-05
4,793	Toward Practical Constraint Databases	1993	VLDB	5.9107617e-05
9,843	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	4.2680295e-05
4,545	Bounded Conjunctive Queries	2014	VLDB	6.0917464e-05
5,719	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	5.3551435e-05
7,603	Polynomial-time program transformations in deductive databases	1990	PODS	4.6959912e-05
4,978	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.7833452e-05