On the Fine-grained Complexity of One-Dimensional
Dynamic Programming

arXiv:1703.00941v1 [cs.CC] 2 Mar 2017

Marvin Künnemann
Ramamohan Paturi
Stefan Schneider
University of California, San Diego
March 6, 2017
Abstract
In this paper, we investigate the complexity of one-dimensional dynamic programming, or
more specifically, of the Least-Weight Subsequence (LWS) problem: Given a sequence of n data
items together with weights for every pair of the items, the task is to determine a subsequence S
minimizing the total weight of the pairs adjacent in S. A large number of natural problems
can be formulated as LWS problems, yielding obvious Opn2 q-time solutions.
In many interesting instances, the Opn2 q-many weights can be succinctly represented. Yet
except for near-linear time algorithms for some specific special cases, little is known about
when an LWS instantiation admits a subquadratic-time algorithm and when it does not. In
particular, no lower bounds for LWS instantiations have been known before. In an attempt
to remedy this situation, we provide a general approach to study the fine-grained complexity
of succinct instantiations of the LWS problem. In particular, given an LWS instantiation
we identify a highly parallel core problem that is subquadratically equivalent. This provides
either an explanation for the apparent hardness of the problem or an avenue to find improved
algorithms as the case may be.
More specifically, we prove subquadratic equivalences between the following pairs (an LWS
instantiation and the corresponding core problem) of problems: a low-rank version of LWS
and minimum inner product, finding the longest chain of nested boxes and vector domination,
and a coin change problem which is closely related to the knapsack problem and pmin, `qconvolution. Using these equivalences and known SETH-hardness results for some of the
core problems, we deduce tight conditional lower bounds for the corresponding LWS instantiations. We also establish the pmin, `q-convolution-hardness of the knapsack problem. Furthermore, we revisit some of the LWS instantiations which are known to be solvable in near-linear
time and explain their easiness in terms of the easiness of the corresponding core problems.

1

Introduction

Dynamic programming (DP) is one of the most fundamental paradigms for designing algorithms
and a standard topic in textbooks on algorithms. Scientists from various disciplines have developed
DP formulations for basic problems encountered in their applications. However, it is not clear
This research is supported by the Simons Foundation. This research is support ed by NSF grant CCF-1213151
from the Division of Computing and Communication Foundations. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the
National Science Foundation.

1

whether the existing (often simple and straightforward) DP formulations are in fact optimal or
nearly optimal. Our lack of understanding of the optimality of the DP formulations is particularly
unsatisfactory since many of these problems are computational primitives.
Interestingly, there have been recent developments regarding the optimality of standard DP
formulations for some specific problems, namely, conditional lower bounds assuming the Strong
Exponential Time Hypothesis (SETH) [27]. The longest common subsequence (LCS) problem is
one such problem for which almost tight conditional lower bounds have been obtained recently. The
LCS problem is defined as follows: Given two strings x and y of length at most n, compute the
length of the longest string z that is a subsequence of both x and y. The standard DP formulation
for the LCS problem involves computing a two-dimensional table requiring Opn2 q steps. This
algorithm is only slower than the fastest known algorithm due to Masek and Paterson [34] by a
polylogarithmic factor. However, there has been no progress in finding more efficient algorithms
for this problem since the 1980s, which prompted attempts as early as in 1976 [6] to understand
the barriers for efficient algorithms and to prove lower bounds. Unfortunately, there have not
been any nontrivial unconditional lower bounds for this or any other problem in general models
of computation. This state of affairs prompted researchers to consider conditional lower bounds
based on conjectures such as 3-Sum conjecture [19] and more recently based on ETH [28] and
SETH [27]. Researchers have found ETH and SETH to be useful to explain the exact complexity
of several NP-complete problems (see the survey paper [33]). Surprisingly, Ryan Williams [39] has
found a simple reduction from the CNF-SAT problem to the orthogonal vectors problem which
under SETH leads to a matching quadratic lower bound for the orthogonal vectors problem. This
in turn led to a number of conditional lower bound results for problems in P (including LCS and
related problems) under SETH [7, 1, 11, 2, 23]. Also see [37] for a recent survey.
The DP formulation of the LCS problem is perhaps the conceptually simplest example of a twodimensional DP formulation. In the standard formulation, each entry of an n ˆ n table is computed
in constant time. The LCS problem belongs to the class of alignment problems which, for example,
are used to model similarity between gene or protein sequences. Conditional lower bounds have
recently been extended to a number of alignment problems [9, 7, 1, 11, 3].
In contrast, there are many problems for which natural quadratic-time DP formulations compute
a one-dimensional table of length n by spending Opnq-time per entry. In this work, we investigate
the optimality of such DP formulations and obtain new (conditional) lower bounds which match
the complexity of the standard DP formulations.
1-dimensional DP: The Least-Weight Subsequence (LWS) Problem. In this paper, we
investigate the optimality of the standard DP formulation of the LWS problem. A classic example
of an LWS problem is airplane refueling [25]: Given airport locations on a line, and a preferred
distance per hop k (in miles), we define the penalty for flying k 1 miles as pk ´ k 1 q2 . The goal is
then to find a sequence of airports terminating at the last airport that minimizes the sum of the
penalties. We now define the LWS problem formally.
Problem 1.1 (LWS). We are given a sequence of n ` 1 data items x0 , . . . , xn , weights wi,j P
t´W, . . . , W u Y t8u for every pair i ă j of indices where the weights may also be functions of the
values of data items xi , and an arbitrary function g : Z Ñ Z. The LWS problem is to determine
T rns which is defined by the following DP formulation.
T r0s “ 0,

T rjs “ min gpT risq ` wi,j
0ďiăj

2

for j “ 1, . . . , n.

(1)

To formulate airplane refueling as an LWS problem, we let xi be the location of the i’th airport,
g be the identity function, and wi,j “ pxj ´ xi ´ kq2 .
In the definition of the LWS problem, we did not specify the encoding of the problem (in
particular, the type of data items and the representation of the weights wi,j ) so we can capture a
larger variety of problems: it not only encompasses classical problems such as the pretty printing
problem due to Knuth and Plass [31], the airplane refueling problem [25] and the longest increasing
subsequence (LIS) [18], but also the unbounded subset sum problem [36, 10], a more general coin
change problem that is effectively equivalent to the unbounded knapsack problem, 1-dimensional
k-means clustering problem [24], finding longest R-chains (for an arbitrary binary relation R), and
many others (for a more complete list of problems definitions, see Section 2).
Under mild assumptions on the encoding of the data items and weights, any instantiation of the
LWS problems can be solved in time Opn2 q using (1) for determining the values T rjs, j “ 1, . . . , n in
time Opnq each. However, the best known algorithms for the LWS problems differ quite significantly
in their time complexity. Some problems including the pretty printing, airline refueling and LIS
turn out to be solvable in near-linear time, while no subquadratic algorithms are known for the
unbounded knapsack problem or for finding the longest R-chain.
The main goal of the paper is to investigate the optimality of the LWS DP formulation for
various problems by proving conditional lower bounds.
Succinct LWS instantiations. In the extremely long presentation of an LWS problem, the
weights wi,j are given explicitly. This is however not a very interesting case from a computational
point of view, as the standard DP formulation takes linear time (in the size of the input) to
compute T rns. In the example of the airplane refueling problem the size of the input is only Opnq
assuming that the values of the data items are bounded by some polynomial in n. For such succinct
representations, we ask if the quadratic-time algorithm based on the standard LWS DP formulation
is optimal. Our approach is to study several natural succinct versions of the LWS problem (by
specifying the type of data items and the weight function1 ) and determine their complexity. We
refer to Section 2 for examples of succinct instantiations of the LWS problem.
Our Contributions and Results. The main contributions of our paper include a general framework for reducing succinct LWS instantiations to what we call the core problems and proving
subquadratic equivalences between them. The subquadratic equivalences are interesting for two
reasons. First, they allows us to conclude conditional lower bounds for certain LWS instantiations,
where previously no lower bounds are known. Second, subquadratic (or more general fine-grained)
equivalences are more useful since they let us translate hardness as well as easiness results.
Our results include tight (up to subpolynomial factors) conditional lower bounds for several
LWS instantiations with succinct representations. These instantiations include the coin change
problem, low rank versions of the LWS problem, and the longest subchain problems. Our results
are somewhat more general. We propose a factorization of the LWS problem into a core problem
and a fine-grained reduction from the LWS problem to the core problem. The idea is that core
problems (which are often well-know problems) capture the hardness of the LWS problem and act
as a potential barrier for more efficient algorithms. While we do not formally define the notion of
a core problem, we identify several core problems which share several interesting properties. For
example, they do not admit natural DP formulations and are easy to parallelize. In contrast, the
quadratic-time DP formulation of LWS problems requires the entries T ris to be computed in order,
suggesting that the general problem might be inherently sequential.
1 In

all our applications, the function g is the trivial identity function.

3

