Pith.

Data Structures and Algorithms · arXiv:2610.42012 v1 · submitted 30 Oct 2026 · 55 references

3SUM Made Simpler (Without Matrix Multiplication), k-SUM Hypothesis Refuted for Odd k, and Real 3SUM/APSP Derandomized

Timothy M. Chan, Reina Itakura, Zhiyuan Ma, Yuancheng Yu

The paper says

“Recently, a truly subquadratic algorithm for the 3SUM problem and a truly subcubic algorithm for the all-pairs shortest paths (APSP) problem were found by Anthropic, as reported by Alman and Vassilevska Williams (2026).”

more of the abstract

These algorithms relied on a new subroutine for rectangular matrix multiplication with selected output entries, which was obtained by modifying known matrix multiplication techniques of Schönhage (1981) and Coppersmith (1982). 1. We present a different truly subquadratic randomized algorithm for 3SUM for integer inputs. It completely avoids the use of matrix multiplication but instead modifies known dynamic programming algorithms for subset convolution and the zeta transform, which rely only on simple subtraction tricks via inclusion–exclusion (and does not even require fast Fourier transform), and so is conceptually easier to understand (the whole solution is about 5 pages long). 2. Following a similar approach, we obtain a randomized algorithm for k-SUM for integer inputs for odd constant k in $O(n^{\lceil k/2\rceil-\varepsilon_k})$ time for some constant εk > 0, disproving the k-SUM Hypothesis for all odd k. 3. Existing reductions from 3SUM and APSP to selected-entries rectangular matrix multiplication were randomized in the case of real-valued input. We present new deterministic reductions, yielding a truly subquadratic deterministic algorithm for Real 3SUM and a truly subcubic deterministic algorithm for Real APSP.

from the abstract

Pith says

Machine review · deepseek-v4-flash · 2 Nov 2026 · what was read was not recorded · not checked by a person

It can be wrong. Challenge this review or reply to it.

The passes disagreed. Reader: holds up. Skeptic: holds up only with conditions. Referee: major revision.

A clearly written paper with a genuinely new matrix-multiplication-free 3SUM algorithm, a surprising odd-k k-SUM refutation, and deterministic real reductions whose corollaries depend on quoted companion bounds that deserve an exponent check before acceptance. This line is wrong

2 major objections · 3 minor

How often objections from reviews like this one are right: not yet measured

Are you an author? What you can do.

Not checked: figures, code, what the 55 references say.

The paper says, at Corollary 5.10

The review did not quote this passage.

Pith says: Objection 1 of 2 · major

The numerical substitution in Corollary 5.10 does not satisfy the hypothesis of the quoted selected-entries bound. With delta=0.050534 and d=n^0.0046983, the middle dimension in the call M_selected-entries(n, d^{12+2delta}, n | n^2/d^{1+delta}) is d^{12+2delta}=n^{0.05685445}, which exceeds the quoted condition d<=n^{0.056853} from [AW26, Corollary 31].

more of objection 1

The corollary is therefore not established as written. Lowering the exponent of d to approximately 0.00469818 appears to restore the condition while still giving O(n^1.9998), but the authors should recompute the substitution, report exact parameter values, and verify that all three terms in the bound remain O(n^1.9998).

The paper says, at Sections 4.2-5.2 (Theorems 4.8, 5.9; Corollaries 4.9, 5.10)

The review did not quote this passage.

Pith says: Objection 2 of 2 · major

The claimed deterministic exponents 2.9997 and 1.9998 are derived solely by substituting two numerical selected-entries bounds quoted from [AW26], an unpublished arXiv preprint, and the manuscript supplies no proof or independent verification of those bounds. This dependency is load-bearing because Corollaries 4.9 and 5.10 are the only places where the deterministic claims acquire their numerical form, and the bound is used outside its stated range in Corollary 5.10.

more of objection 2

The authors should quote the exact theorem statements and hypotheses from [AW26] used here, verify the parameter ranges, and either include a proof of the needed selected-entries bounds in an appendix or, if the venue permits reliance on preprints, state that dependency explicitly and accurately.

3 minor objections

The paper says, at Theorem 2.3

Pith says: minor objection 1 of 3

The displayed time bound appears to contain a typo: the terms written as N * nhat * 2^t and |C| * nhat * 2^t should presumably be N * nhat / 2^t and |C| * nhat / 2^t. The proof text derives N * nhat / 2^t after the choice p0=2^d, and Corollary 2.4 is consistent only with the divided form. Please correct the display.

The paper says, at Corollary 3.6

Pith says: minor objection 2 of 3

