PaperlayerView exact revision on arXiv

Source-linked AI summary

Barely Monotone (min,+)-Convolution in Truly Subquadratic Time

MohammadTaghi Hajiaghayi, Danny Mittal, Saeed Seddighin

arXiv:2610.10503v1cs.DS

TL;DR

Near-n^1.5 algorithms for bounded (min,+)-convolution rely on monotonicity or related structure in at least one input, raising the question of how much monotonicity is needed. The paper measures monotonicity by the number of monotone subsequences and gives algorithms parameterized by that measure. With monotonicity α in A, expected O~(n^{5/3+2α/3}) time suffices for bounded B, without requiring B to be monotone.

  • Problem

    Known bounded-input algorithms near n^1.5 rely on monotonicity or related structure in at least one sequence, motivating the question of how much monotonicity is needed.

    Source: §1 · p. 3

  • Method

    The paper measures monotonicity by the minimum number of monotone subsequences in a sequence and develops convolution algorithms parameterized by the inputs’ monotonicity.

    Source: §1 · p. 3, §1.1 · p. 4

  • Results

    Expected O~(n^{5/3+2α/3}) time suffices when A has monotonicity α, without any assumption on B’s monotonicity.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    An O(N^{4/3−ε}) algorithm for bounded monotone convolution would yield an O(n^{2−3ε/2}) algorithm for bounded convolution.

    Source: §1.1 · p. 5

    Theorem 3.7’s algorithm requires B’s entries to be bounded by O(n).

    Source: §3.3 · p. 11

Abstract

from arXiv · show

The (min,+)-convolution of two sequences A and B of length n is the sequence C with C[k] = min_{i+j=k} (A[i]+B[j]). For bounded inputs, whose entries are integers in {0,...,O(n)}, prior work computes it in truly subquadratic time when the inputs are monotone; the algorithm of Chi, Duan, Xie, and Zhang (STOC 2022) takes expected O~(n^{1.5}) time. We introduce a monotonicity measure ranging from 0 (monotone) to 1/2 (entirely non-monotone): a sequence has monotonicity alpha if it can be partitioned into O(n^alpha) monotone subsequences, and by the Erdos-Szekeres theorem every sequence has monotonicity at most 1/2. We show that truly subquadratic time is achievable even when just one input is barely monotone, that is, has monotonicity 1/2 - Omega(1): if A has monotonicity alpha, we compute the convolution in expected time O~(n^{5/3+2alpha/3}) for every bounded B. If B has monotonicity beta as well, the expected time improves to O~(n^{(3+alpha+beta)/2}), which matches the monotone case for alpha = beta = 0; this algorithm also allows infinite entries placed arbitrarily. We complement these algorithms with fine-grained reductions. Bounded (min,+)-convolution reduces to bounded monotone (min,+)-convolution of length N = O(n^{1.5}), so an O(N^{4/3-eps})-time algorithm for monotone inputs would give an O(n^{2-3eps/2})-time algorithm for bounded inputs. Similarly, entries bounded by n reduce to entries bounded by N^x on sequences of length N = Theta(n^{2/(1+x)}). We also show that if only A has entries in {0,...,M}, we can compute the convolution in O~(n(M+1)) time, and in O~(n^{1.5} sqrt(M)) time if A may also contain +infinity.

1 Introduction

Prior work brought bounded (min, +)-convolution close to truly subquadratic time when inputs have monotone structure, but the amount of monotonicity needed remained unclear. This paper studies algorithms and reductions for inputs with varying monotonicity and value ranges.

1 Introduction

  • Bounded (min, +)-convolution is a natural intermediate target for faster APSP algorithms and is also connected by fine-grained reductions to knapsack-type problems and other problems.For bounded inputs, earlier work obtained a truly subquadratic algorithm with an exponent close to 2; monotone inputs admit faster algorithms.Source: §1 · p. 2

1.1 Our Results

  • If A has monotonicity number O(n^α), bounded (min, +)-convolution takes expected O~(n^(5/3+2α/3)) time for arbitrary bounded B, making the algorithm truly subquadratic when α < 1/2.Here monotonicity is measured by the number of monotone subsequences in a partition; every length-n sequence has monotonicity number O(√n).Source: §1 · p. 3, §1.1 · p. 4
  • When both inputs have few monotone parts, the algorithm runs in O~(n^1.5√(mono(A) mono(B))) time, and permits infinite entries placed arbitrarily when finite entries are partitionable into few monotone subsequences.For a constant number of parts in A, the one-structured-input bound gives O~(n^5/3) time for arbitrary bounded B.Source: §1.1 · p. 4
  • If only A has finite entries in {0, . . . , M}, the convolution is computable deterministically in O~(n(M + 1)) time even when B is arbitrary, including +∞ entries.The proof uses prefix minima of B to estimate initial outputs within additive error M, then splits the instance into subinstances with small value ranges.Source: §1.1 · p. 4
  • A bounded instance of length n reduces to bounded monotone instances of length Θ(n^1.5), so an O(N^(4/3−ε)) monotone algorithm would yield O(n^(2−3ε/2)) time for bounded inputs.The reduction trades sequence length against value range; a related reduction transfers improvements for entries bounded by N^x to bounded inputs.Source: §1.1 · p. 5

