Record link: 
http://hdl.handle.net/20.500.12708/191157
-
Title: 
Fast Convolutions for Near-Convex Sequences
en
Citation: 
Brand, C., & Lassota, A. (2023). Fast Convolutions for Near-Convex Sequences. In S. Iwata & N. Kakimura (Eds.), 34th International Symposium on Algorithms and Computation (ISAAC 2023) (pp. 1–16). Schloss-Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ISAAC.2023.16
-
Publisher DOI: 
10.4230/LIPICS.ISAAC.2023.16
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Brand, Cornelius 
Lassota, Alexandra 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
34th International Symposium on Algorithms and Computation (ISAAC 2023) 
-
ISBN: 
978-3-95977-289-1
-
Volume: 
283
-
Date (published): 
Dec-2023
-
Event name: 
34th International Symposium on Algorithms and Computation (ISAAC 2023) 
en
Event date: 
3-Dec-2023 - 6-Dec-2023
-
Event place: 
Kyoto, Japan
-
Number of Pages: 
16
-
Publisher: 
Schloss-Dagstuhl - Leibniz Zentrum für Informatik
-
Peer reviewed: 
Yes
-
Keywords: 
fine-grained complexity; convex sequences; (min, +)-convolution
en
Abstract: 
We develop algorithms for (min,+)-Convolution and related convolution problems such as Super Additivity Testing, Convolution 3-Sum and Minimum Consecutive Subsums which use the degree of convexity of the instance as a parameter. Assuming the min-plus conjecture (Künnemann-Paturi-Schneider, ICALP'17 and Cygan et al., ICALP'17), our results interpolate in an optimal manner between fully convex instances, which can be solved in near-linear time using Legendre transformations, and general non-convex sequences, where the trivial quadratic-time algorithm is conjectured to be best possible, up to subpolynomial factors.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

7
checked on Jan 6, 2024

Google ScholarTM

Check