Pith. sign in

REVIEW 10 minor 1 cited by

Lower Bounds for Conjunctive Query Evaluation

T0 review · 0 major / 10 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper surveys conditional lower bounds for conjunctive query evaluation and argues that, under standard fine-grained hypotheses, the known algorithms are essentially optimal: near-linear evaluation exists exactly for acyclic queries…

desk verdict A clean, honest survey that consolidates known conditional dichotomies for conjunctive query evaluation; no new theorems, and the central results rest on the less-established Hyperclique Hypothesis, but the paper is upfront about that and the math checks out. read the letter →

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 MSC 68Q1768P1568Q25
keywords conjunctivequeriesfine-grainedcomplexitylowerboundsacyclicfree-connexconstant-delayenumerationdirectaccesshypercliquehypothesis
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This tutorial argues that fine-grained complexity hypotheses draw the line between easy and hard conjunctive query evaluation. Its central message is conditional: if the Triangle Hypothesis and the Hyperclique Hypothesis are true, a self-join-free Boolean conjunctive query can be evaluated in near-linear time exactly when its hypergraph is acyclic. Adding the Strong Exponential Time Hypothesis for counting, and the Sparse Boolean Matrix Multiplication Hypothesis for enumeration and direct access, makes free-connex acyclicity the exact boundary for those tasks. The reader should care because these results turn structural query properties into optimality certificates: the algorithms already used in practice are likely the best possible, and the query's hypergraph alone says so.

What carries the argument

The machinery is the query hypergraph plus a menu of fine-grained hypotheses. A conjunctive query is assigned a hypergraph with one vertex per variable and one edge per atom; acyclicity means that repeatedly deleting a vertex contained in at most one edge, or an edge contained in another edge, removes everything. A structural theorem then says every non-acyclic hypergraph contains an induced cycle or, after deleting edges contained in other edges, a uniform hyperclique — a set of vertices in which every $h$-element subset is an edge. That dichotomy is what lets cyclic self-join-free queries simulate triangle detection and hyperclique detection. The bridge to hardness is the star query, which joins several variables to one common center variable: it encodes Boolean matrix multiplication, dominating set, and 3SUM. On the easy side, classical algorithms evaluate acyclic queries in near-linear time, and free-connex acyclicity — the hypergraph stays acyclic when the free variables are added as an extra edge — is what permits projection without losing constant delay. A 'disruptive trio' (two variables that each share an atom with a third but not with each other, with both ordered before the third) is the local obstruction for lexicographic direct access.

What would settle it

A concrete falsifier: for some $k>4$ and $\varepsilon>0$, decide the Loomis-Whitney query $q^{\mathrm{LW}}_k$ on databases of size $m$ in time $\tilde O(m^{1+1/(k-1)-\varepsilon})$. The reduction in the paper would then solve $k$-clique in $(k-1)$-uniform hypergraphs with $n$ vertices in time $n^{k-(k-1)\varepsilon}$, contradicting the Hyperclique Hypothesis and with it the Boolean dichotomy.

Watch

Extended reading notes

Core claim

The paper's core claims are a set of conditional dichotomies. Under the Triangle and Hyperclique Hypotheses, a self-join-free Boolean conjunctive query is decidable in near-linear time if and only if it is acyclic; under the same two hypotheses, counting answers to a join query is near-linear exactly for acyclic queries. When projections are present, the boundary moves to free-connex acyclicity: assuming the Strong Exponential Time Hypothesis, counting is near-linear exactly for self-join-free free-connex acyclic queries, and assuming the Triangle, Hyperclique, and Sparse Boolean Matrix Multiplication Hypotheses, both constant-delay enumeration and direct access are possible with near-linear preprocessing exactly for those queries. The paper further reports that lexicographic direct access is characterized by acyclicity plus absence of a 'disruptive trio', that sum-order direct access requires an atom containing all variables under the 3SUM Hypothesis, and that super-linear lower bounds exist for Loomis-Whitney joins, star-query counting, and clique embeddings.

Load-bearing premise

Every dichotomy in the paper is conditional on at least one unproven fine-grained hypothesis, and the least supported of these is the Hyperclique Hypothesis: if a $k$-vertex hyperclique can be found in an $h$-uniform hypergraph in time $\tilde O(n^{k-\varepsilon})$ for some $k>h>2$, the Boolean and Loomis-Whitney lower bounds collapse.

Editorial extensions

