2017/02/28 by Marek Cygan, Marcin Mucha, Karol Węgrzycki +1 · 1 citation
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Block (permutation group theory) #Complexity and Algorithms in Graphs #Counterexample #Equivalence (formal languages) #Exponential function #Exponential time hypothesis #Knapsack problem #Sequence (biology) #Stochastic Gradient Optimization Techniques #Subadditivity #cs.CC #cs.DS
paper · pdf · doi:10.1145/3293465
published as ACM Transactions on Algorithms 2019 · Extended abstract published in the proceedings of ICALP 2017. Full version published in TALG 2019
openalex created_date 2017/03/16 · openalex publication_date 2019/01/08 · arxiv created 2019/05/06 · arxiv updated 2019/05/07 · openalex updated_date 2026/06/26
In recent years, significant progress has been made in explaining the apparent hardness of improving upon the naive solutions for many fundamental polynomially solvable problems. This progress has come in the form of conditional lower bounds—reductions from a problem assumed to be hard. The hard problems include 3SUM, All-Pairs Shortest Path, SAT, Orthogonal Vectors, and others. In the (min ,+)-convolution problem, the goal is to compute a sequence ( c [ i ]) n-1 i=0 , where c [ k ] = min i=0,…; , k a [ i ] + b [ k - i ], given sequences ( a [ i ]) n-1 i=0 and ( b [ i ]) n-1 i=0 . This can easily be done in O( n 2 ) time, but no O ( n 2-ε ) algorithm is known for ε > 0. In this article, we undertake a systematic study of the (min ,+)-convolution problem as a hardness assumption. First, we establish the equivalence of this problem to a group of other problems, including variants of the classic knapsack problem and problems related to subadditive sequences. The (min ,+)-convolution problem has been used as a building block in algorithms for many problems, notably problems in stringology. It has also appeared as an ad hoc hardness assumption. Second, we investigate some of these connections and provide new reductions and other results. We also explain why replacing this assumption with the Strong Exponential Time Hypothesis might not be possible for some problems.