The statement that epsilon_k = 2^{-Theta(k)} requires choosing the small constant epsilon in Corollary 3.5 to depend on k as roughly 2^{-Theta(k)} times a sufficiently large constant factor; if epsilon is instead viewed as a fixed absolute constant, the saving in the final k-SUM exponent is Theta(k), not 2^{-Theta(k)}. State the intended choice of epsilon explicitly so the claimed dependence on k is derivable from the proof.

show 1 more

The paper says, at Section 5.2, Theorem 5.9

Pith says: minor objection 3 of 3

The quoted source [AW26, Corollary 31 with c=21 and theta=0.0145] is cited with parameters c and theta that are not defined in this manuscript. Since the numerical conclusion depends on the exact domain of those parameters, please define them or quote the source's statement in full.

What would settle it

Recompute Corollary 5.10 from Theorem 5.9 using the exact statement of [AW26, Corollary 31]: verify the quoted hypotheses (especially d≤n^{0.056853} and the w-dependence) and check whether d=n^{0.0046983} with δ=0.050534 satisfies d^{12+2δ}≤n^{0.056853}; note it evaluates to n^{0.05685445}, slightly over. Lower d to about 0.00469818 to restore compliance and confirm the final exponent remains below 2. Then perform the analogous substitution for Corollary 4.9 against [AW26, Table 2]. If both checks match the source's stated parameter regimes, the concern is resolved.

from the skeptic's reading

How the review went

4 readings by deepseek-v4-flash · 2 Nov 2026

  1. Reader holds up confidence moderate
  2. Skeptic partly agrees: says it holds up only with conditions 13 min 45 s · 28,195 tokens read, 53,698 written Real 3SUM/APSP derandomization rests on quoted [AW26] selected-entries bounds; Corollary 5.10's numeric substitution may fall slightly outside the cited d-range, so the deterministic exponents need an independent check.
  3. Editor wrote the verdict above 1 min 24 s · 29,155 tokens read, 11,688 written
  4. Referee major revision: 2 major objections, 3 minor 3 min 51 s · 28,633 tokens read, 27,935 written

Not run on this paper: the simulated authors' defence.

Pith did not check this review's objections against the paper.

The review in full

The review in brief, machine-written

Bottom line: this paper deserves a serious referee. The integer parts are solid and the paper is unusually readable; the deterministic parts are plausible but the numerical corollaries rest on bounds quoted from an unreviewed preprint, and one of them has a small parameter-range slip.

What is new: Section 2 gives a truly subquadratic integer 3SUM algorithm that avoids matrix multiplication entirely, using trimmed subset convolution (explicitly credited to BHKK10) together with a hashing reduction that I do not think exists elsewhere. The proof is complete enough to follow, with explicit probability bounds in equations (1) and (2), and the parameter choices are balancing decisions, not fitted constants. Section 3's base-r extension is the real surprise: it makes the query cost an arbitrarily small polynomial and yields the odd-k k-SUM refutation. That result would be major if the community accepts the randomized, polynomially bounded integer setting as the relevant formulation, and I saw no gap in the template.

The deterministic sections are clever and honestly presented. The dyadic-interval counting and halving reductions in Sections 4 and 5 are new, and the authors state the non-degeneracy assumption themselves. But Corollaries 4.9 and 5.10 inherit the selected-entries matrix multiplication trade-offs from AW26, an arXiv preprint, quoted rather than re-derived. That is a real dependency, and it is transparent: the paper says exactly which AW26 bounds it uses. If AW26 is treated as established, this is fine; if not, the deterministic exponents are only as solid as that companion. A referee should check the parameter arithmetic against AW26 rather than assume it.

One concrete slip, minor but worth fixing: in Corollary 5.10, with delta = 0.050534 and d = n0.0046983, the selected-entries middle dimension is d^(12+2delta) = n0.05685445, which is just over the quoted d <= n0.056853. Lowering d to about 0.00469818 restores the range and does not change the stated n1.9998 bound, so this is a boundary arithmetic issue, not a structural flaw.

Citation pattern is normal: the authors credit BHKK10, AW26, KL26 and prior reduction work; the self-citations are to building blocks, not to manufactured support. The paper is honest about what it does and does not prove.

Recommendation: send to peer review. Sections 2 and 3 should be accepted on their own; Sections 4 and 5 need an independent verification of the exponent calculations and the quoted AW26 trade-offs. The likely outcome is acceptance with small corrections.

The strongest objection