If this is right

  • For a self-join-free Boolean conjunctive query, near-linear evaluation is possible exactly when the query is acyclic, assuming the Triangle Hypothesis and the Hyperclique Hypothesis.
  • For acyclic join queries, counting answers takes near-linear time exactly for acyclic queries under the same two hypotheses; once projections are present, the boundary becomes free-connex acyclicity under the Strong Exponential Time Hypothesis.
  • Constant-delay enumeration after near-linear preprocessing is possible exactly for free-connex acyclic self-join-free queries, assuming the Triangle, Hyperclique, and Sparse Boolean Matrix Multiplication Hypotheses.
  • The same free-connex acyclicity condition characterizes direct access with constant access time; for lexicographic orders the condition sharpens to acyclicity plus absence of a disruptive trio, and for sum orders it sharpens to having one atom contain all variables under the 3SUM Hypothesis.
  • Beyond linear time, the survey reports lower bounds matching known algorithms: Loomis-Whitney joins under the Hyperclique Hypothesis, star-query counting under the Strong Exponential Time Hypothesis, and join direct access with an exact exponent from the incompatibility number under the Zero-$k$-Clique Hypothesis.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the hypotheses hold, query optimizers can treat acyclicity and free-connexity not just as tractability tests but as optimality certificates: once a plan reaching these shapes is found, no further search for better worst-case algorithms can help.
  • The self-join-free restriction is doing real work: cited work shows self-joins can make some cyclic join queries easy to enumerate, so a natural next question is whether the dichotomy theorems survive for self-join queries or acquire a different boundary.
  • Because every lower bound is a reduction, progress on the hypotheses transfers automatically: a faster hyperclique algorithm would yield faster Loomis-Whitney evaluation, and a near-linear sparse Boolean matrix multiplication algorithm would kill the star-query enumeration lower bound.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 10 minor

Summary. This tutorial surveys fine-grained complexity lower bounds for conjunctive query evaluation. It covers Boolean evaluation, counting, constant-delay enumeration, and direct access, and organizes known results around a set of explicit hypotheses: Sparse Boolean Matrix Multiplication, Triangle, Hyperclique, SETH, 3SUM, and combinatorial and weighted clique hypotheses. The central conditional dichotomies are: linear-time Boolean evaluation of self-join free queries iff acyclic (Theorem 3.7); linear-time counting for join queries iff acyclic (Theorem 3.8); linear-time counting / constant-delay enumeration / direct access for self-join free queries iff free-connex acyclic (Theorems 3.13, 3.17, 3.18); lexicographic direct access for join queries iff acyclic with no disruptive trio (Theorem 3.24); and sum-order direct access iff some atom contains all variables (Theorem 3.26). The paper also sketches super-linear lower bounds via clique embeddings, combinatorial clique hypotheses, Zero-k-Clique, and quantified star size. Proof sketches for representative reductions are included, and omitted proofs are referenced.

Significance. The paper is a survey/tutorial rather than a source of new theorems. Its value, if the surveyed results are correctly reported, is substantial: it gives database theorists a compact, well-organized map of a fast-moving area, and it is explicit about which hypotheses each dichotomy rests on. The included proof sketches (degree-split triangle detection, star-query counting reduction, sparse Boolean matrix multiplication reduction to enumeration, and clique embeddings) are instructive and appear mathematically correct. The paper is also honest about the provisional nature of fine-grained hypotheses (Section 2.2), and it clearly separates conditional claims from algorithmic upper bounds. No circularity or misattribution was detected. The dependence on unproven hypotheses, including the Hyperclique Hypothesis, is an epistemic limitation that the paper itself acknowledges; it is not an internal inconsistency. The main weaknesses are presentation-level: several theorem statements omit qualifiers or use incorrect terminology, and one definition contains a typographical error. These are local and fixable.

minor comments (10)
  1. [Section 3.3, Theorem 3.17; Section 3.4.1, Corollary 3.22] The statements refer to "a conjunctive query q" without the "self-join free" qualifier that the surrounding text establishes ("We will thus restrict to self-join free queries in the remainder of this section"). As printed, Theorem 3.17 overclaims, since the paper itself notes that some cyclic join queries with self-joins admit constant-delay enumeration after linear preprocessing (see the paragraph citing [14, 26]); please add the qualifier to the theorem statements.
  2. [Section 3.4, Theorems 3.18, 3.24, 3.26; Corollary 3.22] The direct-access results state "delay Õ(1)" where the model has an access phase, not an enumeration delay. The phrase should be "access time Õ(1)" throughout the direct-access section.
  3. [Section 3.1.2, Theorem 3.5] The statement excludes k=4 ("for no k > 4"), but the proof works for k=4 as well, since 3-uniform hypercliques of size 4 are covered by the Hyperclique Hypothesis (k=4 > h=3 > 2). Please either include k=4 or justify the exclusion.
  4. [Section 4.2, clique embedding definition] In property (2), the second disjunct reads "ψ(x_i)∩e ≠ ∅ and ψ(x_i)∩e ≠ ∅"; the second occurrence should be ψ(x_j). As typeset, the condition does not constrain the pair (x_i, x_j) as intended.
  5. [Section 4.2, Example 4.3] The displayed exponent calculation is inaccurate: a runtime Õ(m^{5/4−ε}) with m=O(n^4) yields Õ(n^{5−4ε}), not Õ(n^{5−ε}). The contradiction to the Min-Weight-5-Clique Hypothesis still follows after this correction.
  6. [Section 3.4.2, Lemma 3.25 proof] The proof says "there are a∈B, b∈B such that a+b=c"; the intended statement is "a∈A, b∈B" (the lists A and B are swapped).
  7. [Section 4.3, Lemma 4.4] The lemma states "for any k≥2", but the Zero-k-Clique Hypothesis (Hypothesis 8) is stated only for k≥3. Please either restrict to k≥3 or explain how k=2 is covered (for example, via the Triangle Hypothesis as in Lemma 3.21).
  8. [Section 1, metadata] "Additional Key Words and Phrases: todo" is an unfinished placeholder and should be replaced with actual keywords.
  9. [Section 2.3 and Section 4.1.1] There is a typo "multipliation" for "multiplication" in Section 2.3, and the runtime bound for combinatorial k-clique algorithms in Section 4.1.1 appears malformed; both should be corrected against the cited sources.
  10. [Section 3.4, Lemma 3.20] The lemma refers to "q(x1,...,xk)" but the query is introduced as q(x1,...,xr), and the definition of M(m) contains a garbled condition ("|q(D)||∥D∥≤m"); both should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular reasoning detected: the paper is a survey whose conditional lower bounds rest on explicitly stated external fine-grained hypotheses, and its reductions are from those hypotheses to query problems, not from the conclusions back to themselves.