1.2 Technical Overview

  • For barely monotone inputs, the algorithm extends CDXZ by processing monotone-part groups and using random-prime filters to limit the erroneous terms that must be scanned.It fills gaps in each part to preserve segments, then uses additional random-prime aliasing filters for range-restricted convolution counts.Source: §1.2 · p. 6

1.3 Related Work

  • Related work connects convolution to minimum-witness convolution and intermediate matrix products, while monotone convolution has also been linked to binary jumbled indexing.Fine-grained equivalences to other problems include results by Cygan, Mucha, Węgrzycki, and Włodarczyk and Künnemann, Paturi, and Schneider [23].Source: §1.3 · p. 7

2 Preliminaries

The preliminaries define min-plus convolution and give an FFT-based method for bounded value ranges, alongside a randomized-prime divisibility bound.

2 Preliminaries

  • For sequences A and B, (A ⋆ B)[k] is the minimum A[i] + B[j] over indices with i + j = k, with x + ∞ = ∞.A finite minimizing pair is a witness for output k.Source: §2 · p. 7
  • For finite entries in ranges of width M, convolution takes O((n + m)(M + 1) log(n + m + M)) deterministic time.The method encodes pair counts in bivariate polynomials, substitutes z = x^(2M+1), and multiplies exactly with FFT or fast integer multiplication.Source: §2 · p. 8
  • A uniformly random prime p in [P, 2P] divides a fixed nonzero integer z with probability at most c0 ln(|z| + 1)/P.Such a prime can be sampled in eO(P) time.Source: §2 · p. 8

3 Barely Monotone Sequences

Both algorithms for barely monotone sequences combine monotone partitions with the CDXZ framework; one needs a partition of A only, while the other is more involved.

3 Barely Monotone Sequences

  • Both barely monotone algorithms combine monotone partitions with CDXZ, first proving the bound that partitions A only and then the more involved bound for both inputs.The one-input bound is treated in Section 3.3 and the two-input bound in Section 3.4.Source: §3 · p. 8

3.1 Monotone Partitions

A monotone partition divides a sequence’s index set into monotone subsequences; the paper gives an algorithm to find a small partition and uses such partitions in its convolution algorithms.

3.1 Monotone Partitions

  • A sequence with monotonicity number mono(A) can be partitioned into at most min{mono(A) · (ln n + 1), 3√n + log2 n + 1} monotone parts.The partition is computed in O(min{mono(A) log n, √n} · n log n) time, implying mono(A) = O(√n).Source: §3.1 · p. 8
  • The algorithm repeatedly removes the longer of a longest non-decreasing and a longest non-increasing subsequence from the unassigned indices.The remaining indices inherit a partition into at most mono(A) monotone subsequences, yielding the mono(A) log n part bound; Erdős–Szekeres gives the O(√n) bound.Source: §3.1 · pp. 8–9
  • The convolution algorithms can compute partitions of A and, when needed, B into O(min{mono(A) log n, √n}) and O(min{mono(B) log n, √n}) parts.The minimum-witness convolution is encoded using A constant on S and its complement, and B increasing on T and constant elsewhere; outputs below 2n identify the smallest qualifying j.Source: §3.1 · p. 9

3.2 The Coarse-Value Framework

The coarse-value framework rounds input values at scale D, identifies which pairs can witness each output, and recovers candidates while filtering erroneous pairs using random primes.

3.2 The Coarse-Value Framework

  • Writing A[i] = D eA[i] + ai and B[j] = D eB[j] + bj with remainders below D, every witness has coarse sum eC[k] or eC[k] + 1, where eC = eA ⋆ eB.A coarse sum at least eC[k] + 2 cannot attain the minimum.Source: §3.2 · p. 9
  • For each output and offset δ ∈ {0, 1}, erroneous pairs have a coarse sum congruent to the target modulo p but unequal to it; a fixed nonmatching value collides with probability O(log n/P).The prime is chosen uniformly from [P, 2P].Source: §3.2 · pp. 9–10
  • Given the coarse convolution and correction polynomials, the framework computes C in eO(nDp) time.The polynomial encoding has bounded degrees and coefficients, so Kronecker substitution and exact FFT recover the required polynomial values.Source: §3.2 · pp. 9–10
  • A reporting structure returns indices in an interval whose values match a residue modulo p but differ from the target, in O(log N) time plus O(1) per reported position.Preprocessing takes O(N + p) time; sorted residue lists and next pointers skip matching target values.Source: §3.2 · p. 10
  • Within each monotone part, indices sharing a coarse value form a group whose span is disjoint from other groups’ spans in that part.Each part has at most ⌊U/D⌋ + 1 groups, for at most m(U/D + 1) groups overall; total span length is at most mn.Source: §3.2 · p. 10

