Metraipolis › archive › dc_0cbddb3606e4
Barely Monotone (min,+)-Convolution in Truly Subquadratic Time — arXiv:2610.10503
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.10503
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T12:49:50.855Z
- SHA-256 of the archived text
21f558ee45fb514fa8344862578478e47c05ad5758afbb80ea87a2a8f4cd43bf- Stable URL of this page
https://metraipolis.com/documento/dc_0cbddb3606e4
How to cite
Barely Monotone (min,+)-Convolution in Truly Subquadratic Time — arXiv:2610.10503 — arXiv (en), https://arxiv.org/abs/2610.10503 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0cbddb3606e4 (Metraipolis archive dc_0cbddb3606e4, sha256 21f558ee45fb514fa8344862578478e47c05ad5758afbb80ea87a2a8f4cd43bf)
BibTeX
@misc{dc0cbddb3606e4,
title = {Barely Monotone (min,+)-Convolution in Truly Subquadratic Time — arXiv:2610.10503},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.10503},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0cbddb3606e4; sha256 21f558ee45fb514fa8344862578478e47c05ad5758afbb80ea87a2a8f4cd43bf},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.10503. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.10503 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:19:30.214Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).