The reductions between LWS problems and core problems involve a natural intermediate problem, which we call the Static-LWS problem. We first reduce the LWS problem to the Static-LWS
problem in a general way and then reduce the Static-LWS problem to a core problem. The first
reduction is divide-and-conquer in nature and is inherently sequential. The latter reduction is specific to the instantiation of the LWS problem. The Static-LWS problem is easy to parallelize and
does not have a natural DP formulation. However, the problem is not necessarily a natural problem.
The Static-LWS problem can be thought of as a generic core problem, but it is output-intensive.
In the other direction, we show that many of the core problems can be reduced to the corresponding LWS instantiations thus establishing an equivalency between LWS instantiations and their core
problems. This equivalence enables us to translate both the hardness and easiness results (i.e., the
subquadratic-time algorithms) for the core problems to the corresponding LWS instantiations.
The first natural succinct representation of the LWS problem we consider is the low rank
LWS problem, where the weight matrix W “ pwi,j q is of low rank and thus representable as
W “ L ¨ R where L and RT are pn ˆ nop1q q-matrices. For this low rank LWS problem, we identify
the minimum inner product problem (MinInnProd) as a suitable core problem. It is only natural
and not particularly surprising that MinInnProd can be reduced to the low-rank LWS problem
which shows the SETH-hardness of the low-rank LWS problem. The other direction is more
surprising: Inspired by an elegant trick of Vassilevska Williams and Williams [40], we are able to
show a subquadratic-time reduction from the (highly sequential) low-rank LWS problem to the
(highly parallel) MinInnProd problem. Thus, the very compact problem MinInnProd problem
captures exactly the complexity of the low-rank LWS problem (under subquadratic reductions).
We also show that the coin change problem is subquadratically equivalent to the pmin, `qconvolution problem. In the coin change problem, the weight matrix W is succinctly given as a
Toeplitz matrix. At this point, the conditional hardness of the pmin, `q-convolution problem is
unknown. The quadratic-time hardness of the pmin, `q-convolution problem would be very interesting, since it is known that the pmin, `q-convolution problem is reducible to the 3-sum problem
and the APSP problem, However, recent results give surprising subquadratic-time algorithms for
special cases of pmin, `q-convolution [14]. If these subquadratic-time algorithms extend to the
general pmin, `q-convolution problem, our equivalence result also provides a subquadratic-time
algorithm for the coin change problem and the closely related unbounded knapsack problem. As a
corollary, our reductions also give a quadratic-time pmin, `q-convolution-based lower bound for
the bounded case of knapsack.
We next consider the problem of finding longest chains: here, we search for the longest subsequence (chain) in the input sequence such that all adjacent pairs in the subsequence are contained in some binary relation R. We show that for any binary relation R satisfying certain
conditions the chaining problem is subquadratically equivalent to a corresponding (highly parallel) selection problem. As corollaries, we get equivalences between finding the longest chain of
nested boxes (NestedBoxes) and VectorDomination as well as between finding the longest subset chain (SubsetChain) and the orthogonal vectors (OV) problem. Interestingly, these results
have algorithmic implications: known algorithms for low-dimensional vector domination and lowdimensional orthogonal vectors translate to faster algorithms for low-dimensional NestedBoxes
and SubsetChain for small universe size.
Table 1 lists the LWS succinct instantiations (as discussed above) and their corresponding core
problems. All LWS instantiations and core problems considered in this paper are formally defined
in Section 2.
Finally, we revisit classic problems including the longest increasing subsequence problem, the

4

Name
Coin Change

LowRankLWS
R-chains

NestedBoxes
SubsetChain

Weights
Equivalent Core
Reference
Toeplitz matrix:
pmin, `q-convolution Theorem 4.8
wi,j “ wj´i
Remark: Subquadratically equivalent to UnboundedKnapsack
Low rank representation:
MinInnProd
Theorem 3.9
wi,j “ xσi , µj y
matrix induced by R:
SelectionpRq
Theorem 5.3
wi,j “ wj if Rpxi , xj q and 8 o/w
Theorem 5.7
Remark: Result below are corollaries.
wi,j “ ´1 if Bj contains Bi
VectorDomination
wi,j “ ´1 if Si Ď Sj
OrthogonalVectors
Table 1: Summary of our results

Name
Longest Increasing
Subsequence
Unbounded Subset
Sum
Concave 1-dim. DP

Weights
matrix induced by Ră :
wi,j “ ´1 if xi ă xj
Toeplitz t0, 8u matrix:
wi,j “ wj´i P t0, 8u
concave matrix:
wi,j ` wi1 ,j 1 ď wi1 ,j ` wi,j 1
for i ď i1 ď j ď j 1

Õpnq-time reducible to
Sorting
Convolution
SMAWK problem

Reference
[18],
Observation 2
[10],
Observation 3
[25, 21, 38],
Observation 4

Table 2: Near-linear time algorithms following from the proposed framework.
unbounded subset sum problem and the concave LWS problem and analyze the Static-LWS
instantiations to immediately infer that the corresponding core problem can be solved in near-linear
time. Table 2 gives an overview of some of the problems we look at in this context.
Related Work. LWS has been introduced by Hirschberg and Lamore [25]. If the weight function
satisfies the quadrangle inequality 2 formalized by Yao [41], one obtains the concave LWS problem, for
which they give an Opn log nq-time algorithm. Subsequently, improved algorithms solving concave
LWS in time Opnq were given [38, 21]. This yields a fairly large class of weight functions (including,
e.g., the pretty printing and airplane refueling problems) for which linear-time solutions exist. To
generalize this class of problems, further works address convex weight functions3 [20, 35, 30] as well
as certain combinations of convex and concave weight functions [16] and provide near-linear time
algorithms. For a more comprehensive overview over these algorithms and further applications of
the LWS problem, we refer the reader to Eppstein’s PhD thesis [17].
Apart from these notions of concavity and convexity, results on the succinct LWS problems
are typically more scattered and problem-specific (see, e.g., [18, 31, 10, 24]; furthermore, a closely
related recurrence to (1) pops up when solving bitonic TSP [15]). An exception to this rule is a
study of the parallel complexity of LWS [22].
Organization. Section 3 contains the result on low-rank LWS. This is also where we formally
2 See
3A

Section 2 for definitions.
weight function is convex if it satisfies the inverse of the quadrangle inequality.

5

introduce Static-LWS. Section 4 proves the subquadratic equivalence of the coin change problem
and pmin, `q-convolution, while Section 5 discusses chaining problems and their corresponding
selection (core) problem. Our results on near-linear time algorithms are given in Section 6.

2

Preliminaries

In this section, we state our notational conventions and list the main problems considered in this
work.
Problem A subquadratically reduces to problem B, denoted A ď2 B, if for any ε ą 0 there is
a δ ą 0 such that an algorithm for B with time Opn2´ε q implies an algorithm for A with time
Opn2´δ q. We call the two problems subquadratically equivalent, denoted A ”2 B, if there are
subquadratic reductions both ways.
We let rns :“ t1, . . . , nu. When stating running time, we use the notation Õp¨q to hide polylogarithmic factors. For a problem P , we write T P for its time complexity. We generally assume
the word-RAM model of computation with word size w “ Θplog nq. For most problems defined in
this paper, we consider inputs to be integers in the range t´W, . . . , W u where W fits in a constant
number of words4 . For vectors, we use d for the dimension and generally assume d “ nop1q .

Core Problems and Hypotheses. One of the most popular problems in the field of quadratictime conditional hardness is the following problem.

Problem 2.1 (Orthogonal Vectors (OV)). Given a1 , . . . , an , b1 , . . . , bn P t0, 1ud, determine if there
is a pair i, j satisfying xai , bj y “ 0.
Recall that for OV (and the related problems below) we assume d “ nop1q . Thus the naive
algorithm solves OV in time Opn2 ¨ dq “ Opn2`op1q q.
One of the reasons for the popularity of OV is its surprising connection to the Strong Exponential
Time Hypothesis (SETH) [27]: It states that for every ε ą 0 there is a k, such that the k-SAT
problem requires time Ωp2p1´εqn q. By an elegant reduction due to Williams [39], OV is quadratictime SETH-hard, i.e., there is no algorithm with running time time Opn2´ε q for any ε ą 0 unless
SETH is false.
We consider the following generalizations of OV.
Problem 2.2 (MinInnProd). Given a1 , . . . , an , b1 , . . . , bn P t´W, . . . , W ud and a natural number
r P Z, determine if there is a pair i, j satisfying xai , bj y ď r.
Problem 2.3 (AllInnProd). Given a1 , . . . , an P t´W, . . . , W ud and b1 , . . . , bn P t´W, . . . , W ud ,
determine for all j P rns, the value miniPrns xai , bj y.
Problem 2.4 (VectorDomination). Given a1 , . . . , an , b1 , . . . , bn P t´W, . . . , W ud determine if
there is a pair i, j such that ai ď bj component-wise.
Problem 2.5 (SetContainment). Given sets a1 , . . . , an , b1 , . . . , bn Ď rds given as vectors in
t0, 1ud determine if there is a pair i, j such that ai Ď bj .
Note that SetContainment is a special case of VectorDomination and computationally
equivalent to OV, as xa, by “ 0 if and only if a Ď b (in this slight misuse of notation we think of
the Boolean vectors a, b as sets and let b̄ denote the complement of b).
4 For

op1q

the purposes of our reductions, even values up to W “ 2n

6

would be fine.