full rationale

The paper is a tutorial survey that collects known conditional lower bounds for conjunctive query evaluation. Its central dichotomy theorems (e.g., Theorems 3.7, 3.13, 3.17, 3.18, 3.24, 3.26, 4.5) are all explicitly conditional on external fine-grained hypotheses such as the Triangle Hypothesis, the Hyperclique Hypothesis, SETH, the Sparse Boolean Matrix Multiplication Hypothesis, the 3SUM Hypothesis, and the Zero-k-Clique Hypothesis. These hypotheses are not derived from the query evaluation results being surveyed; rather, the paper gives explicit reductions from the hard problems posited by the hypotheses to query evaluation (e.g., Proposition 3.3 reduces triangle finding to cyclic graphlike queries, Theorem 3.5 reduces hyperclique finding to Loomis-Whitney joins, Theorem 3.15 reduces sparse Boolean matrix multiplication to the star query, Lemma 3.21 reduces triangle finding to testing q★2, and Lemma 3.25 reduces 3SUM to sum-order direct access). The upper-bound halves are cited to independent known algorithms such as Yannakakis's algorithm and free-connex acyclic enumeration techniques. Where the author cites his own prior work, e.g., [63] for details of Theorem 3.12 and [22] for direct-access results, the cited results are external published or archived works whose statements do not assume the present survey's claims; the self-citation is for provenance and detail, not as the sole justification of the claim. The paper explicitly acknowledges in Section 2.2 that fine-grained hypotheses carry lower confidence than NP-completeness, which is an epistemic caveat rather than a circular step. No fitted parameters are renamed as predictions, no theorem is defined in terms of its own conclusion, and no uniqueness result is imported from the author's own prior work to force a choice. Therefore the derivation chain is self-contained as a survey of reductions from stated assumptions, and the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 11 assumptions · 0 invented entities

The paper's conditional theorems rest on a menu of unproven fine-grained hypotheses plus standard background results from database theory. No free parameters or invented entities appear; the survey introduces no new objects, and no number is fitted to data. The hypotheses are explicitly stated in Section 2 and used throughout Sections 3 and 4.

assumptions (11)
  • domain assumption Sparse Boolean Matrix Multiplication Hypothesis: no algorithm computes the Boolean product of sparse n x n matrices with m non-zero entries in time O~(m).
    Stated as Hypothesis 1; used in Theorem 3.15 and Theorem 3.16 to rule out linear-preprocessing constant-delay enumeration for non-free-connex queries.
  • domain assumption Triangle Hypothesis: no algorithm decides triangle-freeness on a graph with m edges in time O~(m).
    Stated as Hypothesis 2; used in Theorems 3.7, 3.8, 3.13, 3.14, 3.17, 3.18, 3.22, 3.24, and Lemma 3.21.
  • domain assumption Hyperclique Hypothesis: for no k > h > 2 is there an algorithm that finds a k-hyperclique in an h-uniform hypergraph with n vertices in O~(n^(k - eps)).
    Stated as Hypothesis 3; used in Theorem 3.5 and in all characterizations that assume Triangle plus Hyperclique hypotheses.
  • domain assumption Strong Exponential Time Hypothesis: for every eps > 0 there exists k such that k-SAT on n variables cannot be solved in O~(2^(n(1-eps))).
    Stated as Hypothesis 4; used via Theorem 3.10 in Lemma 3.9 and Theorems 3.12, 3.13, and 4.6.
  • domain assumption 3SUM Hypothesis: no algorithm solves 3SUM on n integers in time O~(n^(2-eps)).
    Stated as Hypothesis 5; used in Lemma 3.25 and Theorem 3.26 for sum-order direct access.
  • domain assumption Combinatorial k-Clique Hypothesis: combinatorial algorithms cannot solve k-Clique in O~(n^(k-eps)).
    Stated as Hypothesis 6; used in Section 4.1.1 to motivate lower bounds for combinatorial join algorithms. The paper notes 'combinatorial' has no formal definition.
  • domain assumption Min-Weight-k-Clique Hypothesis: no algorithm solves Min-Weight-k-Clique in O~(n^(k-eps)).
    Stated as Hypothesis 7; used in Section 4.1.2 and Section 4.2 for tropical semiring aggregation lower bounds.
  • domain assumption Zero-k-Clique Hypothesis: no algorithm solves Zero-k-Clique in O~(n^(k-eps)).
    Stated as Hypothesis 8; used in Lemma 4.4 and Theorem 4.5 for direct access and enumeration lower bounds.
  • standard math AGM bound and worst-case optimal join algorithms.
    Section 2.1 says the reader is assumed familiar with these; used to derive the O~(m^(3/2)) triangle upper bound and Loomis-Whitney upper bounds.
  • standard math RAM model with logarithmic word size and unit-cost operations.
    Section 2.2 defines all runtimes in this model; the lower bounds are stated relative to it.
  • standard math Yannakakis linear-time algorithm for acyclic Boolean conjunctive queries.
    Theorem 3.1 is cited from [79] and used as the upper-bound side of the acyclicity dichotomies.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Lower Bounds for Conjunctive Query Evaluation." pith.science (2026). https://pith.science/paper/N3HD2EJG

