{"id":"1cb1e5ec-854d-4c56-91de-543d3ac79e52","arxiv_id":"2412.06189","paper_version":5,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper introduces the omega-submodular width, a generalization of submodular width that captures fast matrix multiplication, and proves an algorithm that evaluates any Boolean conjunctive query in time proportional to that width.","lead":"This paper defines a new measure, the omega-submodular width, that extends submodular width to include fast matrix multiplication, and gives a matching algorithm that evaluates any Boolean conjunctive query within that time bound. It unifies known combinatorial and matrix-multiplication join algorithms and yields improved algorithms for some query classes.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7.1 rests on Lemma E.11, which is only sketched; the claimed runtime guarantee is not independently established until that lemma is proven.","rationale":"The reader's weakest_assumption already identifies the generalized Reset Lemma and Proof Sequence Construction (Lemmas E.7 and Theorem E.8) as the critical technical core, and notes Lemma E.11 is only sketched. My stress-test pass converges on the same region: Lemma E.11 is the precise bridge without which the algorithm's runtime bound does not follow. The surrounding definitions and the statements of E.7 and E.8 are plausible and internally consistent at the level of the text, and the table results for specific queries (triangles, 4-cliques, 3/4-cycles) provide partial independent support for the framework. However, because the proof of Theorem 7.1 depends on an unproven lemma whose new ingredients (proper conditionals, ω-dominant triples, integrality) are exactly where subtle failures would hide, the conditional verdict is appropriate. I do not see grounds to recommend rejection or unconditional acceptance; the concern is addressable by completing the proof of Lemma E.11 and checking it on small hypergraphs, so the verdict remains CONDITIONAL, i.e., unchanged from the reader's assessment. The abstract's 'recovers best known' claim is slightly overbroad for k-cycles when ω > 2 because the paper's bound is c□_k, which can exceed the best known c_k, but that is a presentation issue separate from the correctness of Theorem 7.1.","tokens_in":54099,"tokens_out":6242,"duration_ms":66131,"concrete_test":"Prove Lemma E.11 by writing the dual of LP (78) over the polymatroid cone (Shannon inequalities plus edge-domination constraints), and show explicitly that every dual feasible point yields an ω-Shannon inequality of the required form with ∥w∥₁/(∥λ∥₁+∥κ∥₁) equal to the dual objective, and that for rational ω an integral inequality can be obtained by clearing denominators. As a numerical cross-check, instantiate the 4-clique hypergraph (Eq. 23), solve one of the LPs in Eq. (28), and derive the asserted inequality explicitly, verifying that the coefficient ratio equals the LP optimum. If the derived ratio differs, or if the derivation requires an extra assumption not in the paper, the proof of Theorem 7.1 is incomplete as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the matching runtime Õ(N^{ω-subw(Q)}) in Theorem 7.1. The proof reduces each LP (34)/(78) to an integral ω-Shannon inequality (54) via Lemma E.11, then applies the generalized Reset Lemma (E.7), the Proof Sequence Construction (E.8), and the disjunctive-rule evaluation (E.10). The load-bearing step is Lemma E.11: it asserts that for every LP of the form (78) with optimum opt, there is an integral ω-Shannon inequality whose coefficients satisfy the structural conditions α_j = β_j = κ_j, ζ_j = κ_j·γ, and whose coefficient ratio satisfies ∥w∥₁/(∥λ∥₁+∥κ∥₁) = opt. This exact equality is what makes Theorem E.10 run in Õ(N^{opt}) and hence in Õ(N^{ω-subw(Q)}).\n\nThe appendix does not prove Lemma E.11; it says the proof is 'very similar' to a lemma in [4,5] and 'relies on the observation' that dual feasible solutions correspond to inequalities. The new content, however, is not cosmetic: the LHS contains proper conditionals h(X_j|G_j), the triples must remain ω-dominant through the reset and proof-sequence steps, and the inequality must be integral for rational ω. A subtle error in the dual-to-inequality correspondence, or in preserving the exact ratio opt after scaling to integers, would leave Theorem 7.1 without its stated guarantee even if all other components are correct. This is the single most load-bearing unproven step in the paper.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the omega-submodular width, a generalization of submodular width that incorporates fast matrix multiplication into the cost model, and claims a matching algorithm: for every Boolean conjunctive query Q and rational omega, the query can be answered in time O-tilde(N^{omega-subw(Q)}) (Theorem 7.1). The framework generalizes variable elimination orders to grouped eliminations, defines an MM expression with group-by variables, reduces computation of the width to finitely many LPs, and proves the main algorithmic claim through a sequence of appendix tools: a generalized Reset Lemma (E.7), a generalized proof-sequence construction (E.8), an evaluation algorithm for disjunctive rules (E.10), and a lemma converting LP optima into omega-Shannon inequalities (E.11). The paper also computes the omega-submodular width for cliques, cycles, and pyramids, recovering known bounds and giving a new k-pyramid bound.","tokens_in":54448,"tokens_out":11320,"duration_ms":122754,"significance":"If Theorem 7.1 holds, this is a substantial contribution: it provides the first general framework for deriving and analyzing matrix-multiplication-based join algorithms for arbitrary Boolean conjunctive queries, unifying combinatorial and non-combinatorial techniques under an information-theoretic umbrella. The paper is honest about the scope of its claims, including the restriction to Boolean queries and the use of square-matrix-multiplication bounds. The appendix contains detailed proofs of the Reset Lemma and proof-sequence construction, and the LP-based computation of the width is a clean and useful reformulation. The new k-pyramid bound is a concrete novel algorithmic prediction. The main weakness is that the load-bearing LP-to-Shannon-inequality lemma is only sketched.","major_comments":[{"comment":"Lemma E.11 is the load-bearing step connecting the LP optimum opt of (78) to an integral omega-Shannon inequality (54) with the specific structural conditions alpha_j = beta_j = kappa_j, zeta_j = kappa_j * gamma, and the exact ratio in (79). The proof is only a sketch: it states that the lemma is 'very similar' to a lemma in [4,5] and 'relies on the observation' that dual feasible solutions correspond to inequalities. This is not sufficient, because the new setting contains proper conditionals h(X_j|G_j), requires preservation of omega-dominance after the reset and proof-sequence steps, and requires integrality for rational omega. A subtle failure in the dual-to-inequality correspondence, in the integral scaling, or in preserving the exact ratio would invalidate the runtime guarantee of Theorem 7.1 even if every other component is correct. Please provide a complete proof of Lemma E.11, or a precise reduction to the corresponding lemma in [4,5] that verifies each new structural condition.","section":"Appendix E.6, Lemma E.11"},{"comment":"The notation conflates the true matrix multiplication exponent omega with the square-MM upper bound omega_square defined in Eq. (6). Definition 4.2 and Eq. (21) use gamma = omega - 2, which is the cost of square block multiplication, and Table 1 explicitly uses omega_square for cycles and rectangular exponents. Theorem 7.1 is stated as a runtime of O-tilde(N^{omega-subw(Q)}) for a rational omega, but the MM subroutine in the proof of Theorem 7.1 (Eq. (84) and the surrounding argument) is only justified for the square-MM bound. Since omega(a,b,c) <= omega_square(a,b,c) with strict inequality for known algorithms when omega > 2 and a,b,c are not all equal, the theorem as stated is stronger than what the proof establishes. Please state the theorem in terms of omega_square-submodular width, or prove that the algorithm achieves the true omega exponent.","section":"Section 3 and Definition 4.2; Theorem 7.1"}],"minor_comments":[{"comment":"The displayed inequality is hard to read because the underbraces and alignment suggest that the left-hand side is a single sum; please format it as omega*h(XYZ) + h(X) + h(Y) + gamma*h(Z) <= RHS, with the two bracketed groups clearly marked as the for-loop and MM costs.","section":"Section 2, Eq. (13)"},{"comment":"After applying Lemma E.11, the proof sets obj = opt * log N, but Theorem E.10 defines obj as the ratio in Eq. (71) with actual degrees. Since deg_Ri(Y_i|X_i) <= N, the intended bound is obj_E.10 <= opt * log N; please make this inequality explicit rather than defining them as equal.","section":"Appendix E.6, proof of Theorem 7.1"},{"comment":"In the case W = G_j Z_j, if kappa'_j = 0 the proof says the entire j-th summand is dropped from [J], which also removes the remaining positive coefficients alpha_j, beta_j, and zeta_j - 1. This is harmless for the inequality itself, but it should be explained why it is compatible with the coverage invariant in Theorem E.10, since the corresponding MM output tables are no longer produced on that branch.","section":"Appendix E.3, Lemma E.7"},{"comment":"There are several typos: 'Subdmodular width' in Section 2, 'Ineqality' in the heading of Lemma E.11, 'Seqence' in the heading of Theorem E.8, 'takeing' in Example D.1, and 'submodular with' in Table 2 caption. Please proofread.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely correct in its high-level architecture, and the detailed derivations for cliques, cycles, and pyramids are valuable. The main barrier to acceptance is the missing proof of Lemma E.11, which is the unique bridge between the LP formulation and the algorithm's runtime guarantee. I would recommend asking the authors for a complete proof of that lemma, or a precise citation-and-adaptation argument, before the paper can be accepted. The omega versus omega_square issue should also be resolved in the final version, since it affects the interpretation of the main theorem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a real contribution and deserves a serious referee, but the headline theorem is only as solid as Lemma E.11, and that lemma is currently a sketch. The core idea is clean: generalize the submodular width by letting each elimination step choose between a combinatorial join and a matrix multiplication, with the MM cost expressed through a polymatroid quantity. The resulting omega-submodular width is a natural object, the generalized variable elimination orders are a sensible extension, and the matching algorithm is a genuine PANDA-style construction with a generalized Reset Lemma and a proof-sequence construction that have to handle proper conditionals and omega-dominant triples. That is nontrivial and, as far as I can tell, honest work.\n\nWhat the paper does well: it recovers known results for triangles, cliques, and 4-cycles, and it derives new bounds for k-pyramids that are strict improvements. The table is careful to distinguish exact values from upper bounds. The appendix is detailed, and the self-citations are to the PANDA line that this work directly extends, so I do not see a citation problem.\n\nThe soft spots are real but addressable. First, Lemma E.11 is load-bearing: it converts an LP optimum into an integral omega-Shannon inequality with an exact coefficient ratio, and that exact equality is what makes the runtime match omega-subw(Q). The appendix says the proof is \"very similar\" to a lemma in [4,5] and \"relies on the observation\" that dual feasible solutions correspond to inequalities. Given the new proper-conditioning terms and the integrality requirement for rational omega, that is not enough. This needs a complete proof, not a pointer.\n\nSecond, the abstract overstates what is recovered. The framework is built on the square-MM bound omega_square, so it recovers the best known complexities only when the best known algorithm uses square MM or when omega=2. For cycles, the paper recovers c_square_k, not the rectangular-MM exponent c_k, and those differ for several even k when omega>2. The table footnote says this, but the abstract's \"recovers the best known complexities\" is too strong. That is a presentation issue, not a fatal flaw, but it should be fixed.\n\nOn the stress-test concern: yes, Lemma E.11 is the weakest link, and the concern lands. I do not see a circularity problem; the definition of omega-subw is not fitted to data, and the new pyramid bounds are derived, not reverse-engineered.\n\nWho this is for: database theory folks working on join algorithms, information inequalities, and worst-case query evaluation. It should go to a serious venue with a referee who will actually check Appendix E. My recommendation: send to peer review, and require a full proof of Lemma E.11 plus a toned-down abstract before acceptance.","headline":"A serious, well-built framework for matrix-multiplication join algorithms, but the main theorem currently rests on a sketched lemma (E.11) that needs a full proof before the runtime claim is air-tight.","tokens_in":54962,"tokens_out":1637,"would_cite":true,"duration_ms":19843,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P15","68Q25","68Q17","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single width measure now sets the cost of every join query when fast matrix multiplication is allowed.","keywords":["Boolean conjunctive queries","omega-submodular width","submodular width","fast matrix multiplication","join algorithms","Shannon inequalities","variable elimination","data complexity"],"falsifier":"Simulate the algorithm on a small query, such as the triangle, on the extremal database described by the lower-bound polymatroid of Lemma C.5, and verify that every branch of the proof sequence stays within $\\tilde{O}(N^{2\\omega/(\\omega+1)})$ and that invariant (75) is maintained at each reset; a branch where the invariant forces an omitted table or an oversized intermediate would disprove Theorem 7.1.","tokens_in":53899,"feed_emoji":"🧮","tokens_out":6216,"duration_ms":60820,"temperature":0.7,"pith_summary":"The paper aims to settle, in one measure, the data complexity of answering any fixed Boolean conjunctive query when fast matrix multiplication is allowed alongside combinatorial join techniques. It defines the $\\omega$-submodular width of a query, a number that generalizes the submodular width by letting each elimination step cost either the usual for-loop join cost or the cost of a matrix multiplication, whichever is smaller. The central theorem states that, for any rational matrix-multiplication exponent $\\omega\\in[2,3]$, every Boolean conjunctive query $Q$ can be answered in $\\tilde{O}(N^{\\omega\\text{-subw}(Q)})$ time on a database of size $N$. If correct, this is the first general framework that derives and analyzes matrix-multiplication join algorithms for arbitrary queries, recovering the best known exponents for triangles, cliques, and cycles and improving the known exponent for $k$-pyramids.","feed_headline":"One new width sets the cost of every join query","feed_subtitle":"The omega-submodular width recovers known join speedups and proves new ones.","key_machinery":"The central objects are generalized variable elimination orders (GVEOs), which partition variables into blocks eliminated one block at a time, and the matrix multiplication expression $\\text{MM}(\\boldsymbol{X};\\boldsymbol{Y};\\boldsymbol{Z}|\\boldsymbol{G})=\\max\\{h(\\boldsymbol{X}|\\boldsymbol{G})+h(\\boldsymbol{Y}|\\boldsymbol{G})+\\gamma h(\\boldsymbol{Z}|\\boldsymbol{G})+h(\\boldsymbol{G}),\\dots\\}$, which captures the log-cost of multiplying two matrices with group-by variables $\\boldsymbol{G}$. The argument is carried by $\\omega$-Shannon inequalities, the generalized reset lemma, and the proof-sequence construction, which together turn symbolic inequalities into executable query plans; each proof step becomes either a degree-based partition, a join, or a matrix multiplication.","core_discovery":"On the paper's own terms, the discovery is that the power of fast matrix multiplication can be absorbed into the submodular-width landscape by replacing each variable-elimination cost with the minimum of the entropy of the union, $h(U^\\sigma_i)$, and a new matrix-multiplication expression $\\text{MM}(\\boldsymbol{X};\\boldsymbol{Y};\\boldsymbol{Z}|\\boldsymbol{G})$, defined from the polymatroid $h$ and the parameter $\\gamma=\\omega-2$. The resulting $\\omega$-submodular width is never above the submodular width, equals it when $\\omega=3$, and is computable by solving finitely many linear programs. The matching algorithm converts an $\\omega$-Shannon inequality into a proof sequence, translates each proof step into a database operation (degree partitioning, joins, or matrix multiplication), and thereby evaluates the query in $\\tilde{O}(N^{\\omega\\text{-subw}(Q)})$ time.","pith_inferences":["A natural next step, not taken in the paper, is to replace the square-blocking bound $\\omega_{\\square}(a,b,c)$ inside the MM expression with the fastest known rectangular multiplication constants $\\alpha$ and $\\mu$; that would yield a refined width whose values could be lower for skewed-degree parts.","Because the algorithm's branching mirrors the proof sequence, one could mechanically derive query plans for families outside the paper's examples, such as Loomis-Whitney joins with repeated attributes, and compare the resulting exponents against hand-designed algorithms.","The paper's conclusion that full conjunctive queries cannot benefit from the same framework suggests a precise open question: which head variables can be preserved through a matrix multiplication without losing tuple identity, and answering it could characterize the frontier of matrix-multiplication-accelerable conjunctive queries."],"forward_implications":["Any fixed Boolean conjunctive query can be evaluated in $\\tilde{O}(N^{\\omega\\text{-subw}(Q)})$ time, with $\\omega\\text{-subw}(Q)\\le \\text{subw}(Q)$ and equality when $\\omega=3$.","Known non-combinatorial algorithms for the triangle, $k$-clique, $4$-cycle, and $k$-cycle appear as special cases of the framework rather than isolated constructions.","For $k$-pyramid queries the framework supplies an algorithm with exponent $2-\\frac{2}{\\omega(k-1)-k+3}$, improving on the best known $2-\\frac{1}{k}$ for suitable $\\omega$ and $k$.","The width can be computed by solving a finite number of linear programs, so the runtime guarantee is constructive for each query.","The framework extends to count and sum queries over the real semiring, but not to full conjunctive queries with free variables or to semirings that do not support matrix multiplication."],"supporting_citations":[{"why":"Supplies the PANDA algorithm and its reset lemma, the foundation that this paper generalizes to $\\omega$-Shannon inequalities.","marker":"[4,5]"},{"why":"Introduces the submodular width, the baseline combinatorial complexity that the $\\omega$-submodular width extends.","marker":"[24]"},{"why":"Gives the triangle algorithm with exponent $2\\omega/(\\omega+1)$, the first non-combinatorial result the framework recovers.","marker":"[6]"},{"why":"Provide the best-known cycle detection exponents $c_k$ that the framework recovers as upper bounds through $c_{\\square,k}$.","marker":"[12,35]"},{"why":"Provides the clique detection exponents for $k$-cliques that the framework recovers.","marker":"[16]"},{"why":"Supplies the current upper bound on the matrix multiplication exponent $\\omega$ used by the framework.","marker":"[32]"},{"why":"Establishes the equivalence between variable elimination orders and tree decompositions used to bridge query plans and polymatroid costs.","marker":"[3]"},{"why":"Established that $\\omega<3$, the fact that makes fast matrix multiplication relevant for join algorithms.","marker":"[29]"}],"fun_headline_variants":["New width unifies fast matrix multiplication and joins","Omega-submodular width: fastest known join algorithms","Matrix multiplication now part of query width calculus","A stronger width that yields faster join queries","Submodular width meets fast matrix multiplication"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire runtime guarantee rests on the generalized reset lemma and the proof-sequence construction in the appendix, which extend the earlier combinatorial reset argument to inequalities with proper conditioning terms and $\\omega$-dominant triples; if either lemma is subtly wrong, the claimed matching bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["New width unifies fast matrix multiplication and joins","Omega-submodular width: fastest known join algorithms","Matrix multiplication now part of query width calculus","A stronger width that yields faster join queries","Submodular width meets fast matrix multiplication"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000349,"raw_usage":{"total_tokens":1918,"prompt_tokens":966,"completion_tokens":952,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":582,"completion_tokens_details":{"reasoning_tokens":883}},"tokens_in":582,"tokens_out":952,"duration_ms":8359,"temperature":1.0,"reasoning_tokens":883,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T19:54:50.110060+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the algorithm on a small query, such as the triangle, on the extremal database described by the lower-bound polymatroid of Lemma C.5, and verify that every branch of the proof sequence stays within $\\tilde{O}(N^{2\\omega/(\\omega+1)})$ and that invariant (75) is maintained at each reset; a branch where the invariant forces an omitted table or an oversized intermediate would disprove Theorem 7.1.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the clique detection exponents for $k$-cliques that the framework recovers."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Established that $\\omega<3$, the fact that makes fast matrix multiplication relevant for join algorithms."}],"review_version":1}