pith. sign in

arxiv: 2605.08588 · v1 · submitted 2026-05-09 · 💻 cs.DS · cs.DM

Node-Weighted Triangles: Faster and Simpler

Shyan Akmal , Nick Fischer This is my paper

Pith reviewed 2026-05-12 01:05 UTC · model grok-4.3

classification 💻 cs.DS cs.DM
keywords node-weighted trianglematrix multiplicationtriangle detectionfine-grained complexitygraph algorithmssubcubic timealgorithm simplification
0
0 comments X

The pith

New algorithm solves node-weighted triangle detection in exact matrix-multiplication time.

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

The paper gives an algorithm that decides whether a vertex-weighted graph contains a triangle whose weights sum to zero. It runs in O(MM(n)) time, the same bound conjectured to be necessary even for the unweighted version. Prior algorithms for the weighted case always carried a small superpolylogarithmic overhead. The new method avoids the recursive decompositions and communication protocols used earlier. If the claim holds, the weighted problem collapses completely into the unweighted one.

Core claim

The authors present a new algorithm for Node-Weighted Triangle that runs in O(MM(n)) time. This closes the gap to unweighted triangle detection completely. The algorithm is much simpler than previous approaches, which use involved recursion schemes and communication protocols.

What carries the argument

A direct, non-recursive reduction of node-weighted triangle detection to a single matrix-multiplication call.

Load-bearing premise

The reduction correctly identifies a zero-sum triangle using only standard matrix multiplication and graph operations.

What would settle it

A concrete graph with a zero-sum-weight triangle on which the algorithm either returns no or exceeds the runtime of a single matrix-multiplication call by more than a constant factor.

read the original abstract

