REVIEW 2 cited by
A short note on the counting complexity of conjunctive queries
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original 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.
Forward citations
Cited by 2 Pith papers
-
The Parametrised Complexity of Counting Small Sub-Hypergraphs
Counting non-induced sub-hypergraphs is fixed-parameter tractable exactly for families with bounded fractional co-independent edge-cover number, and induced counting exactly for bounded fractional edge-cover number, a...
-
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.
Discussion (0). Continue with ORCID to comment.