{"id":"69b69af9-f020-4446-a027-9898594b7ee9","arxiv_id":"2610.42012","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Simpler truly subquadratic randomized integer 3SUM via selected-entries subset convolution, with odd-k k-SUM refutation and deterministic real 3SUM/APSP corollaries.","lead":"Using subset-convolution dynamic programming and hashing, this paper gives a simpler randomized fast algorithm for 3SUM that avoids matrix multiplication, then extends the method to speed up odd-k k-SUM and to derandomize real-valued 3SUM and APSP. The value for a generalist is seeing a record-level algorithmic advance reduced to basic counting and inclusion-exclusion tricks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"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.","rationale":"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.","tokens_in":28195,"tokens_out":53698,"duration_ms":825216,"concrete_test":"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.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"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.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"The paper presents three contributions. First, it gives a Monte Carlo randomized algorithm for integer 3SUM with polynomially bounded inputs running in O(n^1.965) (Corollary 2.4), based on a selected-entries version of subset convolution solved by a trimmed zeta/Mobius transform DP and a hashing-based reduction, avoiding both matrix multiplication and FFT. Second, it extends the approach from bit-vectors to vectors in [r]^d, yielding a randomized algorithm for odd k-SUM in O(n^{ceil(k/2)-epsilon_k}) time for integer inputs and stated as refuting the k-SUM Hypothesis for all odd k (Corollaries 3.5 and 3.6). Third, it gives deterministic reductions from Real APSP and Real 3SUM to selected-entries rectangular matrix multiplication, producing claimed deterministic algorithms in O(n^2.9997) and O(n^1.9998) (Corollaries 4.9 and 5.10), where the numerical exponents are obtained by substituting selected-entries bounds quoted from the unpublished preprint [AW26].","tokens_in":28633,"tokens_out":27935,"duration_ms":231274,"significance":"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.","major_comments":[{"comment":"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]. 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).","section":"Corollary 5.10","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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. 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.","section":"Sections 4.2-5.2 (Theorems 4.8, 5.9; Corollaries 4.9, 5.10)","authors_acknowledge":null,"authors_acknowledge_p":null}],"minor_comments":[{"comment":"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.","section":"Theorem 2.3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"Corollary 3.6","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"Section 5.2, Theorem 5.9","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"major_revision"},"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"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.\n\nWhat 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.\n\nThe 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.\n\nOne concrete slip, minor but worth fixing: in Corollary 5.10, with delta = 0.050534 and d = n^0.0046983, the selected-entries middle dimension is d^(12+2delta) = n^0.05685445, which is just over the quoted d <= n^0.056853. Lowering d to about 0.00469818 restores the range and does not change the stated n^1.9998 bound, so this is a boundary arithmetic issue, not a structural flaw.\n\nCitation 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.\n\nRecommendation: 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.","headline":"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.","tokens_in":29155,"tokens_out":11688,"duration_ms":84250},"pith_extraction":{"msc":["68Q25","68W20","68W40"],"pacs":[],"model":"deepseek/deepseek-v4-flash","headline":"This paper puts integer 3SUM in randomized $O(n^{1.965})$ time using a trimmed zeta transform and hashing, refutes the $k$-SUM Hypothesis for all odd $k$, and derandomizes Real 3SUM and Real APSP.","keywords":["3SUM","k-SUM Hypothesis","subset convolution","zeta transform","selected entries","all-pairs shortest paths","derandomization","fine-grained complexity"],"falsifier":"Work out the cited selected-entries matrix multiplication subroutine at the exact dimensions used here — $d^{4+2\\delta}$ with $\\delta = 0.0226537$ for the APSP corollary and $d^{12+2\\delta}$ with $\\delta = 0.050534$ for the 3SUM corollary — and compare the true cost against the quoted expressions; a single instance where the subroutine needs more time than quoted at those dimensions would overturn Corollaries 4.9 and 5.10 without touching the randomized integer results. For the randomized side, running the Theorem 2.3 algorithm on large balanced inputs would either confirm that the true running time tracks $O(n^{1.965})$ or expose corrections hidden in the $\\tilde{O}$ notation.","tokens_in":29708,"feed_emoji":"⚡","tokens_out":17872,"duration_ms":122194,"temperature":0.7,"pith_summary":"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.","feed_headline":"3SUM falls to n^1.965 with a trimmed zeta transform","feed_subtitle":"The same trick refutes the k-SUM hypothesis for all odd k and derandomizes real 3SUM and APSP.","key_machinery":"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_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It supplies the selected-entries rectangular matrix multiplication subroutine and the two quoted bounds (Table 2 and Corollary 31) that the deterministic Real APSP and Real 3SUM theorems consume, and it defines the problem context of the 3SUM/APSP breakthrough this paper simplifies.","marker":"[AW26]"},{"why":"It supplies the trimmed Möbius inversion idea — computing the zeta transform only on the lattice subsets below a query — that Section 2.1 adapts into selected-entries subset convolution.","marker":"[BHKK10]"},{"why":"It supplies the fast subset convolution machinery: the zeta transform dynamic program and the inclusion–exclusion identity for the covering product that make both the preprocessing and the query algorithms correct.","marker":"[BHKK07]"},{"why":"It supplies the randomized reductions from Real APSP and Real 3SUM to AE Sparse Triangle, and the comparison-trick counting style, that Sections 4–5 derandomize.","marker":"[CVX22]"},{"why":"It supplies the classical comparison trick that rewrites ordering of entry sums as dominance of differences, which underlies the triangle-count formulations of the counting problems.","marker":"[Fre76]"},{"why":"It supplies the staircase decomposition of the Real 3SUM search space that Problem 5.1 uses to reduce 3SUM to predecessor–successor queries over small blocks.","marker":"[GP18]"},{"why":"It provides the reduction from All-Numbers 3SUM to (min,+)-convolution through which the new 3SUM algorithm yields a simpler randomized truly subquadratic (min,+)-convolution algorithm.","marker":"[CMWW19]"},{"why":"It supplies the deterministic reductions for integer inputs whose absence in the real case motivates the new deterministic reductions of Sections 4–5.","marker":"[CX24]"}],"fun_headline_variants":["3SUM in n^1.965 with a trimmed zeta transform, no matmul","k-SUM Hypothesis refuted for every odd k","Real 3SUM and APSP derandomized for the first time","3SUM simplified, odd-k-SUM refuted, real APSP derandomized","Trimmed zeta transform refutes odd-k-SUM and derandomizes real APSP"],"cache_read_input_tokens":0,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["3SUM in n^1.965 with a trimmed zeta transform, no matmul","k-SUM Hypothesis refuted for every odd k","Real 3SUM and APSP derandomized for the first time","3SUM simplified, odd-k-SUM refuted, real APSP derandomized","Trimmed zeta transform refutes odd-k-SUM and derandomizes real APSP"]},"model":"deepseek/deepseek-v4-flash","effort":"low","cost_usd":0.000531,"raw_usage":{"cost":0.0005310578,"is_byok":false,"cost_details":{"upstream_inference_cost":0.0005310578,"upstream_inference_prompt_cost":3.36518e-05,"upstream_inference_completions_cost":0.000497406},"total_tokens":3982,"prompt_tokens":1249,"completion_tokens":2733,"prompt_tokens_details":{"audio_tokens":0,"video_tokens":0,"cached_tokens":1099,"cache_write_tokens":0},"completion_tokens_details":{"audio_tokens":0,"image_tokens":0,"reasoning_tokens":2643}},"tokens_in":1249,"tokens_out":2733,"cost_source":"openrouter_usage","duration_ms":18401,"image_pages":[],"temperature":1.0,"billed_attempts":1,"reasoning_tokens":2643,"transport_provider":"openrouter","cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-11-02T07:59:53.636231+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":"Work out the cited selected-entries matrix multiplication subroutine at the exact dimensions used here — $d^{4+2\\delta}$ with $\\delta = 0.0226537$ for the APSP corollary and $d^{12+2\\delta}$ with $\\delta = 0.050534$ for the 3SUM corollary — and compare the true cost against the quoted expressions; a single instance where the subroutine needs more time than quoted at those dimensions would overturn Corollaries 4.9 and 5.10 without touching the randomized integer results. For the randomized side, running the Theorem 2.3 algorithm on large balanced inputs would either confirm that the true running time tracks $O(n^{1.965})$ or expose corrections hidden in the $\\tilde{O}$ notation.","supporting_citations":[],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}