A tutorial that shows how fine-grained complexity hypotheses yield conditional lower bounds for conjunctive query evaluation across Boolean, counting, enumeration, and direct access settings.
A short note on the counting complexity of conjunctive queries
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
This note closes a minor gap in the literature on the counting complexity of conjunctive queries by showing that queries that are not free-connex do not have a linear time counting algorithm under standard complexity assumptions. More generally, it is shown that the so-called quantified star size is a lower bound for the exponent in the runtime of any counting algorithm for conjunctive queries.
citation-role summary
method 1
citation-polarity summary
fields
cs.DB 1years
2025 1verdicts
UNVERDICTED 1roles
method 1polarities
use method 1representative citing papers
citing papers explorer
-
Lower Bounds for Conjunctive Query Evaluation
A tutorial that shows how fine-grained complexity hypotheses yield conditional lower bounds for conjunctive query evaluation across Boolean, counting, enumeration, and direct access settings.