The load-bearing dependency is the selected-entries matrix-multiplication bound from [AW26], an unpublished arXiv preprint, quoted verbatim in Theorem 4.8 to Corollary 4.9 and Theorem 5.9 to Corollary 5.10. Those corollaries are the only place where the deterministic real claims acquire their numerical exponents; the paper supplies no proof or independent derivation of the quoted n^2/d^{0.0112} + w d^{0.10} and n^2/d^{0.008352} + w d^{0.077647} trade-offs. A secondary red flag is in Corollary 5.10: with δ=0.050534 and d=n^{0.0046983}, the selected-entries dimension is d^{12+2δ}=n^{0.05685445}, slightly above the quoted d≤n^{0.056853}; lowering d to about 0.00469818 fixes it, but the margins are tight enough that the exponent arithmetic should be recomputed from the source's exact statement. Sections 2 and 3 are self-contained and do not inherit this dependency.

The paper's Sections 2 and 3 are largely self-contained: the selected-entries subset-convolution DP and the base-r convolution reduction appear internally coherent, and the unbalanced 3SUM-to-k-SUM grouping is standard for the list formulation of k-SUM. The deterministic real claims, however, are conditional on the selected-entries bounds of [AW26], which is an arXiv preprint rather than a published source. Because the bounds are quoted with exact numerical exponents and then fed into further numeric tuning, an error in the source's hypotheses or in the quoted parameter range propagates directly into Corollaries 4.9 and 5.10. The small range violation in Corollary 5.10 (d^{12+2δ}≈n^{0.05685445} versus the quoted d≤n^{0.056853}) is fixable by lowering d slightly, but it shows the arithmetic was tuned at the edge of the stated regime, so an independent recomputation is warranted. I would not reject the paper: the conditional theorems stand, and the randomized 3SUM and odd-k k-SUM results do not depend on [AW26]. I would mark acceptance conditional on confirming the quoted selected-entries bounds and their applicability at the exact parameter settings used in the deterministic corollaries. The reader's weakest assumption points to the same dependency, but I would express it as a condition on acceptance rather than as a resolved medium-risk caveat.

The referee's report

If the quoted [AW26] bounds are correct, the deterministic results are a genuine advance: they are the first deterministic truly subquadratic and truly subcubic algorithms for Real 3SUM and Real APSP, and the reductions via low-average-rank interval search are elegant. More importantly, Sections 2 and 3 are self-contained and constitute a substantial conceptual simplification of the recent 3SUM breakthrough: the subset-convolution approach needs only inclusion-exclusion and dynamic programming, with explicit probability estimates in Equations (1) and (2), and the odd-k k-SUM extension is a new consequence not obtained by the matrix-multiplication route. The paper is careful about its own limitations, including the non-degeneracy assumption for real inputs and the Monte Carlo nature of the integer algorithm. The main weakness is that the deterministic corollaries depend entirely on numerical trade-offs from an unpublished preprint, and one of the two numerical substitutions appears to violate the cited hypothesis; this needs to be corrected and verified before the deterministic claims are fully established.

Pith's reading of the paper (a machine's summary, not the authors')

The paper's aim is to show that the recent breakthrough speedups for 3SUM and APSP rest on simpler machinery than the matrix-multiplication subroutine they were first announced with. Its central claim is that a trimmed version of the fast zeta transform — a dynamic program for subset convolution that computes only the entries asked for by the queries — combined with randomized hashing solves integer 3SUM in $O(n^{1.965})$ Monte Carlo time, using neither matrix multiplication nor even the fast Fourier transform. The same construction, run over base-$r$ digit vectors instead of bit vectors, yields $O(n^{\lceil k/2\rceil-\varepsilon_k})$-time algorithms for odd constant $k$-SUM, which the paper states as refuting the $k$-SUM Hypothesis for all odd $k$ in the integer, randomized setting. For real-valued inputs, the paper replaces the random sampling in prior reductions with deterministic counting over dyadic intervals and average-rank arguments, obtaining deterministic $O(n^{2.9997})$ Real APSP and $O(n^{1.9998})$ Real 3SUM, conditional on the selected-entries matrix multiplication bounds quoted from the cited work [AW26]. A curious reader would care because these are among the most studied problems in fine-grained complexity, and the paper's version of the algorithms is short enough to read in one sitting.

