Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

All-Pairs Shortest Paths with Few Weights per Node

T0 review · 3 major / 4 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 Node-Weighted APSP runs in $\tilde{O}(n^{(3+\omega)/2})$; Few-Weights APSP is subcubic for $d\leq n^{3-\omega-\delta}$.

desk verdict Strong results and mostly clean proofs, but the final parameter choice in Theorem 1.5 is wrong as written — the error is load-bearing, probably fixable, and the paper deserves a serious referee with requests for revision. read the letter →

arxiv 2506.20017 v1 pith:QDZ2ALGG submitted 2025-06-24 cs.DS

Amir Abboud , Nick Fischer , Ce Jin , Virginia Vassilevska Williams , Zoe Xi This is my paper · ORCID
classification cs.DS MSC 68Q2568W4068R10
keywords APSPnode-weightedfew-weightsall-edgesexacttriangleBalog-Szemerédi-Gowerstheoremadditivecombinatoricsmin-plusproductfine-grainedcomplexity
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 paper studies All-Pairs Shortest Paths (APSP) when each node has at most $d$ distinct outgoing edge weights, a parameter that interpolates between node-weighted APSP ($d=1$) and unrestricted APSP ($d=n$). It proves two things. First, Node-Weighted APSP can be solved deterministically in $\tilde{O}(n^{(3+\omega)/2})=\tilde{O}(n^{2.686})$ time, which is $n^{2.5+o(1)}$ if $\omega=2$, placing the problem in the intermediate class just above the conditional $n^{2.5-o(1)}$ lower bound. Second, for every $\delta>0$, instances with $d\leq n^{3-\omega-\delta}$ distinct weights per node can be solved in $O(n^{3-\epsilon})$ time for some $\epsilon>0$. If matrix multiplication is optimal, this means APSP with any sublinear number of distinct weights per node is subcubic, so the hardest instances must use $n^{1-o(1)}$ weights per node. The proof routes Few-Weights APSP through All-Edges Exact Triangle and applies the Balog-Szemerédi–Gowers covering theorem from additive combinatorics, together with new uniformization and regularization reductions.

What carries the argument

The load-bearing object is the Balog-Szemerédi–Gowers (BSG) Covering Theorem (Theorem 3.1), an additive-combinatorics statement: any two integer sets $X,Y$ of size at most $d$ can be decomposed into $K$ pairs of subsets $X_k,Y_k$ whose sumsets are small, $|X_k+Y_k|\leq O(K^5 d)$, plus a small remainder $R$ with $|R|\leq O(d^2/K)$. The paper uses this decomposition to solve Few-Weights Exact Triangle after reductions: triangles whose weights fall in a structured piece are detected by fast matrix multiplication together with sparse hashing, while remainder triangles are enumerated by brute force, and the two costs are balanced by choosing $K=(n^{3-\omega}/d)^{1/7}$. For Node-Weighted APSP the mechanism is different: multi-level pivot sets (bridging sets) combined with rectangular Boolean min-plus products are iterated level by level, with a derandomization by greedy hitting sets.

What would settle it

Run the BSG covering construction on explicit families of $d$-element integer sets $X,Y$ together with a target sumset $Z$, using $K=(n^{3-\omega}/d)^{1/7}$, and check whether every covering must have some $|X_k+Y_k|=\Omega(K^5 d)$ or $|R|=\Omega(d^2/K)$; if any family forces bounds worse than $O(K^5 d)$ and $O(d^2/K)$, the balancing argument breaks and the claimed $O(n^{3-\epsilon})$ time for $n^{3-\omega-\delta}$-Weights APSP does not follow from this proof.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that neither the node-weighted case nor any sublinear-weight case of APSP is as hard as unrestricted APSP. Theorem 1.2 gives a deterministic algorithm for Node-Weighted APSP in $\tilde{O}(n^{(3+\omega)/2})$ time, improving the fifteen-year-old $\tilde{O}(n^{(9+\omega)/4})$-type bounds and showing that at $\omega=2$ the problem runs in $n^{2.5+o(1)}$ time, matching a conditional lower bound. Theorem 1.4 gives, for every $\delta>0$, a deterministic $O(n^{3-\epsilon})$ algorithm for $n^{3-\omega-\delta}$-Weights APSP; with $\omega=2$ this tolerates $d=n^{1-\epsilon}$ weights per node, positively answering the question of whether APSP-hard instances must exhaust a linear number of weights per node. The same framework solves Few-Weights All-Edges Exact Triangle in subcubic time. A complementary hardness result shows that under the Bounded Min-Plus Hypothesis, undirected $d$-Weights APSP requires $\sqrt{d}\,n^{2.5-o(1)}$ time, so the complexity jumps sharply from $n^{\omega}$ at $d=1$ to $n^{2.5-o(1)}$ at $d=2$.

Load-bearing premise

