Pith. sign in

REVIEW 1 cited by

Lower Bounds for Conjunctive Query Evaluation

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

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

arxiv 2506.17702 v1 pith:N3HD2EJG submitted 2025-06-21 cs.DB cs.CC

Stefan Mengel This is my paper · ORCID
classification cs.DBcs.CC
keywords querycomplexityconjunctivedifferentevaluationknownshowingwill
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

In this tutorial, we will survey known results on the complexity of conjunctive query evaluation in different settings, ranging from Boolean queries over counting to more complex models like enumeration and direct access. A particular focus will be on showing how different relatively recent hypotheses from complexity theory connect to query answering and allow showing that known algorithms in several cases can likely not be improved.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. The Fine-Grained Complexity of Counting Hypergraph Motifs

    cs.CC 2026-07 accept novelty 7.0 of 10

    Hypergraph motif counting is always FPT-near-quadratic in rank, and FPT-near-linear exactly for the degenerate Venn diagrams, assuming Triangle and Hyperclique Hypotheses.

Pith tools