3.3 An Algorithm Using Only One Monotone Partition

A single monotone partition of A supports a faster algorithm for bounded (min, +)-convolution, with running time depending on the number of parts. The section also shows how improvements to this approach would transfer to general bounded convolution.

3.3 An Algorithm Using Only One Monotone Partition

  • For bounded A and B, if m = mono(A), a Las Vegas algorithm computes their convolution in expected eO(n^(5/3)m^(2/3)) time; only B must be bounded by O(n).Source: §3.3 · p. 11
  • The algorithm partitions A into monotone parts, computes a coarse convolution, and queries shifted intervals to identify erroneous pairs.Source: §3.3 · p. 11
  • Each erroneous pair is added exactly once, and the expected number of reports is O(m′n^2 log n/P).Source: §3.3 · p. 11
  • For 2 ≤ m ≤ √n, an O(m n^(1.5−ε))-time algorithm would yield bounded convolution in O(n^(2−ε) + n^1.5 log n) time, including when m = 2.Source: §3.3 · pp. 11–12
  • For constant m ≥ 2, improving the exponent 5/3 to below 3/2 would also improve bounded convolution; the reduction threshold and upper bound meet at m = Θ(√n).Source: §3.3 · p. 12

3.4 Both Sequences Barely Monotone

This section presents and analyzes a refinement-and-pruning algorithm for two barely monotone sequences, allowing infinite entries and giving expected running-time bounds for polynomially bounded values. It also considers the interval-parts case, where the algorithm is simpler but yields no asymptotic improvement.

3.4 Both Sequences Barely Monotone

  • For mA = mB = 1, Theorem 3.10 gives eO(n^1.5) time for convolution when each sequence’s finite entries are monotone, with infinite entries placed arbitrarily.This common generalization of bounded monotone (min, +)-convolution and minimum-witness convolution is not covered by CDXZ [15].Source: §3.4 · p. 12

3.4.3 The Algorithm

  • At each level, polynomial counts and random modular filters identify candidate contributions; the algorithm scans aliased false segments, refines candidate minima, and prunes candidates that cannot be optimal.True contributions always pass the filter; false segments are scanned only if they pass it, trading polynomial-product size against expected scanning cost.Source: §3.4 · pp. 12–13, §3.4.3 · p. 17

3.4.1 Setup

  • Each finite support is partitioned into monotone parts, which are extended to full-length monotone sequences to define segments while counting contributions only from valid original entries.The setup chooses a random scale for splitting values into high and low parts; filled values are used for segments, not as contributing pairs.Source: §3.4.1 · pp. 13–14

3.4.2 Segments

  • Segments are maximal intervals with constant rounded high parts and level values; each parent segment splits into at most three child segments found by two binary searches.False segments near the current rounded minimum are retained for refinement, and every retained segment has a retained parent.Source: §3.4.2 · p. 15

3.4.3 The Algorithm

  • Pruning discards candidates whose lower bounds exceed the best remaining upper bound, while keeping every survivor close to C[k] for the running-time analysis.The stated upper bound on the best remaining candidate is W* + 2^(λ+1) − 2.Source: §3.4.3 · p. 17

3.4.4 Correctness

  • For every choice of the random prime and auxiliary moduli, the algorithm outputs A ⋆ B.At each relevant k, an active candidate attains C[k], and surviving candidates satisfy the correctness invariant.Source: §3.4.4 · pp. 17–18

3.4.5 Running Time

  • The expected running time is O~(n + n^1.5 sqrt(m_A m_B)), including partition computation when needed.The bound also includes O(n) time for empty supports.Source: §3.4.5 · p. 21
  • For finite entries in {0,...,U}, U ≤ n^O(1), expected time is O~(n + n√(m_A m_B U*) + n^1.5√(m_A m_B)), where U* = max(U,n).When m_A = m_B = 1, the bound is O~(n^1.5 + n√U), matching the rectangular bound of Bringmann, Dürr, and Polak [9] for U ≥ n while allowing arbitrarily placed infinite entries.Source: §3.4.5 · p. 21
  • If one sequence’s parts are intervals, prefix-sum differences eliminate scanning and aliasing filters, yielding a simpler algorithm but no asymptotic improvement.This applies, for example, to a single monotone sequence without infinities.Source: §3.4.5 · p. 21

4 From Bounded to Monotone (min, +)-Convolution