The Few-Weights subcubic guarantee rests on the exact quantitative bounds of the Balog-Szemerédi–Gowers covering theorem quoted from earlier work — structured pieces with sumset size $O(K^5 d)$ and a remainder of size $O(d^2/K)$ — and the paper does not re-prove those bounds; if the true exponents or constants are worse, the balancing choice $K=(n^{3-\omega}/d)^{1/7}$ no longer yields subcubic time.

Editorial extensions

If this is right

  • At $\omega=2$, Node-Weighted APSP runs in $n^{2.5+o(1)}$ time, matching the conditional $n^{2.5-o(1)}$ lower bound, so the problem sits in the intermediate complexity class.
  • For every $\delta>0$, instances with $d=n^{3-\omega-\delta}$ distinct weights per node are solvable in $O(n^{3-\epsilon})$ time for some $\epsilon>0$; with $\omega=2$ this covers every $d=n^{1-\epsilon}$, so any cubic-time-hard APSP instance must use $d=n^{1-o(1)}$ weights per node.
  • With current matrix multiplication constants, the algorithm is subcubic for $d\leq n^{0.628}$, improving the previous threshold $d\leq n^{0.384}$.
  • The analogous Few-Weights All-Edges Exact Triangle problem is also subcubic for the same parameter range, generalizing the clustered-3SUM result from arrays to matrices.
  • Under the Bounded Min-Plus Hypothesis, $d$-Weights APSP in undirected graphs requires $\sqrt{d}\,n^{2.5-o(1)}$ time; going from $d=1$ to $d=2$ raises the complexity from $n^{\omega}$ to $n^{2.5-o(1)}$.

Reading between the lines

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

  • The uniformization step suggests the true obstruction is not the count of distinct weights but the additive doubling of the weight sets; a testable extension is a $d$-Weights APSP algorithm whose running time is governed by a doubling constant rather than by $d$ itself.
  • The reduction chain from APSP through Min-Plus and All-Edges Exact Triangle to uniform-and-regular instances may transfer to other all-pairs problems with equality constraints, such as exact-sum triangle counting or clustered variants of min-plus convolution on matrices.
  • The undirected hardness result draws a sharp phase transition at $d=2$ that the paper does not try to match algorithmically; one open test is whether undirected $2$-Weights APSP admits an $O(n^{2.5+o(1)})$ algorithm when $\omega=2$, which would show the $n^{2.5-o(1)}$ lower bound is tight.
  • The framework's dependence on the BSG constants is explicit: if the covering theorem's sumset and remainder bounds were improved, the same algorithm would tolerate $d$ closer to $n^{3-\omega}$ and could turn the exponential-in-$1/\delta$ savings into a polynomial dependence of $\epsilon$ on $\delta$.
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

3 major / 4 minor

Summary. The paper studies All-Pairs Shortest Paths under the restriction that each node has at most d distinct outgoing edge weights. It presents three main algorithmic results: (1) a deterministic Node-Weighted APSP algorithm running in Õ(n^{(3+ω)/2}), improving on the 15-year-old bounds of Chan and Yuster; (2) a deterministic d-Weights APSP algorithm running in Õ(d·n^{(3+ω)/2}); and (3) for d = n^{3−ω−δ}, a subcubic O(n^{3−ε}) deterministic algorithm, obtained through a reduction to All-Edges Exact Triangle and a combination of the Balog–Szemerédi–Gowers covering theorem with new uniformization and regularization steps. The paper also gives a Few-Weights Exact Triangle algorithm and conditional lower bounds showing that undirected APSP with two distinct weights is as hard as n^{2.5−o(1)} under the Bounded Min-Plus Hypothesis.

Significance. If the technical gaps identified below are repaired, this is a strong and important paper. The results positively resolve two stated open questions of the area: with ω = 2, Node-Weighted APSP becomes an intermediate problem at n^{2.5+o(1)}, and APSP with any sublinear number of distinct weights per node becomes truly subcubic. The paper also gives a rare application of additive combinatorics to graph algorithms, extends Chan–Lewenstein Clustered 3SUM ideas to the matrix/graph setting, and includes deterministic derandomization and explicit hardness reductions. The proof structure is ambitious and mostly detailed; several lemmas (deterministic almost-linear hashing, rectangular Boolean min-plus products, the approximation of popular sums) are self-contained and useful beyond this paper.