What carries the argument. The load-bearing object is selected-entries subset convolution: given weighted collections $A, B$ of $t$-subsets of $[d]$ and a collection $C$ of query $2t$-subsets, compute $(f \star g)(C) = \sum_{A \sqcup B = C} f(A) g(B)$ for exactly the queried sets. The paper solves this with a trimmed fast zeta transform: precompute zeta transforms over all subsets of size at most a threshold $s$, and for each query $C$ resume the dynamic program only on subsets of $C$ of size at least $s$; the inclusion–exclusion identity $(f \star_c g)(X) = \sum_{S \subseteq X} (-1)^{|X \setminus S|} \hat{f}(S)\hat{g}(S)$ for the covering product is what makes the continuation correct. The reduction from 3SUM hashes numbers modulo a random prime, reads each residue as a bit vector (a subset of digit positions), and uses 3-wise independent linear scrambling so that, across repetitions, the disjointness needed for subset convolution to detect exact sums holds with high probability. For $k$-SUM, the bit alphabet is replaced by base-$r$ vectors in $[r]^d$, where addition is carry-free more often and the query targets are 'perfectly balanced' vectors; the boosted success probability is driven by the constant $\rho = r^2/(r!)^{1/r}$, which grows linearly in $r$. For the deterministic real-input results, the central device is a counting problem solved by an average-rank invariant: over dyadic intervals of candidate indices, count how many entries lie below a pivot and sum their ranks; maintaining a low average rank lets the algorithm halve each search interval for $O(\log d)$ rounds, replacing random sampling entirely.

Core claim. On the paper's own terms, the discoveries are three. First, the All-Numbers 3SUM problem for polynomially bounded integers — decide for every query $c$ whether $c = a + b$ with $a \in A$, $b \in B$ — is solvable in $O(\hat{n}^{1.965} + N\hat{n}^{0.899} + |C|\hat{n}^{0.965})$ randomized time with $O(1/N)$ error, where $\hat{n} = \sqrt{|A||B|}$ and $N = |A| + |B|$; balanced inputs give $O(n^{1.965})$, improving the $O(n^{1.998})$ originally reported for the selected-entries matrix multiplication approach. Second, the same reduction with base-$r$ digit vectors gives, for every constant $k \ge 1$, a Monte Carlo algorithm for $(2k+1)$-SUM in $O(n^{k+1-\varepsilon_k})$ time with $\varepsilon_k = 2^{-\Theta(k)}$, which the paper reads as disproving the $k$-SUM Hypothesis for all odd $k$. Third, Real APSP and Real 3SUM have deterministic algorithms running in $O(n^{2.9997})$ and $O(n^{1.9998})$ respectively, obtained from new deterministic reductions to selected-entries rectangular matrix multiplication, and these are the first deterministic truly subcubic and truly subquadratic algorithms for the real-valued versions of the two problems.

The premise it rests on. The load-bearing premise is that the selected-entries rectangular matrix multiplication bounds quoted from the cited source [AW26] — $n^2/d^{0.0112} + w d^{0.10}$ for the APSP reduction and $n^2/d^{0.008352} + w d^{0.077647}$ for the 3SUM reduction — are correct and valid at the exact aspect ratios used here, in particular with $d \le n^{0.013843}$ and $d \le n^{0.0046983}$, since the deterministic Real APSP and Real 3SUM theorems do not prove those bounds themselves and also assume non-degenerate real inputs, a point the paper acknowledges.

If the paper is right (Pith's inferences, not the authors')

Integer 3SUM and All-Numbers 3SUM fall into randomized $O(n^{1.965})$ time, improving the $O(n^{1.998})$ of the original selected-entries matrix multiplication approach, and the algorithm is compact enough for a full presentation in about five pages.

The same construction doubles as a 3SUM Indexing data structure: preprocessing in $O(n^{1.965})$ time and space, then deciding whether a query number is in $A + B$ in $O(n^{0.965})$ time with low error probability.

The $k$-SUM Hypothesis fails for every odd constant $k$ (integer inputs, randomized allowed): $(2k+1)$-SUM runs in $O(n^{k+1-\varepsilon_k})$ time with $\varepsilon_k = 2^{-\Theta(k)}$.

By the known reduction to (min,+)-convolution, that problem inherits a simpler randomized truly subquadratic algorithm for polynomially bounded integers, together with its downstream applications.

Real-valued inputs lose the randomness: Real 3SUM in deterministic $O(n^{1.9998})$ and Real APSP in deterministic $O(n^{2.9997})$, the first deterministic truly subquadratic and truly subcubic algorithms for these real problems, assuming the quoted selected-entries matrix multiplication bounds.

The base-$r$ generalization looks like the reusable engine of the paper: because the success probability per trial scales with $\rho = r^2/(r!)^{1/r} = \Theta(r)$, the per-query cost can be driven to an arbitrarily small polynomial. A natural test of the mechanism is whether a different balance condition extends it to even $k$, which the paper leaves untouched.

The dyadic-interval average-rank scheme for replacing random sampling reads as a general desampling template: any randomized reduction that samples to produce candidate pivots for verification could plausibly be converted, so the same strategy may derandomize other sampling-based reductions, for instance for Exact Triangle.

