Structured $(\min ,+)$-Convolution And Its Applications For The Shortest Vector, Closest Vector, and Separable Nonlinear Knapsack Problems

D. V. Gribanov, I. A. Shumilov, D. S. Malyshev

In this work we consider the problem of computing the $(\min ,+)$-convolution of two sequences $a$ and $b$ of lengths $n$ and $m$, respectively, where $n\ge m$. We assume that $a…