Weighted variants of triangle detection are an important object of study because of their prominence in fine-grained complexity. We revisit the Node-Weighted Triangle problem, where the goal is to decide if a vertex-weighted graph contains a triangle whose node weights sum to zero. This problem has been the focus of a celebrated line of work, beginning with a subcubic-time algorithm [Vassilevska, Williams; STOC '06], and culminating in algorithms running almost in matrix multiplication time, $O(\textsf{MM}(n) + n^2\cdot 2^{O(\sqrt{\log n})})$ [Czumaj, Lingas; SODA '07], [Vassilevska W., Williams; STOC '09]. This runtime is almost-optimal, since even detecting an unweighted triangle is conjectured to require matrix multiplication time $\textsf{MM}(n)$. However, the superpolylogarithmic $2^{\Omega(\sqrt{\log n})}$ overhead persists in a world where near-optimal matrix multiplication is possible (i.e., $\textsf{MM}(n) \leq n^2\text{poly}(\log n)$). In this paper, we present a new algorithm solving Node-Weighted Triangle in $O(\textsf{MM}(n))$ time, closing the gap to unweighted triangle detection completely. Remarkably, our algorithm is much simpler than previous approaches, which use involved recursion schemes and communication protocols.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript presents a new algorithm for the Node-Weighted Triangle problem (deciding whether a vertex-weighted graph contains a triangle whose weights sum to zero). It claims to solve the problem in O(MM(n)) time, matching the time for unweighted triangle detection and removing the 2^{O(sqrt(log n))} overhead from prior work, while being substantially simpler than previous recursive and communication-protocol-based approaches.

Significance. If the algorithm and its analysis are correct, the result is significant: it closes the gap to the conjectured matrix-multiplication lower bound for this fine-grained problem and does so with a simpler construction than the Czumaj-Lingas and Vassilevska-Williams algorithms. The explicit emphasis on simplicity is a strength that could aid further extensions to other weighted graph problems.

minor comments (1)
  1. The abstract states the O(MM(n)) bound but does not preview the high-level structure of the new algorithm; adding a short paragraph in the introduction that sketches the key combinatorial or algebraic idea would help readers appreciate the claimed simplicity before the full details.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the result's significance in closing the gap to the matrix-multiplication bound, and recommendation to accept the manuscript. We appreciate the referee's note that the emphasis on simplicity is a strength.

Circularity Check

0 steps flagged

No significant circularity; new algorithmic construction is self-contained

full rationale

The paper presents a direct algorithmic construction for Node-Weighted Triangle that runs in O(MM(n)) time, with a proof of correctness and runtime analysis. This is a standard algorithmic result whose validity rests on explicit steps (reduction to matrix multiplication primitives, handling of node weights) rather than any self-definition, fitted parameter renamed as prediction, or load-bearing self-citation chain. Prior work is cited only for context and contrast; the new algorithm does not import its central claim from those citations. No equations or reductions in the provided abstract or described structure collapse by construction to the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the correctness of an algorithmic construction whose details are not provided in the abstract; no free parameters or new entities are mentioned.

axioms (1)
  • standard math Standard definition of matrix multiplication time MM(n) as the time to multiply two n x n matrices over a ring.
    The target runtime is defined in terms of MM(n), which is a standard concept in the field.

pith-pipeline@v0.9.0 · 5556 in / 1200 out tokens · 60797 ms · 2026-05-12T01:05:08.282538+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    We present a new algorithm solving Node-Weighted Triangle in O(MM(n)) time... run an unweighted triangle detection algorithm on a small collection of subgraphs... reducing NWT to the structured version where each vertex weight appears the same number of times.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    SIAM Journal on Computing , publisher =

    Williams, Virginia Vassilevska and Williams, Ryan , year =. SIAM Journal on Computing , publisher =. doi:10.1137/09076619x , number =

    work page doi:10.1137/09076619x

  2. [2]

    SIAM Journal on Computing , publisher =

    Czumaj, Artur and Lingas, Andrzej , year =. SIAM Journal on Computing , publisher =. doi:10.1137/070695149 , number =

    work page doi:10.1137/070695149

  3. [3]

    SIAM Journal on Computing , publisher =

    Itai, Alon and Rodeh, Michael , year =. SIAM Journal on Computing , publisher =. doi:10.1137/0207033 , number =

    work page doi:10.1137/0207033

  4. [4]

    Alman, R

    Josh Alman and Ran Duan and Virginia. Proceedings of the 2025 Annual. 2025 , url =. doi:10.1137/1.9781611978322.63 , timestamp =

    work page doi:10.1137/1.9781611978322.63 2025

  5. [5]

    Fischer, M. J. and Meyer, A. R. , booktitle=. Boolean matrix multiplication and transitive closure , year=

    work page

  6. [6]

    A 2/3-approximation algorithm for vertex-weighted matching , volume =

    Al-Herz, Ahmed and Pothen, Alex , year =. A 2/3-approximation algorithm for vertex-weighted matching , volume =. doi:10.1016/j.dam.2019.09.013 , journal =

    work page doi:10.1016/j.dam.2019.09.013 2019

  7. [7]

    Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC) , pages =

    Chuzhoy, Julia and Trabelsi, Ohad , year =. doi:10.1145/3717823.3718185 , booktitle =

    work page doi:10.1145/3717823.3718185

  8. [8]

    , year =

    Karger, David R. , year =. Minimum cuts in near-linear time , volume =. Journal of the ACM , publisher =. doi:10.1145/331605.331608 , number =

    work page doi:10.1145/331605.331608

  9. [9]

    On some fine-grained questions in algorithms and complexity , pages 3447–3487

    Williams, Virginia Vassilevska , year =. doi:10.1142/9789813272880_0188 , booktitle =

    work page doi:10.1142/9789813272880_0188

  10. [10]

    Ryan , year =

    Williams, Virginia Vassilevska and Williams, R. Ryan , year =. Journal of the ACM , publisher =. doi:10.1145/3186893 , number =

    work page doi:10.1145/3186893

  11. [11]

    doi:10.1145/3717823.3718240 , booktitle =

    Abboud, Amir and Fischer, Nick and Jin, Ce and Williams, Virginia Vassilevska and Xi, Zoe , year =. doi:10.1145/3717823.3718240 , booktitle =

    work page doi:10.1145/3717823.3718240

  12. [12]

    doi:10.1007/11786986_24 , booktitle =

    Vassilevska, Virginia and Williams, Ryan and Yuster, Raphael , year =. doi:10.1007/11786986_24 , booktitle =

    work page doi:10.1007/11786986_24

  13. [13]

    and Yuster, R

    Alon, N. and Yuster, R. and Zwick, U. , year =. Finding and counting given length cycles , volume =. Algorithmica , publisher =. doi:10.1007/bf02523189 , number =

    work page doi:10.1007/bf02523189

  14. [14]

    Time-space trade-offs for predecessor search

    Vassilevska, Virginia and Williams, Ryan , year =. doi:10.1145/1132516.1132550 , booktitle =

    work page doi:10.1145/1132516.1132550

  15. [15]

    2020 , volume=

    Williams, Virginia Vassilevska and Xu, Yinzhan , booktitle=. 2020 , volume=

    work page 2020

  16. [16]

    and Xu, Yinzhan , year =

    Chan, Timothy M. and Xu, Yinzhan , year =. doi:10.1137/1.9781611977936.4 , booktitle =

    work page doi:10.1137/1.9781611977936.4

  17. [17]

    doi:10.1007/978-3-662-44777-2_1 , booktitle =

    Abboud, Amir and Lewi, Kevin and Williams, Ryan , year =. doi:10.1007/978-3-662-44777-2_1 , booktitle =

    work page doi:10.1007/978-3-662-44777-2_1

  18. [18]

    11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , pages =

    Lincoln, Andrea and Polak, Adam and Vassilevska Williams, Virginia , title =. 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , pages =. 2020 , volume =. doi:10.4230/LIPIcs.ITCS.2020.53 , annote =

    work page doi:10.4230/lipics.itcs.2020.53 2020