major comments (3)
  1. [§5.5, proof of Theorem 1.5] The final parameter choice is invalid. The text says 'Picking ϵ = δ/14 and Δ = n^{2−c/ϵ} for some sufficiently large constant c', but Lemma 5.15 explicitly requires Δ ≥ 1. For every fixed c and all sufficiently small δ, c/ϵ = 14c/δ > 2, so Δ = n^{negative} < 1. With such Δ, the term eO(n^3/Δ) in the displayed running time is supercubic and cannot be absorbed into any O(n^{3−ϵ'}) bound. Thus the proof of Theorem 1.5, and consequently of Theorem 1.4, is incomplete as written. This appears fixable by choosing Δ = n^β with a positive exponent β = Θ(δ / 2^{O(1/ϵ)}) (or an equivalent reparameterization), giving subcubic time with exponentially small savings.
  2. [§5.4, Lemma 5.13, ordinary case] There is a sign inconsistency in the uniformization construction. The definitions state A_g[i,k] = A[i,k] + s_{i,g}, B_h[k,j] = B[k,j] + t_{j,h}, and C_{g,h}[i,j] = C[i,j] + s_{i,g} + t_{j,h}, which does preserve exact triangles. But the uniformity claim immediately after reads 'A_g[i,k] = A[i,k] − s_{i,g} ∈ X_{i,g} − s_{i,g} ⊆ S_g'. With the plus definitions, each A_g entry lies in X_{i,g} + s_{i,g} ⊆ 2s_{i,g} + S_g, and the union over i of these shifted sets need not have size O(d). Therefore the assertion that the constructed instances are d-uniform is not established. The intended construction is presumably A_g = A − s, B_h = B − t, C_{g,h} = C − s − t, and the text should be corrected accordingly.
  3. [§5.4, Lemma 5.13, Step 1.2] The popular exceptional case contains a condition that contradicts the running-time analysis. The text says 'we enumerate all (i,j) ∈ [n]^2 with C[i,j] ∉ P_{i,j}' immediately after defining popular exact triangles by C[i,j] ∈ P_{i,j}. The bound O(n^3/∆) that follows is valid only when enumerating the popular pairs, because Property (2) of Lemma 3.3 bounds the number of pairs with nonempty P_{i,j}. This is presumably a typo ('∉' should be '∈'), but as written the analysis of the popular case is not justified.
minor comments (4)
  1. [§4.3, Step 3] The text says 'We compute a size-O(n log n/2^L) hitting set H of P', but the set P is not defined at that point; it should read 'of Q', the set of paths constructed in Step 2.
  2. [§5.4, Step 2.1] In the unpopular ordinary case, the phrase 'all representations C_{g,h}[i,j] = a+b for (a,b) ∈ S_j × T_j' should presumably be 'S_g × T_h'; the row/column indices j and h are mixed, which makes the statement hard to parse.
  3. [§5.5, Algorithm 1] In the base case 'If d = 0 then stop', it would be helpful to state explicitly that this is correct because the d-weights promise implies that at least one of the matrices has no non-⊥ entries, so no exact triangle can exist.
  4. [§3.2 and §5.3] The quantitative claims depend on the exact constants and exponents in the quoted BSG Covering theorem (Theorem 3.1). Since the theorem is quoted rather than re-proved, the paper should at least point to the exact statement in [CL15] that yields the displayed bounds, so that the reader can verify the constants are not weaker than needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; central results are constructively derived from external theorems.

full rationale

The paper's main theorems are proved by explicit reductions and algorithm design, with no fitted parameters. The few-weights algorithm depends on the Balog-Szemeredi-Gowers covering theorem (Theorem 3.1, quoted from [CL15]) and fast matrix multiplication, both external to this paper, and the parameter choices in Lemmas 3.2 and 5.15 balance the displayed running-time terms rather than recreating the output. The deterministic approximation of popular sums invokes [FJX25], a published result by two of the current authors; it is used as a subroutine and is not a restatement of the paper's target theorems, so it is a normal self-citation rather than load-bearing circularity. The Node-Weighted APSP algorithm in Section 4 is self-contained given the Boolean min-plus product lemma. No step was found where a quantity called a prediction is defined from the target result, nor where a hypothesis or parameter is fitted to the data being derived. The closing parameter selection in the proof of Theorem 1.5 has an apparent quantitative issue (Delta = n^{2 - c/epsilon} can be less than 1 for small delta), but that is a correctness concern about the manuscript as written, not evidence that the derivation reduces to its own inputs.

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

The central algorithmic claims rely on standard external theorems (BSG covering, fast matrix multiplication, FFT polynomial multiplication, prime number theorem) and on clearly stated domain assumptions (integer polynomially bounded weights, word-RAM). No free parameters are fitted to data, and no new entities are invented. The conditional hardness results add the Bounded Min-Plus Product hypothesis as an explicitly labeled assumption.

assumptions (7)
  • standard math Balog-Szemerédi-Gowers covering theorem (Theorem 3.1) with quantitative bounds |X_k+Y_k|<=O(K^5 d) and |R|<=O(d^2/K), as stated in [CL15]
    The Few-Weights algorithm (Lemma 3.2) chooses K=(n^{3-omega}/d)^{1/7} based on these bounds; the subcubic time guarantee depends on them. The theorem is cited, not proved in the paper.
  • standard math Fast matrix multiplication algorithms with exponent omega<=2.371339 and rectangular exponents omega(a,b,c) as used (e.g., [ADV+25])
    The running time bounds (e.g., Õ(n^{(3+omega)/2})) are stated in terms of omega and rectangular multiplication exponents.
  • standard math Deterministic almost-linear almost-perfect hashing (Lemma 5.7), proved via the Prime Number Theorem
    Used in the small-doubling Exact Triangle algorithm (Lemma 5.5) to isolate sums; the proof relies on the quantitative Prime Number Theorem [RS62].
  • standard math Polynomial multiplication via FFT (Lemma 5.6, [AGM97])
    Used in Lemma 5.5 to multiply matrices of univariate polynomials in time Õ(n^omega d).
  • domain assumption Integer edge weights in {-M,...,M} with M=n^c for a constant c (stated in Section 2 and Definition 1.1)
    All theorems assume polynomially bounded integer weights; without this, some reductions (e.g., Lemma 5.4) would not have the claimed log-depth.
  • domain assumption Word-RAM model with O(log n)-bit words (stated in Section 2)
    Standard model for the complexity bounds; the paper explicitly assumes it.
  • domain assumption Bounded Min-Plus Product Hypothesis and u-dir-APSP Hypothesis (used only for lower bounds, Section 6)
    The conditional hardness results (Theorem 1.6, Theorem 6.5) rely on these hypotheses; they are clearly labeled as hypotheses and do not affect the algorithmic upper bounds.

how reviews work

0 comments
Cite this review

Pith. "Pith review of All-Pairs Shortest Paths with Few Weights per Node." pith.science (2026). https://pith.science/paper/QDZ2ALGG

@misc{pith2026250620017,
  author       = {Pith},
  title        = {Pith review of: All-Pairs Shortest Paths with Few Weights per Node},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QDZ2ALGG}},
  note         = {Machine review of arXiv:2506.20017}
}
abstract