Since subquadratic solutions to any of these problems trivially give a subquadratic solution to
OV, these problems are also quadratic-time SETH-hard. However, the converse does not necessarily hold. In particular, the strongest currently known upper bounds differ: while for OV and
SetContainment for small dimension d “ c ¨ logpnq, an n2´1{Oplog cq -time algorithm is known [4],
2
for VectorDomination the best known algorithm runs only in time n2´1{Opc log cq [26, 13].
Another fundamental quadratic-time problem is pmin, `q-convolution, defined below.
Problem 2.6 (pmin, `q-convolution). Given vectors a “ pa0 , . . . , an´1 q, b “ pb0 , . . . , bn´1 q P
t´W, . . . , W un , determine its pmin, `q-convolution a ˚ b defined by
pa ˚ bqk “

min

0ďi,jăn:i`j“k

ai ` b j

for all 0 ď k ď 2n ´ 2.

As opposed to the classical convolution, which we denote as a f b, solvable in time Opn log nq
using FFT, no strongly subquadratic algorithm for pmin, `q-convolution is known. Compared to
OV, we have less support for believing that no Opn2´ε q-time algorithm for pmin, `q-convolution
exists. In particular, interesting special cases can be solved in subquadratic-time [14] and there
are subquadratic-time co-nondeterministic and nondeterministic algorithms [8, 12]. At the same
time, breaking this long-standing quadratic-time barrier is a prerequisite for progress on refuting
the 3SUM and APSP conjectures. This makes it an interesting target particularly for proving
subquadratic equivalences, since both positive and negative resolutions of this open question appear
to be reasonable possibilities.
Succinct LWS Versions and Applications. In the definition of LWS (Problem 1.1) we did not
fix the encoding of the problem (in particular, the choice of data items, as well the representation
of the weights wi,j and the function g). Assuming that g can be determined in Õp1q and that
W “ polypnq, this problem can naturally be solved in time Õpn2 q, by evaluating the central
recurrence (1) for each j “ 1, . . . , n – this takes Õpnq time for each j, since we take the minimum
over at most n expressions that can be evaluated in time Õp1q by accessing the previously computed
entries T r0s, . . . , T rj ´ 1s as well as computing g. In all our applications, g will be the identity
function, hence it will suffice to define the type of data items and the corresponding weight matrix.
Throughout this paper, whenever we fix a representation of the weight matrix W “ pwi,j qi,j , we
denote the corresponding problem LWSpWq.
In the remainder of this section, we list problems considered in this paper that can be expressed
as an LWS instantiations. At this point, we typically give the most natural formulations of these
problems – the corresponding definitions as LWS instantiations are given in the corresponding
sections.
We start off with a natural succinct “low-rank” version of LWS.
Problem 2.7 (LowRankLWS). LowRankLWS is the LWS problem where the weight matrix
W is of rank d ! n. The input is given succinctly as two matrices A and B, which are pn ˆ dq- and
pd ˆ nq-matrices respectively, and W “ A ¨ B.
Alternatively, LowRankLWS may be interpreted in the following way: There are places
0, 1, . . . , n, each of which is equipped with an in- and an out-vector. The cost of going from place
i to j is then defined as the inner product of the out-vector of i with the in-vector of j, and the
task is to compute the minimum-cost monotonically increasing path to reach place n starting from
0. In Section 3, we prove subquadratic equivalence to MinInnProd.
We consider the following coin change problem and variations of Knapsack.
7

Problem 2.8 (CC). We are given a weight sequence w “ pw1 , . . . , wn q with wi P t´W, . . . , W u Y
t8u, i.e., the
ř the weight of the multiset of denominations I
ř coin with value i has weight wi . Find
such that iPI i “ n and the sum of the weights iPI wi is minimized.

Problem 2.9 (UnboundedKnapsack). We are given a sequence of profits p “ pp1 , . . . , pn q with
pi P t0, 1, . . . , W u, ř
i.e., the item of size i has profit
ř pi . Find the total profit of the multiset of
indices I such that iPI i ď n and the total profit iPI pi is maximized.

Note that if we replace multiset by set in the above definition, we obtain the bounded version
of the problem, which we denote by Knapsack.
We remark that our perspective on CC and UnboundedKnapsack (as well as UnboundedSubsetSum below) using LWS is slightly different than many classical accounts of Knapsack: We
define the problem size as the budget size instead of the number of items, thus our focus is on
pseudo-polynomial time algorithms for the typical formulations of these problems.
Note that we state the coin change problem as allowing positive or negative weights, but UnboundedKnapsack only allows for positive profits. Furthermore, CC is a minimization problem,
while UnboundedKnapsack is a maximization problem. For CC, the maximization problem is
trivially equivalent as we can negate all weights. Furthermore, we can freely translate the range of
the weights in the coin change problem by defining wi1 “ i ¨ M ` wi for all i and sufficiently large or
small M . The most significant difference between CC and UnboundedKnapsack is that for CC
the indices have to sum to exactly n, while for UnboundedKnapsack n is only an upper bound.
We will encounter an important generalization of the two problems above, defined as follows.
Problem 2.10 (oiCC). The output-intensive version of CC is to determine, given an input to
CC, the weight of the optimal multiset such that the denominations sum up to j for all 1 ď j ď n.
It is easy to see that oiCC is at least as hard as both CC and UnboundedKnapsack. We
will relate the above Knapsack variants to pmin, `q-convolution in Section 4.
In Section 6, we will revisit near-linear time algorithms for the following special case of the coin
change problem.
Problem 2.11 (UnboundedSubsetSum). Given a subset S Ď rns, determine whether there is a
multiset of elements of S that sums up to exactly n.
We also discuss problems where the goal is to find the longest chain among data items, where
the notion of a chain is defined by some binary relation R. We first give the definition of the general
problem which is parameterized by R.
Problem 2.12 (ChainLWS). Fix a set X of objects and a relation R Ď X ˆ X. The Weighted
Chain Least-Weight Subsequence Problem for R, denoted ChainLWSpRq, is the following problem:
Given data items x0 , . . . , xn P X, weights w1 , . . . , wn´1 P t´W, . . . , W u, find the weight of the
increasing sequence i0 “ 0 ă i1 ă i2 ă . . . ă ř
ik “ n such that for all j with 1 ď j ď k the pair
k´1
pxij´1 , xij q is in the relation R and the weight j“1 wij is minimized.
The following problems are specializations of this problem for different relations.

Problem 2.13 (NestedBoxes). Given n boxes in d dimensions, given as non-negative, d-dimensional
vectors pb1 , . . . , bn q, find the longest chain such that each box fits into the next (without rotation).
We say box that box a fits into box b if for all dimensions 1 ď i ď d, ai ď bi .
8

Problem 2.14 (SubsetChain). Given n sets from a universe U of size d, given as Boolean,
d-dimensional vectors pb1 , . . . , bn q, find the longest chain such that each set is a subset of the next.
Note that SubsetChain is a special case of NestedBoxes.
Problem 2.15 (LIS). Given a sequence of n integers x1 , . . . , xn , compute the length of the longest
subsequence that is strictly increasing.
Finally, we will briefly discuss the following class of LWS problems that turn out to be solvable
in near-linear time.
Problem 2.16 (ConcLWS). Given an LWS instance in which the weights satisfy the quadrangle
inequality
for i ď i1 ď j ď j 1 ,
wi,j ` wi1 ,j 1 ď wi1 ,j ` wi,j 1
solve it. The weights are not explicitly given, but each wi,j can be queried in constant time.

3

LowRankLWS

Let us first analyze the following canonical succinct representation of a low-rank weight matrix
W “ pwi,j qi,j : If W is of rank d ! n, we can write it more succinctly as W “ A ¨ B, where A and B
are pn ˆ dq- and pd ˆ nq matrices, respectively. We can express the resulting natural LWS problem
equivalently as follows.
Problem 3.1 (LowRankLWS). We define the following LWS instantiation LowRankLWS “
LWSpWLowRankq.
Data items: out-vectors µ0 , . . . , µn´1 P t´W, . . . , W ud , in-vectors σ1 , . . . , σn P t´W, . . . , W ud
Weights: wpi, jq “ xµi , σj y for 0 ď i ă j ď n
In this section, we show that this problem is equivalent, under subquadratic reductions, to the
following non-sequential problem.
Problem 3.2 (MinInnProd). Given a1 , . . . , an , b1 , . . . , bn P t´W, . . . , W ud and a natural number
r P Z, determine if there is a pair i, j satisfying xai , bj y ď r.
We first give a simple reduction from MinInnProd that along the way proves quadratic-time
SETH-hardness of LowRankLWS.
Lemma 3.3. It holds that T MinInnProdpn, d, W q ď T LowRankLWSp2n ` 1, d ` 2, dW q ` Opndq.
Proof. Given a1 , . . . , an , b1 , . . . , bn P t´W, . . . , W ud , let O “ p0, . . . , 0q P Zd be the all-zeroes vector
and define the following in- and out-vectors
µ0 “ pdW, 0, Oq,
µi “ p0, dW, ai q,

µn`j “ p0, 0, Oq,

σ2n`1 “ pdW, dW, Oq,
σi “ p0, 0, Oq,

σn`j “ pdW, 0, bj q,

for i “ 1, . . . , n,

for j “ 1, . . . , n.

To prove correctness, we show that in the constructed LowRankLWS instance, we have T r2n`1s “
mini,j xai , bj y, from which the results follows immediately. Inductively, we have T ris “ 0 for i “
1, . . . , n, since xµi1 , σi y “ 0 for all 0 ď i1 ă i ď n. Similarly, for j “ 1, . . . , n one can inductively show
9

that T rn ` js “ min1ďiďn,j 1 ďj xai , bj 1 y, using that xµ0 , σn`j y “ pdW q2 ě maxi,j xai , bj y, xµi , σn`j y “
xai , bj y and xµn`j 1 , σn`j y “ 0 for all 1 ď i, j ď n and j 1 ď j. Finally, using (1) xµ0 , σ2n`1 y “
pdW q2 ě maxi,j xai , bj y and T r0s “ 0, (2) xµi , σ2n`1 y “ pdW q2 ě maxi,j xai , bj y and T ris “ 0 for
i “ 1, . . . , n and (3) xµn`j , σ2n`1 y “ 0 and T rn ` js “ min1ďiďn,1ďj 1 ďj xai , bj 1 y for all j “ 1, . . . , n,
we can finally determine T r2n ` 1s “ mini,j xai , bj y.
To prove the other direction, we will give a quite general approach to compute the sequential
LWS problem by reducing to a natural static subproblem of LWS:
Problem 3.4 (Static-LWSpWq). Fix an instance of LWSpWq. Given intervals I :“ ta`1, . . . , a`
N u and J :“ ta`N `1, . . . , a`2N u, together with the correctly computed values T ra`1s, . . . , T ra`
N ` 1s, the Static Least-Weight Subsequence Problem (Static-LWS) asks to determine
T 1 rjs :“ min T ris ` wi,j

for all j P J.

iPI

Lemma 3.5 (LWSpWq ď2 Static-LWSpWq). For any choice of W, if Static-LWSpWq can be
solved in time OpN 2´ε q for some ε ą 0, then LWSpWq can be solved in time Õpn2´ε q.
Proof. In what follows, we fix LWS as LWSpWq and Static-LWS as Static-LWSpWq.
We define the subproblem Spti, . . . , ju, pti , . . . , tj qq that given an interval spanned by 1 ď i ď
j ď n and values tk “ min0ďk1 ăi T rk 1 s ` wk1 ,k for each point k P ti, . . . , ju, computes all values
T rks for k P ti, . . . , ju. Note that a call to Sprns, pw0,1 , . . . , w0,n qq solves the LWS problem, since
T r0s “ 0 and thus the values of tk , k P rns are correctly initialized.
We solve S using Algorithm 1. We briefly argue correctness, using the invariant that tk “
Algorithm 1 Reducing LWS to Static-LWS
1: function S(ti, . . . , ju, pti , . . . , tj q)
2:
if i “ j then
3:
return T ris Ð ti
4:
m Ð r j´i
2 s
5:
pT ris, . . . , T ri ` m ´ 1sq Ð Spti, . . . , i ` m ´ 1u, pti , . . . , ti`m´1 qq
6:
solve Static-LWS on the subinstance given by I :“ ti, . . . , i`m´1u and J :“ ti`m, . . . , i`
2m ´ 1u:
7:
Ź obtains values T 1 rks “ miniďk1 ăi`m T rk 1 s ` wk1 ,k for k “ i ` m, . . . , i ` 2m ´ 1.
1
8:
tk Ð minttk , T 1 rksu for all k “ i ` m, . . . , i ` 2m ´ 1.
9:
pT ri ` ms, . . . , T ri ` 2m ´ 1sq Ð Spti ` m, . . . , i ` 2m ´ 1u, pt1i`m , . . . , t1i`2m´1 qq
10:
if j “ i ` 2m then
11:
T rjs :“ minttj , miniďkăj T rks ` wk,j u.
12:
return pT ris, . . . , T rjsq
min0ďk1 ăi T rk 1 s ` wk1 ,k in every call to S. If S is called with i “ j, then the invariant yields
ti “ min0ďk1 ăi T rk 1 s ` wk1 ,i “ T ris, thus T ris is computed correctly. For the call in Line 5, the
invariant is fulfilled by assumption, hence the values pT ris, . . . , T ri ` m ´ 1sq are correctly computed.
For the call in Line 9, we note that for k “ i ` m, . . . , i ` 2m ´ 1, we have
t1k “ minttk , T 1 rksu “ mint min
T rk 1 s ` wk1 ,k ,
1
0ďk ăi

min

iďk1 ăi`m

10

T rk 1 s ` wk1 ,k u “

min

0ďk1 ăi`m

T rk 1 s ` wk1 ,k .

Hence the invariant remains satisfied. Thus, the values pT ri ` ms, . . . , T ri ` 2m ´ 1sq are correctly
computed. Finally, if j “ i ` 2m, we compute the remaining value T rjs correctly, since tj “
min0ďkăi T rks ` wk,j by assumption.
To analyze the running time T S pnq of S on an interval of length n :“ j ´ i ` 1, note that
each call results in two recursive calls of interval lengths at most n{2. In each call, we need an
additional overhead that is linear in n and T Static-LWS pn{2q. Solving the corresponding recursion
T S pnq ď 2T S pn{2q ` T Static-LWS pn{2q ` Opnq, we obtain that an OpN 2´ε q-time algorithm StaticLWS, with 0 ă ε ă 1 yields T LWSpnq ď T S pnq “ Opn2´ε q. Similarly, an OpN logc N q-time
algorithm for Static-LWS would result in an Opn logc`1 nq-time algorithm for LWS.
For the special case of LowRankLWS, it is straightforward to see that the static version boils
down to the following natural reformulation.
Problem 3.6 (AllInnProd). Given a1 , . . . , an P t´W, . . . , W ud and b1 , . . . , bn P t´W, . . . , W ud ,
determine for all j P rns, the value miniPrns xai , bj y. (Again, we typically assume that d “ nop1q and
op1q
W “ 2n .)
Lemma 3.7 (Static-LWSpWLowRank q ď2 AllInnProd). We have
T Static-LWSpWLowRank q pn, d, W q ď T AllInnProdpn, d ` 1, nW q ` Opndq.
Proof. Consider Static-LWSpWLowRankq. Let I “ ta ` 1, . . . , a ` N u, J “ ta ` N ` 1, . . . , a `
2N u and values T ra ` 1s, . . . , T ra ` N s be given. To determine T 1 rjs “ miniPI T ris ` wi,j for all
j P J, it is sufficient to solve AllInnProd on the vectors aa`1 , . . . , aa`N , ba`N `1 , . . . , ba`2N P
tnW, . . . , nW ud`1 defined by
ai :“ pµi , T risq

bj “ pσj , 1q,

for all i P I, j P J,

since then xai , bj y “ T ris ` xµi , σj y “ T ris ` wi,j . The claim immediately follows (note that
|T ris| ď nW ).
Finally, inspired by an elegant trick of [40], we reduce AllInnProd to MinInnProd.
Lemma 3.8 (AllInnProd ď2 MinInnProd). We have
?
T AllInnProdpn, d, W q ď Opn ¨ T MinInnProdp n, d ` 3, ndW 2 q ¨ log2 nW q.
Proof. We first observe that we can tune MinInnProd to also return a witness pi, jq with xai , bj y ď
r, if it exists. To do so, we replace each ai by the pd` 2q-dimensional vector a1i “ pai ¨n, pi ´ 1qn, ´1q
and similarly, each bj by the pd ` 2q-dimensional vector b1j “ pbj ¨ n, ´1, j ´ 1q. Clearly, we have
xa1i , b1j y “ xai , bj yn2 ´ pi ´ 1qn ´ pj ´ 1q. Thus xa1i , b1j y ď rn2 if and only if xai , bj y ď r since i, j P rns.
Using a binary search over r, we can find mini,j xa1i , b1j y, from whose precise value we can determine
also a witness, if it exists. Thus the running time witpn, d, W q for finding such a witness is bounded
by Oplog nW q ¨ T MinInnProdpn, d ` 2, nW q.
To solve AllInnProd, i.e., to compute pj :“ miniPrns xai , bj y for all j P rns, we employ a
parallel binary search. Consider in particular the following problem P: Given arbitrary r1 , . . . , rn ,
determine for all j P rns whether there exists i P rns
? such that xai , bj y ď rj . We will show below
that this problem can be solved in time Opn ¨ witp n, d ` 1, dW 2 qq. The claim then follows, since
starting from feasible intervals R1 “ ¨ ¨ ¨ “ Rn “ t´dW 2 , . . . , dW 2 u satisfying pj P Rj , we can
11

halve the sizes of each interval simultaneously by a single call to P. Thus, after OplogpdW qq
calls, the true
in the
T AllInnProdpn, d, wq “
? time guarantee
? values pj 2can be determined, resulting
MinInnProd
2
p n, d ` 3, ndW q log2 pnW qq, as desired.
Opn ¨ witp n, d ` 1, dW q ¨ logpdW qq “ Opn ¨ T
We complete the proof of the claim by showing how to solve P. Without loss of generality, we
2
can assume that rj ď dW?
for every j, since no larger inner product
may exist. We group the
?
vectors a1 , . . . , an in g :“ r ns groups A1 , . . . , Ag of size at most n each, and do the same for the
vectors b1 , . . . , bn to obtain B1 , . . . , Bg . Now, we iterate over all pairs of groups Ak , Bℓ , k, ℓ P rgs:
For each such choice of pairs, we do the following process. For each vector ai P Ak , we define
the pd ` 1q-dimensional vector ãi :“ pai , ´1q and for every vector bj P Bℓ , we define b̃j :“ pbj , rj q.
In the obtained instance tãi uaPAk , tb̃j ubPBℓ , we try to find some i, j such that xãi , b̃j y ď 0, which
is equivalent to xai , bj y ď rj . If we succeed in finding such a witness, we delete bj and b˜j (but
remember its witness) and repeat finding witnesses (an deleting the witnessed bj ) until we cannot
find any. The process then ends and we turn to the next pair of groups.
It is easy to see that for all j P rns, we have xai , bj y ď rj for some i P rns if and only if the
above process finds a witness for bj at some point. To argue about the running time, we charge the
running time of every call to witness finding to either (1) the pair Ak , Bℓ , if the call is the first call
in the process for Ak , Bℓ , or (2) to bj , if the call resulted from finding a witness for bj in the previous
call. Note that every pair Ak , Bℓ is charged by exactly one call and every bj is charged by at most
one call (since in after a witness for bj is found, we delete bj and no further
bj can be
? witness for
2
2
found). Thus
in
total,
we
obtain
a
running
time
of
at
most
pg
`
nq
¨
witp
n,
d
`
1,
dW
q
`
Opnq “
?
Opn ¨ witp n, d ` 1, dW 2 qq.
Theorem 3.9. We have LowRankLWS ”2 MinInnProd.
Proof. In Lemmas 3.3, 3.5, 3.7, and 3.8, we have proven
MinInnProd ď2 LowRankLWS “ LWSpWLowRank q
ď2 Static-LWSpWLowRank q ď2 AllInnProd ď2 MinInnProd,
proving the claim.

4

Coin Change and Knapsack Problems

In this section, we focus on the following problem related to Knapsack: Assume we are given
coins of denominations d1 , . . . , dm with corresponding weights w1 , . . . , wm and a target value n,
determine a way to represent n using these coins (where each coin can be used arbitrarily often)
minimizing the total sum of weights of the coins used. Since without loss of generality di ď n for
all i, we can assume that m ď n and think of n as our problem size. In particular, we describe the
input by weights w1 , . . . , wn where wi denotes the weight of the coin of denomination i (if no coin
with denomination i exists, we set wi “ 8). It is straightforward to see that this problem is an
LWS instance LWSpWcc q, where the weight matrix Wcc is a Toeplitz matrix.
Problem 4.1 (CC). We define the following LWS instantiation CC “ LWSpWcc q.
Data items: weight sequence w “ pw1 , . . . , wn q with wi P t´W, . . . , W u Y t8u
Weights: wi,j “ wj´i for 0 ď i ă j ď n

12

Translated into a Knapsack-type formulation (i.e., denominations are weights, weights are profits,
and the objective becomes to maximize the profit), the problem differs from UnboundedKnapsack
only in that it searches for the most profitable multiset of items of weight exactly n, instead of at
most n.
Problem 4.2 (UnboundedKnapsack). We are given a sequence of profits p “ pp1 , . . . , pn q with
pi P t0, 1, . . . , W u, ř
i.e., the item of size i has profit
ř pi . Find the total profit of the multiset of
indices I such that iPI i ď n and the total profit iPI pi is maximized.

The purpose of this section is to show that both CC and UnboundedKnapsack are subquadratically equivalent to the pmin, `q-convolution problem. Along the way, we also prove
quadratic-time pmin, `q-convolution-hardness of Knapsack. Recall the definition of pmin, `qconvolution.

Problem 4.3 (pmin, `q-convolution). Given vectors a “ pa0 , . . . , an´1 q, b “ pb0 , . . . , bn´1 q P
t´W, . . . , W un , determine its pmin, `q-convolution a ˚ b defined by
pa ˚ bqk “

min

0ďi,jăn:i`j“k

ai ` b j

for all 0 ď k ď 2n ´ 2.

As opposed to the classical convolution, which we denote as a f b, solvable in time Opn log nq
using FFT, no strongly subquadratic algorithm for pmin, `q-convolution is known. Compared to
the popular orthogonal vectors problem, we have less support for believing that no Opn2´ε q-time
algorithm for pmin, `q-convolution exists. In particular, interesting special cases can be solved in
subquadratic time [14] and there are subquadratic-time co-nondeterministic and nondeterministic
algorithms [8, 12]. At the same time, breaking this long-standing quadratic-time barrier is a prerequisite for progress on refuting the 3SUM and APSP conjectures. This makes it an interesting target
particularly for proving subquadratic equivalences, since both positive and negative resolutions of
this open question appear to be reasonable possibilities.
To obtain our result, we address two issues: (1) We show an equivalence between the problem
of determining only the value T rns, i.e., the best way to give change only for the target value n,
and to determine all values T r1s, . . . , T rns, which we call the output-intensive version. (2) We show
that the output-intensive version is subquadratic equivalent to pmin, `q-convolution.
Problem 4.4 (oiCC). The output-intensive version of CC is to determine, given an input to CC,
all values T r1s, . . . , T rns.
We first consider issue (2) and provide a pmin, `q-convolution-based lower bound for oiCC.
Lemma 4.5 (pmin, `qconv ď2 oiCC). We have T pmin,`qconv pn, W q ď T oiCCp6n, 4p2W ` 1qq `
Opnq.
Proof. We first do a translation of the input. Note that for any scalars α, β, we have pa`αq˚pb`βq “
pa ˚ bq ` α ` β. Let M :“ 2W ` 1. Without loss of generality, we may assume that
2M ď ai ď 3M
0 ď bj ď M

for all i “ 0, . . . , n ´ 1,
for all j “ 0, . . . , n ´ 1.

We now define a CC instance with a problem size n1 “ 6n and W 1 “ 4M by defining
w “ p4M qn ˝ pan´1 , . . . , a0 q ˝ p4M qn ˝ pbn´1 , . . . , b0 q ˝ p4M q2n .
13

We now claim that T r4n ` is “ pa ˚ bq2n´i for i “ 1, . . . , 2n, which immediately yields the lemma.
To do so, we will prove the following sequence of identities.
T ris “ 4M
T rn ` is “ an´i

T r2n ` is “ 4M
T r3n ` is “ bn´i

for i P rns,
for i P rns,

(2)
(3)

for i P r2ns,

(6)

for i P rns,
for i P rns,

T r4n ` is “ pa ˚ bq2n´i

(4)
(5)

In the last line, we define, for our convenience, pa ˚ bq2n´1 “ 4M (note that before, we defined only
the entries pa ˚ bqk with k ď 2n ´ 2).
For later convenience, observe that 0 ď wi ď 4M for all i P rn1 s. It is easy to see that this
implies 0 ď T ris ď 4M for i P rn1 s.
The identities in (2) are obvious.
To prove the identities in (3) inductively over i, recall that T rn ` is “ minj“1,...,n`i tT rn `
i ´ js ` wj u. Observe that T rn ` i ´ js ` wj ă 4M can only occur if j ě n ` 1 (since otherwise
wj “ 4M ), which implies n ` i ´ j ď n and T rn ` i ´ js “ 4M except for the case j “ n ` i. In
this case, we have T rn ` i ´ js ` wj “ T r0s ` wn`i “ an´i ď 4M .
To prove the identities in (4), observe that for 1 ď j ď 3n, we have wj ě 2M by assumption
mini ai ě 2M . Similarly, we have already argued that T ri1 s ě 2M for 1 ď i1 ď 2n. Thus, we can
inductively show that T r2n ` is “ mintT r0s ` w2n`i , minj“1,...,2n`i´1 T r2n ` i ´ js ` wj u “ 4M
using w2n`i “ 4M and that every sum in the inner minimum expression is at least 4M .
To prove the identities in (5), note that for T r3n ` i ´ js ` wj ă 4M to hold, we must have
either n ` 1 ď j ď 2n or 3n ` 1 ď j ď 3n ` i, since otherwise wj “ 4M . We observe that for
n ` 1 ď j ď 2n, we have wj ě mini ai ě 2M and T r3n ` i ´ js ě mini ai ě 2M . Thus, we may
assume that 3n ` 1 ď j ď 3n ` i. Note that in this case, we have T r3n ` i ´ js “ 4M except for
the case j “ 3n ` i, where we have T r3n ` i ´ js ` wj “ T r0s ` w3n`i “ bn´i ă 4M .
Finally, for the identities in (6), we might have T r4n ` is ` wj ă 4M only if n ` 1 ď j ď 2n or
3n ` 1 ď j ď 4n. First consider the case that i “ 1. We have
T r4n ` 1s “ mintw4n`1 ,

T r4n ` 1 ´ js `wj ,

min

n`1ďjď2n looooooomooooooon
“4M

min

T r4n ` 1 ´ js `wj u “ 4M.

3n`1ďjď4n looooooomooooooon
“4M

Inductively over 1 ă i ď 2n, we will prove T r4n ` is “ pa ˚ bq2n´i . By definition,
T r4n ` is “ mintw4n`i ,

min

n`1ďjď2n

T r4n ` i ´ js ` wj ,

min

3n`1ďjď4n

T r4n ` i ´ js ` wj u

T rn ` i ´ j 1 s ` bn´j 1 u
“ mintw4n`i , min
T r3n ` i ´ j 1 s ` an´j 1 , min
1
1
1ďj ďn

1ďj ďn

(7)

Note that
min

1ďj 1 ďn

T
rn ` i ´ j 1 s
loooooomoooooon

“4M for

j 1 ěi

or

`bn´j 1 “

min

maxt1,i´nuďj 1 ďminti´1,nu

an´pi´j 1 q ` bn´j 1 “ pa ˚ bq2n´i

j 1 ăi´n

where the last equation follows from noting that the choice of j 1 lets n ´ j 1 and n ´ pi ´ j 1 q range
over all admissible pairs of values in t0, . . . , n ´ 1u summing up to 2n ´ i. Similarly, we inductively
prove that
min T r3n ` i ´ j 1 s ` an´j 1 “

1ďj 1 ďn

min

maxt1,i´nuďj 1 ďminti´1,nu

14

an´pi´j 1 q ` bn´j 1 “ pa ˚ bq2n´i ,

since an´j 1 ě 2M and T r3n ` i ´ j 1 s ě 2M whenever j 1 ě i or j 1 ă i ´ n (where the last
regime uses T r4n ` i1 s “ pa ˚ bq2n´i1 ě 2M inductively for i1 ă i). Finally, since pa ˚ bq2n´i ď
pmaxi ai q ` pmaxj bj q ď 4M , we can simplify (7) to T r4n ` is “ pa ˚ bq2n´i .
Using the notion of Static-LWS, the other direction is straight-forward.
Lemma 4.6. We have oiCC ď2 Static-LWSpWcc q ď2 pmin, `qconv.
Proof. In Lemma 3.5, we have in fact reduced the output-intensive version of LWSpWq to our
static problem Static-LWSpWq, thus specialized to the coin change problem, we only need to
show that Static-LWSpWcc q subquadratically reduces to pmin, `q-convolution. Consider an
input instance to Static-LWS given by I “ ta ` 1, . . . , a ` N u, J “ ta ` N ` 1, . . . , a ` 2N u and
values T ris, i P I. Defining M :“ 2W ` 1 and the vectors
N times
hkkkkkkikkkkkkj
u :“ pnM, T ra ` 1s, . . . , T ra ` N s, nM, . . . , nM q,
v :“ pnM, w1 , . . . , w2N q,

we have pu ˚ vqN `k “ mini“1,...,N T ra ` is ` wN `k´i “ T 1 ra ` N ` ks for all k “ 1, . . . , N , thus
a pmin, `q-convolution of two p2n ` 1q-dimensional vectors solves Static-LWSpWcc q, yielding
the claim.
The last two lemmas resolve issue (2). We proceed to issue (1) and show that the outputintensive version is subquadratically equivalent to both CC and UnboundedKnapsack that only
ask to determine a single output number. We introduce the following notation for our convenience:
Recall that
ř weight wi denotes the weight of a coin of denomination i. For a multiset S Ď rns, we let
dpSq :“ iPS i denote its total denomination, i.e., sum of the denomination of theřcoins in S (where
multiples uses of the same coin is allowed, since S is a multiset). We let wpSq :“ iPS w
ři denote the
weight of the multiset. Analogously, when considering a Knapsack instance, ppSq “ i pi denotes
the total profit of the item (multi)set S.
It is trivial to see that UnboundedKnapsack ď2 oiCC. Furthermore, we can give the following
simple reduction from CC to UnboundedKnapsack.
Oberservation 1 (CC ď2 UnboundedKnapsack ď2 oiCC). We have
T CC pn, W q ď T UnboundedKnapsackpn, nW q ` Opnq and T UnboundedKnapsackpn, W q ď T oiCCpn, W q `
Opnq.
Proof. Given a CC instance, for every weight wi ă 8, we create an item of size i and profit
pi :“ i ¨ M ´ wi in our resulting UnboundedKnapsack instance for a sufficiently large constant
M ě nW . This way, all profits are positive and every multiset S whose sizes sum up to B has a profit
of ppSq “ B ¨ M ´ wpSq. Since M ě nW ě maxS,dpSqďn |wpSq|, this ensures that the maximumprofit multiset of total size/denomination at most n has a total size/denomination of exactly n.
Thus, the optimal multiset S ˚ has profit pps˚ q “ n ¨ M ´ minS:dpSq“n wpSq “ n ¨ M ´ T rns, from
which we can derive T rns, as desired.
Given an UnboundedKnapsack instance, we define for every item of size i and profit pi
the corresponding weight wi “ ´pi in a corresponding CC instance. It remains to compute all
T r1s, . . . , T rns in this instance and determining their minimum, concluding the reduction.

15

The remaining part is similar in spirit to Lemma 3.8: Somewhat surprisingly, the same general
approach works despite the much more sequential nature of the Knapsack/CoinChange problem –
this sequentiality can be taken care of by a more careful treatment of appropriate subproblems that
involves solving them in a particular order and feeding them with information gained during the
process.
In what follows, to clarify which instance is currently considered, we let T I denote the T -table of
the (oi)CC LWS problem (see Problem 1.1) corresponding to instance I. Dropping the superscript
always refers to T I .
?
Lemma 4.7 (oiCC ď2 CC). We have that T oiCCpn, W q ď OplogpnW q ¨ n ¨ T CC p24 n, 3n2 W qq.
?
Proof. Let I be an oiCC instance. To define our subproblems, we set N :“ r ns and define
N ranges W1 :“ t1, . . . , N u, . . . , WN :“ tpN ´ 1qN ` 1, . . . , N 2 u. To determine all T ris “
minS:dpSq“i wpSq, we will compute T ris for all i P Wj successively over all j “ 1, . . . , N . The case
of j “ 1 and j “ 2 can be computed by the naive algorithm in time OpN 2 q “ Opnq. Consider
now any fixed j ě 3 and assume that all values T ris for i P Wj 1 with j 1 ă j have already been
computed. We employ a parallel binary search. For every i P Wj , we set up a feasible range Ri
initialized to t´nW, . . . , nW u. We will maintain the invariant that T ris P Ri and will halve the
size of all feasible ranges Ri , i P Wj simultaneously using a small number of calls to the following
problem PpM, W̄ q: Given an instance J for CC specified by the weights w̃1 , . . . , w̃M , as well as
values r̃1 , . . . , r̃M P t´W̄ , . . . , W̄ u Y t´8, 8u, determine whether there exists an i P rM s with
T J ris ď r̃i , and if so, also return a witness i. We will later prove that this problem can be solved in
time T P pM, W̄ q “ OpT CC p2M, 3M 2 W̄ qq. Clearly, after OplogpnW qq rounds of this parallel binary
search, the feasible ranges consists of single values, thus determining the values of all T ris for i P Wj .
Since we will show that halving all feasible ranges for range Wj takes OpN q calls to Pp12N, nW q,
and we need to determine at most N ranges W3 , . . . , WN , the total time for this process amounts
to OplogpnW qN 2 ¨ T P p12N, nW qq “ OplogpnW qN 2 ¨ T CC p24N, 3n2 W qq.
We now describe how to use P to halve the size of all feasible ranges Ri , i P Wj : we set
ri to the median of Ri and aim to determine, for all i P Wj , whether T ris ď ri , i.e., whether
some multiset S with dpSq “ i and wpSq ď ri exists. We achieve this by the following process:
For every k “ 1, . . . , j, we consider only two ranges, namely Wk “ tpk ´ 1qN ` 1, . . . , kN u and
Wj´k Y Wj´k`1 “ tpj ´ k ´ 1qN ` 1, . . . , pj ´ k ` 1qN u. Let us first consider the case k ě 2. Here,
we can define the 2N -dimensional vectors a, b with
#
wpk´1qN `ℓ for ℓ P rN s,
aℓ “
8
for ℓ ą N,
bℓ “ T rpj ´ k ´ 1qN ` ℓs

for ℓ P r2N s.

(Note that all T ris, i P Wj´k Y Wj´k`1 for k ě 2 have already been computed by assumption.) We
are interested in all those values of the pmin, `q-convolution a˚b of these vectors that correspond
to summing up some wpk´1qN `ℓ with some T rpj ´ k ´ 1qN ` ℓ1 s such that pj ´ 2qN ` ℓ ` ℓ1 P Wj .
More specifically, we aim to determine whether there is some ℓ with pa ˚ bqN `ℓ ď rpj´1qN `ℓ . To do
so, we use the reduction from pmin, `q-convolution to oiCC given in Lemma 4.5 to create an
oiCC instance J . From this instance of problem size 12N we can read off the values of a ˚ b as a
certain interval in the corresponding T J -table. Thus, we can test whether pa ˚ bqN `ℓ ď rpj´1qN `ℓ
for some ℓ using Pp12N, nW q: for every ℓ, we let i be the unique index in the T J -table representing
16

the entry pa ˚ bqN `ℓ and set r̃i :“ rpj´1qN `ℓ . For all other i1 , we set r̃i1 “ ´8, thus enforcing that
those indices will never be reported.
For the special case k “ 1, we proceed slightly differently: Here, we define the 2N -dimensional
vectors a, b with
aℓ “ T rℓs
for ℓ P r2N s
#
T rpj ´ 2qN ` ℓs for ℓ P rN s
bℓ “
8
for ℓ ą N.
(Note that all necessary T ris, i P W1 Y W2 and T ris, i P Wj´1 have already been computed by
assumption.) Analogously to above, we use Pp12N, nW q to test whether pa ˚ bqN `ℓ ď rpj´1qN `ℓ
using the reduction from pmin, `q-convolution to oiCC given in Lemma 4.5.
Once an i P Wj has been reported to satisfy T ris ď ri for some witnessing subproblem given
by the ranges Wk and Wj´k Y Wj´k`1 for some k, we set ri :“ ´8 and repeat on the same
subproblem k (analogously to the approach of Lemma 3.8). Note that for every j, we have j ď N
subproblems and at most N many indices i P Wj that can be reported. Thus, we use at most
OpN q many calls to the subproblem P.
To briefly argue correctness, note that by construction, we only determine some i with T ris ď ri
if we have found a witness. For the converse, let k be the largest index such that the optimal multiset
for i includes a coin in Wk . Then the subproblem given by the ranges Wk and Wj´k Y Wj´k`1
will give a witness. This is obvious for k ě 2. For k “ 1, note that no weight in Wk1 with k 1 ą 1 is
used in an optimal multiset for T ris P Wj . In particular, the optimal multiset S can be represented
as S “ S 1 Y S 2 , where S 1 is a multiset of total denomination i1 P Wj´1 and S 2 is a multiset of
total denomination i ´ i1 P W1 Y W2 . Thus, in the instance constructed from a, b, we will find the
witness T ris ď T ri1 s ` T ri ´ i1 s ď ri .
We finally describe how to solve PpM, W̄ q in time T CCp2M, 3M 2 W̄ q. First consider the problem
without finding a witnessing i. Let w̃1 , . . . , w̃M , r̃1 , . . . , r̃M be an instance J of PpM, W̄ q. We define
a CC instance K of problem size 2M by giving the weights
wi1 :“ w̃i
1
w2M´i

for all i P rM s,

:“ ´3M W̄ ´ r̃i

for all i P rM s.

We claim that T K r2M s ď ´3M W̄ iff the input instance to P is a yes instance: First observe that
T K r1s “ T J r1s, . . . , T K rM s “ T J rM s since the first M weights agree for both J and K. Consider
the case that there is some i P rM s with T J ris ď r̃i . Then we have T Kr2M s ď T K ris ` w2M´i “
pT J ris ´ r̃i q ´ 3M W̄ ď ´3M W̄ , as desired. Conversely, assume that all T J ris ą r̃i . We distinguish
the cases whether the optimal subsequence S uses only weights among w̃1 , . . . , w̃M or not. In the
first case, since |w̃i | ď W for i P rM s, we have that wpSq ě 2M ¨ miniPrns |w̃i | ě ´2M W̄ ą ´3M W̄ .
Otherwise, S uses exactly one weight among w̃M`1 , . . . , w̃2M . Let this weight be w̃2M´i . Then
wpSq “ T K ris ` w̃2M´i “ pT J ris ´ r̃i q ´ 3M W̄ ą ´3M W̄ since T J ris ą r̃i , yielding the claim.
Very similar to Lemma 3.8, we can now tune the above reduction to also produce a witness i
such that T J ris ď r̃i . For this, we scale all weights wi1 , i P r2M s by a factor of M and subtract
a value of i ´ 1 for every wi1 , i P rM s. It is easy to see that a yes instance K attains some value
T K r2M s “ ´κ ¨ M ´ i for some integers κ ě 3 and 0 ď i ă n, where i ` 1 is a witness for
T J ri ` 1s ď r̃i`1 , thus computing T K r2M s lets us derive a witness as well. Thus, problem P can
be solved by a single call to T CCp2M, 3M 2 W̄ q.
17

The results above prove the following theorem.
Theorem 4.8. We have pmin, `qconv ”2 CC ”2 UnboundedKnapsack. Furthermore, the
bounded version of Knapsack admits no strongly subquadratic-time algorithm unless pmin, `qconvolution can be solved in strongly subquadratic time.
Proof. Lemmas 4.5 and 4.6 prove pmin, `qconv ”2 oiCC, while Observation 1 and Lemma 4.7
establish oiCC ”2 CC ”2 UnboundedKnapsack, yielding the first claim.
The second claim follows from inspecting the proofs of Lemma 4.5, Lemma 4.7 and the first
claim of Observation 1 and observing that we only reduce to CC/Knapsack instances in which
the optimal multiset (for each total size) is always a set, i.e., uses each element at most once.

5

Chain LWS

In this section we consider a special case of of Least-Weight Subsequence problems called the Chain
Least-Weight Subsequence. This captures problems in which edge weights are given implicitly by
a relation R that determines which pairs of data items we are allowed to chain – the aim is to find
the longest chain.
An example of a Chain Least-Weight Subsequence problem is the NestedBoxes problem.
Given n boxes in d dimensions, given as non-negative, d-dimensional vectors b1 , . . . , bn , find the
longest chain such that each box fits into the next (without rotation). We say box that box a fits
into box b if for all dimensions 1 ď i ď d, ai ď bi .
NestedBoxes is not immediately a least-weight subsequence problem, as for least weight subsequence problems we are given a sequence of data items, and require any sequence to start at the
first item and end at the last. We can easily convert NestedBoxes into a LWS problem by sorting
the vectors by the sum of the entries and introducing two special boxes, one very small box K such
that K fits into any box bi and one very large box J such that any bi fits into J.
We define the chain least-weight subsequence problem with respect to any relation R and consider a weighted version where data items are given weights. To make the definition consistent
with the definition of LWS the output is the weight of the sequence that minimizes the sum of the
weights.
Problem 5.1 (ChainLWS). Fix a set of objects X and a relation R Ď X ˆ X. We define the
following LWS instantiation ChainLWSpRq “ LWSpWChainLWSpRq q.
Data items: sequence
of objects x0 , . . . , xn P X with weights w1 , . . . , wn P t´W, . . . , W u.
#
wj if pxi , xj q P R,
for 0 ď i ă j ď n.
Weights: wi,j “
8 otherwise,
The input to the (weighted) chain least-weight subsequence problem is a sequence of data items,
and not a set. Finding the longest chain in a set of data items is NP-complete in general. For
example, consider the box overlap problem: The input is a set of boxes in two dimensions, given by
the top left corner and the bottom right corner, and the relation consists of all pairs such that the
two boxes overlap. This problem is a generalization of the Hamiltonian path problem on induced
subgraphs of the two-dimensional grid, which is an NP-complete problem [29].
We relate ChainLWSpRq to the class of selection problems with respect to the same relation
R.

18

Problem 5.2 (Selection Problem). Given data items a1 , . . . , an , b1 , . . . , bn and a relation Rpai , bj q,
determine if there is a pair i, j satisfying Rpai , bj q. We denote this selection problem with respect
to a relation R by SelectionpRq.
The class of selection problems includes several well studied problems including MinInnProd,
OV [39, 4] and VectorDomination [26].
We will use the selection problems in the search variant, where we find a pair satisfying the R
if such a pair exists. To reduce the the search variant to the decision variants in a fine-grained way,
we can use a simple, binary search type reduction from the decision problem to the search problem:
We give a subquadratic reduction from ChainLWSpRq to SelectionpRq that is independent
of R.
Theorem 5.3. For all relations R such that R can be computed in time subpolynomial in the
number of data items n, ChainLWSpRq ď2 SelectionpRq.
The proof is again based on Static-LWS and a variation on a trick of [40].
As an intermediate step, we define Static-ChainLWS as the equivalent of Static-LWS in the
special case for chains.
Problem 5.4 (Static-ChainLWS). Fix an instance of ChainLWSpRq. Given intervals I :“
ta ` 1, . . . , a ` N u and J :“ ta ` N ` 1, . . . , a ` 2N u for some a and N , together with the correctly
computed values T ra ` 1s, . . . , T ra ` N s, the Static Chain Least-Weight Subsequence Problem
(Static-ChainLWS) asks to determine
T 1 rjs :“

min

iPI:Rpi,jq

T ris ` wj

for all j P J.

Similar to the definition of ChainLWS, Static-ChainLWS is the special case of Static-LWS
where the the weights wi,j are restricted to be either wj or 8, depending on R. As a result, Lemma
3.5 applies directly.
Corollary 5.5 (ChainLWSpRq ď2 Static-LWSpRq). For any R, if Static-ChainLWSpRq can
be solved in time Opn2´ε q for some ε ą 0, then ChainLWSpRq can be solved in time Õpn2´ε q.
We now reduce Static-ChainLWSpRq to SelectionpRq with a variation on the trick by [40].
Lemma 5.6 (Static-ChainLWSpRq ď2 SelectionpRq). For all relations R such that R can
be computed in time subpolynomial in the number of data items n, Static-ChainLWSpRq ď2
SelectionpRq.
Proof. As a first step, we sort the data items ai , i P I “ ta ` 1, . . . , a ` N u by T ris in increasing
order and we will assume for the remainder of the proof that for all?a ` 1 ď i ă a ` N we have
T ris ď T ri ` 1s. We then split the set aa`1 , . . . , aa`N into g :“ r N s groups A1 , . . . , Ag with
Ai “ tapi´1qrN {gs , . . . , airN {gs´1 u. We split the set ba`N `1 , . . . , ba`2N into B1 , . . . , Bg in a similar
fashion. We then iterate over all pairs Ak , Bl with k, l P rgs in lexicographic order, and for each pair
we do the following. Call the oracle for SelectionpRq on the input Ak , Bl to find a pair ai , bj such
that the relation R is satisfied on the pair. If there is no such pair, move to the next pair Ak˚ , Bl˚
of sets of data items. If there is such a pair, find the first element ai˚ P Ak such that Rpai˚ , bj q
using a simple linear scan. As we first sorted A and iterate over sets Ak , Bl in lexicographic order,
we have T 1 rjs “ T ri˚ s ` wj . We then remove bj from Bl and repeat.
19

For the runtime analysis, we observe, that the oracle can find a pair of elements at most OpN q
times, as each time we find a pair we remove an element from the input. In the case where we do
find a pair of elements we do a linear scan that takes OpN {gq time. Furthermore, each pair of sets
Ak , Bl can fail to find a?pair at most once. Hence, if T Selection is the time to solve the selection
problem and using g “ N we get a time of
?
?
?
?
T pN q “ N T Selection p N q ` N pT Selection p N q ` N q “ N T Selection p N q
(8)
which is subquadratic if T Selection pN q is subquadratic.
Theorem 5.7. Let D be the set of possible data items. For any relation R such that
• There is a data item K such that pK, dq P R for all d P D.
• There is a data item J such that pd, Jq P R for all d P D.
• For any set of data items d1 , . . . , dn there is a sequence i1 , . . . , in such that for any j ă k,
pdij , dik q R R. This ordering can be computed in time Opn2´δ q for δ ą 0. We call this ordering
the natural ordering.
Then SelectionpRq ď2 ChainLWSpRq.
Proof. We construct an unweighted ChainLWS problem with all weights set to ´1, so that the
problem is to find the longest chain. Let a1 , . . . an and b1 , . . . , bn be the data items of SelectionpRq
and sort both sets according to the natural ordering. We claim that for the sequence of data items
K, a1 , . . . an , b1 , . . . , bn , J the weight of the least weight subsequence is ´3 exactly if there is a pair
pai , bj q P R. Because of the property of the natural ordering, any valid subsequence starting at K
and ending at J contains at most one element ai and at most one element bj . If there is a pair
pai , bj q P R, then the sequence K, ai , bj , J will have value ´3. If there is no such pair, any valid
sequence contains at most one element other than K and J and its value is therefore at least ´2.
The proof is in the appendix.
In the rest of the section we give some interesting instantiations of the subquadratic equivalence
of Selection and ChainLWS.
Corollary 5.8 (NestedBoxes ”2 VectorDomination). The weighted NestedBoxes problem
2
on d “ c log n dimensions can be solved in time n2´p1{Opc log cqq . For d “ ωplognq, the (unweighted)
NestedBoxes problem cannot be solved in time Opn2´ε q for any ε ą 0 assuming SETH.
Proof. Let R be the relation that contains all pairs of non-negative, d-dimensional vectors a, b such
that ai ď bi for all i. Now SelectionpRq is VectorDomination, and ChainLWSpRq is the
NestedBoxes problem.
Using the reduction from Theorem 5.3 and the algorithms for vector domination of the stated
runtime [26, 13] we immediately get an algorithm for NestedBoxes.
We apply Theorem 5.7 with J “ W d where W is the largest coordinate in all input vectors,
K “ 0d and use the sum of the coordinates of the boxes as the natural ordering. SETH-hardness
of NestedBoxes then follows from the SETH-hardness of vector domination [39].

20

If we restrict NestedBoxes and VectorDomination to Boolean vectors, then we get SubsetChain and SetContainment respectively. In this case the upper bound improves to n2´1{Oplog cq
[4].
We would like to point out that the definition of ChainLWS requires the input to be a sequence
of data items, and not a set. Consider the following definition:
Problem 5.9 (ChainSet). Let a set of data items data items tx0 , . . . , xn u, weights w1 , . . . , wn´1 P
t´W, . . . , W u and a relation Rpxi , xj q be given. The chain set problem for R, denoted ChainSetpRq
asks to find the weight sequence i0 , i1 , i2 , . . . , ik such that for all j with 1 ď j ď k the pair pxij´1 , xij q
řk´1
is in the relation R and the weight j“1 wij is minimized.

While ChainLWS can always be solved in quadratic time, ChainSet is NP-complete. For
example, consider the box overlap problem: The input is a set of boxes in two dimensions, given by
the top left corner and the bottom right corner, and the relation consists of all pairs such that the
two boxes overlap. This problem is a generalization of the Hamiltonian path problem on induced
subgraphs of the two-dimensional grid, which is an NP-complete problem [29]. This is a formal
barrier to a more general reduction than Theorem 5.7, as we need some mechanism to impose an
ordering on the data items.

6

Near-linear time algorithms

In this section, we classify problems to be solvable in near-linear time using the lens of our framework.
Note that in these instances, near-linear time solutions have already been known, however, our
focus on the static variants of LWS provides a simple, general approach to find fast algorithms
by identifying a simple “core” problem. Since in this paper, we generally ignore subpolynomial
factors in the running time, we concentrate here on the reduction from some LWS variant to its
corresponding core problem and disregard reductions in the other direction.

6.1

Longest Increasing Subsequence

The longest increasing subsequence problem LIS has been first investigated by Fredman [18], who
gave an Opn log nq-time algorithm and gave a corresponding lower bound based on Sorting. The
following LWS instantiation is equivalent to LIS.
Problem 6.1 (LIS). We define the following LWS instantiation LIS “ LWSpWLIS q.
Data items: integers
# x1 , . . . , xn P t1, . . . , W u
´1 if xi ă xj
Weights: wi,j “
8 ow.
It is straightforward to verify that ´T rns yields the value of the longest increasing subsequence of
x1 , . . . , xn . Using the static variant of LWS introduced in Section 3, we observe that LIS effectively
boils down to Sorting.
Oberservation 2. LIS can be solved in time Õpnq.
Proof. By Lemma 3.5, we can reduce LIS to the static variant Static-LWSpWLISq. It is straightforward to see that the latter can be reformulated as follows: Given pa1 , T r1sq, . . . , paN , T rN sq and
21

b1 , . . . , bN , determine for every j “ 1, . . . , N , the value T 1 rjs “ ´1 ` min1ďiďN,ai ăbj T ris. To do
so, it suffices to sort the first list as pai1 , T ri1 sq, . . . , paiN , T riN sq with ai1 ď ¨ ¨ ¨ ď aiN and the
second as bj1 , . . . , bjN with bj1 ď ¨ ¨ ¨ ď bjN . Finally, a single pass over both lists will do: For each
k “ 1, . . . , N , we search for the largest ℓ such that aiℓ ă bjk , then the T 1 -value corresponding to bjℓ
is ´1 ` min1ďℓ1 ďℓ T riℓ1 s. By this approach, it is easy to see that after sorting, these values can be
computed in time OpN q. For the exact running time, note that solving Static-LWSpWLIS q takes
time OpN log N q due to sorting, yielding a Opn log2 nq-time algorithm for LIS by Lemma 3.5.

6.2

Unbounded Subset Sum

UnboundedSubsetSum is a variant of the classical SubsetSum, in which repetitions of elements
are allowed. While improved pseudo-polynomial-time algorithms for SubsetSum could only recently be found [32, 10], there is a simple algorithm solving UnboundedSubsetSum in time
Opn log nq [10]. It can be cast into an LWS formulation as follows.
Problem 6.2 (UnboundedSubsetSum). We define the following LWS instantiation LIS “
LWSpWUSS q.
Data items: S Ď#rns
0 if j ´ i P S
Weights: wi,j “
8 ow.
Note that in this formulation, T rns “ 0 iff there is a multiset of numbers from S that sums up
to n. It is a straightforward observation that the static variant of UnboundedSubsetSum can be
solved by classical convolution, i.e., p¨, `q-convolution.
Oberservation 3. UnboundedSubsetSum can be solved in time Õpnq.
Proof. Noting that all weights wi,j are either 0 or 8, it is easy to see that the static variant
Static-LWSpWUSS q can be reformulated as follows: Given a subset X Ď I “ ta ` 1, . . . , a ` N u,
determine, for all j P J “ ta`N `1, . . . , a`2N u, whether there exists some i P X such that j ´i P S.
To do so, we do the following: We represent X as an N -bit vector x “ px1 , . . . , xN q P t0, 1uN with
xi “ 1 iff. a ` i P X. Furthermore, we represent the “relevant part” of S by defining a 2N -bit
vector s “ ps1 , . . . , s2N q P t0, 1u2N with si “ 1 iff. i P S. Then the p¨, `q-convolution r “ x f s of
x and s allows us to determine T 1 ra ` N ` js for j “ 1, . . . , N : this values is 0 iff rN `j ą 0 and
8 otherwise. Correctness follows from the observation that rN `j ą 0 is equivalent to the existence
of some i P rN s and k P r2N s with i ` k “ N ` j and xi “ sk “ 1. This in turn is equivalent to
a ` i P X and pa ` N ` jq ´ pa ` iq “ N ` j ´ i “ k P S, as desired.
Thus Static-LWSpWUSS q can be solved by a single convolution computation, which can be
performed in time OpN log N q. Thus by Lemma 3.5, this gives rise to a Opn log2 nq-time algorithm
for UnboundedSubsetSum.

6.3

Concave LWS

The concave LWS problem is a special case of LWS in which the weights satisfy the quadrangle
inequality. Since a complete description of the input instance consists of Ωpn2 q weights, we use
the standard assumption that each wi,j can be queried in constant time. This allows for sublinear
solutions in the input description, in particular there exist Opnq-time algorithms [38, 21].

22

Problem 6.3 (ConcLWS). We define the following LWS instantiation LIS “ LWSpWconc q.
Weights: wi,j given by oracle access, satisfying wi,j ` wi1 ,j 1 ď wi1 ,j ` wi,j 1 for i ď i1 ď j ď j 1 .
We revisit ConcLWS and its known connection to the problem of computing column (or row)
minima in a totally monotone5 pn ˆ nq-matrix, which we call the SMAWK problem because of
its remarkable Opnq-time solution called the SMAWK algorithm [5].
Oberservation 4. ConcLWS can be solved in time Õpnq.
Proof. The static variant of ConcLWS can be formulated as follows: Given intervals I “ ta `
1, . . . , a ` N u and J “ ta ` N ` 1, . . . , a ` 2N u, we define a matrix M :“ pmi,j qiPI,jPJ q with
mi,j “ T ris ` wi,j . It is easy to see that M is a totally monotone matrix since w satisfies the
quadrangle inequality. Note that the minimum of column j P J in M is miniPI T ris ` wi,j “ T 1 rjs
by definition. Thus, using the SMAWK algorithm we can determine all T 1 rjs in simultaneously in
time OpN q.
Thus by Lemma 3.5, we obtain an Opn log nq-time algorithm for ConcLWS.
Acknowledgments. We would like to thank Karl Bringmann and Russell Impagliazzo for helpful
discussions and comments.

References
[1] Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Quadratic-time hardness
of LCS and other sequence similarity measures. In Proc. 56th Annual IEEE Symposium on
Foundations of Computer Science (FOCS’15), pages 59–78, 2015.
[2] Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams.
Simulating branching programs with edit distance and friends or: A polylog shaved is a lower
bound made. In Proc. 48th Annual ACM Symposium on Symposium on Theory of Computing
(STOC’16), 2016. To appear.
[3] Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster
alignment of sequences. In Proc. 41st International Colloquium on Automata, Languages, and
Programming (ICALP’14), pages 39–51, 2014.
[4] Amir Abboud, Ryan Williams, and Huacheng Yu. More applications of the polynomial method
to algorithm design. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA’15), pages 218–230, 2015.
[5] Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, and Robert E. Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2:195–208, 1987.
[6] Alfred V. Aho, Daniel S. Hirschberg, and Jeffrey D. Ullman. Bounds on the complexity of the
longest common subsequence problem. Journal of the ACM, 23(1):1–12, 1976.
5 A matrix M “ pm q
1
1
i,j i,j is totally monotone if for all i ă i and j ă j , we have that mi,j ą mi1 ,j implies that
mi,j 1 ą mi1 ,j 1 . For a more comprehensive treatment, we refer to [5, 21].

23

[7] Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic
time (unless SETH is false). In Proc. 47th Annual ACM Symposium on Theory of Computing
(STOC’15), pages 51–58, 2015.
[8] David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John
Iacono, Stefan Langerman, Mihai Patrascu, and Perouz Taslakian. Necklaces, convolutions,
and X+Y. Algorithmica, 69(2):294–314, 2014.
[9] Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In Proc. 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS’14), pages 661–670, 2014.
[10] Karl Bringmann. A near-linear pseudopolynomial time algorithm for subset sum. In Proc. 28th
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17), pages 1073–1084, 2017.
[11] Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string
problems and dynamic time warping. In Proc. 56th Annual IEEE Symposium on Foundations
of Computer Science (FOCS’15), pages 79–97, 2015.
[12] Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and
Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and
consequences for non-reducibility. In Proc. 7th ACM Conference on Innovations in Theoretical
Computer Science (ITCS’16), pages 261–270, 2016.
[13] Timothy M Chan. Speeding up the four russians algorithm by about one more logarithmic
factor. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15),
pages 212–217. Society for Industrial and Applied Mathematics, 2015.
[14] Timothy M. Chan and Moshe Lewenstein. Clustered integer 3sum via additive combinatorics.
In Proc. 47th Annual ACM Symposium on Theory of Computing, (STOC’15), pages 31–40,
2015.
[15] Mark de Berg, Kevin Buchin, Bart M. P. Jansen, and Gerhard J. Woeginger. Fine-grained
complexity analysis of two classic TSP variants. In Proc. 43rd International Colloquium on
Automata, Languages, and Programming (ICALP’16), pages 5:1–5:14, 2016.
[16] David Eppstein. Sequence comparison with mixed convex and concave costs. J. Algorithms,
11(1):85–101, 1990.
[17] David A. Eppstein. Efficient algorithms for sequence analysis with concave and convex gap
costs. PhD thesis, Columbia University, 1989.
[18] Michael L. Fredman. On computing the length of longest increasing subsequences. Discrete
Mathematics, 11(1):29 – 35, 1975.
[19] Anka Gajentaan and Mark H Overmars. On a class of o (n2) problems in computational
geometry. Computational geometry, 5(3):165–185, 1995.
[20] Zvi Galil and Raffaele Giancarlo. Speeding up dynamic programming with applications to
molecular biology. Theoretical Computer Science, 64(1):107–118, 1989.

24

[21] Zvi Galil and Kunsoo Park. A linear-time algorithm for concave one-dimensional dynamic
programming. Inf. Process. Lett., 33(6):309–311, 1990.
[22] Zvi Galil and Kunsoo Park. Parallel algorithms for dynamic programming recurrences with
more than O(1) dependency. J. Parallel Distrib. Comput., 21(2):213–222, 1994.
[23] Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Ryan Williams. Completeness for
first-order properties on sparse structures with algorithmic applications. In Proc. 28th Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA’17), pages 2162–2181, 2017.
[24] A. Grønlund, K. Green Larsen, A. Mathiasen, J. Sindahl Nielsen, S. Schneider, and M. Song.
Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D. ArXiv e-prints,
January 2017. arXiv:1701.07204.
[25] Daniel S. Hirschberg and Lawrence L. Larmore. The least weight subsequence problem. SIAM
Journal on Computing, 16(4):628–638, 1987.
[26] Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, and Stefan Schneider. 0-1 integer
linear programming with a linear number of constraints. arXiv preprint arXiv:1401.5512, 2014.
[27] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer
and System Sciences, 62(2):367 – 375, 2001.
[28] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly
exponential complexity? Journal of Computer and System Sciences, 63(4):512–530, 2001.
[29] Alon Itai, Christos H Papadimitriou, and Jayme Luiz Szwarcfiter. Hamilton paths in grid
graphs. SIAM Journal on Computing, 11(4):676–686, 1982.
[30] Maria M. Klawe and Daniel J. Kleitman. An almost linear time algorithm for generalized
matrix searching. SIAM J. Discrete Math., 3(1):81–97, 1990.
[31] Donald E. Knuth and Michael F. Plass. Breaking paragraphs into lines. Softw., Pract. Exper.,
11(11):1119–1184, 1981.
[32] Konstantinos Koiliaris and Chao Xu. A faster pseudopolynomial time algorithm for subset
sum. In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA’17), pages
1062–1072, 2017.
[33] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential
time hypothesis. Bulletin of the EATCS, 105:41–72, 2011.
[34] William J. Masek and Mike Paterson. A faster algorithm computing string edit distances.
Journal of Computer and System Sciences, 20(1):18–31, 1980.
[35] Webb Miller and Eugene W. Myers. Sequence comparison with concave weighting functions.
Bulletin of Mathematical Biology, 50(2):97–120, 1988.
[36] David Pisinger. Dynamic programming on the word RAM. Algorithmica, 35(2):128–145, 2003.
[37] Virginia Vassilevska Williams. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk). In Proc. 10th International Symposium on Parameterized and Exact Computation (IPEC’15), pages 17–29, 2015.
25

[38] Robert E. Wilber. The concave least-weight subsequence problem revisited. J. Algorithms,
9(3):418–425, 1988.
[39] Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications.
Theoretical Computer Science, 348(2):357–365, 2005.
[40] Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix
and triangle problems. In Proc. 51st Annual IEEE Symposium on Foundations of Computer
Science (FOCS’10), pages 645–654, 2010.
[41] F. Frances Yao. Efficient dynamic programming using quadrangle inequalities. In Proc. 12th
Annual ACM Symposium on Theory of Computing (STOC’80), pages 429–435, 1980.

26