The section reduces bounded (min, +)-convolution to convolution on non-decreasing sequences by expanding each input entry into a rounded block with an index offset. The expansion parameter trades transformed length against value range, yielding conditional fine-grained consequences for monotone convolution algorithms.

Theorem 4.2 reduction

  • Any bounded inputs A, B in {0, ..., U}^n can be transformed into non-decreasing sequences of length N = 2nw and entries at most n(2⌊U/w⌋+3), with the original convolution recoverable in O(nw) time.The reduction uses K = 2⌊U/w⌋+3 and expands each entry into 2w rounded values with an index-dependent offset.Source: §4 · p. 22
  • The reduction recovers each output through selected transformed-convolution entries, where rounding the summed input values preserves the needed floor information.The identity underlying the readout minimizes the two rounded terms over a run of at least w consecutive indices.Source: §4 · pp. 22–23

Fine-grained consequences

  • An O(N^{4/3−ε})-time algorithm for bounded monotone convolution would imply an O(n^{2−3ε/2})-time algorithm for bounded convolution.The reduction uses N = 2n⌈√n⌉ and has O(n^1.5) construction cost.Source: §4 · p. 23
  • For w = ⌈n^γ⌉, the transformed length is Θ(n^{1+γ}) and the entry bound is O(n^{2−γ}), for fixed γ in [0,1).The choice γ = 1/2 gives the length and value-range balance used in Corollary 4.4.Source: §4 · p. 23
  • Across this trade-off, an O((NV)^{2/3−ε}) monotone-convolution algorithm would yield an O(n^{2−3ε}+n^{1+γ}) algorithm for bounded inputs.Here N = Θ(n^{1+γ}) and V = Θ(n^{2−γ}), so NV = Θ(n^3).Source: §4 · p. 23

5 Bounded Value Ranges

This section gives reductions that change the value range and algorithms that exploit a bounded sequence, including cases with infinite entries. The resulting running times depend on the range bound and on whether the bounded sequence may contain +∞.

5.1 Reducing the Value Range

  • The value-layer reduction maps inputs with entries in {0, ..., U} to sequences of length N = 2n(⌊U/L⌋+1) and entries in {0, ..., 2L}, from which the original convolution is recovered in O(N) time.The recovery takes the minimum over layer pairs whose transformed-convolution value is below 2L.Source: §5.1 · p. 24
  • If length-N convolution with entries in {0, ..., N^x} takes O(N^{1+x−ε}) time, bounded length-n convolution takes O(n^{2−2ε/(1+x)}) time.The reduction uses N = Θ(n^{2/(1+x)}).Source: §5.1 · p. 24

5.2 One Bounded Sequence Suffices

  • When only A is bounded in {0, ..., M}, convolution with arbitrary integer or +∞ entries in B is deterministic in O(n(M+1) log n) time.The method partitions outputs into levels derived from B's prefix minima and computes sub-convolutions over restricted intervals.Source: §5.2 · pp. 24–25
  • The O(n(M+1) log n) algorithm relies on A having no infinite entries, because its comparison pair must have finite value.The paper separately extends another result to inputs whose finite entries can be partitioned into few monotone subsequences.Source: §5.2 · p. 25

5.3 Bounded Entries with Infinities

  • If A has entries in {0, ..., M}∪{+∞}, convolution with arbitrary integer or +∞ entries in B is deterministic in O(n^1.5√M log n) time.The method groups B's finite entries into value buckets, identifies relevant buckets per output, and evaluates those buckets.Source: §5.3 · pp. 25–26
  • Minimum-witness convolution is the special case M = 1 with A indicating S and B giving indices in T, and an O(n^1.5−ε) algorithm for the broader problem would improve its state of the art.For each k, the minimum-witness task returns the smallest j in T such that k−j belongs to S.Source: §5.3 · p. 26

6 Research History and Use of AI Tools

The paper is presented as part of a research program on structured special cases of APSP and (min, +)-problems. It records the program's progress and discloses which results used AI models.

Research context

  • The authors describe this paper as progress toward faster algorithms for structured APSP and (min, +)-problem special cases, with monotone convolution central to their effort.They note that the first artifact of the program was their SODA 2027 paper on dynamic algorithms.Source: §6 · pp. 26–27
  • After Alman and Vassilevska Williams [1] obtained a truly subcubic APSP algorithm for polynomially bounded integer weights, the authors posted this paper as progress on structured special cases they consider independently interesting.They state that their small-monotonicity algorithms have exponents below the exponent close to 2 that follows from [1].Source: §6 · p. 27

Use of AI tools

  • The authors report that AI models were used for Theorem 4.2 and its corollaries, Theorem 5.1 and Corollary 5.2, and paper writing.They state that all other results were obtained without AI.Source: §6 · p. 27
Loading 2610.10503v1…