@misc{pith2026250617702,
  author       = {Pith},
  title        = {Pith review of: Lower Bounds for Conjunctive Query Evaluation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/N3HD2EJG}},
  note         = {Machine review of arXiv:2506.17702}
}
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.

Figures

Figures reproduced from arXiv: 2506.17702 by the authors.

Figure 1
Figure 1. Visualization of the embedding in Example 4.2. In each node of the cycle, we first give the name of the [PITH_FULL_IMAGE:figures/full_fig_p017_1.png] view at source ↗

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.

Reference graph

Works this paper leans on

85 extracted references · 29 canonical work pages · cited by 1 Pith paper

  1. [1]

    If the Current Clique Algorithms Are Optimal, so Is Valiant’s Parser

    Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the Current Clique Algorithms Are Optimal, so Is Valiant’s Parser. SIAM J. Comput., 47(6):2527–2555, 2018. doi:10.1137/16M1061771

    doi:10.1137/16m1061771 2018

  2. [2]

    The time complexity of fully sparse matrix multiplication

    Amir Abboud, Karl Bringmann, Nick Fischer, and Marvin Künnemann. The time complexity of fully sparse matrix multiplication. In David P. Woodruff, editor,Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, V A, USA, January 7-10, 2024, pages 4670–4703. SIAM, 2024. doi:10.1137/1.9781611977912.167

    work page doi:10.1137/1.9781611977912.167 2024

  3. [3]

    Faster combinatorial k-clique algorithms

    Amir Abboud, Nick Fischer, and Yarin Shechter. Faster combinatorial k-clique algorithms. In José A. Soto and Andreas Wiese, editors, LATIN 2024: Theoretical Informatics - 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I , volume 14578 of Lecture Notes in Computer Science , pages 193–206. Springer, 2024. doi:10.100...

    doi:10.1007/978-3-031-55598-5 2024

  4. [4]

    Popular conjectures imply strong lower bounds for dynamic problems

    Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434–443. IEEE Computer Society, 2014. doi:10.1109/FOCS.2014.53. 20 Stefan Mengel

    doi:10.1109/focs.2014.53 2014

  5. [5]

    More asymmetry yields faster matrix multiplication

    Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 2005–2039. SIAM, 2025. doi:10.1...

    doi:10.1137/1.9781611978322.63 2025

  6. [6]

    Finding and counting given length cycles

    Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209–223,

  7. [7]

    Ranked enumeration for MSO on trees via knowledge compilation

    Antoine Amarilli, Pierre Bourhis, Florent Capelli, and Mikaël Monet. Ranked enumeration for MSO on trees via knowledge compilation. In Graham Cormode and Michael Shekelyan, editors, 27th International Conference on Database Theory, ICDT 2024, March 25-28, 2024, Paestum, Italy , volume 290 of LIPIcs, pages 25:1–25:18. Schloss Dagstuhl - Leibniz-Zentrum für...

    doi:10.4230/lipics.icdt.2024.25 2024

  8. [8]

    Faster join-projects and sparse matrix multiplications

    Rasmus Resen Amossen and Rasmus Pagh. Faster join-projects and sparse matrix multiplications. In Ronald Fagin, editor, Database Theory - ICDT 2009, 12th International Conference, St. Petersburg, Russia, March 23-25, 2009, Proceedings , volume 361 of ACM International Conference Proceeding Series , pages 121–126. ACM, 2009. doi:10.1145/1514894. 1514909

    work page doi:10.1145/1514894 2009

