Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

Fast Matrix Multiplication meets the Submodular Width

T0 review · 2 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read A single width measure now sets the cost of every join query when fast matrix multiplication is allowed.

desk verdict 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. read the letter →

arxiv 2412.06189 v5 pith:CYHHGYHJ submitted 2024-12-09 cs.DB cs.CCcs.ITmath.IT

Mahmoud Abo Khamis , Xiao Hu , Dan Suciu This is my paper · ORCID
classification cs.DBcs.CCcs.ITmath.IT MSC 68P1568Q2568Q1705C85
keywords Booleanconjunctivequeriesomega-submodularwidthsubmodularfastmatrixmultiplicationjoinalgorithmsShannoninequalitiesvariableeliminationdatacomplexity
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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

2 major / 4 minor

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.

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 (2)
  1. [Appendix E.6, Lemma E.11] 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.
  2. [Section 3 and Definition 4.2; Theorem 7.1] 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.
minor comments (4)
  1. [Section 2, Eq. (13)] 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.
  2. [Appendix E.6, proof of Theorem 7.1] 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.
  3. [Appendix E.3, Lemma E.7] 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.
  4. [Throughout] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the omega-submodular width is a formal definition and Theorem 7.1 is a constructive algorithm for it; prior results are benchmarks, not calibration.

full rationale

The paper's central object, omega-subw(H), is defined independently in Definition 4.7 as a max-min over polymatroids, GVEOs, and elimination costs, and Section 6 reduces its computation to LPs. Theorem 7.1 is not obtained by fitting a parameter to a runtime: it gives a constructive algorithm whose proof translates an optimal dual solution of LP (34)/(78) into an integral omega-Shannon inequality (Lemma E.11), decomposes it into a proof sequence (Theorem E.8), and realizes each proof step as a database operation (Theorem E.10). The coefficient ratio in Lemma E.11 is an LP-duality identity, not a definitional restatement of the target runtime. The generalized Reset Lemma and proof-sequence construction are proved in the appendix rather than imported as black boxes. The reported recoveries of known triangle, clique, and cycle bounds are sanity checks against independent literature; the k-pyramid bound is a derived upper bound, not a renamed known result. The main caveat is that Lemma E.11 is stated with a proof sketch referring to prior work [4,5] by overlapping authors; if that lemma fails, Theorem 7.1 would lack its stated guarantee. That is a completeness or correctness risk, not a circular reduction: no equation in the paper is shown to be equivalent to its own input by construction.

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

The central claim is a mathematical theorem; it rests on standard information-theoretic and algorithmic background plus the paper's own lemmas. No parameters are fitted to data. The novel objects are definitions, and the key lemmas are asserted within the paper rather than imported from prior work. The choice of square-MM bound is an explicit limitation, not a hidden fitted constant.

assumptions (5)
  • domain assumption The set of edge-dominated polymatroids Gamma intersection ED models the possible degree configurations of database instances.
    Inherited from PANDA and submodular width [4,5,24]; used in Definition 4.7 and throughout Section 4. Not proven in this paper.
  • standard math Equivalence of tree decompositions and (generalized) variable elimination orders (Proposition 3.1 and Proposition 4.8).
    Cited to [3]; used to define omega-subw via GVEOs in Section 4.
  • domain assumption Matrix multiplication can be performed in time O(n^{omega+o(1)}) and rectangular multiplication via block decomposition achieves omega_square(a,b,c) (Eq. 6).
    Background from [29,32]; the framework's width is measured against the square-MM bound, which may be weaker than optimal rectangular MM.
  • standard math LP strong duality and Farkas' lemma relate primal feasible polymatroids to dual omega-Shannon inequalities.
    Used in Lemma E.11 and Proposition E.4 in Appendix E.
  • domain assumption omega is a rational constant in [2,3]; irrational omega is handled by rational approximation.
    Assumed in Theorem 7.1 to obtain integral inequalities and finite LPs.
invented entities (5)
  • omega-submodular width (omega-subw)
    purpose: New width measure that quantifies the best query-answering exponent when fast matrix multiplication is allowed.
    Defined in Definition 4.7; internal mathematical definition with no external falsifiable handle.
  • Generalized Variable Elimination Order (GVEO)
    purpose: Allows eliminating multiple variables at once so that a single matrix multiplication can eliminate a block.
    Definition 4.1; generalizes standard VEOs.
  • Matrix multiplication expression MM(X;Y;Z|G)
    purpose: Expresses the log-scale cost of a matrix multiplication operation in polymatroid terms.
    Definition 4.2; the core translation of MM cost into information theory.
  • Variable elimination via MM expression EMM(X)
    purpose: Minimum MM cost over all ways to partition neighboring hyperedges into two matrices.
    Definition 4.5.
  • omega-Shannon inequality
    purpose: A class of inequalities used to drive the PANDA-style algorithm with MM terms.
    Definition E.3 in Appendix E.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast Matrix Multiplication meets the Submodular Width." pith.science (2026). https://pith.science/paper/CYHHGYHJ