The randomized integer results stand independently of the matrix multiplication literature, but the deterministic real results inherit their exponents from two quoted bounds; a better bound for selected-entries rectangular matrix multiplication would immediately improve Corollaries 4.9 and 5.10 by re-optimizing the two parameters $\delta$ and $d$.

The paper leaves the Monte Carlo status of its integer algorithms as is; converting the hashing to a deterministic small-bias construction would give fully deterministic truly subquadratic integer 3SUM, a step the authors flag as plausible but do not take.

Check this review

Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.

How often reviews like this one are right

Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.

How often objections from reviews like this one are right: not yet measured

Every value above, in the review's public record (JSON)

Reviews by people

This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.

Request a human review

How Pith checks papers · The full audit of this paper

The paper

Abstract

Recently, a truly subquadratic algorithm for the 3SUM problem and a truly subcubic algorithm for the all-pairs shortest paths (APSP) problem were found by Anthropic, as reported by Alman and Vassilevska Williams (2026). These algorithms relied on a new subroutine for rectangular matrix multiplication with selected output entries, which was obtained by modifying known matrix multiplication techniques of Schönhage (1981) and Coppersmith (1982). 1. We present a different truly subquadratic randomized algorithm for 3SUM for integer inputs. It completely avoids the use of matrix multiplication but instead modifies known dynamic programming algorithms for subset convolution and the zeta transform, which rely only on simple subtraction tricks via inclusion–exclusion (and does not even require fast Fourier transform), and so is conceptually easier to understand (the whole solution is about 5 pages long). 2. Following a similar approach, we obtain a randomized algorithm for k-SUM for integer inputs for odd constant k in $O(n^{\lceil k/2\rceil-\varepsilon_k})$ time for some constant εk > 0, disproving the k-SUM Hypothesis for all odd k. 3. Existing reductions from 3SUM and APSP to selected-entries rectangular matrix multiplication were randomized in the case of real-valued input. We present new deterministic reductions, yielding a truly subquadratic deterministic algorithm for Real 3SUM and a truly subcubic deterministic algorithm for Real APSP.

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.

abstract compiled · 2026-11-02

The authors' main claim, as the classifier picked it out 0.41

“We present a different truly subquadratic randomized algorithm for 3SUM for integer inputs.”

How the main claim is stated: asserted 1.00

What the abstract itself states, as probabilities: claims first 0.19 · states limitation 0.52 · human participants 0.02 · controlled comparison 0.08 · randomized assignment 0.07 · states quantitative result 0.95 · compares with prior results 0.97 · mentions code or data availability 0.02

The abstract, sentence by sentence

This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.

SentenceRoleThe authors' own workStates the main conclusionStrength
Recently, a truly subquadratic algorithm for the 3SUM problem and a truly subcubic algorithm for the all-pairs shortest paths (APSP) problem were found by Anthropic, as reported by Alman and Vassilevska Williams (2026). background 1.00 0.03 0.04 asserted 1.00
These algorithms relied on a new subroutine for rectangular matrix multiplication with selected output entries, which was obtained by modifying known matrix multiplication techniques of Sch\"onhage (1981) and Coppersmith (1982). 1. background 0.99 0.05 0.03 asserted 1.00
We present a different truly subquadratic randomized algorithm for 3SUM for integer inputs. contribution 0.97 0.95 0.38 asserted 1.00
It completely avoids the use of matrix multiplication but instead modifies known dynamic programming algorithms for subset convolution and the zeta transform, which rely only on simple subtraction tricks via inclusion--exclusion (and does not even require fast Fourier transform), and so is conceptually easier to understand (the whole solution is about 5 pages long). 2. method 0.76 0.94 0.26 asserted 1.00
Following a similar approach, we obtain a randomized algorithm for $k$-SUM for integer inputs for odd constant $k$ in $O(n^{\lceil k/2\rceil-\varepsilon_k})$ time for some constant $\varepsilon_k>0$, disproving the $k$-SUM Hypothesis for all odd $k$. 3. result 0.68 0.95 0.37 asserted 1.00
Existing reductions from 3SUM and APSP to selected-entries rectangular matrix multiplication were randomized in the case of real-valued input. gap 0.60 0.07 0.04 asserted 1.00
We present new deterministic reductions, yielding a truly subquadratic deterministic algorithm for Real 3SUM and a truly subcubic deterministic algorithm for Real APSP. contribution 0.79 0.95 0.28 asserted 1.00

What kind of paper the classifier reports this is: method or tool 0.73 · evidence from proof or derivation 0.98