Show all 85 references
  1. [9]

    Open access at https: //github.com/pdm-book/community, 2022

    Marcelo Arenas, Pablo Barceló, Leonid Libkin, Wim Martens, and Andreas Pieris.Database Theory. Open access at https: //github.com/pdm-book/community, 2022. accessed March 2025, commit 9f403e4f8bb14eccca301eda2feafe90179b98df

    2022

  2. [10]

    Size bounds and query plans for relational joins

    Albert Atserias, Martin Grohe, and Dániel Marx. Size bounds and query plans for relational joins. SIAM J. Comput., 42(4):1737–1767, 2013. doi:10.1137/110859440

    2013 doi

  3. [11]

    Algorithmes et complexité des problèmes d’énumération pour l’évaluation de requêtes logiques

    Guillaume Bagan. Algorithmes et complexité des problèmes d’énumération pour l’évaluation de requêtes logiques. (Algorithms and complexity of enumeration problems for the evaluation of logical queries) . PhD thesis, University of Caen Normandy, France, 2009. URL: https://tel.ar...

    2009

  4. [12]

    On acyclic conjunctive queries and constant delay enumeration

    Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On acyclic conjunctive queries and constant delay enumeration. In Jacques Duparc and Thomas A. Henzinger, editors,Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne...

    2007 doi

  5. [13]

    On the desirability of acyclic database schemes

    Catriel Beeri, Ronald Fagin, David Maier, and Mihalis Yannakakis. On the desirability of acyclic database schemes. J. ACM, 30(3):479–513, 1983. doi:10.1145/2402.322389

    1983

  6. [14]

    Constant delay enumeration for conjunctive queries: a tutorial

    Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt. Constant delay enumeration for conjunctive queries: a tutorial. ACM SIGLOG News, 7(1):4–33, 2020. doi:10.1145/3385634.3385636

    2020

  7. [15]

    Answering conjunctive queries under updates

    Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering conjunctive queries under updates. In Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts, editors,Proceedings of the 36th ACM SIGMOD-SIGACT- SIGAI Symposium on Principles of Database Systems, PODS 2017...

    2017

  8. [16]

    Answering ucqs under updates and in the presence of integrity constraints

    Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering ucqs under updates and in the presence of integrity constraints. In Benny Kimelfeld and Yael Amsterdamer, editors, 21st International Conference on Database Theory, ICDT 2018, March 26-29, 2018, Vienna, Austr...

    2018 doi

  9. [17]

    On the complexity of the multiplication of matrices of small formats

    Markus Bläser. On the complexity of the multiplication of matrices of small formats. J. Complex., 19(1):43–60, 2003. doi:10.1016/S0885-064X(02)00007-9

    2003 doi

  10. [18]

    A negative conjunctive query is easy if and only if it is beta-acyclic

    Johann Brault-Baron. A negative conjunctive query is easy if and only if it is beta-acyclic. In Patrick Cégielski and Arnaud Durand, editors, Computer Science Logic (CSL’12) - 26th International Workshop/21st Annual Conference of the EACSL, CSL 2012, September 3-6, 2012, Fonta...

    2012 doi

  11. [19]

    De la pertinence de l’énumération : complexité en logiques propositionnelle et du premier ordre

    Johann Brault-Baron. De la pertinence de l’énumération : complexité en logiques propositionnelle et du premier ordre. (The relevance of the list: propositional logic and complexity of the first order) . PhD thesis, University of Caen Normandy, France, 2013. URL: https://tel.ar...

    2013

  12. [20]

    Hypergraph acyclicity revisited

    Johann Brault-Baron. Hypergraph acyclicity revisited. ACM Comput. Surv., 49(3):54:1–54:26, 2016. doi:10.1145/ 2983573

    2016

  13. [21]

    Unbalanced triangle detection and enumeration hardness for unions of conjunctive queries

    Karl Bringmann and Nofar Carmeli. Unbalanced triangle detection and enumeration hardness for unions of conjunctive queries. Log. Methods Comput. Sci., 21(1), 2025. URL: https://doi.org/10.46298/lmcs-21(1:29)2025, doi:10.46298/LMCS- 21(1:29)2025

    2025 doi

  14. [22]

    Tight fine-grained bounds for direct access on join queries

    Karl Bringmann, Nofar Carmeli, and Stefan Mengel. Tight fine-grained bounds for direct access on join queries. In Leonid Libkin and Pablo Barceló, editors, PODS ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022 , pages 427–436. ACM,...

    2022

  15. [23]

    Dynamic dynamic time warping

    Karl Bringmann, Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, and Eva Rotenberg. Dynamic dynamic time warping. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, V A, USA, January 7...

    2024 doi

  16. [24]

    Direct access for conjunctive queries with negation

    Florent Capelli, Nofar Carmeli, Oliver Irwin, and Sylvain Salvati. Direct access for conjunctive queries with negation. CoRR, abs/2310.15800, 2023. URL: https://doi.org/10.48550/arXiv.2310.15800, arXiv:2310.15800, doi:10.48550/ ARXIV.2310.15800

    2023 doi

  17. [25]

    On the enumeration complexity of unions of conjunctive queries

    Nofar Carmeli and Markus Kröll. On the enumeration complexity of unions of conjunctive queries. ACM Trans. Database Syst., 46(2):5:1–5:41, 2021. doi:10.1145/3450263

    2021 doi

  18. [27]

    Tractable orders for direct access to ranked answers of conjunctive queries

    Nofar Carmeli, Nikolaos Tziavelis, Wolfgang Gatterbauer, Benny Kimelfeld, and Mirek Riedewald. Tractable orders for direct access to ranked answers of conjunctive queries. ACM Trans. Database Syst. , 48(1):1:1–1:45, 2023. doi: 10.1145/3578517

    2023 doi

  19. [28]

    Katrin Casel and Markus L. Schmid. Fine-grained complexity of regular path queries. Log. Methods Comput. Sci. , 19(4),

  20. [29]

    Chandra and Philip M

    Ashok K. Chandra and Philip M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In John E. Hopcroft, Emily P. Friedman, and Michael A. Harrison, editors,Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, C...

    1977

  21. [30]

    A trichotomy in the complexity of counting answers to conjunctive queries

    Hubie Chen and Stefan Mengel. A trichotomy in the complexity of counting answers to conjunctive queries. In Marcelo Arenas and Martín Ugarte, editors, 18th International Conference on Database Theory, ICDT 2015, March 23-27, 2015, Brussels, Belgium, volume 31 of LIPIcs, pages ...

    2015 doi

  22. [31]

    On the asymptotic complexity of matrix multiplication

    Don Coppersmith and Shmuel Winograd. On the asymptotic complexity of matrix multiplication. SIAM J. Comput., 11(3):472–492, 1982. doi:10.1137/0211038

    1982 doi

  23. [32]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3

    2015 doi

  24. [33]

    Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication

    Artur Czumaj and Andrzej Lingas. Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication. SIAM J. Comput., 39(2):431–444, 2009. doi:10.1137/070695149

    2009 doi

  25. [34]

    Graph pattern detection: Hardness for all induced patterns and faster noninduced cycles

    Mina Dalirrooyfard, Thuy-Duong Vuong, and Virginia Vassilevska Williams. Graph pattern detection: Hardness for all induced patterns and faster noninduced cycles. SIAM J. Comput., 50(5):1627–1662, 2021. doi:10.1137/20M1335054

    2021 doi

  26. [35]

    The complexity of counting homomorphisms seen from the other side.Theor

    Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side.Theor. Comput. Sci., 329(1-3):315–323, 2004. URL: https://doi.org/10.1016/j.tcs.2004.08.008, doi:10.1016/J.TCS.2004.08.008

    2004 doi

  27. [36]

    Ranked enumeration of join queries with projections.Proc

    Shaleen Deep, Xiao Hu, and Paraschos Koutris. Ranked enumeration of join queries with projections.Proc. VLDB Endow., 15(5):1024–1037, 2022. URL: https://www.vldb.org/pvldb/vol15/p1024-deep.pdf, doi:10.14778/3510397.3510401

    2022

  28. [37]

    Counting answers to existential questions

    Holger Dell, Marc Roth, and Philip Wellnitz. Counting answers to existential questions. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 201...

    2019 doi

  29. [38]

    Structural tractability of counting of solutions to conjunctive queries

    Arnaud Durand and Stefan Mengel. Structural tractability of counting of solutions to conjunctive queries. In Wang- Chiew Tan, Giovanna Guerrini, Barbara Catania, and Anastasios Gounaris, editors, Joint 2013 EDBT/ICDT Conferences, ICDT ’13 Proceedings, Genoa, Italy, March 18-22...

    2013

  30. [39]

    The complexity of weighted counting for acyclic conjunctive queries

    Arnaud Durand and Stefan Mengel. The complexity of weighted counting for acyclic conjunctive queries. J. Comput. Syst. Sci., 80(1):277–296, 2014. URL: https://doi.org/10.1016/j.jcss.2013.08.001, doi:10.1016/J.JCSS.2013.08.001

    2014 doi

  31. [40]

    On the complexity of fixed parameter clique and dominating set

    Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theor. Comput. Sci., 326(1-3):57–67, 2004. URL: https://doi.org/10.1016/j.tcs.2004.05.009, doi:10.1016/J.TCS.2004.05.009

    2004 doi

  32. [41]

    Fan, Paraschos Koutris, and Hangdong Zhao

    Austen Z. Fan, Paraschos Koutris, and Hangdong Zhao. The fine-grained complexity of boolean conjunctive queries and sum-product problems. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors,50th International Colloquium on Automata, Languages, and Programming, ICALP ...

    2023 doi

  33. [42]

    Logic and algorithms in database theory and ai boot camp

    Simons Institute for the Theory of Computing. Logic and algorithms in database theory and ai boot camp. https: //simons.berkeley.edu/workshops/logic-algorithms-database-theory-ai-boot-camp#simons-tabs, August 2023. 22 Stefan Mengel

    2023

  34. [43]

    Overmars

    Anka Gajentaan and Mark H. Overmars. On a class of𝑂(𝑛2) problems in computational geometry. Comput. Geom., 5:165–185, 1995. doi:10.1016/0925-7721(95)00022-2

    1995 doi

  35. [44]

    Faster algorithms for rectangular matrix multiplication

    François Le Gall. Faster algorithms for rectangular matrix multiplication. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012 , pages 514–523. IEEE Computer Society, 2012. doi:10.1109/FOCS.2012.80

    2012 doi

  36. [45]

    Which arithmetic operations can be performed in constant time in the RAM model with addition? CoRR, abs/2206.13851, 2022

    Etienne Grandjean and Louis Jachiet. Which arithmetic operations can be performed in constant time in the RAM model with addition? CoRR, abs/2206.13851, 2022. URL: https://doi.org/10.48550/arXiv.2206.13851, arXiv:2206.13851, doi:10.48550/ARXIV.2206.13851

    2022 doi arXiv

  37. [46]

    Counting solutions to conjunctive queries: structural and hybrid tractability

    Gianluigi Greco and Francesco Scarcello. Counting solutions to conjunctive queries: structural and hybrid tractability. In Richard Hull and Martin Grohe, editors, Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS’14, Snowbird, U...

    2014

  38. [47]

    Parameterized complexity for the database theorist

    Martin Grohe. Parameterized complexity for the database theorist. SIGMOD Rec., 31(4):86–96, 2002. doi:10.1145/ 637411.637428

    2002

  39. [48]

    The complexity of homomorphism and constraint satisfaction problems seen from the other side

    Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM, 54(1):1:1–1:24, 2007. doi:10.1145/1206035.1206036

    2007

  40. [49]

    When is the evaluation of conjunctive queries tractable? In Jeffrey Scott Vitter, Paul G

    Martin Grohe, Thomas Schwentick, and Luc Segoufin. When is the evaluation of conjunctive queries tractable? In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors, Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, C...

    2001

  41. [50]

    Fast matrix multiplication for query processing.Proc

    Xiao Hu. Fast matrix multiplication for query processing.Proc. ACM Manag. Data, 2(2):98, 2024.doi:10.1145/3651599

    2024 doi

  42. [51]

    On the complexity of k-sat

    Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst. Sci. , 62(2):367–375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727, doi:10.1006/JCSS.2000.1727

    2001

  43. [52]

    Which problems have strongly exponential complexity? J

    Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512–530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774, doi:10.1006/JCSS.2001.1774

    2001

  44. [53]

    Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang

    Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Counting triangles under updates in worst-case optimal time. In Pablo Barceló and Marco Calautti, editors,22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal, vo...

    2019 doi

  45. [54]

    Trade-offs in static and dynamic evaluation of hierarchical queries

    Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Trade-offs in static and dynamic evaluation of hierarchical queries. In Dan Suciu, Yufei Tao, and Zhewei Wei, editors, Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 20...

    2020

  46. [55]

    Conjunctive queries with free access patterns under updates

    Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Conjunctive queries with free access patterns under updates. In Floris Geerts and Brecht Vandevoort, editors, 26th International Conference on Database Theory, ICDT 2023, March 28-31, 2023, Ioannina, Greece , volume 255...

    2023 doi

  47. [56]

    Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New Yo...

    1972 doi

  48. [57]

    Curtin, Benjamin Moseley, Hung Q

    Mahmoud Abo Khamis, Ryan R. Curtin, Benjamin Moseley, Hung Q. Ngo, XuanLong Nguyen, Dan Olteanu, and Maximilian Schleich. Functional aggregate queries with additive inequalities. ACM Trans. Database Syst., 45(4):17:1– 17:41, 2020. doi:10.1145/3426865

    2020 doi

  49. [58]

    Fast matrix multiplication meets the subdmodular width

    Mahmoud Abo Khamis, Xiao Hu, and Dan Suciu. Fast matrix multiplication meets the subdmodular width. CoRR, abs/2412.06189, 2024. URL: https://doi.org/10.48550/arXiv.2412.06189, arXiv:2412.06189, doi:10.48550/ARXIV. 2412.06189

    2024 doi arXiv

  50. [59]

    Ngo, and Atri Rudra

    Mahmoud Abo Khamis, Hung Q. Ngo, and Atri Rudra. FAQ: questions asked frequently. In Tova Milo and Wang-Chiew Tan, editors, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016 ,...

    2016

  51. [60]

    Ngo, and Dan Suciu

    Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? In Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts, editors, Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symp...

    2017

  52. [61]

    Ryan Williams

    Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, Janua...

    2018 doi

  53. [62]

    Tractable hypergraph properties for constraint satisfaction and conjunctive queries

    Dániel Marx. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. J. ACM, 60(6):42:1– 42:51, 2013. doi:10.1145/2535926

    2013 doi

  54. [63]

    A short note on the counting complexity of conjunctive queries

    Stefan Mengel. A short note on the counting complexity of conjunctive queries. CoRR, abs/2112.01108, 2021. URL: https://arxiv.org/abs/2112.01108, arXiv:2112.01108

    2021 arXiv

  55. [64]

    On the complexity of the subgraph problem

    Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415–419, 1985

    1985

  56. [65]

    Hung Q. Ngo. Worst-case optimal join algorithms: Techniques, results, and open problems. In Jan Van den Bussche and Marcelo Arenas, editors, Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018 , pages ...

    2018

  57. [66]

    Ngo, Ely Porat, Christopher Ré, and Atri Rudra

    Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. Worst-case optimal join algorithms. J. ACM, 65(3):16:1–16:40,

  58. [67]

    Size bounds for factorised representations of query results

    Dan Olteanu and Jakub Závodný. Size bounds for factorised representations of query results. ACM Trans. Database Syst., 40(1):2:1–2:44, 2015. doi:10.1145/2656335

    2015 doi

  59. [68]

    On the possibility of faster SAT algorithms

    Mihai Pătraşcu and Ryan Williams. On the possibility of faster SAT algorithms. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1065–1075. SIAM, 2010. doi:10.1...

    2010 doi

  60. [69]

    Tractable counting of the answers to conjunctive queries

    Reinhard Pichler and Sebastian Skritek. Tractable counting of the answers to conjunctive queries. J. Comput. Syst. Sci. , 79(6):984–1001, 2013. URL: https://doi.org/10.1016/j.jcss.2013.01.012, doi:10.1016/J.JCSS.2013.01.012

    2013 doi

  61. [70]

    A glimpse on constant delay enumeration (invited talk)

    Luc Segoufin. A glimpse on constant delay enumeration (invited talk). In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France, volume 25 of LIPIcs, pages 13–2...

    2014 doi

  62. [71]

    Constant delay enumeration for conjunctive queries

    Luc Segoufin. Constant delay enumeration for conjunctive queries. SIGMOD Rec., 44(1):10–17, 2015. doi:10.1145/ 2783888.2783894

    2015

  63. [72]

    Gaussian elimination is not optimal

    Volker Strassen. Gaussian elimination is not optimal. Numerische mathematik, 13(4):354–356, 1969

    1969

  64. [73]

    Optimal algorithms for ranked enumeration of answers to full conjunctive queries

    Nikolaos Tziavelis, Deepak Ajwani, Wolfgang Gatterbauer, Mirek Riedewald, and Xiaofeng Yang. Optimal algorithms for ranked enumeration of answers to full conjunctive queries. Proc. VLDB Endow. , 13(9):1582–1597, 2020. URL: http://www.vldb.org/pvldb/vol13/p1582-tziavelis.pdf, d...

    2020

  65. [74]

    Leslie G. Valiant. General context-free recognition in less than cubic time. J. Comput. Syst. Sci. , 10(2):308–315, 1975. doi:10.1016/S0022-0000(75)80046-8

    1975 doi

  66. [75]

    Moshe Y. Vardi. The complexity of relational query languages (extended abstract). In Harry R. Lewis, Barbara B. Simons, Walter A. Burkhard, and Lawrence H. Landweber, editors,Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, Cal...

    1982

  67. [76]

    Ryan Williams

    Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. J. ACM, 65(5):27:1–27:38, 2018. doi:10.1145/3186893

    2018 doi

  68. [77]

    Finding, minimizing, and counting weighted subgraphs

    Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput., 42(3):831–854, 2013. doi:10.1137/09076619X

    2013 doi

  69. [78]

    On some fine-grained questions in algorithms and complexity

    Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the international congress of mathematicians: Rio de janeiro 2018 , pages 3447–3487. World Scientific, 2018

    2018

  70. [79]

    Algorithms for acyclic database schemes

    Mihalis Yannakakis. Algorithms for acyclic database schemes. In Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings , pages 82–94. IEEE Computer Society, 1981

    1981

  71. [80]

    Detecting short directed cycles using rectangular matrix multiplication and dynamic programming

    Raphael Yuster and Uri Zwick. Detecting short directed cycles using rectangular matrix multiplication and dynamic programming. In J. Ian Munro, editor,Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January...

    2004

  72. [81]

    Space-time tradeoffs for conjunctive queries with access patterns

    Hangdong Zhao, Shaleen Deep, and Paraschos Koutris. Space-time tradeoffs for conjunctive queries with access patterns. In Floris Geerts, Hung Q. Ngo, and Stavros Sintos, editors, Proceedings of the 42nd ACM SIGMOD-SIGACT- SIGAI Symposium on Principles of Database Systems, PODS...

    2023

  73. [82]

    Fan, Xiating Ouyang, and Paraschos Koutris

    Hangdong Zhao, Austen Z. Fan, Xiating Ouyang, and Paraschos Koutris. Conjunctive queries with negation and aggregation: A linear time characterization. Proc. ACM Manag. Data, 2(2):75, 2024. doi:10.1145/3651138

    2024 doi

  74. [85]

    doi:10.1145/3584372.3588675

  75. [1997]

    doi:10.1007/BF02523189

    doi

  76. [2020]

    doi:10.1145/3375395.3387646

  77. [2023]

    URL: https://doi.org/10.46298/lmcs-19(4:15)2023, doi:10.46298/LMCS-19(4:15)2023

    2023 doi

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.