@misc{pith2026241206189,
  author       = {Pith},
  title        = {Pith review of: Fast Matrix Multiplication meets the Submodular Width},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CYHHGYHJ}},
  note         = {Machine review of arXiv:2412.06189}
}
read the original abstract

One fundamental question in database theory is the following: Given a Boolean Conjunctive Query (BCQ) Q, what is the best complexity for computing the answer to Q in terms of the input database size N? When restricted to the class of combinatorial algorithms, it is known that the best known complexity for any query Q is captured by the submodular width of Q. However, beyond combinatorial algorithms, certain queries are known to admit faster algorithms that often involve a clever combination of fast matrix multiplication and data partitioning. Nevertheless, there is no systematic way to derive and analyze the complexity of such algorithms for arbitrary queries Q. In this work, we introduce a general framework that captures the best complexity for answering any BCQ Q using matrix multiplication. Our framework unifies both combinatorial and non-combinatorial techniques under the umbrella of information theory. It generalizes the notion of submodular width to a new stronger notion called the omega-submodular width that naturally incorporates the power of fast matrix multiplication. We describe a matching algorithm that computes the answer to any query Q in time corresponding to the omega-submodular width of Q. We show that our framework recovers the best known complexities for Boolean queries that have been studied in the literature, to the best of our knowledge, and also discovers new algorithms for some classes of queries that improve upon the best known complexities.

Figures

Figures reproduced from arXiv: 2412.06189 by the authors.