What was examined, and what was not

Sources read

  • arXiv listing abstract v1

Not examined

  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers

Levels run

  • P abstract

Not run

  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

How the labels were made

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-02: 1 request, 5,966 input tokens.

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON

Figures (1)
Figure 1 of the paper
Figure 1. Known simple reductions [Pat10, BCD ˘ +14, VW18, CMWW19]. (The dashed ones are for integer input, unless one uses more complicated, recent techniques [FPS26].) We find a simpler way to obtain a truly subquadratic, Monte-Carlo randomized algorithm for 3SUM for polynomially bounded integer inputs. The key idea is to switch to a different but related problem, subset convolution (see Problem 2.1). Standard algorithms for subset convolution are based on the so-called zeta (or Möbius) transform, which is solved by simple dynamic programming (DP), using just subtraction or…

Figures are the authors', reproduced from the paper.

References (55)
  1. [1] Josh Alman and Virginia Vassilevska Williams , year=. Truly Subquadratic. 2610.06783 , archivePrefix= on PithPith's reviewarXiv
  2. [2] Timothy M. Chan and Virginia. Hardness for triangle problems under even more believable hypotheses: reductions from real. Proc. 54th Annual. 2022 , _url =. doi:10.1145/3519935.3520032 , timestamp = on Pithdoi:10.1145/3519935.3520032
  3. [3] Timothy M. Chan , title =. 2020 , _url =. doi:10.1145/3363541 , timestamp = on Pithdoi:10.1145/3363541
  4. [4] Timothy M. Chan and R. Ryan Williams , title =. 2021 , _url =. doi:10.1145/3402926 , timestamp = on Pithdoi:10.1145/3402926
  5. [5] Timothy M. Chan and Virginia. Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted. Proc. 55th Annual. 2023 , _url =. doi:10.1145/3564246.3585237 , timestamp = on Pithdoi:10.1145/3564246.3585237
  6. [6] Michael L. Fredman , title =. 1976 , _url =. doi:10.1137/0205006 , timestamp = on Pithdoi:10.1137/0205006
  7. [7] Timothy M. Chan and Yinzhan Xu , _editor =. Simpler Reductions from. Proc. ACM-SIAM Symposium on Simplicity in Algorithms (SOSA) , pages =. 2024 , _url =. doi:10.1137/1.9781611977936.4 , timestamp = on Pithdoi:10.1137/1.9781611977936.4
  8. [8] Virginia. Monochromatic Triangles, Triangle Listing and. Proc. 61st. 2020 , _url =. doi:10.1109/FOCS46700.2020.00078 , timestamp = on Pithdoi:10.1109/focs46700.2020.00078
  9. [9] Nick Fischer and Piotr Kaliciak and Adam Polak , _editor =. Deterministic. Proc. 15th Innovations in Theoretical Computer Science Conference (ITCS) , _series =. 2024 , _url =. doi:10.4230/LIPICS.ITCS.2024.49 , timestamp = on Pithdoi:10.4230/lipics.itcs.2024.49
  10. [10] Tsvi Kopelowitz and Seth Pettie and Ely Porat , _editor =. Higher Lower Bounds from the. Proc. 27th Annual. 2016 , _url =. doi:10.1137/1.9781611974331.CH89 , timestamp = on Pithdoi:10.1137/1.9781611974331.ch89
  11. [11] Mihai P. Towards polynomial lower bounds for dynamic problems , booktitle =. 2010 , url =. doi:10.1145/1806689.1806772 , timestamp = on Pithdoi:10.1145/1806689.1806772
  12. [12] Sankeerth Rao Karingula and Shachar Lovett , year=. A simplified proof of polynomial improvements for. 2610.15663 , archivePrefix= on PithPith's reviewarXiv
  13. [13] Barna Saha and Christopher Ye , year=. Simple, Faster (min, +) Matrix Multiplication and. 2610.20297 , archivePrefix= on PithPith's reviewarXiv
  14. [14] Ruhollah Majdoddin , year=. Thin matrix products up to D N^. 2610.17420 , archivePrefix= on PithPith's reviewarXiv
  15. [15] Allan Gr. Threesomes, Degenerates, and Love Triangles , journal =. 2018 , url =. doi:10.1145/3185378 , timestamp = on Pithdoi:10.1145/3185378
  16. [16] Amihood Amir and Timothy M. Chan and Moshe Lewenstein and Noa Lewenstein , title =. Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), Part. 2014 , _crossref =. doi:10.1007/978-3-662-43948-7\_10 , timestamp = on Pithdoi:10.1007/978-3-662-43948-7
  17. [17] Ilya Baran and Erik D. Demaine and Mihai P. Subquadratic Algorithms for. Algorithmica , volume =. 2008 , _url =. doi:10.1007/S00453-007-9036-3 , timestamp = on Pithdoi:10.1007/s00453-007-9036-3
  18. [18] Arnold Sch. Partial and Total Matrix Multiplication , journal =. 1981 , _url =. doi:10.1137/0210032 , timestamp = on Pithdoi:10.1137/0210032
  19. [19] Don Coppersmith , title =. 1982 , url =. doi:10.1137/0211037 , timestamp = on Pithdoi:10.1137/0211037
  20. [20] Yuzhou Gu and Adam Polak and Virginia. Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths , booktitle =. 2021 , doi = on Pith
