  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,\ldots,k} $ $\{a[i] $ $+$
$b[k-i]\}$, given sequences $(a[i])^{n-1}_{i=0}$ and $(b[i])_{i=0}^{n-1}$. This
can easily be done in $O(n^2)$ time, but no $O(n^{2-\varepsilon})$ algorithm is
known for $\varepsilon > 0$. In this paper, 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 SETH might not
be possible for some problems.

Data Structures and Algorithms;Computational Complexity