Figure 1
Figure 1. The proof sequence for the Shannon inequality [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Diagram of the polymatroid for the clique-3 hypergraph. [PITH_FULL_IMAGE:figures/full_fig_p024_2.png] view at source ↗
Figure 3
Figure 3. Diagram of the polymatroid for cycle-4 hypergraph. [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Diagram of the polymatroid for 3-Pyramid hypergraph. [PITH_FULL_IMAGE:figures/full_fig_p030_4.png]

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. Lower Bounds for Conjunctive Query Evaluation

    cs.DB 2025-06 unverdicted

    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.

Reference graph

Works this paper leans on

73 extracted references · 57 canonical work pages · cited by 1 Pith paper

  1. [1]

    Amir Abboud, Karl Bringmann, Nick Fischer, and Marvin Künnemann. 2024. The Time Complexity of Fully Sparse Matrix Multiplication. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) . SIAM, 4670–4703

    work page 2024

  2. [2]

    Curtin, Benjamin Moseley, Hung Q

    Mahmoud Abo Khamis, Ryan R. Curtin, Benjamin Moseley, Hung Q. Ngo, Xuanlong Nguyen, Dan Olteanu, and Maximilian Schleich. 2020. Functional Aggregate Queries with Additive Inequalities. ACM Trans. Database Syst. 45, 4, Article 17 (dec 2020), 41 pages. https://doi.org/10.1145/3426865

    doi:10.1145/3426865 2020

  3. [3]

    Ngo, and Atri Rudra

    Mahmoud Abo Khamis, Hung Q. Ngo, and Atri Rudra. 2016. FAQ: Questions Asked Frequently. In 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 , Tova Milo and Wang-Chiew Tan (Eds.). ACM, 13–28. https://doi.org/10.1145/2902251.2902280

    arXiv 2016

  4. [4]

    Ngo, and Dan Suciu

    Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. 2017. What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?. In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017 , Emanuel Sallinger, Jan Van den Bussche, and Floris Ge...

    arXiv 2017

  5. [5]

    PANDA: Query Evaluation in Submodular Width

    Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. 2024. PANDA: Query Evaluation in Submodular Width. arXiv e-prints, Article arXiv:2402.02001 (Feb. 2024), arXiv:2402.02001 pages. https://doi.org/10.48550/arXiv.2402.02001 arXiv:2402.02001 [cs.DB]

    work page Pith review arXiv doi:10.48550/arxiv.2402.02001 2024

  6. [6]

    Noga Alon, Raphael Yuster, and Uri Zwick. 1997. Finding and Counting Given Length Cycles. Algorithmica 17, 3 (1997), 209–223. https://doi.org/10.1007/BF02523189

    doi:10.1007/bf02523189 1997

  7. [7]

    Rasmus Resen Amossen and Rasmus Pagh. 2009. Faster join-projects and sparse matrix multiplications. In Proceedings of the 12th International Conference on Database Theory . ACM, 121–126

    work page 2009

  8. [8]

    Albert Atserias, Martin Grohe, and Dániel Marx. 2008. Size Bounds and Query Plans for Relational Joins. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA . IEEE Computer Society, 739–748. https://doi.org/10.1109/FOCS.2008.43

    doi:10.1109/focs.2008.43 2008

Show all 73 references
  1. [9]

    Albert Atserias, Martin Grohe, and Dániel Marx. 2013. Size Bounds and Query Plans for Relational Joins. SIAM J. Comput. 42, 4 (2013), 1737–1767. https://doi.org/10.1137/110859440

    2013 doi

  2. [10]

    Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams. 2024. Fast Approximate Counting of Cycles. In51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) . Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 37–1

    2024

  3. [11]

    Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams, and Yinzhan Xu. 2024. Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing . 923–934

    2024

  4. [12]

    Mina Dalirrooyfard, Thuy Duong Vuong, and Virginia Vassilevska Williams. 2019. Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 1167–1178

    2019

  5. [13]

    Rina Dechter. 1999. Bucket elimination: a unifying framework for reasoning. Artif. Intell. 113, 1–2 (Sept. 1999), 41–85. https://doi.org/10.1016/S0004-3702(99)00059-4 Fast Matrix Multiplication meets the Submodular Width 19

    1999 doi

  6. [14]

    Rina Dechter. 2019. Reasoning with Probabilistic and Deterministic Graphical Models . Springer Cham. https://doi.org/ 10.1007/978-3-031-01583-0

    2019 doi

  7. [15]

    Shaleen Deep, Xiao Hu, and Paraschos Koutris. 2020. Fast join project query evaluation using matrix multiplication. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data . 1213–1223

    2020

  8. [16]

    Friedrich Eisenbrand and Fabrizio Grandoni. 2004. On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science 326, 1-3 (2004), 57–67

    2004

  9. [17]

    Francois Le Gall and Florent Urrutia. [n. d.]. Improved Rectangular Matrix Multiplication using Pow- ers of the Coppersmith-Winograd Tensor . 1029–1046. https://doi.org/10.1137/1.9781611975031.67 arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611975031.67

    doi

  10. [18]

    Martin Grohe and Dániel Marx. 2006. Constraint solving via fractional edge covers. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006 . ACM Press, 289–298. http://dl.acm.org/citation.cfm?id=11...

    2006

  11. [19]

    Martin Grohe and Dániel Marx. 2014. Constraint Solving via Fractional Edge Covers. ACM Trans. Algorithms 11, 1 (2014), 4:1–4:20. https://doi.org/10.1145/2636918

    2014 doi

  12. [20]

    Xiao Hu. 2024. Fast matrix multiplication for query processing. Proceedings of the ACM on Management of Data 2, 2 (2024), 1–25

    2024

  13. [21]

    Zichun Huang and Shimin Chen. 2022. Density-optimized intersection-free mapping and matrix multiplication for join-project operations. Proceedings of the VLDB Endowment 15, 10 (2022), 2244–2256

    2022

  14. [22]

    Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams, and Nicole Wein. 2025. Beyond 2-Approximation for k-Center in Graphs. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) . SIAM, 175–211

    2025

  15. [23]

    Ce Jin, Virginia Vassilevska Williams, and Renfei Zhou. 2024. Listing 6-Cycles. In 2024 Symposium on Simplicity in Algorithms (SOSA). SIAM, 19–27

    2024

  16. [24]

    Dániel Marx. 2013. Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries. J. ACM 60, 6 (2013), 42:1–42:51. https://doi.org/10.1145/2535926

    2013 doi

  17. [25]

    Hung Q. Ngo. 2018. Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (Houston, TX, USA) (PODS ’18). Association for Computing Machinery, New York, NY, USA, ...

    2018

  18. [26]

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

    Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. 2018. Worst-case Optimal Join Algorithms. J. ACM 65, 3, Article 16 (March 2018), 40 pages. https://doi.org/10.1145/3180143

    2018 doi

  19. [27]

    Ngo, Christopher Ré, and Atri Rudra

    Hung Q. Ngo, Christopher Ré, and Atri Rudra. 2013. Skew strikes back: new developments in the theory of join algorithms. SIGMOD Rec. 42, 4 (2013), 5–16. https://doi.org/10.1145/2590989.2590991

    2013

  20. [28]

    Mihai Patrascu. 2010. Towards polynomial lower bounds for dynamic problems. In Proceedings of the forty-second ACM symposium on Theory of computing . 603–610

    2010

  21. [29]

    Volker Strassen. 1969. Gaussian elimination is not optimal.Numer. Math.13 (1969), 354–356. https://api.semanticscholar. org/CorpusID:121656251

    1969

  22. [30]

    Jakub Tětek. 2022. Approximate Triangle Counting via Sampling and Fast Matrix Multiplication. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 107–1

    2022

  23. [31]

    Veldhuizen

    Todd L. Veldhuizen. 2014. Triejoin: A Simple, Worst-Case Optimal Join Algorithm. InProc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014 , Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy (Eds.). OpenProceedings.org, 96–1...

    2014 doi

  24. [32]

    Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. [n. d.]. New Bounds for Matrix Multiplication: from Alpha to Omega . 3792–3835. https://doi.org/10.1137/1.9781611977912.134 arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611977912.134

    doi

  25. [33]

    Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. 2024. New bounds for matrix multiplication: from alpha to omega. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) . SIAM, 3792–3835

    2024

  26. [34]

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

    1981

  27. [35]

    Raphael Yuster and Uri Zwick. 2004. Detecting short directed cycles using rectangular matrix multiplication and dynamic programming.. In SODA, Vol. 4. 254–260

    2004

  28. [36]

    Nevin Lianwen Zhang and David Poole. 1996. Exploiting causal independence in Bayesian network inference. J. Artif. Int. Res. 5, 1 (Dec. 1996), 301–328

    1996

  29. [37]

    subsumes

    Nevin Lianwen Zhang and David L. Poole. 1994. A simple approach to Bayesian network computations. https: //api.semanticscholar.org/CorpusID:2978086 20 Mahmoud Abo-Khamis, Xiao Hu, & Dan Suciu A MISSING DETAILS FROM SECTION 3 In this appendix, we provide further examples and de...

    1994

  30. [38]

    Consider a generalized elimination ordering 𝝈 =({𝑋},{𝑌},{𝑍},{𝑊}). By choosingA ={{𝑋,𝑊},{𝑌,𝑊}} andB ={{𝑋,𝑊},{𝑍,𝑊}}, EMM𝝈 1 ≤ MM(𝑌 ;𝑍 ;𝑋|𝑊) = max    𝛾ℎ(𝑌|𝑊)+ ℎ(𝑋|𝑊)+ ℎ(𝑍|𝑊)+ ℎ(𝑊) ℎ(𝑌|𝑊)+ 𝛾ℎ(𝑍|𝑊)+ ℎ(𝑋|𝑊)+ ℎ(𝑊) ℎ(𝑌|𝑊)+ ℎ(𝑍|𝑊)+ 𝛾ℎ(𝑋|𝑊)+ ℎ(𝑊) ≤ 𝛾 2+ 1 2+ 1 = 𝜔+ 1 2 . Case 2...

  31. [39]

    Wlog, supposeℎ(𝑌|𝑋) > 1

  32. [40]

    Asℎ(𝑋𝑌)≤ 1, we haveℎ(𝑋) =ℎ(𝑋𝑌)− ℎ(𝑌|𝑋) < 1− 1 2 = 1

  33. [41]

    Similarly, we haveℎ(𝑌),ℎ(𝑍),ℎ(𝑊) < 1

  34. [42]

    We have EMM𝝈 1 ≤ MM(𝑌 ;𝑍 ;𝑋|𝑊) = 𝜔+1 2

    Consider a generalized elimination ordering 𝝈 =({𝑋},{𝑌},{𝑍},{𝑊}). We have EMM𝝈 1 ≤ MM(𝑌 ;𝑍 ;𝑋|𝑊) = 𝜔+1 2 . Direction𝜔-subw(H)≥ 𝜔+1 2 . We identify a polymatroid 𝒉∈ Γ∩ ED as follows: let𝑋,𝑌,𝑍,𝑊 be independently random variables withℎ(𝑋) =ℎ(𝑌) =ℎ(𝑍) =ℎ(𝑊) = 1

  35. [43]

    From Proposition C.4, for an arbitrary generalized elimination ordering 𝝈∈𝜋(V) , EMM𝝈 1 = 𝜔+1 2

    Then, we haveℎ(V) = 2. From Proposition C.4, for an arbitrary generalized elimination ordering 𝝈∈𝜋(V) , EMM𝝈 1 = 𝜔+1 2 . From (40), we conclude𝜔-subw(H)≥ 𝜔+1 2 . □ Lemma C.7. For the following 5-clique hypergraphH ,𝜔-subw(H) = 𝜔 2+ 1. H =({𝑋,𝑌,𝑍,𝑊,𝐿 },{{𝑋,𝑌},{𝑋,𝑍},{𝑋,𝑊},{𝑋,𝐿},...

  36. [44]

    By choosingA ={{𝑋,𝑊},{𝑌,𝑊},{𝑋,𝐿}} andB ={{𝑋,𝑊},{𝑍,𝑊}}, EMM𝝈 1 ≤ MM(𝑌𝑍,𝑊,𝑋 |𝐿) =ℎ(𝑌𝑍)+ 𝛾· min{ℎ(𝑊|𝐿),ℎ(𝑋|𝐿)}+ max{ℎ(𝑊|𝐿),ℎ(𝑋|𝐿)}+ ℎ(𝐿) ≤ 1+𝛾 2+ 1 = 𝜔 2+ 1

    Consider a generalized elimination ordering𝝈 = ({𝑋},{𝑌𝑍},{𝑊},{𝐿}). By choosingA ={{𝑋,𝑊},{𝑌,𝑊},{𝑋,𝐿}} andB ={{𝑋,𝑊},{𝑍,𝑊}}, EMM𝝈 1 ≤ MM(𝑌𝑍,𝑊,𝑋 |𝐿) =ℎ(𝑌𝑍)+ 𝛾· min{ℎ(𝑊|𝐿),ℎ(𝑋|𝐿)}+ max{ℎ(𝑊|𝐿),ℎ(𝑋|𝐿)}+ ℎ(𝐿) ≤ 1+𝛾 2+ 1 = 𝜔 2+ 1. • Case 2: None of the above, i.e., each vertex has at l...

  37. [45]

    We have EMM𝝈 1 ≤ MM(𝑌𝑍 ;𝑊𝐿 ;𝑋)≤ 𝜔 2+ 1

    Consider a generalized elimination ordering 𝝈 =({𝑋},{𝑌},{𝑍},{𝑊},{𝐿}). We have EMM𝝈 1 ≤ MM(𝑌𝑍 ;𝑊𝐿 ;𝑋)≤ 𝜔 2+ 1. Direction𝜔-subw(H)≥ 𝜔 2+ 1. We identify a polymatroid𝒉∈ Γ∩ ED as follows: let𝑋,𝑌,𝑍,𝑊,𝐿 be independently random variables withℎ(𝑋) =ℎ(𝑌) =ℎ(𝑍) =ℎ(𝑊) =ℎ(𝐿) = 1

  38. [46]

    Then, we have ℎ(V) = 5

  39. [47]

    □ Lemma C.8

    From Proposition C.4, for an arbitrary generalized elimination ordering 𝝈∈ 𝜋(V) , EMM𝝈 1 = 𝜔 2+ 1. □ Lemma C.8. For a𝑘-clique hypergraphH =(V,E) for𝑘≥ 6, whereV ={𝑋1,𝑋 2,··· ,𝑋𝑘} and E ={{𝑋𝑖,𝑋𝑗} :𝑖,𝑗 ∈[ 𝑘],𝑖 ≠ 𝑗},𝜔-subw(H) = 1 2·⌈ 𝑘 3⌉+ 1 2·⌈ 𝑘−1 3 ⌉+ 1 2·⌊ 𝑘 3⌋·( 𝜔− 2). Proof...

  40. [48]

    As𝑈 𝝈 3 ,𝑈 𝝈 4 ⊆𝑈 𝝈 1 , we have: max 𝑖∈[| 𝝈|] min ℎ(𝑈 𝝈 𝑖), EMM𝝈 𝑖 ≤ max{min{𝜔(1− Δ), 2− Δ}, 1+ Δ}

    =ℎ(𝑌𝑍𝑊)≤ ℎ(𝑌|𝑍𝑊)+ ℎ(𝑍𝑊)≤ ℎ(𝑌|𝑍)+ ℎ(𝑍𝑊)≤ 1+ Δ. As𝑈 𝝈 3 ,𝑈 𝝈 4 ⊆𝑈 𝝈 1 , we have: max 𝑖∈[| 𝝈|] min ℎ(𝑈 𝝈 𝑖), EMM𝝈 𝑖 ≤ max{min{𝜔(1− Δ), 2− Δ}, 1+ Δ}. • Case 3: two non-tangent vertices have all their neighboring conditional entropies smaller than Δ. Suppose𝑋,𝑍 are two non-tangent ...

  41. [49]

    Similarly, ℎ(𝑈 𝝈

    = ℎ(𝑋𝑌𝑊) ≤ℎ(𝑊|𝑋𝑌)+ ℎ(𝑋𝑌) ≤ℎ(𝑊|𝑋)+ ℎ(𝑋𝑌) ≤ 1+ Δ. Similarly, ℎ(𝑈 𝝈

  42. [50]

    As𝑈 𝝈 3 ,𝑈 𝝈 4 ⊆𝑈 𝝈 1 , we have max 𝑖∈[| 𝝈|] min ℎ(𝑈 𝝈 𝑖), EMM𝝈 𝑖 ≤ 1+ Δ

    =ℎ(𝑍𝑌𝑊)≤ ℎ(𝑊|𝑍𝑌)+ ℎ(𝑍𝑌)≤ ℎ(𝑊|𝑍)+ ℎ(𝑍𝑌)≤ 1+ Δ. As𝑈 𝝈 3 ,𝑈 𝝈 4 ⊆𝑈 𝝈 1 , we have max 𝑖∈[| 𝝈|] min ℎ(𝑈 𝝈 𝑖), EMM𝝈 𝑖 ≤ 1+ Δ. • Case 4: two tangent vertices have all their neighboring conditional entropies smaller than Δ, and the other two have some neighboring conditional entropy l...

  43. [51]

    = ℎ(𝑋𝑌𝑍) ≤ℎ(𝑋)+ ℎ(𝑌𝑍) ≤2− Δ andℎ(𝑈 𝝈

  44. [52]

    As 𝑈 𝝈 3 ,𝑈 𝝈 4 ⊆𝑈 𝝈 1 , we have max 𝑖∈[| 𝝈|] min ℎ(𝑈 𝝈 𝑖), EMM𝝈 𝑖 ≤ 2− Δ

    = ℎ(𝑋𝑍𝑊) ≤ℎ(𝑋)+ ℎ(𝑍𝑊) ≤2− Δ. As 𝑈 𝝈 3 ,𝑈 𝝈 4 ⊆𝑈 𝝈 1 , we have max 𝑖∈[| 𝝈|] min ℎ(𝑈 𝝈 𝑖), EMM𝝈 𝑖 ≤ 2− Δ. – We can also further distinguish two more cases: ∗ Ifℎ(𝑌|𝑍)≤ Δ 2 andℎ(𝑋|𝑊)≤ Δ 2 , we haveℎ(𝑋𝑌𝑍𝑊)≤ ℎ(𝑋|𝑌𝑍𝑊)+ ℎ(𝑌|𝑍𝑊)+ ℎ(𝑍𝑊)≤ ℎ(𝑋|𝑊)+ ℎ(𝑌|𝑍)+ ℎ(𝑍𝑊)≤ 1+ Δ. ∗ Otherwise, either...

  45. [53]

    Moreover,ℎ(𝑈 𝝈

    =ℎ(𝑋𝑌𝑍)≤ ℎ(𝑋)+ ℎ(𝑌𝑍)≤ 2− Δ. Moreover,ℎ(𝑈 𝝈

  46. [54]

    As 𝑈 𝝈 3 ,𝑈 𝝈 4 ⊆𝑈 𝝈 1 , we have: max 𝑖∈[| 𝝈|] min ℎ(𝑈 𝝈 𝑖), EMM𝝈 𝑖 ≤ max 1+ Δ, min (𝜔− 1)( 1− Δ)+ 1− Δ 2 , 2− Δ

    = ℎ(𝑍𝑊𝑋) ≤ℎ(𝑍|𝑊𝑋)+ ℎ(𝑊𝑋) ≤ℎ(𝑍|𝑊)+ ℎ(𝑊𝑋) ≤1+ Δ. As 𝑈 𝝈 3 ,𝑈 𝝈 4 ⊆𝑈 𝝈 1 , we have: max 𝑖∈[| 𝝈|] min ℎ(𝑈 𝝈 𝑖), EMM𝝈 𝑖 ≤ max 1+ Δ, min (𝜔− 1)( 1− Δ)+ 1− Δ 2 , 2− Δ . Putting all cases together, we obtain the upper bound: max 1+ Δ, min (𝜔− 1)( 1− Δ)+ 1− Δ 2, 2− Δ If 5 2≤ 𝜔≤ 3, we s...

  47. [55]

    Putting two cases together, we obtain the desired upper bound

    If 2≤ 𝜔≤ 5 2, we set Δ = 2(𝜔−1) 2𝜔+1 to obtain the upper bound as 4𝜔−1 2𝜔+1 . Putting two cases together, we obtain the desired upper bound. Direction𝜔-subw(H)≥ 2− 3 2·min{𝜔, 5 2}+1 . Correspondingly, we identify a polymatroid𝒉∈ Γ∩ED by distinguishing the following two cases: ...

  48. [56]

    Letℎ(𝑋) =(𝑎𝑏),ℎ(𝑌) =(𝑐𝑑),ℎ(𝑍) =(𝑑𝑒) andℎ(𝑊) =(𝑎𝑒). We have • ℎ(𝑋) =ℎ(𝑌) = 1 2,ℎ(𝑍) =ℎ(𝑊) = 3 4; • ℎ(𝑋𝑌) =ℎ(𝑌𝑍) =ℎ(𝑍𝑊) =ℎ(𝑊𝑋) = 1 andℎ(𝑋𝑍) =ℎ(𝑌𝑊) = 5 4; • ℎ(𝑋𝑍𝑊) =ℎ(𝑌𝑍𝑊) = 5 4 andℎ(𝑋𝑌𝑍) =ℎ(𝑋𝑌𝑊) = 3 2; • ℎ(𝑋𝑌𝑍𝑊) = 3 2; Consider any generalized elimination ordering 𝝈∈𝜋(V) . We di...

  49. [57]

    =ℎ(𝑋𝑌𝑊) = 3 2 and EMM𝝈 1 = MM(𝑌,𝑊,𝑋 ) = 𝜔 2+ 1 4≥ 3 2 when𝜔≥ 5

  50. [58]

    • 𝝈[1] ={𝑊}.ℎ(𝑈 𝝈

    The case with 𝝈[1] ={𝑊} is the same. • 𝝈[1] ={𝑊}.ℎ(𝑈 𝝈

  51. [59]

    =ℎ(𝑋𝑍𝑊) = 5 4 and EMM𝝈 1 = MM(𝑋,𝑍,𝑊 ) = 𝜔 2+ 1 4≥ 3 2 when𝜔≥ 5

  52. [60]

    • |𝝈[1]| = 2.ℎ(𝑈 𝝈

    The case with 𝝈[1] ={𝑍} is the same. • |𝝈[1]| = 2.ℎ(𝑈 𝝈

  53. [61]

    Case 2:𝜔 < 5

    =ℎ(V) = 3 2 and EMM𝝈 1 ≥ MM(𝑋,𝑊,𝑍 ) = 𝜔 2+ 1 4≥ 3 2. Case 2:𝜔 < 5

  54. [62]

    Let𝑋 =(𝑏𝑐𝑓),𝑌 =(𝑑𝑒𝑓),𝑍 =(𝑎𝑒𝑓),𝑊 =(𝑎𝑏𝑓)

    Let𝑎,𝑏,𝑐,𝑑,𝑒,𝑓 be independently random variables withℎ(𝑎) = 2(𝜔−1) 2𝜔+1 ,ℎ(𝑏) = ℎ(𝑐) =ℎ(𝑑) =ℎ(𝑒) = 𝜔−1 2𝜔+1 andℎ(𝑓) = 5−2𝜔 2𝜔+1 . Let𝑋 =(𝑏𝑐𝑓),𝑌 =(𝑑𝑒𝑓),𝑍 =(𝑎𝑒𝑓),𝑊 =(𝑎𝑏𝑓). We have • ℎ(𝑊) =ℎ(𝑍) = 𝜔+2 2𝜔+1 andℎ(𝑋) =ℎ(𝑌) = 3 2𝜔+1; • ℎ(𝑊𝑋) =ℎ(𝑋𝑌) =ℎ(𝑌𝑍) =ℎ(𝑍𝑊) = 1,ℎ(𝑊𝑌) =ℎ(𝑋𝑍) = 3𝜔 ...

  55. [63]

    The case with 𝝈[1] ={𝑌} is the same

    = ℎ(𝑋𝑌𝑊) = 4𝜔−1 2𝜔+1 and EMM𝝈 1 = MM(𝑌,𝑊,𝑋 ) = 𝜔+2 2𝜔+1+ 3(𝜔−1) 2𝜔+1 = 4𝜔−1 2𝜔+1 . The case with 𝝈[1] ={𝑌} is the same. • 𝝈[1] ={𝑊}.ℎ(𝑈 𝝈

  56. [64]

    The case with 𝝈[1] ={𝑍} is the same

    =ℎ(𝑋𝑍𝑊) = 3𝜔 2𝜔+1 and EMM𝝈 1 = MM(𝑋,𝑍,𝑊 ) = 2(𝜔+2) 2𝜔+1 + 3(𝜔−2) 2𝜔+1 = 5𝜔−2 2𝜔+1 > 4𝜔−1 2𝜔+1 . The case with 𝝈[1] ={𝑍} is the same. • |𝝈[1]| = 2.ℎ(𝑈 𝝈

  57. [65]

    =ℎ(V) = 4𝜔−1 2𝜔+1 and EMM𝝈 1 ≥ MM(𝑌,𝑊,𝑋 ) = 4𝜔−1 2𝜔+1 . □

  58. [66]

    We define below an upper bound,𝑐□ 𝑘 , on𝑐𝑘 that uses only square matrix multiplication and show that 𝜔-subw(H) ≤𝑐□ 𝑘 for any 𝑘-cycle graphH

    defines an exponent𝑐𝑘 for detecting a𝑘-cycle in a graph, and the definition is based on rectangular matrix multiplication. We define below an upper bound,𝑐□ 𝑘 , on𝑐𝑘 that uses only square matrix multiplication and show that 𝜔-subw(H) ≤𝑐□ 𝑘 for any 𝑘-cycle graphH. In particular...

  59. [67]

    Consider a generalized elimination ordering 𝝈 =({𝑌}, 𝑨, 𝑩,{𝑋1}). We have EMM𝝈 1 ≤ MM(𝑨; 𝑩;𝑌|𝑋1)≤ 𝛾ℎ(𝑨)+ ℎ(𝑩)+ ℎ(𝑋1𝑌)≤ 𝛾(1− Δ)+( 1− Δ)+ 1 Combining all the cases, we obtain the desired upper bound1+ max{Δ,𝛾(1− Δ)+( 1− Δ)} = 2− 1 𝜔 , by setting Δ = 1− 1 𝜔 (note that Δ≥ 1 2). Dir...

  60. [68]

    EMM𝝈 1 = min{MM(𝑋1,𝑋 2,𝑌 ;𝑋3), MM(𝑋1,𝑋 2𝑋3,𝑌)} = 2− 1 𝜔 ; Fast Matrix Multiplication meets the Submodular Width 31 • 𝝈[1] ={𝑋1}.ℎ(𝑈 𝝈

    = ℎ(V) = 2− 1 𝜔 . EMM𝝈 1 = min{MM(𝑋1,𝑋 2,𝑌 ;𝑋3), MM(𝑋1,𝑋 2𝑋3,𝑌)} = 2− 1 𝜔 ; Fast Matrix Multiplication meets the Submodular Width 31 • 𝝈[1] ={𝑋1}.ℎ(𝑈 𝝈

  61. [69]

    EMM𝝈 1 = min{MM(𝑋2,𝑌,𝑋 1|𝑋3), MM(𝑋2𝑋3,𝑌,𝑋 1), MM(𝑋2,𝑋 3𝑌,𝑋 1)} = The case with 𝝈[1] ={𝑋2} or 𝝈[1] ={𝑋3} is the same

    = ℎ(V) = 2− 1 𝜔 . EMM𝝈 1 = min{MM(𝑋2,𝑌,𝑋 1|𝑋3), MM(𝑋2𝑋3,𝑌,𝑋 1), MM(𝑋2,𝑋 3𝑌,𝑋 1)} = The case with 𝝈[1] ={𝑋2} or 𝝈[1] ={𝑋3} is the same. • 𝝈[1] ={𝑋1,𝑌}.ℎ(𝑈 𝝈

  62. [70]

    EMM𝝈 1 = MM(𝑋2,𝑋 3,𝑋 1𝑌) = 2− 1 𝜔

    = ℎ(V) = 2− 1 𝜔 . EMM𝝈 1 = MM(𝑋2,𝑋 3,𝑋 1𝑌) = 2− 1 𝜔 . The case with 𝝈[1] ={𝑋2,𝑌} or 𝝈[1] ={𝑋3,𝑌} is the same. • 𝝈[1] ={𝑋1,𝑋 2}.ℎ(𝑈 𝝈

  63. [71]

    EMM𝝈 1 = MM(𝑋3,𝑌,𝑋 1𝑋2) = 2− 1 𝜔

    =ℎ(V) = 2− 1 𝜔 . EMM𝝈 1 = MM(𝑋3,𝑌,𝑋 1𝑋2) = 2− 1 𝜔 . The case with 𝝈[1] ={𝑋1,𝑋 3} or 𝝈[1] ={𝑋2,𝑋 3} is the same. Hence, for such 𝒉, we have max 𝑖∈[| 𝝈|] min ℎ 𝑈 𝝈 𝑖 , EMM𝝈 𝑖 ≥ 2− 1 𝜔 . □ Lemma C.14. For the following hypergraph representing a 𝑘-pyramid: H =({𝑌,𝑋 1,𝑋 2,··· ,𝑋𝑘},...

  64. [72]

    If𝜔 = 3,𝜔-subw(H)≤ 2− 1 2𝜔−1 = subw(H) = 9

  65. [73]

    If𝜔 < 3,𝜔-subw(H) < subw(H) . Proof. Let Δ = 2(𝜔−1) 2𝜔−1 . We partition all polymatroids 𝒉 into the following cases: • Case 1:ℎ(𝑋𝑌|𝑊)≤ Δ orℎ(𝑍𝐿|𝑊)≤ Δ. wlog, supposeℎ(𝑋𝑌|𝑊)≤ Δ. We haveℎ(𝑋𝑌𝑍𝑊𝐿)≤ ℎ(𝑋𝑌|𝑍𝑊𝐿)+ ℎ(𝑍𝑊𝐿)≤ ℎ(𝑋𝑌|𝑊)+ ℎ(𝑍𝑊𝐿)≤ 1+ Δ. • Case 2:ℎ(𝑋𝑌|𝐿)≤ Δ orℎ(𝑍𝑊|𝐿)≤ Δ. This cas...

Pith tools

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