show 35 more
  1. [21] Shucheng Chi and Ran Duan and Tianle Xie and Tianyi Zhang , title =. Proc. 54th. 2022 , doi = on Pith
  2. [22] Karl Bringmann and Fabrizio Grandoni and Barna Saha and Virginia. Truly Subcubic Algorithms for Language Edit Distance and. 2019 , doi = on Pith
  3. [23] Timothy M. Chan and Moshe Lewenstein , title =. Proc. 47th. 2015 , doi = on Pith
  4. [24] Marek Cygan and Marcin Mucha and Karol W. On Problems Equivalent to. 2019 , _url =. doi:10.1145/3293465 , timestamp = on Pithdoi:10.1145/3293465
  5. [25] Andreas Bj. Fourier meets. Proc. 39th Annual. 2007 , _url =. doi:10.1145/1250790.1250801 , timestamp = on Pithdoi:10.1145/1250790.1250801
  6. [26] Andreas Bj. Set Partitioning via Inclusion--Exclusion , journal =. 2009 , _url =. doi:10.1137/070683933 , timestamp = on Pithdoi:10.1137/070683933
  7. [27] Karl Bringmann and Nick Fischer and Vasileios Nakos , _editor =. Sparse nonnegative convolution is equivalent to dense nonnegative convolution , booktitle =. 2021 , _url =. doi:10.1145/3406325.3451090 , timestamp = on Pithdoi:10.1145/3406325.3451090
  8. [28] Karl Bringmann and Nick Fischer and Vasileios Nakos , _editor =. Deterministic and. Proc. 2022 , _url =. doi:10.1137/1.9781611977073.119 , timestamp = on Pithdoi:10.1137/1.9781611977073.119
  9. [29] Isaac Goldstein and Tsvi Kopelowitz and Moshe Lewenstein and Ely Porat , _editor =. Conditional Lower Bounds for Space/Time Tradeoffs , booktitle =. 2017 , _url =. doi:10.1007/978-3-319-62127-2\_36 , timestamp = on Pithdoi:10.1007/978-3-319-62127-2
  10. [30] Tsvi Kopelowitz and Ely Porat , title =. CoRR , volume =. 2019 , _url =. 1907.11206 , timestamp = on PithPith's reviewarXiv
  11. [31] Itai Dinur and Alexander Golovnev , _editor =. Improved Time-Space Tradeoffs for 3SUM-Indexing , booktitle =. 2026 , _url =. doi:10.4230/LIPICS.ICALP.2026.78 , timestamp = on Pithdoi:10.4230/lipics.icalp.2026.78
  12. [32] Alexander Golovnev and Siyao Guo and Thibaut Horel and Sunoo Park and Vinod Vaikuntanathan , _editor =. Data structures meet cryptography:. Proc. 52nd Annual. 2020 , _url =. doi:10.1145/3357713.3384342 , timestamp = on Pithdoi:10.1145/3357713.3384342
  13. [33] Timothy M. Chan , _editor =. Speeding up the. Proc. 26th Annual. 2015 , _url =. doi:10.1137/1.9781611973730.16 , timestamp = on Pithdoi:10.1137/1.9781611973730.16
  14. [34] Timothy M. Chan , title =. Discret. Comput. Geom. , volume =. 2019 , _url =. doi:10.1007/S00454-019-00062-5 , timestamp = on Pithdoi:10.1007/s00454-019-00062-5
  15. [35] Amir Abboud and Nick Fischer and Zander Kelley and Shachar Lovett and Raghu Meka , _editor =. New Graph Decompositions and Combinatorial. Proc. 56th Annual. 2024 , _url =. doi:10.1145/3618260.3649696 , timestamp = on Pithdoi:10.1145/3618260.3649696
  16. [36] Huacheng Yu , title =. Inf. Comput. , volume =. 2018 , _url =. doi:10.1016/J.IC.2018.02.006 , timestamp = on Pithdoi:10.1016/j.ic.2018.02.006
  17. [37] Richard Cole and Ramesh Hariharan , _editor =. Verifying candidate matches in sparse and wildcard matching , booktitle =. 2002 , _url =. doi:10.1145/509907.509992 , timestamp = on Pithdoi:10.1145/509907.509992
  18. [38] Timothy M. Chan and Qizheng He , _editor =. Reducing. Proc. 3rd Symposium on Simplicity in Algorithms (SOSA) , pages =. 2020 , _url =. doi:10.1137/1.9781611976014.1 , timestamp = on Pithdoi:10.1137/1.9781611976014.1
  19. [39] R. Ryan Williams , title =. 2018 , _url =. doi:10.1137/15M1024524 , timestamp = on Pithdoi:10.1137/15m1024524
  20. [40] Timothy M. Chan , title =. Algorithmica , volume =. 2008 , _url =. doi:10.1007/S00453-007-9062-1 , timestamp = on Pithdoi:10.1007/s00453-007-9062-1
  21. [41] Timothy M. Chan , title =. 2010 , _url =. doi:10.1137/08071990X , timestamp = on Pithdoi:10.1137/08071990x
  22. [42] Virginia. Subcubic Equivalences Between Path, Matrix, and Triangle Problems , journal =. 2018 , _url =. doi:10.1145/3186893 , timestamp = on Pithdoi:10.1145/3186893
  23. [43] David Bremner and Timothy M. Chan and Erik D. Demaine and Jeff Erickson and Ferran Hurtado and John Iacono and Stefan Langerman and Mihai P. Necklaces, Convolutions, and. Algorithmica , volume =. 2014 , _url =. doi:10.1007/S00453-012-9734-3 , timestamp = on Pithdoi:10.1007/s00453-012-9734-3
  24. [44] Nick Fischer and Adam Polak and Jonas Schmidt , year=. 2610.10153 , archivePrefix= on PithPith's reviewarXiv
  25. [45] Virginia. Finding, Minimizing, and Counting Weighted Subgraphs , journal =. 2013 , _url =. doi:10.1137/09076619X , timestamp = on Pithdoi:10.1137/09076619x
  26. [46] Richard M. Karp , title =. Oper. Res. Lett. , volume =. 1982 , _url =. doi:10.1016/0167-6377(82)90044-X , timestamp = on Pithdoi:10.1016/0167-6377(82)90044-x
  27. [47] Karl Bringmann and Vasileios Nakos , _editor =. A Fine-Grained Perspective on Approximating Subset Sum and Partition , booktitle =. 2021 , _url =. doi:10.1137/1.9781611976465.108 , timestamp = on Pithdoi:10.1137/1.9781611976465.108
  28. [48] Karl Bringmann , _editor =. Knapsack with Small Items in Near-Quadratic Time , booktitle =. 2024 , _url =. doi:10.1145/3618260.3649719 , timestamp = on Pithdoi:10.1145/3618260.3649719
  29. [49] Ce Jin , _editor =. 0-1 Knapsack in Nearly Quadratic Time , booktitle =. 2024 , _url =. doi:10.1145/3618260.3649618 , timestamp = on Pithdoi:10.1145/3618260.3649618
  30. [50] Andreas Bj. Trimmed. Theory Comput. Syst. , volume =. 2010 , _url =. doi:10.1007/S00224-009-9185-7 , timestamp = on Pithdoi:10.1007/s00224-009-9185-7
  31. [51] Josh Alman and Baitian Li , title =. Proc. 66th. 2025 , _url =. doi:10.1109/FOCS63196.2025.00074 , timestamp = on Pithdoi:10.1109/focs63196.2025.00074
  32. [52] John D. Markel , title =. IEEE Transactions on Audio and Electroacoustics , volume = on Pith
  33. [53] Henrik V. Sorensen and C. Sidney Burrus , title =. 1993 , url =. doi:10.1109/78.205723 , timestamp = on Pithdoi:10.1109/78.205723
  34. [54] Ryan Williams , title =. Proc. 65th. 2024 , _url =. doi:10.1109/FOCS61266.2024.00088 , timestamp = on Pithdoi:10.1109/focs61266.2024.00088
  35. [55] Marvin K. On the Fine-Grained Complexity of One-Dimensional Dynamic Programming , booktitle =. 2017 , _url =. doi:10.4230/LIPICS.ICALP.2017.21 , timestamp = on Pithdoi:10.4230/lipics.icalp.2017.21
Cited by 5 Pith papers

Challenges and discussion

Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.

No comments yet.

Sign in to comment