We study the central All-Pairs Shortest Paths (APSP) problem under the restriction that there are at most $d$ distinct weights on the outgoing edges from every node. For $d=n$ this is the classical (unrestricted) APSP problem that is hypothesized to require cubic time $n^{3-o(1)}$, and at the other extreme, for $d=1$, it is equivalent to the Node-Weighted APSP problem. We present new algorithms that achieve the following results: 1. Node-Weighted APSP can be solved in time $\tilde{O}(n^{(3+\omega)/2}) = \tilde{O}(n^{2.686})$, improving on the 15-year-old subcubic bounds $\tilde{O}(n^{(9+\omega)/4}) = \tilde{O}(n^{2.843})$ [Chan; STOC '07] and $\tilde{O}(n^{2.830})$ [Yuster; SODA '09]. This positively resolves the question of whether Node-Weighted APSP is an ``intermediate'' problem in the sense of having complexity $n^{2.5+o(1)}$ if $\omega=2$, in which case it also matches an $n^{2.5-o(1)}$ conditional lower bound. 2. For up to $d \leq n^{3-\omega-\epsilon}$ distinct weights per node (where $\epsilon > 0$), the problem can be solved in subcubic time $O(n^{3-f(\epsilon)})$ (where $f(\epsilon) > 0$). In particular, assuming that $\omega = 2$, we can tolerate any sublinear number of distinct weights per node $d \leq n^{1-\epsilon}$, whereas previous work [Yuster; SODA '09] could only handle $d \leq n^{1/2-\epsilon}$ in subcubic time. This promotes our understanding of the APSP hypothesis showing that the hardest instances must exhaust a linear number of weights per node. Our result also applies to the All-Pairs Exact Triangle problem, thus generalizing a result of Chan and Lewenstein on "Clustered 3SUM" from arrays to matrices. Notably, our technique constitutes a rare application of additive combinatorics in graph algorithms.

Figures

Figures reproduced from arXiv: 2506.20017 by the authors.

Figure 2
Figure 2. Our reduction from (n, n1/2+ϵ , n | n 1/2+ϵ )-Min Plus Product to directed APSP with n 2ϵ distinct weights. Let q = ⌈n 1/2−ϵ ⌉. For any integer x ∈ [0, n1/2+ϵ ) we can represent it as x = x1 · q + x2 where x2 = x mod q ∈ {0, . . . , q −1} and x1 = ⌊x/q⌋ ∈ {0, . . . , n2ϵ −1}. We define four matrices A′ , A′′, B, B′′ as follows, for all i, j ∈ [n], k ∈ [n 1/2+ϵ ]: A ′ [i, k] = q ·  A[i, k] q  , A′′[i, k] = A[i, k] … view at source ↗
Figure 3
Figure 3. Our reduction from d-column weight (n, n/d)-Min-Plus Product to node-weighted APSP. • J has a node j for every column j of B, with weight 0. • K1 has a node (k, z) with weight z for every pair k ∈ [n x ], z ∈ A(k). • K2 has a node (k, y) with weight y for every pair k ∈ [n x ], y ∈ B(k). Every layer has ≤ n nodes by construction. The edges are as follows: • For every k ∈ [n x ] and every z ∈ A(k), y ∈ B(k), add an e… view at source ↗

Review history (2 revisions) →

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. TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability

    cs.CL 2026-08 reject novelty 7.0 of 10

    The paper introduces TCS-Bench, a 300-task proof-generation benchmark from top TCS papers, and reports frontier LLM accuracies from 30% to 68% using an automated verifier.

Reference graph

Works this paper leans on

56 extracted references · 17 canonical work pages · cited by 1 Pith paper

  1. [1]

    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 36th ACM-SIAM Symposium on Discrete Algorithms ( SODA 2025) . SIAM , 2025. To appear. URL: https://arxiv.org/abs/2404.16349

    arXiv 2025

  2. [2]

    On the exponent of the all pairs shortest path problem

    Noga Alon, Zvi Galil, and Oded Margalit. On the exponent of the all pairs shortest path problem. J. Comput. Syst. Sci. , 54(2):255--262, 1997. https://doi.org/10.1006/JCSS.1997.1388 doi:10.1006/JCSS.1997.1388

    arXiv 1997

  3. [3]

    Subcubic equivalences between graph centrality problems, apsp, and diameter

    Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams . Subcubic equivalences between graph centrality problems, apsp, and diameter. ACM Trans. Algorithms , 19(1):3:1--3:30, 2023. https://doi.org/10.1145/3563393 doi:10.1145/3563393

    work page doi:10.1145/3563393 2023

  4. [4]

    New algorithms and lower bounds for all-pairs max-flow in undirected graphs

    Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. New algorithms and lower bounds for all-pairs max-flow in undirected graphs. Theory Comput. , 17:1--27, 2021. URL: https://theoryofcomputing.org/articles/v017a005/

    work page 2021

  5. [5]

    Andrew Arnold and Daniel S. Roche. Output-sensitive algorithms for sumset and sparse polynomial multiplication. In Kazuhiro Yokoyama, Steve Linton, and Daniel Robertz, editors, 40th International Symposium on Symbolic and Algebraic Computation ( ISSAC 2015) , pages 29--36. ACM , 2015. https://doi.org/10.1145/2755996.2756653 doi:10.1145/2755996.2756653

    arXiv 2015

  6. [6]

    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 Annual IEEE Symposium on Foundations of Computer Science ( FOCS 2014) , pages 434--443. IEEE Computer Society, 2014. https://doi.org/10.1109/FOCS.2014.53 doi:10.1109/FOCS.2014.53

    doi:10.1109/focs.2014.53 2014

  7. [7]

    Matching triangles and basing hardness on an extremely popular conjecture

    Amir Abboud, Virginia Vassilevska Williams , and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. SIAM J. Comput. , 47(3):1098--1122, 2018. https://doi.org/10.1137/15M1050987 doi:10.1137/15M1050987

    work page doi:10.1137/15m1050987 2018

  8. [8]

    Negative-weight single-source shortest paths in near-linear time: Now faster! In 64th IEEE Annual Symposium on Foundations of Computer Science ( FOCS 2023) , pages 515--538

    Karl Bringmann, Alejandro Cassis, and Nick Fischer. Negative-weight single-source shortest paths in near-linear time: Now faster! In 64th IEEE Annual Symposium on Foundations of Computer Science ( FOCS 2023) , pages 515--538. IEEE , 2023. https://doi.org/10.1109/FOCS57990.2023.00038 doi:10.1109/FOCS57990.2023.00038

    arXiv 2023

Show all 56 references
  1. [9]

    Sparse nonnegative convolution is equivalent to dense nonnegative convolution

    Karl Bringmann, Nick Fischer, and Vasileios Nakos. Sparse nonnegative convolution is equivalent to dense nonnegative convolution. In 53rd Annual ACM Symposium on Theory of Computing ( STOC 2021) , pages 1711--1724. ACM , 2021. https://doi.org/10.1145/3406325.3451090 doi:10.114...

    2021

  2. [10]

    Deterministic and las vegas algorithms for sparse nonnegative convolution

    Karl Bringmann, Nick Fischer, and Vasileios Nakos. Deterministic and las vegas algorithms for sparse nonnegative convolution. In Joseph (Seffi) Naor and Niv Buchbinder, editors, 33th ACM-SIAM Symposium on Discrete Algorithms ( SODA 2022) , pages 3069--3090. SIAM , 2022. https:...

    2022 doi

  3. [11]

    Tree edit distance cannot be computed in strongly subcubic time (unless APSP can)

    Karl Bringmann, Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Tree edit distance cannot be computed in strongly subcubic time (unless APSP can). ACM Trans. Algorithms , 16(4):48:1--48:22, 2020. https://doi.org/10.1145/3381878 doi:10.1145/3381878

    2020 doi

  4. [12]

    Truly sub-cubic algorithms for language edit distance and rna-folding via fast bounded-difference min-plus product

    Karl Bringmann, Fabrizio Grandoni, Barna Saha, and Virginia Vassilevska Williams . Truly sub-cubic algorithms for language edit distance and rna-folding via fast bounded-difference min-plus product. In Irit Dinur, editor, 57th Annual IEEE Symposium on Foundations of Computer S...

    2016 doi

  5. [13]

    Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product

    Karl Bringmann, Fabrizio Grandoni, Barna Saha, and Virginia Vassilevska Williams . Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product. SIAM J. Comput. , 48(2):481--512, 2019. https://doi.org/10.1137/17M112720X doi:...

    2019 doi

  6. [15]

    The complexity of partial derivatives

    Walter Baur and Volker Strassen. The complexity of partial derivatives. Theor. Comput. Sci. , 22:317--330, 1983. https://doi.org/10.1016/0304-3975(83)90110-X doi:10.1016/0304-3975(83)90110-X

    1983 doi

  7. [16]

    A statistical theorem of set addition

    Antal Balog and Endre Szemerédi. A statistical theorem of set addition. Combinatorica , 14:263--268, 1994. URL: https://doi.org/10.1007/BF01212974

    1994 doi

  8. [17]

    Improving viterbi is hard: Better runtimes imply faster clique algorithms

    Arturs Backurs and Christos Tzamos. Improving viterbi is hard: Better runtimes imply faster clique algorithms. In Doina Precup and Yee Whye Teh, editors, 34th International Conference on Machine Learning ( ICML 2017) , volume 70 of Proceedings of Machine Learning Research , pa...

    2017

  9. [18]

    Faster algorithms for bounded-difference min-plus product

    Shucheng Chi, Ran Duan, and Tianle Xie. Faster algorithms for bounded-difference min-plus product. In 33th ACM-SIAM Symposium on Discrete Algorithms ( SODA 2022) , pages 1435--1447. SIAM , 2022. https://doi.org/10.1137/1.9781611977073.60 doi:10.1137/1.9781611977073.60

    2022 doi

  10. [19]

    Faster min-plus product for monotone instances

    Shucheng Chi, Ran Duan, Tianle Xie, and Tianyi Zhang. Faster min-plus product for monotone instances. In Stefano Leonardi and Anupam Gupta, editors, 54th Annual ACM Symposium on Theory of Computing ( STOC 2022) , pages 1529--1542. ACM , 2022. https://doi.org/10.1145/3519935.35...

    2022

  11. [20]

    Verifying candidate matches in sparse and wildcard matching

    Richard Cole and Ramesh Hariharan. Verifying candidate matches in sparse and wildcard matching. In John H. Reif, editor, 34th Annual ACM Symposium on Theory of Computing ( STOC 2002) , pages 592--601. ACM , 2002. https://doi.org/10.1145/509907.509992 doi:10.1145/509907.509992

    2002

  12. [21]

    Timothy M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput. , 39(5):2075--2089, 2010. https://doi.org/10.1137/08071990X doi:10.1137/08071990X

    2010 doi

  13. [22]

    A greedy heuristic for the set-covering problem

    Vasek Chv \' a tal. A greedy heuristic for the set-covering problem. Math. Oper. Res. , 4(3):233--235, 1979. URL: https://doi.org/10.1287/moor.4.3.233, https://doi.org/10.1287/MOOR.4.3.233 doi:10.1287/MOOR.4.3.233

    1979 doi

  14. [23]

    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. https://doi.org/10.1137/070695149 doi:10.1137/070695149

    2009 doi

  15. [24]

    Chan and Moshe Lewenstein

    Timothy M. Chan and Moshe Lewenstein. Clustered integer 3sum via additive combinatorics. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th Annual ACM on Symposium on Theory of Computing ( STOC 2015) , pages 31--40. ACM , 2015. https://doi.org/10.1145/2746539.2746568 doi...

    2015

  16. [25]

    Chan, Virginia Vassilevska Williams , and Yinzhan Xu

    Timothy M. Chan, Virginia Vassilevska Williams , and Yinzhan Xu. Algorithms, reductions and equivalences for small weight variants of all-pairs shortest paths. In 48th International Colloquium on Automata, Languages, and Programming ( ICALP 2021) , volume 198 of LIPIcs , pages...

    2021 doi

  17. [26]

    Chan, Virginia Vassilevska Williams , and Yinzhan Xu

    Timothy M. Chan, Virginia Vassilevska Williams , and Yinzhan Xu. Fredman's trick meets dominance product: Fine-grained complexity of unweighted apsp, 3sum counting, and more. In Barna Saha and Rocco A. Servedio, editors, 55th Annual ACM Symposium on Theory of Computing ( STOC ...

    2023

  18. [27]

    Faster algorithms for dual-failure replacement paths

    Shiri Chechik and Tianyi Zhang. Faster algorithms for dual-failure replacement paths. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming ( ICALP 2024) , volume 297 of LIPIcs , pages...

    2024 doi

  19. [28]

    Faster algorithms for all pairs non-decreasing paths problem

    Ran Duan, Ce Jin, and Hongxun Wu. Faster algorithms for all pairs non-decreasing paths problem. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming ( ICALP 2019) , vol...

    2019 doi

  20. [29]

    Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths

    Ran Duan and Seth Pettie. Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. In Claire Mathieu, editor, 20th Annual ACM-SIAM Symposium on Discrete Algorithms ( SODA 2009) , pages 384--391. SIAM , 2009. https://doi.org/10.1137/1.9781611973068.43...

    2009 doi

  21. [30]

    Improved bounds for rectangular monotone min-plus product and applications

    Anita D \" u rr. Improved bounds for rectangular monotone min-plus product and applications. Inf. Process. Lett. , 181:106358, 2023. URL: https://doi.org/10.1016/j.ipl.2023.106358, https://doi.org/10.1016/J.IPL.2023.106358 doi:10.1016/J.IPL.2023.106358

    2023

  22. [31]

    Deterministic sparse pattern matching via the Baur - Strassen theorem

    Nick Fischer. Deterministic sparse pattern matching via the Baur - Strassen theorem. In David P. Woodruff, editor, 35th ACM-SIAM Symposium on Discrete Algorithms ( SODA 2024) , pages 3333--3353. SIAM , 2024. https://doi.org/10.1137/1.9781611977912.119 doi:10.1137/1.9781611977912.119

    2024 doi

  23. [32]

    New applications of 3SUM -counting in fine-grained complexity and pattern matching

    Nick Fischer, Ce Jin, and Yinzhan Xu. New applications of 3SUM -counting in fine-grained complexity and pattern matching. In 36th ACM-SIAM Symposium on Discrete Algorithms ( SODA 2025) . SIAM , 2025. To appear. URL: https://arxiv.org/abs/2410.20764

    2025 arXiv

  24. [33]

    Fischer and Albert R

    Michael J. Fischer and Albert R. Meyer. Boolean matrix multiplication and transitive closure. In 12th Annual Symposium on Switching and Automata Theory ( SWAT 1971) , pages 129--131. IEEE Computer Society, 1971. https://doi.org/10.1109/SWAT.1971.4 doi:10.1109/SWAT.1971.4

    1971 doi

  25. [34]

    Essentially optimal sparse polynomial multiplication

    Pascal Giorgi, Bruno Grenet, and Armelle Perret du Cray. Essentially optimal sparse polynomial multiplication. In Ioannis Z. Emiris and Lihong Zhi, editors, 45th International Symposium on Symbolic and Algebraic Computation ( ISSAC 2020) , pages 202--209. ACM , 2020. https://d...

    2020

  26. [35]

    Timothy W. Gowers. A new proof of Szemerédi 's theorem. GAFA Geometric And Functional Analysis , 11:465--588, 08 2001. https://doi.org/10.1007/s00039-001-0332-9 doi:10.1007/s00039-001-0332-9

    2001 doi

  27. [36]

    Flow trees for vertex-capacitated networks

    Refael Hassin and Asaf Levin. Flow trees for vertex-capacitated networks. Discret. Appl. Math. , 155(4):572--578, 2007. URL: https://doi.org/10.1016/j.dam.2006.08.012, https://doi.org/10.1016/J.DAM.2006.08.012 doi:10.1016/J.DAM.2006.08.012

    2007 doi

  28. [37]

    Monika Rauch Henzinger, Satish Rao, and Harold N. Gabow. Computing vertex connectivity: New bounds from old techniques. J. Algorithms , 34(2):222--250, 2000. URL: https://doi.org/10.1006/jagm.1999.1055, https://doi.org/10.1006/JAGM.1999.1055 doi:10.1006/JAGM.1999.1055

  29. [38]

    Shaving logs via large sieve inequality: Faster algorithms for sparse convolution and more

    Ce Jin and Yinzhan Xu. Shaving logs via large sieve inequality: Faster algorithms for sparse convolution and more. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, 56th Annual ACM Symposium on Theory of Computing ( STOC 2024) , pages 1573--1584. ACM , 2024. https://d...

    2024

  30. [39]

    LCA queries in directed acyclic graphs

    Miroslaw Kowaluk and Andrzej Lingas. LCA queries in directed acyclic graphs. In Lu \' s Caires, Giuseppe F. Italiano, Lu \' s Monteiro, Catuscia Palamidessi, and Moti Yung, editors, 32nd International Colloquium on Automata, Languages and Programming ( ICALP 2005) , volume 358...

    2005 doi

  31. [40]

    3SUM in preprocessed universes: Faster and simpler

    Shashwat Kasliwal, Adam Polak, and Pratyush Sharma. 3SUM in preprocessed universes: Faster and simpler. In 8th Symposium on Simplicity in Algorithms ( SOSA 2025) . SIAM , 2025. To appear. URL: https://arxiv.org/abs/2410.16784

    2025

  32. [41]

    On the ratio of optimal integral and fractional covers

    L \' a szl \' o Lov \' a sz. On the ratio of optimal integral and fractional covers. Discret. Math. , 13(4):383--390, 1975. https://doi.org/10.1016/0012-365X(75)90058-8 doi:10.1016/0012-365X(75)90058-8

    1975 doi

  33. [42]

    Monochromatic triangles, intermediate matrix products, and convolutions

    Andrea Lincoln, Adam Polak, and Virginia Vassilevska Williams . Monochromatic triangles, intermediate matrix products, and convolutions. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference ( ITCS 2020) , volume 151 of LIPIcs , pages 53:1--53:1...

    2020 doi

  34. [43]

    Computing dominances in e \^ n

    Jir \' Matousek. Computing dominances in e \^ n. Inf. Process. Lett. , 38(5):277--278, 1991. https://doi.org/10.1016/0020-0190(91)90071-O doi:10.1016/0020-0190(91)90071-O

    1991 doi

  35. [44]

    Nearly optimal sparse polynomial multiplication

    Vasileios Nakos. Nearly optimal sparse polynomial multiplication. IEEE Trans. Inf. Theory , 66(11):7231--7236, 2020. https://doi.org/10.1109/TIT.2020.2989385 doi:10.1109/TIT.2020.2989385

    2020

  36. [45]

    Barkley Rosser and Lowell Schoenfeld

    J. Barkley Rosser and Lowell Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois Journal of Mathematics , 6(1):64--94, 1962. https://doi.org/10.1215/ijm/1255631807 doi:10.1215/ijm/1255631807

    1962

  37. [46]

    Language edit distance and maximum likelihood parsing of stochastic grammars: Faster algorithms and connection to fundamental graph problems

    Barna Saha. Language edit distance and maximum likelihood parsing of stochastic grammars: Faster algorithms and connection to fundamental graph problems. In Venkatesan Guruswami, editor, 56th Annual IEEE Symposium on Foundations of Computer Science ( FOCS 2015) , pages 118--13...

    2015 doi

  38. [47]

    On the all-pairs-shortest-path problem in unweighted undirected graphs

    Raimund Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci. , 51(3):400--403, 1995. URL: https://doi.org/10.1006/jcss.1995.1078, https://doi.org/10.1006/JCSS.1995.1078 doi:10.1006/JCSS.1995.1078

    1995

  39. [48]

    All pairs shortest paths in undirected graphs with integer weights

    Avi Shoshan and Uri Zwick. All pairs shortest paths in undirected graphs with integer weights. In 40th Annual IEEE Symposium on Foundations of Computer Science ( FOCS 1999) , pages 605--615. IEEE Computer Society, 1999. https://doi.org/10.1109/SFFCS.1999.814635 doi:10.1109/SFF...

    1999

  40. [49]

    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 ( ICM 2018) , pages 3447--3487, 2018. https://doi.org/10.1142/9789813272880_0188 doi:10.1142/9789813272880_0188

    2018 doi

  41. [50]

    Finding a maximum weight triangle in n\( ^ 3-delta \) time, with applications

    Virginia Vassilevska and Ryan Williams. Finding a maximum weight triangle in n\( ^ 3-delta \) time, with applications. In Jon M. Kleinberg, editor, 38th Annual ACM Symposium on Theory of Computing ( STOC 2006) , pages 225--231. ACM , 2006. https://doi.org/10.1145/1132516.11325...

    2006

  42. [51]

    Ryan Williams

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

    2013 doi

  43. [52]

    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. https://doi.org/10.1145/3186893 doi:10.1145/3186893

    2018 doi

  44. [53]

    Algorithms and lower bounds for replacement paths under multiple edge failure

    Virginia Vassilevska Williams , Eyob Woldeghebriel, and Yinzhan Xu. Algorithms and lower bounds for replacement paths under multiple edge failure. In 63rd IEEE Annual Symposium on Foundations of Computer Science ( FOCS 2022) , pages 907--918. IEEE , 2022. https://doi.org/10.11...

    2022

  45. [54]

    All pairs bottleneck paths and max-min matrix products in truly subcubic time

    Virginia Vassilevska, Ryan Williams, and Raphael Yuster. All pairs bottleneck paths and max-min matrix products in truly subcubic time. Theory Comput. , 5(1):173--189, 2009. URL: https://doi.org/10.4086/toc.2009.v005a009, https://doi.org/10.4086/TOC.2009.V005A009 doi:10.4086/T...

    2009 doi

  46. [55]

    Truly subcubic min-plus product for less structured matrices, with applications

    Virginia Vassilevska Williams and Yinzhan Xu. Truly subcubic min-plus product for less structured matrices, with applications. In 31st ACM-SIAM Symposium on Discrete Algorithms ( SODA 2020) , pages 12--29. SIAM , 2020. https://doi.org/10.1137/1.9781611975994.2 doi:10.1137/1.97...

    2020 doi

  47. [56]

    Efficient algorithms on sets of permutations, dominance, and real-weighted APSP

    Raphael Yuster. Efficient algorithms on sets of permutations, dominance, and real-weighted APSP . In Claire Mathieu, editor, 20th Annual ACM-SIAM Symposium on Discrete Algorithms ( SODA 2009) , pages 950--957. SIAM , 2009. https://doi.org/10.1137/1.9781611973068.103 doi:10.113...

    2009 doi

  48. [57]

    All pairs shortest paths using bridging sets and rectangular matrix multiplication

    Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM , 49(3):289--317, 2002. https://doi.org/10.1145/567112.567114 doi:10.1145/567112.567114

    2002

Pith tools

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