# Subset Sum in Time $2^{n/2}/\mathrm{poly}(n)$

Xi Chen, Yaonan Jin, Tim Randolph, and Rocco A. Servedio
{xichen<EMAIL_ADDRESS>{yj2552<EMAIL_ADDRESS>
Columbia University

###### Abstract

A major goal in the area of exact exponential algorithms is to give an
algorithm for the (worst-case) $n$-input Subset Sum problem that runs in time
$2^{(1/2-c)n}$ for some constant $c>0$. In this paper we give a Subset Sum
algorithm with worst-case running time $O(2^{n/2}\cdot n^{-\gamma})$ for a
constant $\gamma>0.5023$ in standard word RAM or circuit RAM models. To the
best of our knowledge, this is the first improvement on the classical “meet-
in-the-middle” algorithm for worst-case Subset Sum, due to Horowitz and Sahni,
which can be implemented in time $O(2^{n/2})$ in these memory models [HS74].

Our algorithm combines a number of different techniques, including the
“representation method” introduced by Howgrave-Graham and Joux [HGJ10] and
subsequent adaptations of the method in Austrin, Kaski, Koivisto, and Nederlof
[AKKN16], and Nederlof and Wegrzycki [NW21], and “bit-packing” techniques used
in the work of Baran, Demaine, and Pǎtraşcu [BDP05] on subquadratic algorithms
for 3SUM.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Computational Model
    2. 1.2 Results, Techniques, and Organization
  2. 2 Preliminaries
    1. 2.1 Preliminary Results
  3. 3 $\Omega(n^{0.5}/\log n)$-Factor Speedup via Bit Packing
  4. 4 $\Omega(n^{0.01})$-Factor Speedup via Orthogonal Vectors and the Representation Method
    1. 4.1 Auxiliary Lemmas
  5. 5  Subset Sum in Time $O(2^{n/2}\cdot n^{-0.5023})$
    1. 5.1 Auxiliary Lemmas
  6. 6 Extensions and Future Work

##  1 Introduction

One of the most well-known and simple-to-state NP-complete problems is the
_Subset Sum_ problem. An instance of Subset Sum consists of a list
$X=(x_{1},\dots,x_{n})$ of $n$ positive integer values and a positive integer
target $t$, and the output is either a subset $S\subseteq X$ such that
$\sum_{x_{i}\in S}x_{i}=t$ or a report that no such subset exists. Subset Sum
was one of the original 21 problems proved NP-complete in Karp’s seminal paper
[Kar72] and has been the subject of intensive study from many different
perspectives for at least five decades.

This paper is motivated by the following open problem in the theory of exact
exponential time algorithms: how quickly can we solve worst-case instances of
Subset Sum? Exhaustive search over all possible solutions yields a trivial
$2^{n}\cdot\mathrm{poly}(n)$-time algorithm. In 1974, Horowitz and Sahni
introduced the “meet-in-the-middle” technique, which gives an algorithm that
can be implemented in $O(2^{n/2})$ time in standard RAM models [HS74]. Since
then, obtaining a $2^{(1/2-c)n}$-time algorithm for some constant $c>0$ has
emerged as a major goal in the exact exponential time algorithms community
(explicitly mentioned in [Woe08, CFJ+14, AKKN15, AKKN16, NW21] and numerous
other works) which has attracted the attention of many researchers.

Intriguing progress has been made on a number of variants of the core worst-
case Subset Sum problem. More than forty years ago Schroeppel and Shamir
[SS81] improved the $2^{n/2}\cdot\mathrm{poly}(n)$ space complexity of the
meet-in-the-middle algorithm by giving an algorithm that runs in
$2^{n/2}\cdot\mathrm{poly}(n)$ time and $2^{n/4}\cdot\mathrm{poly}(n)$ space.
An exciting recent breakthrough by Nederlof and Wegrzycki [NW21] further
improved this space complexity to $2^{0.249999n}$. In [HGJ10] Howgrave-Graham
and Joux gave an algorithm which can solve _average-case_ Subset Sum instances
in time $2^{0.337n}$,111See the last paragraph of [BCJ11] for a discussion of
the runtime of [HGJ10]. and this was later improved to $2^{0.291n}$ in the
work of Becker et al. [BCJ11]. The closely related _Equal Subset Sum_ problem,
which looks for two subsets with the same sum, can be solved exponentially
faster than suggested by meet-in-the-middle [MNPW19] and also yields further
improvements in the average case [CJRS22]. However, to the best of our
knowledge, there have been no improvements on the worst-case $O(2^{n/2})$
runtime of the meet-in-the-middle algorithm for Subset Sum since it was first
introduced almost fifty years ago.

Our contribution: Worst-case Subset Sum in $2^{n/2}/\mathrm{poly}(n)$ time.
Given the longstanding difficulty of achieving a $2^{(1/2-c)n}$-time worst-
case algorithm for Subset Sum, it is natural to consider the relaxed goal of
achieving _some_ nontrivial speedup of the meet-in-the-middle algorithm. In
this paper we achieve this goal; more precisely, we give three different
randomized algorithms for worst-case Subset Sum, each of which runs in time
$O(2^{n/2}\cdot n^{-\gamma})$ for a specific constant $\gamma>0$ in a standard
word RAM or circuit RAM model (described in detail in Section 1.1 below). Our
fastest algorithm, which combines techniques from our other two algorithms,
runs in time $O(2^{n/2}\cdot n^{-0.5023})$.

The improvements we achieve over the $O(2^{n/2})$ runtime of the meet-in-the-
middle algorithm for Subset Sum are analogous to “log-shaving” improvements on
the runtimes of well-known and simple polynomial-time algorithms for various
problems which have resisted attempts at polynomial-factor improvements. There
is a substantial strand of research along these lines (see [Cha13b, Cha13a]
for a non-exhaustive overview); indeed, Abboud and Bringmann [AB18] have
recently stated that: “A noticeable fraction of Algorithms papers in the last
few decades improve the runtime of well-known algorithms for fundamental
problems by logarithmic factors.” In our setting, since the well-known and
simple algorithm for Subset Sum (namely, meet-in-the-middle) runs in
exponential time, saving a $\mathrm{poly}(n)$ factor, as we do, is analogous
to “log-shaving”. Indeed, as we discuss in Section 1.2 below, our first and
most straightforward algorithm is based on “bit-packing” techniques that were
used by Baran, Demaine, and Pǎtraşcu [BDP05] to shave log factors from the
standard $O(n^{2})$-time algorithm for the 3SUM problem. We find it somewhat
surprising that the “log-shaving” perspective has not previously appeared in
the literature on Subset Sum, and we hope that our work will lead to further
(and more substantial) runtime improvements for Subset Sum and other problems
with well-known and simple exponential-time algorithms.

######  Remark 1.

We note that by an easy reduction, an algorithm for 4SUM running in time
$O(n^{2}/\log(n)^{\alpha})$ for any constant $\alpha>0$ would immediately
imply a Subset Sum algorithm running in time $O(2^{n/2}/n^{\alpha})$, which
would be a result comparable to ours. However, while log-shaving results for
3SUM are known [BDP05, GP18], giving an $o(n^{2})$ algorithm for 4SUM is a
well-known open problem.

###  1.1 Our Computational Model

Before presenting our results and techniques we describe the models of memory
and computation that we use. A Subset Sum instance is parameterized by the
number of inputs $n$ and the size of the target value $t$ (without loss of
generality, $x_{1},x_{2},\dots,x_{n}\leq t$). Thus it is natural to adopt a
memory model with word length $\ell=\Theta(\log t)$ such that each input
integer can be stored in a single word. This is the framework used in the work
of Pisinger [Pis03], which studies dynamic programming approaches for Subset
Sum in the word RAM model (see [Pis03, Equation (1)]). We also note that this
memory model is analogous to the standard RAM model that is commonly used for
problems such as 3SUM (see e.g. [BDP05]), where it is assumed that each input
value is at most $\mathrm{poly}(n)$ and hence fits into a single $O(\log
n)$-bit machine word.

This framework lets us consider arbitrary input instances of Subset Sum with
no constraints on the size of the input integers. If $t=2^{o(n)}$, standard
dynamic programming algorithms [Bel66] solve the problem in time
$O(nt)=2^{o(n)}$, which supersedes our $\mathrm{poly}(n)$-factor improvements
over meet-in-the-middle; hence throughout the paper we assume
$t=2^{\Omega(n)}$. It is arguably most natural to think about instances in
which $t=2^{\Theta(n)}$, in which case $\ell=\Theta(n)$, and we encourage the
first-time reader to imagine $\ell=\Theta(n)$ for easy digestion. More
precisely, we make the assumption throughout the paper that the word size
$\ell=\mathrm{poly}(n)$, although some of our results even hold for extremely
large word sizes and are footnoted accordingly.

We consider runtime in two standard variants of the RAM model. The first is
_circuit RAM_ ; in this model, any operation that maps a constant number of
words to a single word and has a $\mathrm{poly}(\ell)$-size circuit with
unbounded fan-in gates can be performed in time proportional to the depth of
the circuit. Consequently, in the circuit RAM model, $\mathsf{AC}^{0}$
operations on a constant number of words can be performed in constant time,
and multiplying, performing modular division, etc., on two $\ell$-bit words
can be performed in time $O(\log\ell)$. The second is _word RAM_ , in which
the usual arithmetic operations, including multiplication, are assumed to take
unit time, but arbitrary $\mathsf{AC}^{0}$ operations are not atomic
operations on words. We present each of our algorithms for the stronger
circuit RAM model,222Note that any algorithm in the word RAM model can be
simulated in the circuit RAM model with no more than an $O(\log\ell)$-factor
slowdown. and explain adaptations that give corresponding word RAM algorithms.

###  1.2 Results, Techniques, and Organization

In Section 2 we establish our notation and review some background results and
observations that will be used throughout the paper.

Sections 3, 4 and 5 give our three new algorithms, which augment the standard
meet-in-the-middle approach in different ways to achieve their respective
runtime improvements. Each of our algorithms is a randomized decision
algorithm that runs in the time bound claimed below and on every input
instance outputs the correct answer with probability at least $3/4$. Further,
each of our algorithms has one-sided error, i.e., it never makes a mistake
when it outputs “yes”. (See Observation 2 for a discussion of how such
randomized decision algorithms yield randomized search algorithms with the
same asymptotic runtime.)

Our first and simplest algorithm, presented in Section 3, achieves a runtime
of $\widetilde{O}(2^{n/2}\cdot\ell^{-1/2})\leq\widetilde{O}(2^{n/2}\cdot
n^{-1/2})$ in the circuit RAM model and $\widetilde{O}(2^{n/2}\cdot n^{-1/2})$
in the word RAM model, for all $\ell=\mathrm{poly}(n)$.333The notation
$\widetilde{O}(\cdot)$ suppresses $\mathrm{polylog}(\ell)=\mathrm{polylog}(n)$
factors. It works by adapting the bit-packing trick, a technique developed by
Baran, Demaine, and Pǎtraşcu [BDP05] for the 3SUM problem, for the 2
algorithm. The idea is to compress the two lists of partial subset sums used
in 2 by packing hashes of multiple values into a machine word, while
preserving enough information to make it possible to run (an adaptation of) 2
on the lists of hashed and packed values. This results in a runtime savings
over performing 2 on the original lists (without hashing and packing), because
processing a pair of words, each containing multiple hashed values, takes
constant expected time in the circuit RAM model and can be memoized to take
constant time in the word RAM model.

Our second algorithm, given in Section 4, achieves a runtime of
$O(2^{n/2}\cdot\ell^{-\gamma})\leq O(2^{n/2}\cdot n^{-\gamma})$ for some
constant $\gamma>0.01$ in the circuit RAM model and $O(2^{n/2}\cdot
n^{-\gamma})$ in the word RAM model, for all $\ell=\mathrm{poly}(n)$. Although
the time savings is smaller than our first algorithm, we believe that this
algorithm is conceptually interesting since it avoids bit-packing and instead
combines 2 with two techniques devised in prior work on Subset Sum. The first
of these is the “representation method” introduced by Howgrave-Graham and Joux
[HGJ10]. Roughly speaking, the idea of this method is to (i) increase the size
of the search space in such a way that a single solution has many
“representations” in the space of enhanced solutions, and then (ii) search
over only a fraction of the enhanced solution space. A consequence of
expanding the solution space, though, is that a number of “pseudosolutions”,
solutions that contain certain input elements more than once, are introduced.
This leads us to the second technique, i.e. the use of a fast subroutine for
the Orthogonal Vectors (OV) problem (recall that OV is the problem of deciding
whether two lists of $\\{0,1\\}$-vectors contain a pair of vectors, one from
each list, that are orthogonal). The fast OV subroutine lets us efficiently
rule out pseudosolutions while running (an adaptation of) 2 on a fraction of
the enhanced solution space.

In Section 5 we give our fastest algorithm, which uses a delicate combination
of the techniques from Sections 3 and 4 to obtain a runtime of $O(2^{n/2}\cdot
n^{-0.5023})$ for all $\ell=\mathrm{poly}(n)$. While the runtime improvement
over Section 3 is not large, this algorithm demonstrates that by leveraging
insights specific to the Subset Sum problem, we can achieve time savings
beyond what is possible with more “generic” log shaving techniques. Finally,
in Section 6 we briefly discuss directions for future work.

##  2 Preliminaries

To ease readability, we adopt the following notational conventions throughout
the paper: lowercase Roman letters ($\ell$, $n$, etc.) denote variables;
lowercase Greek letters ($\varepsilon$, $\alpha$, etc.) denote numerical
constants; capital Roman letters ($L$, $W$, etc.) denote sets, multisets, or
lists; and calligraphic capital letters ($\mathcal{W}$, $\mathcal{Q}$, etc.)
denote collections of sets of numbers.

Logarithms. When written without a specified base, $\log(\cdot)$ denotes the
base-2 logarithm.

Big-O Notation. We augment big-$O$ notation with a tilde ($\widetilde{O}$,
$\widetilde{\Omega}$, $\widetilde{\Theta}$ etc.) to suppress
$\mathrm{polylog}(\ell)=\mathrm{polylog}(n)$ factors. For example, we have
$\widetilde{O}(2^{n})=O(2^{n}\cdot\mathrm{polylog}(n))$ and
$\widetilde{\Omega}(n)=\Omega(\frac{n}{\mathrm{polylog}(n)})$.

Probability Notation. Random variables are written in boldface. In particular,
we write “$\bm{x}\sim S$” to indicate that an element $\bm{x}$ is sampled
uniformly at random from a finite multiset $S$.

Set Notation. We write $[a:b]$ for the set of integers $\\{a,a+1,\dots,b\\}$
and $[a]$ for $\\{1,2,\dots,a\\}$. We write $\mathbb{P}[a:b]$ for the set of
all primes in the interval $[a:b]$.

Given a multiset or list $Y$ of integers, we adopt several shorthands:
$\Sigma(Y):=\sum_{y\in Y}y$ denotes the sum, $W(Y):=\\{\Sigma(T)\mid
T\subseteq Y\\}$ denotes the set of distinct sub-multiset sums, and $L_{Y}$
denotes the list containing the elements of $W(Y)$ sorted in increasing order.

Also, we often write $f(Y)$ for the multiset or list obtained by applying
operation $f$ element-wise, such as $Y+\alpha=\\{y+\alpha\mid y\in Y\\}$ and
$\alpha Y=\\{\alpha y\mid y\in Y\\}$. The only exception is $(Y\bmod p)$,
which denotes the set of distinct residues $\\{(y\bmod p)\mid y\in Y\\}$.

Stirling’s Approximation for Binomial Coefficients. We use the following well-
known consequence of Stirling’s approximation (see e.g. [FG06, Lemma 16.19]):
For each integer $j\in[0:n/2]$,

$\sum_{i\,\leq\,j}\binom{n}{i}~{}\leq~{}2^{H(j/n)\cdot n},$ (1)

where $H(y):=-y\log(y)-(1-y)\log(1-y)$ is the binary entropy function.

Pseudolinear Hashing. Recall that $\ell=\mathrm{poly}(n)$ is the word length
in our memory model. Given an integer $m\leq\ell$, we write $\bm{h}_{m}$ to
denote the random hash function defined as

$\bm{h}_{m}(y)~{}~{}:=~{}~{}(\bm{u}\cdot y\pmod{2^{\ell}})\gg\ell-m.$ (2)

Here the input $y$ is an $\ell$-bit integer, $\bm{u}$ is selected uniformly at
random from all odd $\ell$-bit integers, and $\gg$ denotes a bit shift to the
right, i.e., dividing $\bm{u}\cdot y\pmod{2^{\ell}}$ by $2^{\ell-m}$ and then
truncating the result so that only the higher-order $m$ bits remain.

This hash function $\bm{h}_{m}(y)$ can be evaluated in time
$O(\log\ell)=O(\log n)$ for $\ell=\mathrm{poly}(n)$ in the circuit RAM model,
i.e., essentially the time to multiply, or constant time $O_{n}(1)$ in the
word RAM model. Further, $\bm{h}_{m}$ has the following useful properties
[DHKP97, BDP05].

######  Lemma 1 (Pseudolinear Hashing [DHKP97, BDP05]).

The following hold for the hash function $\bm{h}_{m}$:

  1. 1.

Pseudolinearity. For any two $\ell$-bit integers $y$, $z$ and any outcome of
$\bm{h}_{m}$,

$\bm{h}_{m}(y)+\bm{h}_{m}(z)~{}\in~{}\bm{h}_{m}(y+z)-\\{0,1\\}\pmod{2^{m}}.$

  2. 2.

Pseudouniversality. For any two $\ell$-bit integers $y$, $z$ with $y\neq z$,

$\mathop{{\bf
Pr}\/}\big{[}\bm{h}_{m}(y)=\bm{h}_{m}(z)\big{]}~{}=~{}O(2^{-m}).$

###  2.1 Preliminary Results

First of all, for the purposes of this paper, we can assume that the input
target $t$ have size $2^{\Omega(n)}$:

######  Observation 1 (Assumptions about Input Instances).

Given a Subset Sum instance $(X,\,t)$ with $t\leq 2^{0.499n}$, the standard
dynamic programming algorithm [Bel66] takes time $O(nt)=2^{0.499n+o(n)}$, much
faster than the $\mathrm{poly}(n)$-factor speedups we are targeting. Hence
without loss of generality, we assume $t=2^{\Omega(n)}$ and $\ell=\Omega(\log
t)=\Omega(n)$ throughout the paper.

We further observe that the randomized decision algorithms that we give can be
converted into randomized search algorithms with the same asymptotic runtimes:

######  Observation 2 (Search-to-Decision Reductions).

Given a deterministic decision algorithm DET for the Subset Sum problem, the
standard search-to-decision reduction solves an $n$-integer instance by
running DET a total of $n$ times, with the $i$-th execution being on an
$(n-i+1)$-integer subinstance. Each of our randomized algorithms RAN succeeds
with probability $\geq 3/4$, returns no false positives, and runs in time
$\mathrm{TIME}(n)=2^{\Theta(n)}$. On the same $(n-i+1)$-integer subinstance,
we can reduce the failure probability to $\leq 1/4^{i}$ by repeating RAN a
number of $i$ times. Overall, the success probability is $\geq
1-\sum_{i=1}^{n}1/4^{i}\geq 2/3$ and the runtime is
$\sum_{i=1}^{n}i\cdot\mathrm{TIME}(n+1-i)=O(\mathrm{TIME}(n))$.

A basic primitive for our algorithms is the sorted list $L_{Y}$ containing the
elements of $W(Y)$, all distinct subset sums, for a given multiset $Y$ of size
$|Y|=k$. Figure 1 shows an $O(2^{k})$-time folklore algorithm that enumerates
$L_{Y}$:

Procedure $\textup{\text{\tt Sorted-Sum-Enumeration}}(Y)$ Input: An integer
multiset $Y=\\{y_{1},\dots,y_{k}\\}$. Output: A sorted list $L_{Y}:=L_{k}$ of
$W(Y)$, all distinct subset sums for $Y$. 1. Initialize $L_{0}:=(0)$. Then for
each $i\in[k]$: 2. Create the sorted list $L^{\prime}_{i-1}:=L_{i-1}+y_{i}$.
3. Create the sorted list $L_{i}$ obtained by merging $L_{i-1}$,
$L^{\prime}_{i-1}$ and removing duplicates. Figure 1: Efficiently enumerating
subset sums of $k\geq 1$ integers.

######  Lemma 2 (Sorted Sum Enumeration; Folklore).

1 runs in time $O(2^{k})$.

###### Proof.

We essentially adapt the classic merge sort algorithm. Since
$|L_{i-1}|=|L^{\prime}_{i-1}|\leq|L_{i}|\leq 2|L_{i-1}|$ for each $i\in[k]$,
the runtime of 1 is

$\textstyle\sum_{i\in[k]}O(|L^{\prime}_{i-1}|+|L_{i}|)~{}=~{}\sum_{i\in[k]}O(|L_{i}|)~{}=~{}\sum_{i\in[k]}O(2^{i})~{}=~{}O(2^{k}).\qed$

We can improve this runtime analysis if $|W(Y)|$ is smaller than $2^{k}$ by a
$\mathrm{poly}(k)$ factor:

######  Lemma 3 (Sorted Sum Enumeration for Small $W(Y)$).

If $Y$ is a multiset of $|Y|=k$ integers with $|W(Y)|\leq 2^{k}\cdot
k^{-\varepsilon}$ for some constant $\varepsilon>0$, 1 runs in time
$O(2^{k}\cdot k^{-\varepsilon}\cdot\log k)$.

###### Proof.

If $|W(Y)|\leq 2^{k}\cdot k^{-(1+\varepsilon)}$, then since
$|L_{i}|\leq|L_{k}|=|W(Y)|$ for each $i\in[k]$, it is easy to check that the
algorithm runs in time $O(k\cdot|W(Y)|)=O(2^{k}\cdot k^{-\varepsilon})$; so
suppose that $|W(Y)|\geq 2^{k}\cdot k^{-(1+\varepsilon)}$. Using the bound
$|L_{i}|\leq 2^{i}$ for $i\leq\log|W(Y)|$ and the bound $|L_{i}|\leq|W(Y)|$
for $\log|W(Y)|<i\leq k$, the runtime of 1 is upper bounded by

$\displaystyle\textstyle\sum_{i\in[k]}O(|L_{i}|)$
$\displaystyle~{}=~{}\textstyle\sum_{i\,\leq\,\log|W(Y)|}O(2^{i})+\sum_{\log|W(Y)|<i\leq
k}O(|W(Y)|)$ $\displaystyle~{}=~{}O(|W(Y)|)+(1+\varepsilon)\cdot\log k\cdot
O(|W(Y)|)$ $\displaystyle~{}=~{}O(|W(Y)|\cdot\log k)~{}=~{}O(2^{k}\cdot
k^{-\varepsilon}\cdot\log k).\qed$

######  Remark 2.

Lemma 3 gives a tight analysis of the algorithm when $|W(Y)|=2^{k}\cdot
k^{-\varepsilon}$, as can be seen by considering the particular size-$k$
multiset $Y=(2^{0},2^{1},\dots,2^{k-\varepsilon\log k-1},1,1,\dots,1)$.

Finally, Figure 2 shows the classic meet-in-the-middle algorithm for Subset
Sum, by Horowitz and Sahni [HS74], which serves as our baseline for
comparison.

######  Lemma 4.

The worst-case runtime of 2 is $O(2^{n/2}).$

###### Proof.

This follows immediately from Lemma 2 as $|L_{A}|,|L_{B}|\leq 2^{n/2}$. ∎

Procedure $\textup{\text{\tt Meet-in-the-Middle}}(X,\,t)$ Input: An integer
multiset $X=\\{x_{1},\,x_{2},\,\dots,\,x_{n}\\}$ and an integer target $t$.
Output: “yes” if $(X,t)$ is a Subset Sum instance that has a solution, “no”
otherwise. 0. Fix any partition of $X=A\cup B$ such that $|A|=|B|={n}/{2}$. 1.
Enumerate the sorted lists $L_{A}$ and $L_{B}$ using 1. 2. Initialize two
pointers at the smallest value in $L_{A}$ and the largest value in $L_{B}$.
If these two values sum to the target $t$, then return “yes”;
if they sum to less than $t$, then increment the pointer into $L_{A}$ and
repeat;
and if they sum to more than $t$, then increment the pointer into $L_{B}$ and
repeat.
If either pointer goes past the end of its list, then return “no”. Figure 2:
The classic Meet-in-the-Middle algorithm [HS74].

##  3 $\Omega(n^{0.5}/\log n)$-Factor Speedup via Bit Packing

In this section we analyze our first and simplest algorithm, 3 (see Figure
3).444As explained in Section 1.1, we assume $\ell=\mathrm{poly}(n)$
throughout; however, our results for 3 apply for superpolynomial word length
as long as $\ell=O(2^{n/3})$. We leave the extensional modifications to the
proofs for this regime as an exercise for the interested reader.

Procedure $\textup{\text{\tt Bit-Packing}}(X,\,t)$ Input: An integer multiset
$X=\\{x_{1},\,x_{2},\,\dots,\,x_{n}\\}$ and an integer target $t$. Setup: Draw
a random hash function $\bm{h}_{m}$ with $m=3\log\ell$ (cf. Equation 2). 0.
Fix any partition of $X=A\cup B\cup D$ such that $|D|=\log\ell$ and
$|A|=|B|=\frac{n-|D|}{2}$. 1. Create the set $W(D)$ and the sorted lists
$L_{A}$, $L_{B}$ using 1. 2. Create lists $\bm{h}_{m}(L_{A})$ and
$\bm{h}_{m}(L_{B})$ by applying $\bm{h}_{m}$ element-wise to $L_{A}$ and
$L_{B}$.
Let $\bm{H}_{A}$ be the list obtained from $\bm{h}_{m}(L_{A})$ by packing
$(\ell/m)$ elements of $\bm{h}_{m}(L_{A})$
into each $\ell$-bit word of $\bm{H}_{A}$ (preserving the sorted ordering) and
likewise for $\bm{H}_{B}$. 3. For each $t^{\prime}\in(t-W(D))$: 4. Initialize
indices $i:=0$ and $j:=|\bm{H}_{B}|-1$. While $i<|\bm{H}_{A}|$ and $j\geq 0$:
5. If the indexed words $\bm{H}_{A}[i]$ and $\bm{H}_{B}[j]$ contain a pair of
hashes $(\bm{h}_{m}(a^{\prime}),\,\bm{h}_{m}(b^{\prime}))$
such that
$\bm{h}_{m}(a^{\prime})+\bm{h}_{m}(b^{\prime})\in\bm{h}_{m}(t^{\prime})-\\{0,\,1\\}\pmod{2^{m}}$,
use 2 to search for a solution
$(a,\,b)\in L_{A}[i\ell/m:(i+1)\ell/m-1]\times L_{B}[j\ell/m:(j+1)\ell/m-1]$
such that $a+b=t^{\prime}$. Halt and return “yes” if a solution is found. 6.
If $L_{A}[(i+1)\ell/m-1]+L_{B}[j\ell/m]<t^{\prime}$, increment $i\leftarrow
i+1$.
Otherwise, decrement $j\leftarrow j-1$. 7. Return “no” (i.e., no solution was
found for any $t^{\prime}\in(t-W(D))$). Figure 3: The Bit-Packing algorithm.

######  Theorem 1.

3 is a zero-error randomized algorithm for the Subset Sum problem with
expected runtime $O(2^{n/2}\cdot\ell^{-1/2}\cdot\log\ell)\leq O(2^{n/2}\cdot
n^{-1/2}\cdot\log n)$ in the circuit RAM model.555By halting 3 and returning
“no” if its runtime exceeds $C\cdot 2^{n/2}\cdot\ell^{-1/2}\cdot\log\ell$ for
a large enough constant $C>0$, we get an one-sided error algorithm with
success probability $\geq 3/4$, as claimed in Section 1.2.

3 works by packing $\ell/m$ hashed values into a single word via our
pseudolinear hash function $\bm{h}_{m}$, for $m=3\log\ell$, while preserving
enough information to run 2 on the lists of hashed and packed values. This
allows us to compare two length-$(\ell/m)$ sublists of $L_{A}$ and $L_{B}$ in
constant expected time in the circuit RAM model, since each hashed and packed
sublist fits into a constant number of words, instead of time $O(\ell/m)$ like
the original 2 algorithm. So far, this is essentially the approach taken by
[BDP05] in their bit-packing algorithm for 3SUM. However, in our context the
$O(\ell/m)$ speedup described above is offset by the following issue: if we
follow the original 2 setup and take $|A|=|B|=\frac{n}{2}$, the lists $L_{A}$
and $L_{B}$ may have length $\Omega(2^{n/2})$, increasing the runtime.

To deal with this, we set aside a small set $D\subseteq X$ of $|D|=\log\ell$
many input elements and solve the remaining subinstance $X\setminus D$ for
each shifted target $t^{\prime}\in(t-W(D))$. Removing the elements in $D$
shortens the lists $L_{A}$ and $L_{B}$, which are now formed from the elements
in $X\setminus D$, and allows us to enumerate and pack them quickly. Balancing
the overhead of solving each of these subinstances against the savings
described earlier, we get the claimed speedup
$\Omega(\ell^{1/2}/\log\ell)\geq\Omega(n^{1/2}/\log n)$.

###### Proof of Correctness for 3.

The algorithm outputs “yes” only if a triple $(a,\,b,\,t^{\prime})\in
L_{A}\times L_{B}\times(t-W(D))$ with $a+b=t^{\prime}$ is found, so it never
returns a false positive.

It remains to show that for any $t^{\prime}\in(t-W(D))$, we are guaranteed to
find a shifted solution $(a,\,b)\in L_{A}\times L_{B}$ such that
$a+b=t^{\prime}$, if one exists. Without loss of generality, we consider two
sublists $L_{A}[i\ell/m:(i+1)\ell/m-1]$ and $L_{B}[j\ell/m:(j+1)\ell/m-1]$
that contain such a shifted solution $(a,\,b)$ and correspond to two packed
words $\bm{H}_{A}[i]$ and $\bm{H}_{B}[j]$ for some indices $i$ and $j$. The
existence of such a shifted solution $a+b=t^{\prime}$ combined with the
condition in Line 6 ensures that the algorithm will not step past either the
packed word $\bm{H}_{A}[i]$ or $\bm{H}_{B}[j]$ before reaching the other one,
so the algorithm will compare these two packed words at some point. Following
Lemma 1, we have
$\bm{h}_{m}(a)+\bm{h}_{m}(b)\in\bm{h}_{m}(t^{\prime})-\\{0,\,1\\}\pmod{2^{m}}$,
satisfying the condition in Line 5. Thus we are guaranteed to find the shifted
solution $(a,\,b)$ by running 2 to check all pairs in
$L_{A}[i\ell/m:(i+1)\ell/m-1]\times L_{B}[j\ell/m:(j+1)\ell/m-1]$. ∎

###### Proof of Runtime for 3.

Recalling the assumption $\ell=\mathrm{poly}(n)$:

  * •

Line 1 takes time
$O(2^{|A|}+2^{|B|}+2^{|D|})=O(2^{n/2}\cdot\ell^{-1/2}+\ell)=O(2^{n/2}\cdot\ell^{-1/2})$
by Lemma 2, for the choices of $|A|$, $|B|$, and $|D|$.

  * •

Line 2 takes time $(|L_{A}|+|L_{B}|)\cdot
O(\log\ell)=O(2^{n/2}\cdot\ell^{-1/2}\cdot\log\ell)$, where $O(\log\ell)$
bounds the time for each evaluation of the hash function $\bm{h}_{m}$.

  * •

Line 3 (the outer loop) is performed for at most $|W(D)|\leq 2^{|D|}=\ell$
iterations.

  * •

Line 4 (the inner loop) is performed for at most
$(|L_{A}|+|L_{B}|)\cdot\frac{1}{\ell/m}=O(2^{n/2}\cdot\ell^{-3/2}\cdot\log\ell)$
iterations, since each iteration either increments $i\leftarrow i+1$ or
decrements $j\leftarrow j-1$.

  * •

Line 5: (i) Checking whether the “If” condition holds for any two words
$\bm{H}_{A}[i]$ and $\bm{H}_{B}[j]$ requires a single $\mathsf{AC}^{0}$
operation on three words, taking constant time in the circuit RAM model. (ii)
Finding a solution $(a,\,b)$ using 2 on the two length-$(\ell/m)$ sublists
takes time $O(\ell/m)=O(\ell/\log\ell)$.

The “If” test is passed (i) at most once for a correct solution and (ii) each
time we encounter a hash collision. Note that the sequence of pairs of words
$(\bm{H}_{A}[i],\,\bm{H}_{B}[j])$ we compare is completely determined by
$L_{A}$ and $L_{B}$ and is unaffected by the outcome of the random hash
function $\bm{h}_{m}$. Thus by Lemma 1, each of the $(\ell/m)^{2}$ hash pairs
in $(\bm{H}_{A}[i],\,\bm{H}_{B}[j])$ incurs a collision with probability
$O(2^{-m})$. By a union bound, the expected time taken for Line 5 because of
hash collisions is at most $(\ell/m)^{2}\cdot O(2^{-m})\cdot
O(\ell/m)=O(1/\log^{3}(\ell))=o_{n}(1)$, since $m=3\log\ell$ and
$\ell=\Omega(n)$.

  * •

Line 6 clearly takes time $O_{n}(1)$.

Consequently, 3 has expected runtime

$\displaystyle\mathrm{TIME}(n,\,\ell)$
$\displaystyle~{}=~{}O(2^{n/2}\cdot\ell^{-1/2}+\ell)+O(2^{n/2}\cdot\ell^{-1/2}\cdot\log\ell)$
Lines 1 and 2
$\displaystyle\phantom{~{}=~{}}+1\cdot\big{(}O_{n}(1)+O(\ell/\log\ell)+O_{n}(1)\big{)}$
Lines 3 to 6; solution $\displaystyle\phantom{~{}=~{}}+\ell\cdot
O(2^{n/2}\cdot\ell^{-3/2}\cdot\log\ell)\cdot\big{(}O_{n}(1)+o_{n}(1)+O_{n}(1)\big{)}$
Lines 3 to 6; collisions
$\displaystyle~{}=~{}O(2^{n/2}\cdot\ell^{-1/2}\cdot\log\ell).$

######  Observation 3 (Adapting 3 to Word RAM).

In the word RAM model, multiplication and evaluation of our pseudolinear hash
function $\bm{h}_{m}$ each take constant time. Hence, for any word length
$\ell=\Omega(n)$ we can get a variant of 3 with expected runtime
$O(2^{n/2}\cdot n^{-1/2}\cdot\log n)$, essentially by performing 3 as if the
word length were $\ell^{\prime}:=0.1n$. By a similar conversion from [BDP05]:

Run 3 as if the word length were $\ell^{\prime}=0.1n$, which results in the
modified parameters $m^{\prime}=3\log\ell^{\prime}$,
$|D^{\prime}|=\log\ell^{\prime}$, and
$|A^{\prime}|=|B^{\prime}|=(n-|D^{\prime}|)/2$ etc., except for two
modifications:

  1. 1.

Line 2 packs
$q^{\prime}:=\min\\{\ell^{\prime},\,\ell\\}/m^{\prime}=\Theta(\frac{n}{\log
n})$ many $m^{\prime}$-bit hashes into each word of $\bm{H}_{A^{\prime}}$,
$\bm{H}_{B^{\prime}}$, so every $(\ell^{\prime}/m^{\prime})$ hashes are stored
in $\ell^{\prime}/(m^{\prime}q^{\prime})=\Theta_{n}(1)$ words rather than a
single word.

  2. 2.

Before Line 5, create a table that memoizes the result of every comparison of
two $\ell^{\prime}$-bit strings in time
$(2^{\ell^{\prime}})^{2}\cdot\mathrm{poly}(\ell^{\prime})=O(2^{0.21n})$. This
table can then be accessed via a
$2\ell^{\prime}/(m^{\prime}q^{\prime})=\Theta_{n}(1)$-word index in constant
time. Line 5 replaces the constant-time $\mathsf{AC}^{0}$ circuit RAM
operation on two $\ell^{\prime}$-bit strings with a constant-time lookup into
this table.

Compared with running 3 itself for $\ell^{\prime}=0.1n$, the only difference
of this variant is that $\bm{H}_{A^{\prime}}$ and $\bm{H}_{B^{\prime}}$ are
stored in $\Theta_{n}(1)$ times as many words, so the correctness is easy to
check. The expected time taken for the collisions in each execution of Line 5
is $(q^{\prime})^{2}\cdot O(2^{-m^{\prime}})\cdot O(q^{\prime})=o_{n}(1)$.
Thus, the overall runtime is as claimed:

$\displaystyle\underbrace{O(2^{|A^{\prime}|}+2^{|B^{\prime}|}+2^{|D^{\prime}|}+2^{0.21n})}_{\text{Lines~{}\ref{alg:BitPacking:1}
and
\ref{alg:BitPacking:2}}}~{}+~{}\underbrace{O(q^{\prime})+2^{|D^{\prime}|}\cdot
O((2^{|A^{\prime}|}+2^{|B^{\prime}|})/q^{\prime})}_{\text{Lines~{}\ref{alg:BitPacking:3}
to \ref{alg:BitPacking:6}; solution versus collisions}}~{}=~{}O(2^{n/2}\cdot
n^{-1/2}\cdot\log n).$

##  4 $\Omega(n^{0.01})$-Factor Speedup via Orthogonal Vectors and the
Representation Method

Our second algorithm, 4 (see Figure 4), achieves a speedup of
$\Omega(\ell^{\gamma})\geq\Omega(n^{\gamma})$ over 2 for a constant
$\gamma>0.01$.666Similar to Section 3, while we investigate 4 in the regime
$\ell=\mathrm{poly}(n)$, analogous results apply for word length $\ell$ as
large as $O(2^{cn})$ for an absolute constant $c>0$. While this is a smaller
speedup than that achieved by the 3 algorithm, the 4 algorithm does not use
“bit tricks”. Instead, 4 combines 2 with the representation method of
Howgrave-Graham and Joux [HGJ10], so as to reduce the Subset Sum problem to
many small instances of the Orthogonal Vectors (OV) problem: namely, instances
with $O(\ell/\log\ell)$ many binary vectors of dimension
$\Theta(\log\ell)=\Theta(\log n)$. Such instances of OV can be solved quickly
through a single $\mathsf{AC}^{0}$ word operation in the circuit RAM model (or
through constantly many operations in the word RAM model after an initial
memoization step), which leads to our speedup.

The high-level idea behind our algorithm is to partition the input $X=A\cup
B\cup C$ into two large subsets777Technically, sub-multisets. We make the same
simplification hereafter. $A$ and $B$ and one small subset $C$ of size
$|C|=\Theta(\log\ell)$, and to run 2 on two lists formed from subsets of
$(A\cup C)$ and $(B\cup C)$. We describe in more detail below just how these
lists are formed, but roughly speaking they are created by modifying the
representation method (in a way somewhat similar to the algorithm of Nederlof
and Wegryzcki [NW21]) to ensure that the lists are not too long. Further, to
eliminate the false positives due to overlapping subsets of $C$, we exploit a
fast implementation of a function that computes a batch of small instances of
Orthogonal Vectors. (To see the relevance of the Orthogonal Vectors problem in
this context, note that a solution to an instance of OV on $k$-dimensional
Boolean vectors corresponds to two disjoint subsets of the set $[k]$.) Before
giving more details we provide some helpful notation:

Notation and setup. We write $\mathcal{Q}(C):=\\{T\mid T\subseteq
C~{}\text{and}~{}|T|\leq\frac{|C|}{4}\\}$ to denote the collection of all
quartersets for $C$. While $\mathcal{Q}(C)$ is useful for intuition, in fact,
as explained below, our algorithm will use a slight variant of it: we define
$\mathcal{Q}^{+\varepsilon_{2}}(C)$ to be the collection of all subsets of
size at most $(1+\varepsilon_{2})\frac{|C|}{4}$, where $\varepsilon_{2}>0$ is
a small constant that is fixed in the detailed description of the algorithm.

We denote by OV the Boolean function on $2\ell=\mathrm{poly}(n)$ many input
bits that takes as input two lists $(x^{1},\dots,x^{\ell/|C|})$,
$(y^{1},\dots,y^{\ell/|C|})$ of (at most) $\ell/|C|$ many binary vectors each,
where each binary vector $x^{i},\,y^{j}\in\\{0,1\\}^{|C|}$, and returns $1$ if
and only if the two lists contain an orthogonal pair, i.e., a pair $(i,\,j)$
such that $x^{i}_{k}\cdot y^{j}_{k}=0$ for every $1\leq k\leq|C|$. It is easy
to see that 4 is an $\mathsf{AC}^{0}$ operation on two $\ell$-bit words, and
thus it takes constant time in the circuit RAM model.

We return to the intuitive overview of our approach. At a high level, the
representation method works by first expanding the search space of possible
solutions; for our algorithm this is done by writing down the list
$\mathcal{Q}^{+\varepsilon_{2}}(C)$ of all “near-quartersets”. If a certain
Subset Sum solution $S\subseteq X$ satisfies $|S\cap C|\leq\frac{|C|}{2}$, the
restricted solution $S\cap C=Q_{1}\cup Q_{2}$ is the union of many different
pairs of disjoint quartersets, namely $Q_{1},Q_{2}\in\mathcal{Q}(C)$ with
$Q_{1}\cap Q_{2}=\emptyset$. In fact, we work on the list of near-quartersets,
$\mathcal{Q}^{+\varepsilon_{2}}(C)$, rather than $\mathcal{Q}(C)$, so as to
cover all disjoint pairs $(Q_{1},\,Q_{2})$ with $|Q_{1}|+|Q_{2}|\approx|C|/2$.

We then _filter_ the list $\mathcal{Q}^{+\varepsilon_{2}}(C)$: given a random
prime modulus $\bm{p}$ we extract those near-quartersets that fall into two
particular residue classes that sum to $\Sigma(S\cap C)\pmod{\bm{p}}$. With
appropriate preprocessing checks and parameter settings, this significantly
reduces the search space while ensuring that we retain some disjoint pair of
near-quartersets $Q_{1},\,Q_{2}\in\mathcal{Q}^{+\varepsilon_{2}}(C)$ that
recover the restricted solution, $Q_{1}\cup Q_{2}=S\cap C$ with $Q_{1}\cap
Q_{2}=\emptyset$.

Finally, we use a modified 2 procedure to search for a solution, i.e., two
sum-subset couples
$(a,\,Q_{1})\in(L_{A}\times\mathcal{Q}^{+\varepsilon_{2}}(C))$,
$(b,\,Q_{2})\times(L_{B}\times\mathcal{Q}^{+\varepsilon_{2}}(C))$ with
$a+\Sigma(Q_{1})+b+\Sigma(Q_{2})=\Sigma(S\cap A)+\Sigma(S\cap B)+\Sigma(S\cap
C)=\Sigma(S)=t$, verifying $Q_{1}\cap Q_{2}=\emptyset$ via the Boolean
function 4.

Procedure $\textup{\text{\tt Representation-OV}}(X,\,t)$ Input: An integer
multiset $X=\\{x_{1},\,x_{2},\,\dots,\,x_{n}\\}$ and an integer target $t$.
Setup: Constants $\varepsilon_{1}\approx 0.1579$ and $\varepsilon_{2}\approx
0.2427$, the solutions to Equations 3 and 4. Setup: Parameters $\beta\approx
1.1186$, $\lambda\approx 0.0202$, $s(\ell)$, and $k(n,\,\ell)$, all to be
specified in the proof. Setup: A uniform random prime modulus
$\bm{p}\sim\mathbb{P}[\ell^{1+\beta/2}:2\ell^{1+\beta/2}]$. 0. Fix any
partition of $X=A\cup B\cup C$ such that
$|C|=\beta\log(\frac{\ell}{\beta\log\ell})$ and $|A|=|B|=\frac{n-|C|}{2}$. 1.
Use Lemma 6 to solve $(X,t)$ if there exists a solution $S\subseteq X$ with
$|S\cap C|\notin(1\pm\varepsilon_{1})\frac{|C|}{2}$. 2. Use Lemma 5 to solve
$(X,t)$ if $|W(C)|\leq 2^{|C|}\cdot\ell^{-\lambda}$. 3. Create the sorted
lists $L_{A}$ and $L_{B}$ using 1. Let $\\{\bm{L}_{A,\,i}\\}_{i\in[\bm{p}]}$
be the sorted sublists given by $\bm{L}_{A,\,i}:=\\{a\in L_{A}\mid
a\equiv_{\bm{p}}i\\}$ and likewise for $\\{\bm{L}_{B,\,i}\\}_{i\in[\bm{p}]}$.
Create the collection $\mathcal{Q}^{+\varepsilon_{2}}(C)=\\{Q\mid Q\subseteq
C\text{ and }|Q|\leq(1+\varepsilon_{2})\frac{|C|}{4}\\}$. 4. Repeat Lines 5 to
6 either $s(\ell)$ times or until a total of $k(n,\,\ell)$ many sum-subset
couples have been created in Line 5 (whichever comes first): 5. Sample a
uniform random residue $\bm{r}\sim[\bm{p}]$. Then use Lemma 8 and the
subroutine
5 to create the sorted lists $\bm{R}_{A,\,\bm{r}}$ and $\bm{R}_{B,\,\bm{r}}$:
$\bm{R}_{A,\,\bm{r}}=\\{(a^{\prime}:=a+\Sigma(Q_{1}),\,Q_{1})\mid(a,\,Q_{1})\in
L_{A}\times\mathcal{Q}^{+\varepsilon_{2}}(C)~{}\text{with}~{}a^{\prime}\equiv_{\bm{p}}\bm{r}\\}$
and
$\bm{R}_{B,\,\bm{r}}=\\{(b^{\prime}:=b+\Sigma(Q_{2}),\,Q_{2})\mid(b,\,Q_{2})\in
L_{B}\times\mathcal{Q}^{+\varepsilon_{2}}(C)~{}\text{with}~{}b^{\prime}\equiv_{\bm{p}}(t-\bm{r})\\}$.
$\triangleright$ In fact, $\bm{R}_{A,\,\bm{r}}$ and $\bm{R}_{B,\,\bm{r}}$ are
stored in a succinct format by 5. 6. Use Lemma 8 (based on 2 and the Boolean
function 4)
to search the sorted lists $\bm{R}_{A,\,\bm{r}}$ and $\bm{R}_{B,\,\bm{r}}$ for
a solution $(a^{\prime},\,Q_{1})$, $(b^{\prime},\,Q_{2})$ such that
$a^{\prime}+b^{\prime}=t$ and $Q_{1}\cap Q_{2}=\emptyset$. Halt and return
“yes” if a solution is found. 7. Return “no” (i.e., no solution was found).
$\triangleright$ Possibly a false negative. Figure 4: The Representation-OV
algorithm.

Now we are ready to state and prove our result about 4:

######  Theorem 2.

4 is a one-sided error randomized algorithm for the Subset Sum problem (with
no false positives) with worst-case runtime $O(2^{n/2}\cdot\ell^{-\gamma})\leq
O(2^{n/2}\cdot n^{-\gamma})$, for some constant $\gamma>0.01$, and a success
probability at least $1/3$ in the circuit RAM model.

###### Proof of Correctness for 4.

The constants $\varepsilon_{1}\approx 0.1579$ and $\varepsilon_{2}\approx
0.2427$ given in the description of the algorithm are the solutions to the
following equations:

$\displaystyle\tfrac{1-H((1-\varepsilon_{1})/2)}{(1-\varepsilon_{1})/2}$
$\displaystyle~{}=~{}1-H(\tfrac{1-\varepsilon_{2}}{2}),$ (3) $\displaystyle
1+\varepsilon_{1}-3H(\tfrac{1-\varepsilon_{1}}{2})$
$\displaystyle~{}=~{}-2H(\tfrac{1+\varepsilon_{2}}{4}).$ (4)

Also, we set $\beta:=\frac{1}{H((1+\varepsilon_{2})/4)}\approx 1.1186$ and
$\lambda:=(1-10^{-5})\cdot\frac{1-\varepsilon_{1}}{2}\cdot\beta\cdot(1-H(\frac{1-\varepsilon_{2}}{2}))\approx
0.0202$.

Lines 1 and 2 preprocess the instance $(X,\,t)$, solving it deterministically
via Lemmas 5 and 6 unless both Conditions 4 and 4 hold:

Condition (1): $(X,\,t)$ is either a “yes” instance with $|S\cap
C|\in[(1-\varepsilon_{1})\frac{|C|}{2}:\frac{|C|}{2}]$ for each solution
$S\subseteq X$,888Given Line 1, a solution $S\subseteq X$ or its complementary
$(X\setminus S)$, as a solution to the complementary instance
$(X,\,\Sigma(X)-t)$, must have this property. or a “no” instance.

Condition (2): $|W(C)|>2^{|C|}\cdot\ell^{-\lambda}$. Note that this implies
$|W(T)|>2^{|T|}\cdot\ell^{-\lambda}$ for each $T\subseteq C$.

Lines 3 to 7 accept only if a solution
$t=a^{\prime}+b^{\prime}=(a+\Sigma(Q_{1}))+(b+\Sigma(Q_{2}))$ is found in Line
6, for which $a\in L_{A}$, $b\in L_{B}$, and
$Q_{1},\,Q_{2}\in\mathcal{Q}^{+\varepsilon_{2}}(C)$ are disjoint. As a
consequence, the algorithm never reports false positives.

It remains to show that Lines 4 to 6 accept a “yes” instance $(X,\,t)$ with
probability at least $1/3$ when $(X,\,t)$ satisfies Conditions 4 and 4.
Consider a solution $S\subseteq X$ and the following set $W^{\prime}$
containing distinct sums of all “$\varepsilon_{2}$-balanced” subsets of $S\cap
C$:

$W^{\prime}~{}:=~{}\\{\,\Sigma(Q)\mid Q\subseteq(S\cap
C)~{}\text{and}~{}|Q|\in(1\pm\varepsilon_{2})\tfrac{|S\cap C|}{2}\,\\}.\hskip
11.09654pt$

Line 3 creates the residue sublists
$L_{A}=\\{\bm{L}_{A,\,i}\\}_{i\in[\bm{p}]}$ and
$L_{B}=\\{\bm{L}_{B,\,i}\\}_{i\in[\bm{p}]}$. We say that a residue
$i\in[\bm{p}]$ is good if it satisfies $i-\Sigma(S\cap
A)\in(W^{\prime}\bmod\bm{p})$, namely there exists a subset
$Q_{1}\subseteq(S\cap C)$ of size $|Q_{1}|\in(1\pm\varepsilon_{2})\frac{|S\cap
C|}{2}$ such that $\Sigma(S\cap A)+\Sigma(Q_{1})\equiv_{\bm{p}}i$. On sampling
a good residue $\bm{r}=i$ in Line 5, both $Q_{1}$ and $Q_{2}:=(S\cap
C)\setminus Q_{1}$ are of size at most $(1+\varepsilon_{2})\frac{|S\cap
C|}{2}\leq(1+\varepsilon_{2})\frac{|C|}{4}$, so they are included in the
collection $\mathcal{Q}^{+\varepsilon_{2}}(C)$ and, respectively, in the lists
$\bm{R}_{A,\,\bm{r}}$ and $\bm{R}_{B,\,\bm{r}}$ created in Line 5. Then using
Lemma 8, we are ensured to find the solution $S=(S\cap A)\cup(S\cap
B)\cup(Q_{1}\cup Q_{2})$.

Hence it suffices to (i) lower bound the probability that at least one of the
$s(\ell)$ samples $\bm{r}\sim[\bm{p}]$ is good, and (ii) upper bound the
probability that these samples generate a total of $k(n,\,\ell)$ or more sum-
subset couples.

(i). We claim that the size of set $W^{\prime}$ is at least $\Omega(2^{|S\cap
C|}\cdot\ell^{-\lambda})\geq\widetilde{\Omega}(\ell^{(1-\varepsilon_{1})\cdot\beta/2-\lambda})$
and is at most $2^{|S\cap C|}\leq\ell^{\beta/2}$. The lower bound on the size
comes from a combination of two observations. First, the set $(S\cap C)$ has
at least $2^{|S\cap C|}\cdot\ell^{-\lambda}$ many distinct subset sums, by
Condition 4. Second, the number of subsets $Q\subseteq(S\cap C)$ of size
$|Q|\notin(1\pm\varepsilon_{2})\frac{|S\cap C|}{2}$ is at most $2\cdot
2^{H(\frac{1-\varepsilon_{2}}{2})\cdot|S\cap C|}=o(2^{|S\cap
C|}\cdot\ell^{-\lambda})$, given Stirling’s approximation (Equation 1) and the
technical condition

$\textstyle\frac{|S\cap
C|}{\log\ell}\cdot(1-H(\frac{1-\varepsilon_{2}}{2}))~{}\geq~{}(1-o_{n}(1))\cdot\frac{1-\varepsilon_{1}}{2}\cdot\beta\cdot(1-H(\frac{1-\varepsilon_{2}}{2}))~{}>~{}\lambda,$

which is true for our choice of $\lambda$.

The upper and lower bounds on $|W^{\prime}|$ allow us to apply Lemma 7: with
probability at least $3/4$ over the modulus
$\bm{p}\sim\mathbb{P}[\ell^{1+\beta/2}:2\ell^{1+\beta/2}]$, there are
$|W^{\prime}\bmod\bm{p}|=\Omega(|W^{\prime}|)=\widetilde{\Omega}(\ell^{(1-\varepsilon_{1})\cdot\beta/2-\lambda})$
many good residues. Conditioned on this event, taking

$s(\ell)~{}:=~{}\widetilde{\Theta}(\ell^{1+\lambda+\varepsilon_{1}\cdot\beta/2})~{}\geq~{}\widetilde{\Omega}\left(\tfrac{\bm{p}}{|(W^{\prime}\bmod\bm{p})|}\right)$

many samples $\bm{r}\sim[\bm{p}]$ yields at least one good residue with
probability $\geq 2/3$.

(ii). All candidate lists $\\{\bm{R}_{A,\,i}\\}_{i\in[\bm{p}]}$,
$\\{\bm{R}_{B,\,i}\\}_{i\in[\bm{p}]}$ together have a total of

$(|L_{A}|+|L_{B}|)\cdot|\mathcal{Q}^{+\varepsilon_{2}}(C)|\leq 2\cdot
2^{(n-|C|)/2}\cdot 2^{|C|/\beta}=O(2^{n/2}\cdot\ell^{1-\beta/2})$

sum-subset couples, by construction (Line 3), the choices of $|A|$, $|B|$,
$|C|$, and Stirling’s approximation (Equation 1). For any outcome of the
random modulus $\bm{p}=p=\Theta(\ell^{1+\beta/2})$, a number of $s(\ell)$
samples $\bm{r}\sim[p]$ generate a total of
$O(2^{n/2}\cdot\ell^{1-\beta/2})\cdot
s(\ell)/p=\widetilde{O}(2^{n/2}\cdot\ell^{-((1-\varepsilon_{1}/2)\cdot\beta-(1+\lambda))})$
sum-subset couples in expectation. By setting a large enough cutoff

$k(n,\,\ell)~{}:=~{}\widetilde{\Theta}(2^{n/2}\cdot\ell^{-((1-\varepsilon_{1}/2)\cdot\beta-(1+\lambda))}),\hskip
79.6678pt$

the probability that $k(n,\,\ell)$ or more sum-subset couples are generated is
at most $1/6$.

Overall, our algorithm succeeds with probability
$\geq(3/4)\cdot(2/3)-(1/6)=1/3$. ∎

###### Proof of Runtime for 4.

Recalling the assumption $\ell=\mathrm{poly}(n)$:

  * •

Line 1 takes time
$\widetilde{O}(2^{n/2}\cdot\ell^{-(1-H((1-\varepsilon_{1})/2))\cdot\beta/2})$,
by Lemma 6.

  * •

Line 2 takes time $\widetilde{O}(2^{n/2}\cdot\ell^{-\lambda/2})$, by Lemma 5.

  * •

Line 3 takes time $O(2^{|A|}+2^{|B|}+2^{|C|})\cdot
O(\log\ell)=\widetilde{O}(2^{n/2}\cdot\ell^{-\beta/2})$, by Lemma 2, the
choices of $|A|$, $|B|$, $|C|$, and that the modulo operation in the circuit
RAM model takes time $O(\log\ell)$.

  * •

Lines 4 to 6 take time
$\widetilde{O}(k(n,\,\ell))=\widetilde{O}(2^{n/2}\cdot\ell^{-((1-\varepsilon_{1}/2)\cdot\beta-(1+\lambda))})$,
because a single iteration (Lemma 8) takes time
$\widetilde{O}(|\bm{R}_{A,\,\bm{r}}|+|\bm{R}_{B,\,\bm{r}}|)$ and by
construction we create a total of at most
$\sum_{\bm{r}}(|\bm{R}_{A,\,\bm{r}}|+|\bm{R}_{B,\,\bm{r}}|)\leq k(n,\,\ell)$
many sum-subset couples.

The runtime of Line 3 is dominated by that of Line 1, so the bottleneck occurs
in Line 1, Line 2, or Lines 4 to 6. For the choices of constants given in the
algorithm, we achieve a speedup of $\Omega(\ell^{\gamma})$ for any constant
$\gamma\in(0,\,\gamma_{*})$, where the

$\textstyle\gamma_{*}~{}:=~{}\min\Big{\\{}\,\lambda/2,\quad(1-H(\frac{1-\varepsilon_{1}}{2}))\cdot\beta/2,\quad(1-\varepsilon_{1}/2)\cdot\beta-(1+\lambda)\,\Big{\\}}~{}=~{}\lambda/2~{}\approx~{}0.0101.\qed$

###  4.1 Auxiliary Lemmas

A first “preprocessing lemma” stems from the observation that a not-too-large
subset $Y\subseteq X$ with few distinct subset sums (i.e., $|W(Y)|\ll
2^{|Y|}$) can help speed up 2. This idea goes back to [AKKN15, AKKN16],
although the condition of “few distinct subset sums” we use refers to sets
with polynomially rather than exponentially fewer subset sums than the maximum
possible number.

######  Lemma 5 (Speedup via Additive Structure).

Let $(X,\,t)$ be an $n$-integer Subset Sum instance. Given as input $(X,\,t)$
and a subset $Y\subseteq X$ of size $|Y|\leq n/2$ such that $|W(Y)|\leq
2^{|Y|}\cdot\ell^{-\varepsilon}$ for some constant $\varepsilon>0$, the
instance $(X,\,t)$ can be solved deterministically in time
$\widetilde{O}(2^{n/2}\cdot\ell^{-\varepsilon/2})$.

###### Proof.

Fix any size-$(\frac{n+\varepsilon\log\ell}{2})$ subset $A$ such that
$Y\subseteq A\subseteq X$; we have $|W(A)|\leq 2^{|A\setminus
Y|}\cdot|W(Y)|\leq 2^{n/2}\cdot\ell^{-\varepsilon/2}$. We also have
$|W(X\setminus A)|\leq 2^{|X\setminus A|}=2^{n/2}\cdot\ell^{-\varepsilon/2}$.
By Lemmas 2 and 3, it takes overall time
$O(2^{n/2}\cdot\ell^{-\varepsilon/2}\cdot\log n)$ in the regime
$\ell=\mathrm{poly}(n)$ to create the sorted lists $L_{A}$, $L_{X\setminus A}$
and to run 2. ∎

Another useful preprocessing lemma shows that the existence of a solution that
is “unbalanced” vis-a-vis a given small subset yields a speedup:

######  Lemma 6 (Speedup via Unbalanced Solutions).

Let $(X,\,t)$ be an $n$-integer Subset Sum instance that has a solution. Given
as input $(X,\,t)$ and a subset $Y\subseteq X$ of size
$|Y|=\beta\log(\ell/(\beta\log\ell))$ for $\beta$ as specified in 4 such that
some solution $S\subseteq X$ satisfies $|S\cap
Y|\notin(1\pm\varepsilon)\frac{|Y|}{2}$ for some constant $\varepsilon>0$, the
solution $S$ can be found deterministically in time
$\widetilde{O}(2^{n/2}\cdot\ell^{-\delta/2})$, where the constant
$\delta:=(1-H(\frac{1-\varepsilon}{2}))\cdot\beta$.

###### Proof.

We can assume without loss of generality that the solution $S$ satisfies
$|S\cap Y|\leq\frac{|Y|}{2}$ (since either the original instance $(X,\,t)$ or
the complementary instance $(X,\,\Sigma(X)-t)$ must satisfy this property, and
we can attempt both instances and only double the runtime). Hence we can
suppose $|S\cap Y|\leq(1-\varepsilon)\frac{|Y|}{2}$. Then the sorted list
$L^{\prime}_{Y}$ of the set $\\{\Sigma(T)\mid T\subseteq
Y~{}\text{and}~{}|T|\leq(1-\varepsilon)\frac{|Y|}{2}\\}$ can be created in
time $O(2^{|Y|})=O(\ell^{\beta})=\mathrm{poly}(n)$ using 1 (restricted to
subsets of sizes $<(1-\varepsilon)\frac{|Y|}{2}$).

Fix any size-$(\frac{n+(\delta/\beta)|Y|}{2})$ subset $A$ with $Y\subseteq
A\subseteq X$. In the regime $\ell=\mathrm{poly}(n)$, we can use
$L^{\prime}_{Y}$ and Lemma 3 to create the sorted list $L^{\prime}_{A}$ of
$\\{\Sigma(T)\mid T\subseteq A~{}\text{and}~{}|T\cap
Y|<(1-\varepsilon)\frac{|Y|}{2}\\}$ in time

$\widetilde{O}(|L^{\prime}_{A}|)\leq\widetilde{O}(2^{|A\setminus
Y|}\cdot|L^{\prime}_{Y}|)\leq\widetilde{O}(2^{|A\setminus Y|}\cdot
2^{H(\frac{1-\varepsilon}{2})\cdot|Y|})\leq\widetilde{O}(2^{n/2}\cdot\ell^{-\delta/2}),$

following Stirling’s approximation (Equation 1) and the choices of $|Y|$ and
$|A|$. Moreover, we can use Lemma 2 to create the sorted list $L_{X\setminus
A}$ in time $O(2^{|X\setminus
A|})=\widetilde{O}(2^{n/2}\cdot\ell^{-\delta/2})$.

Provided $|S\cap Y|<(1-\varepsilon)\frac{|Y|}{2}$, running 2 on
$L^{\prime}_{A}$ and $L_{X\setminus A}$ solves $(X,t)$ and takes time
$O(|L^{\prime}_{A}|+|L_{X\setminus
A}|)=\widetilde{O}(2^{n/2}\cdot\ell^{-\delta/2})$. The overall runtime is
$\widetilde{O}(2^{n/2}\cdot\ell^{-\delta/2})$. ∎

The next lemma specifies a parameter space within which any set of distinct
integers is likely to fall into many residue classes modulo a random prime.
This allows us to reduce the search space by considering only solutions that
fall into certain residue classes.

######  Lemma 7 (Distribution of Integer Sets modulo Random Primes).

Fix a set $Y$ of at most $|Y|\leq\ell^{\beta/2}$ distinct $\ell$-bit integers
for $\beta$ as specified in 4. For a uniform random modulus
$\bm{p}\sim\mathbb{P}[\ell^{1+\beta/2}:2\ell^{1+\beta/2}]$, the residue set
has size $|(Y\bmod\bm{p})|=\Theta(|Y|)$ with probability at least $3/4$.

###### Proof.

By the prime number theorem [HW+79, Equation (22.19.3)], there are at least
$\frac{\ell^{1+\beta/2}}{(1+\beta/2)\cdot\log\ell}$ primes in
$\mathbb{P}[\ell^{1+\beta/2}:2\ell^{1+\beta/2}]$ (for any sufficiently large
$\ell$). Given any two distinct integers $y\neq z\in Y$, the difference
$|y-z|\leq 2^{\ell}$ has at most $\frac{\ell}{(1+\beta/2)\cdot\log\ell}$
distinct prime factors in $\mathbb{P}[\ell^{1+\beta/2}:2\ell^{1+\beta/2}]$.
Thus under a uniform random choice of modulus
$\bm{p}\sim\mathbb{P}[\ell^{1+\beta/2}:2\ell^{1+\beta/2}]$, the second
frequency moment $\bm{f}_{(2)}:=|\\{(y,\,z)\mid y,\,z\in
Y~{}\text{with}~{}y\equiv_{\bm{p}}z\\}|$ has the expectation

$\displaystyle\operatorname{{\bf E}}_{\bm{p}}[\bm{f}_{(2)}]~{}=~{}|\\{y=z\in
Y\\}|+|\\{y\neq z\in
Y\\}|\cdot\ell^{-\beta/2}~{}=~{}|Y|+(|Y|^{2}-|Y|)\cdot\ell^{-\beta/2}~{}\leq~{}2|Y|.$

Therefore, with an arbitrarily high constant probability, we have
$\bm{f}_{(2)}=O(|Y|)$ and, by the Cauchy-Schwarz inequality
$|Y\bmod\bm{p}|\cdot\bm{f}_{(2)}\geq|Y|^{2}$, a residue set of size
$|Y\bmod\bm{p}|=\Omega(|Y|)$. ∎

Subroutine $\textup{\text{\tt Residue-Couple-
List}}(\\{L_{A,\,i}\\}_{i\in[p]},\,\mathcal{Q}^{+\varepsilon}(C),\,r)$ Input:
A collection of $p=\mathrm{poly}(\ell)$ sorted sublists
$L_{A}=\bigcup_{i\in[p]}L_{A,\,i}$, for some subset $A\subseteq X$, indexed by
residue class modulo $p$. Output: A sorted sum-subset list $R_{A,\,r}$ with
elements in the sum-collection format
$(a^{\prime},\,\mathcal{Q}_{a^{\prime}})$. 5(a) For each
$Q\in\mathcal{Q}^{+\varepsilon}(C)$, create the sum-subset sublist
$R_{Q}:=f_{Q}(L_{A,\,j(Q)})$ by applying $f_{Q}$, the element-to-couple
operation $a\mapsto(a^{\prime}:=a+\Sigma(Q),\,Q)$, to the particular input
sublist of index $j(Q):=((r-\Sigma(Q))\bmod p)$. $\triangleright$ Each $R_{Q}$
is sorted by the sums $a^{\prime}$. 5(b) Let $R_{A,\,r}$ be the list obtained
by merging $\\{R_{Q}\\}_{Q\in\mathcal{Q}^{+\varepsilon}(C)}$, sorted by sums
$a^{\prime}=a+\Sigma(Q)$.
For each distinct sum $a^{\prime}$, compress all couples
$(a^{\prime},\,Q_{1})$, $(a^{\prime},\,Q_{2})$, $\dots$ with the same first
element $=a^{\prime}$ into a single data object
$(a^{\prime},\,\mathcal{Q}_{a^{\prime}}:=\\{Q_{1},Q_{2},\dots\\})$.
$\triangleright$ Note that for each sum $a^{\prime}$ we have
$a^{\prime}\equiv_{p}r$ and
$|\mathcal{Q}_{a^{\prime}}|\leq|\mathcal{Q}^{+\varepsilon}(C)|$. Figure 5: The
Residue-Couple-List subroutine.

######  Lemma 8 (Sorted Lists $\bm{R}_{A,\,\bm{r}}$ and $\bm{R}_{B,\,\bm{r}}$;
Lines 5 and 6).

In the context of 4: (i) Line 5 uses the subroutine 5 to create the sorted
lists $\bm{R}_{A,\,\bm{r}}$, $\bm{R}_{B,\,\bm{r}}$ in time
$\widetilde{O}(|\bm{R}_{A,\,\bm{r}}|+|\bm{R}_{B,\,\bm{r}}|)$. Moreover, (ii)
Line 6 finds a solution pair $(a^{\prime},\,Q_{1})\in\bm{R}_{A,\,\bm{r}}$,
$(b^{\prime},\,Q_{2})\in\bm{R}_{B,\,\bm{r}}$, if one exists, in time
$O(|\bm{R}_{A,\,\bm{r}}|+|\bm{R}_{B,\,\bm{r}}|)$.

###### Proof.

Line 5 creates $\bm{R}_{A,\,\bm{r}}$ and $\bm{R}_{B,\,\bm{r}}$ using the
subroutine 5 (see Figure 5). First, we claim that 5 takes time
$\widetilde{O}(|\bm{R}_{A}|)$ in the regime $\ell=\mathrm{poly}(n)$:

  * •

Line 5(a) takes time
$\Sigma_{Q\,\in\,\mathcal{Q}^{+\varepsilon_{2}}(C)}O(|\bm{R}_{Q}|)=O(|\bm{R}_{A,\,\bm{r}}|)$,
since all shifts $\Sigma(Q)$ for $Q\in\mathcal{Q}^{+\varepsilon_{2}}(C)$ can
be precomputed and memoized when the collection
$\mathcal{Q}^{+\varepsilon_{2}}(C)$ is created in Line 3.

  * •

Line 5(b) builds one sorted list $\bm{R}_{A,\,\bm{r}}$ from
$|\mathcal{Q}^{+\varepsilon_{2}}(C)|\leq
2^{|C|/\beta}=\ell/(\beta\log\ell)=\mathrm{poly}(n)$ sorted sublists
$\\{\bm{R}_{Q}\\}_{Q\,\in\,\mathcal{Q}^{+\varepsilon_{2}}(C)}$, taking time
$O(|\bm{R}_{A,\,\bm{r}}|\cdot\log n)$ via the classic merge sort algorithm.

After Line 5 creates the sorted lists
$\bm{R}_{A,\,\bm{r}}=\\{(a^{\prime},\,\bm{\mathcal{Q}}_{a^{\prime}})\\}$ and
$\bm{R}_{B,\,\bm{r}}=\\{(b^{\prime},\,\bm{\mathcal{Q}}_{b^{\prime}})\\}$, Line
6 can run 2 based on the (ordered) indices $a^{\prime}$ and $b^{\prime}$ in
time $O(|\bm{R}_{A,\,\bm{r}}|+|\bm{R}_{B,\,\bm{r}}|)$. This ensures that we
discover every pair $(a^{\prime},\,\bm{\mathcal{Q}}_{a^{\prime}})$,
$(b^{\prime},\,\bm{\mathcal{Q}}_{b^{\prime}})$ such that
$a^{\prime}+b^{\prime}=t$. Such a pair yields a solution if and only if it
contains two disjoint near-quartersets
$Q_{1}\in\bm{\mathcal{Q}}_{a^{\prime}}$,
$Q_{2}\in\bm{\mathcal{Q}}_{b^{\prime}}$ with $Q_{1}\cap Q_{2}=\emptyset$,
which we can check in constant time by one call of the Boolean function 4.
Namely, each near-quarterset $Q\in\mathcal{Q}^{+\varepsilon_{2}}(C)$ is stored
in $|C|<\beta\log\ell$ bits, so each collection
$\bm{\mathcal{Q}}_{a^{\prime}},\,\bm{\mathcal{Q}}_{b^{\prime}}\subseteq\mathcal{Q}^{+\varepsilon_{2}}(C)$
can be stored a single word
$|C|\cdot|\mathcal{Q}^{+\varepsilon_{2}}(C)|\leq\ell$. Thus one call of 4
suffices to check a given pair $(a^{\prime},\,\bm{\mathcal{Q}}_{a^{\prime}})$,
$(b^{\prime},\,\bm{\mathcal{Q}}_{b^{\prime}})$. Overall, Line 6 takes time
$O(|\bm{R}_{A,\,\bm{r}}|+|\bm{R}_{B,\,\bm{r}}|)$. ∎

######  Observation 4 (Adapting 4 to Word RAM).

In the word RAM model, it may take superconstant time to evaluate the Boolean
function 4. Similar to the strategy used in Section 3, our word RAM variant
avoids this issue by performing 4 as if the word length were
$\ell^{\prime}:=0.1n$ (using sets $A^{\prime}$, $B^{\prime}$, $C^{\prime}$,
etc., with appropriate size modifications), except for three modifications:

  1. 1.

In lines 3 and 5(b), on creating a (sub)collection
$\mathcal{Q}\subseteq\mathcal{Q}^{+\varepsilon_{2}}(C^{\prime})$ as a bit
string, store it in at most
$\leq\lceil|\mathcal{Q}^{+\varepsilon_{2}}(C^{\prime})|\cdot|C^{\prime}|/\ell\rceil\leq\lceil\ell^{\prime}/\ell\rceil=\Theta(1)$
words (since a single word with $\ell$ bits may be insufficient).

  2. 2.

In Line 3, after creating the collection
$\mathcal{Q}^{+\varepsilon_{2}}(C^{\prime})$, create a lookup table OV′ that
memoizes the input-output result of the Boolean function 4 on each
subcollection pair
$\mathcal{Q}_{a^{\prime}},\,\mathcal{Q}_{b^{\prime}}\subseteq\mathcal{Q}^{+\varepsilon_{2}}(C^{\prime})$
in time
$(2^{|\mathcal{Q}^{+\varepsilon_{2}}(C^{\prime})|})^{2}\cdot\mathrm{poly}(|\mathcal{Q}^{+\varepsilon_{2}}(C^{\prime})|)\leq(2^{\ell^{\prime}})^{2}\cdot\mathrm{poly}(\ell^{\prime})=O(2^{0.21n})$.
This table can then be accessed using a
$2\lceil\ell^{\prime}/\ell\rceil=\Theta(1)$-word index in constant time.

  3. 3.

Line 6 replaces the Boolean function 4 (namely a constant-time
$\mathsf{AC}^{0}$ circuit RAM operation) with constant-time lookup into OV′.

Compared with running 4 itself for $\ell^{\prime}=0.1n$, the only difference
of this variant is that $\bm{R}_{A,\,\bm{r}}$ and $\bm{R}_{B,\,\bm{r}}$ are
stored in $\lceil\ell^{\prime}/\ell\rceil=\Theta(1)$ times as many words,
given $\ell=\Omega(n)$. Hence, it is easy to check the correctness and the
runtime
$O(2^{n/2}\cdot{\ell^{\prime}}^{-\gamma}\cdot\lceil\ell^{\prime}/\ell\rceil)=O(2^{n/2}\cdot
n^{-\gamma})$, for the same constant $\gamma>0.01$.

##  5  Subset Sum in Time $O(2^{n/2}\cdot n^{-0.5023})$

The algorithm in this section is a delicate combination of 3 and 4. Our main
result (see Theorem 3) demonstrates that problem-specific features of Subset
Sum can be exploited to obtain an (additional) nontrivial time savings beyond
what can be achieved only by augmenting 2 with generic bit-packing tricks.
Although the bookkeeping to analyze the algorithm of this section is somewhat
intricate, many of the ideas in this section were previewed in Section 4.

We begin by describing a difficulty that arises in the attempt to combine the
two building-block algorithms: (i) 3 saves time by removing a subset
$D\subseteq X$ from the input, then running a 2 variant on the resulting
subinstance multiple times. (ii) 4 runs a 2 variant on multiple subinstances
indexed by residue classes modulo a random prime $\bm{p}$. This presents a
problem: to get the time savings from bit packing, we would like to reuse
subinstances multiple times, but to get the time savings from the
representation method we need to build separate subinstances with respect to
each residue class $\pmod{\bm{p}}$ that contains elements of $W(D)$. To solve
this problem, we construct $D$ in a way that ensures the elements of $W(D)$
fall into few residue classes $\pmod{\bm{p}}$. Specifically, we fix $\bm{p}$
and consider two cases. In one case, the elements of $X$ fall into few residue
classes $\pmod{\bm{p}}$ and it is possible to choose a small set $D$ such that
the elements of $D$ (and $W(D)$) fall into very few residue classes
$\pmod{\bm{p}}$. In this case we need to construct just
$|W(D)\bmod\bm{p}|=\mathrm{polylog}(n)$ distinct subinstances. In the other
case, the elements of $X$ fall into many residue classes $\pmod{\bm{p}}$. In
this case, a carefully selected $D$ satisfies the weaker bound
$|W(D)\bmod\bm{p}|=\widetilde{O}(n^{\delta})$ for a small constant $\delta>0$,
increasing the number of subinstances we need to construct. However, the fact
that the elements of $X$ fall into many residue classes $\pmod{\bm{p}}$ lets
us select a larger set $C$ such that the subset sums in $W(S\cap C)$
distribute well $\pmod{\bm{p}}$ for any solution $S$, which offsets the
increase in runtime.

Like the $\mathsf{AC}^{0}$ operation 4 in the 4 algorithm, the core of our new
algorithm is another $\mathsf{AC}^{0}$ operation, 5.1, that solves Orthogonal
Vectors on small instances. In comparison, 5.1 also takes as input two
$\ell$-bit words containing multiple bit vectors of length $O(\log n)$, but
now the bit vectors in either word may come from two or more lists, and each
list is indexed by the $m$-bit hash $\bm{h}_{m}(s)$ of a corresponding subset
sum $s$, for $m=3\log\ell$. Hence, 5.1 may solve multiple small Orthogonal
Vectors instances at once.

######  Theorem 3.

Packed-Representation-OVis a one-sided error randomized algorithm for the
Subset Sum problem (with no false positives) with worst-case runtime
$O(2^{n/2}\cdot n^{-(1/2+\gamma)})$, for some constant $\gamma>0.0023$, and a
success probability at least $1/12$ in the circuit RAM model.

Define the density constant $\rho:=\frac{\log n}{\log\ell}$, which is bounded
as $0<\rho\leq 1+\Theta(\frac{1}{\log n})$ given $\ell=\mathrm{poly}(n)$ and
$\ell=\Omega(n)$.999Another density parameter $n/\log t$ is widely used in the
literature (e.g., [AKKN16]), which can be regarded as $n/\ell$ in our language
(since $\ell=\Omega(\log t)$). In comparison, our density constant
$\rho=\frac{\log n}{\log\ell}$ is more “fine-grained”.

In the density range $0<\rho\leq(2-H(1/4))^{-1}\approx 0.8412$,
LABEL:alg:packed-rep-ov can achieve the claimed speedup
$\widetilde{\Omega}(\ell^{1/2})=\widetilde{\Omega}(n^{1/(2\rho)})\geq\Omega(n^{0.5943})\geq\Omega(n^{0.5023})$
by naively simulating 3, so it suffices to consider the remaining range
$(2-H(1/4))^{-1}<\rho\leq 1+\Theta(1/\log n)$.

###### Proof of Correctness for Packed-Representation-OV.

The constant $\lambda=\lambda(\rho)$ given in the description of the algorithm
is defined by the following equation:

$\textstyle\lambda~{}=~{}\lambda(\rho)~{}:=~{}(1-10^{-5})\cdot\frac{1-\varepsilon_{1}}{2}\cdot(1-H(\frac{1-\varepsilon_{2}}{2}))\cdot\beta~{}\approx~{}1.8065\times
10^{-2}\cdot\beta(\rho).$ (5)

The other two constants $\beta=\beta(\rho)$,
$\varepsilon^{\prime}_{1}=\varepsilon^{\prime}_{1}(\rho)$ will be specified
later.

Lines LABEL:alg:packed-rep-ov:1 and LABEL:alg:packed-rep-ov:2 preprocess the
instance $(X,\,t)$, solving it by either or both of Lemmas 11 and 12, unless
the outcome of the random subset $\bm{C}=C$ satisfies Conditions 5 and 5 in
both cases. Lemma 11 applies in LABEL:pack-rep-case2, provided
$2^{|C|}=2^{\beta\log(\ell/(\beta\log\ell))}=\widetilde{\Omega}(\ell^{\beta})>\ell^{\lambda}$
by Equation 5. (In LABEL:pack-rep-case1 we have $|W(C)\pmod{\bm{p}}|=2^{|C|}$
by Lemma 9, which is even stronger than Condition 5.)

Condition (1): $(X,\,t)$ is either a “yes” instance with $|S\cap
C|\in[(1-e_{1})\frac{|C|}{2}:\frac{|C|}{2}]$ for each solution $S\subseteq X$
(cf. Footnote 8), or a “no” instance.

Condition (2): $|W(C)|>2^{|C|}\cdot\ell^{-\lambda}$. Note that this implies
$|W(T)|>2^{|T|}\cdot\ell^{-\lambda}$ for each $T\subseteq C$.

Lines LABEL:alg:packed-rep-ov:3 to LABEL:alg:packed-rep-ov:10 accept only if a
solution $(a^{\prime},\,Q_{1})$, $(b^{\prime},\,Q_{2})$ is found in Line
LABEL:alg:packed-rep-ov:9 for which $a^{\prime}+b^{\prime}=t^{\prime\prime}$
and $Q_{1}\cap Q_{2}=\emptyset$. As a consequence, the algorithm never makes a
false positive mistake.

It remains to show that Lines LABEL:alg:packed-rep-ov:3 to LABEL:alg:packed-
rep-ov:9 accept a “yes” instance $(X,\,t)$ with constant probability. Fix any
outcome of the partition $X=\bm{A}\cup\bm{B}\cup\bm{C}\cup\bm{D}=A\cup B\cup
C\cup D$. Consider a solution $S\subseteq X$ and the set
$W^{\prime}=W^{\prime}(S\cap C)$ of distinct sums of all the
“$e_{2}$-balanced” subsets of $S\cap C$:

$W^{\prime}~{}:=~{}\\{\,\Sigma(Q)\mid Q\subseteq(S\cap
C)~{}\text{and}~{}|Q|\in(1\pm e_{2})\tfrac{|S\cap C|}{2}\,\\}.$

Line LABEL:alg:packed-rep-ov:3 creates the residue sublists
$L_{A}=\\{L_{A,\,i}\\}_{i\in[\bm{p}]}$ and
$L_{B}=\\{L_{B,\,i}\\}_{i\in[\bm{p}]}$. We say that a residue $i\in[\bm{p}]$
is good if it satisfies $i-\Sigma(S\cap A)\in(W^{\prime}\bmod\bm{p})$, namely
there exists a subset $Q_{1}\subseteq(S\cap C)$ of size $|Q_{1}|\in(1\pm
e_{2})\frac{|S\cap C|}{2}$ such that $\Sigma(S\cap
A)+\Sigma(Q_{1})\equiv_{p}i$.

In the particular iteration $t^{\prime}_{*}:=((t-\Sigma(S\cap D))\bmod\bm{p})$
of Line LABEL:alg:packed-rep-ov:4: on sampling a good residue $\bm{r}=i$ in
Line LABEL:alg:packed-rep-ov:6, both sets $Q_{1}$ and $Q_{2}:=(S\cap
C)\setminus Q_{1}$ are of size $\leq(1+e_{2})\frac{|S\cap
C|}{2}\leq(1+e_{2})\frac{|C|}{4}$, so they are included in
$\mathcal{Q}^{+e_{2}}(C)$ and, respectively, in the lists
$R_{A,\,t^{\prime}_{*},\,\bm{r}}$ and $R_{B,\,t^{\prime}_{*},\,\bm{r}}$
created in Line LABEL:alg:packed-rep-ov:6. As a consequence, later in the
iteration $t^{\prime\prime}_{*}:=t-\Sigma(S\cap D)$ of Line LABEL:alg:packed-
rep-ov:8, we can find the solution pair $(a^{\prime},\,Q_{1})$,
$(b^{\prime},\,Q_{2})$ with constant probability, by Lemma 14, for which
$a^{\prime}+b^{\prime}=(\Sigma(S\cap A)+\Sigma(Q_{1}))+(\Sigma(S\cap
B)+\Sigma(Q_{2}))=t^{\prime\prime}_{*}$ and $Q_{1}\cap Q_{2}=\emptyset$.

Hence, it suffices to reason about the iteration $t^{\prime}_{*}$ of Line
LABEL:alg:packed-rep-ov:4, (i) lower-bounding the probability that at least
one of the $s(\ell)$ many samples $\bm{r}\sim[\bm{p}]$ in Line
LABEL:alg:packed-rep-ov:6 is good, and (ii) upper-bounding the probability
that these samples generate a total of $k(n,\,\ell)$ or more sum-subset
couples.

LABEL:pack-rep-case1: The proof below only relies on Condition 5, and works
for any outcome of the modulus $\bm{p}=p=\Theta(n^{1+\beta/2})$ and the
partition $X=\bm{A}\cup\bm{B}\cup\bm{C}\cup\bm{D}=A\cup B\cup C\cup D$.

(i). By Lemma 9, we have $|W(C)\bmod p|=2^{|C|}$, which implies that $|W(S\cap
C)\bmod p|=2^{|S\cap C|}$ and $|W^{\prime}\bmod p|=\binom{|S\cap C|}{|S\cap
C|/2}=\widetilde{\Omega}(2^{|S\cap
C|})\geq\widetilde{\Omega}(2^{(1-\varepsilon^{\prime}_{1})\cdot|C|/2})=\widetilde{\Omega}(\ell^{(1-\varepsilon^{\prime}_{1})\cdot\rho/4})$,
by Stirling’s approximation, Condition 5, and the choice of $|C|$, $e_{1}$,
$e_{2}$. Hence, a number of $s(\ell)=\Omega(\tfrac{p}{|W^{\prime}\bmod p|})$
samples $\bm{r}\sim[p]$ yield at least one good residue with probability $\geq
2/3$, for any large enough

$\displaystyle
s(\ell)~{}=~{}s^{\prime}(\ell)~{}:=~{}\widetilde{\Theta}(\ell^{1+\beta/2-(1-\varepsilon^{\prime}_{1})\cdot\rho/4}).$

(ii). All candidate lists $\\{R_{A,\,t^{\prime}_{*},\,i}\\}_{i\in[p]}$,
$\\{R_{B,\,t^{\prime}_{*},\,i}\\}_{i\in[\bm{p}]}$ contain a total of
$(|L_{A}|+|L_{B}|)\cdot|\mathcal{Q}^{+e_{2}}(C)|=\widetilde{O}(2^{n/2}\cdot\ell^{-1/2}\cdot\ell^{(H(1/4)-1/2)\cdot\rho/2-(1-\rho+\beta/2)/2})$
many sum-subset couples, by their construction (Line LABEL:alg:packed-rep-
ov:3), the choices of $|A|$, $|B|$, $|C|$, $e_{2}$, and Stirling’s
approximation (Equation 1). Thus, a number of $s^{\prime}(\ell)$ many samples
$\bm{r}\sim[p]$ in expectation generate at most
$(|L_{A}|+|L_{B}|)\cdot|\mathcal{Q}^{+e_{2}}(C)|\cdot
s^{\prime}(\ell)/p\leq\frac{1}{3}k(n,\,\ell)$ sum-subset couples, for any
large enough cutoff

$\displaystyle
k(n,\,\ell)~{}=~{}k^{\prime}(n,\,\ell)~{}:=~{}\widetilde{\Theta}(2^{n/2}\cdot\ell^{-1/2}\cdot\ell^{-((1-H(1/4)-\varepsilon^{\prime}_{1}/2)\cdot\rho/2+(1-\rho+\beta/2)/2)})$

By Markov’s inequality, the probability that $k^{\prime}(n,\,\ell)$ or more
couples are generated is at most $1/3$.

To conclude, LABEL:pack-rep-case1 succeeds with probability $\geq
2/3-1/3=1/3$.

LABEL:pack-rep-case2. The proof below relies on both Conditions 5 and 5, and
works for any outcome of the created subset $\bm{D}=D\subseteq X$.

Consider the collection $\mathcal{C}^{\prime}(X)$ of
size-$(\beta\log(\frac{\ell}{\beta\log\ell}))$ subsets $C^{\prime}\subseteq X$
that satisfy both conditions:

$\mathcal{C}^{\prime}(X)~{}:=~{}\\{C^{\prime}\subseteq
X\mid\text{Conditions~{}{\ref{con:packed-rep-ov:1}} and {\ref{con:packed-rep-
ov:2}} hold, and $|C^{\prime}|=\beta\log(\tfrac{\ell}{\beta\log\ell})$}\\},$

and also consider its restriction to $(X\setminus D)$:

$\mathcal{C}(X\setminus D)~{}:=~{}\\{C\subseteq(X\setminus
D)\mid\text{Conditions~{}{\ref{con:packed-rep-ov:1}} and {\ref{con:packed-rep-
ov:2}} hold, and $|C|=\beta\log(\tfrac{\ell}{\beta\log\ell})$}\\}.$

Obviously, the conditional random subset $\bm{C}$, given LABEL:pack-rep-case2
and Conditions 5 and 5, is distributed as $\bm{C}\sim\mathcal{C}(X\setminus
D)$.

Let $P_{2}\subseteq\mathbb{P}[\ell^{1+\beta/2}:2\ell^{1+\beta/2}]$ be the set
of primes such that for the input instance $X$ the algorithm enters
LABEL:pack-rep-case2 (“LABEL:pack-rep-case2 primes”), and $P_{1}$ the set of
primes such that for the input instance $X$ the algorithm enters LABEL:pack-
rep-case1 (“LABEL:pack-rep-case1 primes”). Without loss of generality we
suppose $|P_{2}|\geq 3|P_{1}|$, i.e., LABEL:pack-rep-case2 occurs with
probability $\geq 3/4$ over the modulus
$\bm{p}\sim\mathbb{P}[\ell^{1+\beta/2}:2\ell^{1+\beta/2}]$. (Otherwise,
LABEL:pack-rep-case1 occurs with probability $\geq 1/4$ and already gives a
success probability $\geq 1/4\cdot 1/3=1/12$.) Obviously, the conditional
modulus $\bm{p}$, given LABEL:pack-rep-case2, is distributed as $\bm{p}\sim
P_{2}$.

(i). Each subset $C^{\prime}\in\mathcal{C}^{\prime}(X)$ satisfies
$\frac{|S\cap
C^{\prime}|}{\log\ell}\cdot(1-H(\frac{1-\varepsilon_{2}}{2}))\geq(1-o_{n}(1))\cdot\beta\cdot\frac{1-\varepsilon_{1}}{2}\cdot(1-H(\frac{1-\varepsilon_{2}}{2}))>\lambda$,
by Condition 5, Equation 5, and the choice of $|C^{\prime}|=|C|$. This
technical condition, together with Condition 5, allows us to use the same
arguments as in the proof of correctness for Theorem 2, showing that
$|W^{\prime}(S\cap C^{\prime})\bmod\bm{p}|=\Theta(|W^{\prime}(S\cap
C^{\prime})|)=\widetilde{\Omega}(\ell^{(1-\varepsilon_{1})\cdot\beta/2-\lambda})$
with probability $\geq 3/4$ over the modulus $\bm{p}\sim(P_{1}\cup
P_{2})=\mathbb{P}[\ell^{1+\beta/2}:2\ell^{1+\beta/2}]$. On sampling a random
subset $\bm{C}^{\prime}\sim\mathcal{C}^{\prime}(X)$, we have an analogous
guarantee:

$\displaystyle\operatorname{{\bf
Pr}}_{(\bm{p},\,\bm{C}^{\prime})\,\sim\,(P_{1}\cup
P_{2})\times\mathcal{C}^{\prime}(X)}\big{[}\,|\bm{W}^{\prime}(S\cap\bm{C}^{\prime})\bmod\bm{p}|=\widetilde{\Omega}(\ell^{(1-\varepsilon_{1})\cdot\beta/2-\lambda})\,\big{]}~{}\geq~{}3/4.$

Since there are at least three times as many LABEL:pack-rep-case2 primes as
LABEL:pack-rep-case1 primes, we have

$\displaystyle\operatorname{{\bf
Pr}}_{(\bm{p},\,\bm{C}^{\prime})\,\sim\,P_{2}\times\mathcal{C}^{\prime}(X)}\big{[}\,|\bm{W}^{\prime}(S\cap\bm{C}^{\prime})\bmod\bm{p}|=\widetilde{\Omega}(\ell^{(1-\varepsilon_{1})\cdot\beta/2-\lambda})\,\big{]}~{}\geq~{}2/3.$

But the (actual) random subset $\bm{C}$ is distributed as
$\bm{C}\sim\mathcal{C}(X\setminus D)$ rather than
$\bm{C}^{\prime}\sim\mathcal{C}^{\prime}(X)$, i.e., we shall also consider the
effect of the restriction to $(X\setminus D)$. For the choices of
$|C^{\prime}|=|C|$ and $|D|$, this restriction only removes a negligible
fraction of subsets:

$\displaystyle\textstyle\frac{|\mathcal{C}^{\prime}(X)\setminus\mathcal{C}(X\setminus
D)|}{|\mathcal{C}^{\prime}(X)|}~{}\leq~{}1-\binom{n-|D|}{|C^{\prime}|}\big{/}\binom{n}{|C^{\prime}|}~{}\in~{}\frac{\beta\log^{2}(\ell)}{n}\cdot(1\pm
o_{n}(1))~{}=~{}o_{n}(1).$

Thus, a uniform random $\bm{C}\sim\mathcal{C}(X\setminus D)$ yields a large
residue set with constant probability:

$\displaystyle\operatorname{{\bf
Pr}}_{(\bm{p},\,\bm{C})\,\sim\,P_{2}\times\mathcal{C}(X\setminus
D)}\big{[}\,|\bm{W}^{\prime}(S\cap\bm{C})\bmod\bm{p}|=\widetilde{\Omega}(\ell^{(1-\varepsilon_{1})\cdot\beta/2-\lambda})\,\big{]}~{}\geq~{}2/3-o_{n}(1).$

Conditioned on this event, a number of
$s(\ell)=\Omega(\tfrac{\bm{p}}{|\bm{W}^{\prime}(S\cap\bm{C})\bmod\bm{p}|})$
samples $\bm{r}\sim[\bm{p}]$ yields at least one good residue with probability
$\geq 4/5$, for any large enough

$\displaystyle
s(\ell)~{}=~{}s^{\prime\prime}(\ell)~{}:=~{}\widetilde{\Theta}(\ell^{1+\varepsilon_{1}\cdot\beta/2+\lambda}).$

(ii). By adapting the proof of LABEL:pack-rep-case1, (ii) for the current
choices of $|A|$, $|B|$, $|C|$, the probability that $k(n,\,\ell)$ or more
sum-subset couples are generated is at most $1/6$, for any large enough cutoff

$k(n,\,\ell)~{}=~{}k^{\prime\prime}(n,\,\ell)~{}:=~{}\widetilde{\Theta}(2^{n/2}\cdot\ell^{-1/2}\cdot\ell^{-((1-H(\frac{1+\varepsilon_{2}}{4})-\varepsilon_{1}/2)\cdot\beta-\lambda)}).$

To conclude, LABEL:pack-rep-case2 succeeds with probability
$\geq(2/3-o_{n}(1))\cdot 4/5-1/6\geq 1/3$. ∎

###### Proof of Runtime for LABEL:alg:packed-rep-ov.

Line LABEL:alg:packed-rep-ov:0 takes time
$\mathrm{poly}(\ell)=\mathrm{poly}(n)$ in the either case given Lemmas 9 and
10, which is dominated by runtime of the rest of our algorithm:

LABEL:pack-rep-case1. For the choices of parameters, the bottleneck occurs in
Line LABEL:alg:packed-rep-ov:1 or Lines LABEL:alg:packed-rep-ov:4 to
LABEL:alg:packed-rep-ov:9:

  * •

Line LABEL:alg:packed-rep-ov:1 takes time
$\widetilde{O}(2^{n/2}\cdot\ell^{-1/2}\cdot\ell^{-(1-H(\frac{1-\varepsilon^{\prime}_{1}}{2}))\cdot\rho/4})$,
by Lemma 12 and the choice of $|C|$.

  * •

Line LABEL:alg:packed-rep-ov:2 is skipped in this case.

  * •

Line LABEL:alg:packed-rep-ov:3 takes time
$O(2^{|A|}+2^{|B|}+2^{|C|}+2^{|D|})=\widetilde{O}(2^{n/2}\cdot\ell^{-1/2}\cdot\ell^{-(2-\rho+\beta)/4})$,
by Lemma 2 and the choices of $|A|$, $|B|$, $|C|$, $|D|$. This runtime is
dominated by that of Line LABEL:alg:packed-rep-ov:1 as
$(1-H(\frac{1-\varepsilon_{1}^{\prime}}{2}))\rho<(2-\rho+\beta)$ for $\rho\leq
1$.

  * •

Lines LABEL:alg:packed-rep-ov:4 to LABEL:alg:packed-rep-ov:9 take time
$\widetilde{O}(k^{\prime}(n,\,\ell)\cdot\ell^{1-\rho+\beta/2})=\widetilde{O}(2^{n/2}\cdot\ell^{-1/2}\cdot\ell^{-((4-2H(1/4)-\varepsilon^{\prime}_{1})\cdot\rho-2-\beta)/4})$.

Lines LABEL:alg:packed-rep-ov:4 iterates Lines LABEL:alg:packed-rep-ov:5 to
LABEL:alg:packed-rep-ov:7 a total of
$|W(D)\bmod\bm{p}|=\widetilde{O}(\ell^{1-\rho+\beta/2})$ times, by Lemma 10.
Here each iteration takes time
$\widetilde{O}(\sum_{\bm{r}}(|\bm{R}_{A,\,t^{\prime},\,\bm{r}}|+|\bm{R}_{B,\,t^{\prime},\,\bm{r}}|))=\widetilde{O}(k^{\prime}(n,\,\ell))$,
by Lemma 13 and the classic merge sort algorithm (of depth $\log
s^{\prime}(\ell)=O(\log\ell)=O(\log n)$).

Line LABEL:alg:packed-rep-ov:8 iterates Line LABEL:alg:packed-rep-ov:9 a total
of $2^{|D|}=\ell^{2-\rho+\beta/2}$ times, by the choice of $|D|$.
Here each iteration takes time
$\widetilde{O}(k^{\prime}(n,\,\ell)\cdot\ell^{-1})$, by Lemma 14.

Thus we achieve a speedup of
$\widetilde{\Omega}(\ell^{1/2+\gamma^{\prime}_{*}})$, where the

$\textstyle\gamma^{\prime}_{*}~{}:=~{}\min\big{\\{}\,\frac{1-H((1-\varepsilon^{\prime}_{1})/2)}{4}\cdot\rho,\quad\frac{4-2H(1/4)-\varepsilon^{\prime}_{1}}{4}\cdot\rho-\frac{1}{2}-\frac{\beta}{4}\,\big{\\}}.$

LABEL:pack-rep-case2. For the choices of parameters, the bottleneck occurs in
Line LABEL:alg:packed-rep-ov:1, Line LABEL:alg:packed-rep-ov:2, or Lines
LABEL:alg:packed-rep-ov:4 to LABEL:alg:packed-rep-ov:9:

  * •

Line LABEL:alg:packed-rep-ov:1 takes time
$\widetilde{O}(2^{n/2}\cdot\ell^{-1/2}\cdot\ell^{-(1-H(\frac{1-\varepsilon_{1}}{2}))\cdot\beta/2})$,
by Lemma 12 and the choice of $|C|$.

  * •

Line LABEL:alg:packed-rep-ov:2 takes time
$\widetilde{O}(2^{n/2}\cdot\ell^{-1/2}\cdot\ell^{-\lambda/2})$, by Lemma 11.

  * •

Line LABEL:alg:packed-rep-ov:3 takes time
$O(2^{|A|}+2^{|B|}+2^{|C|}+2^{|D|})=\widetilde{O}(2^{n/2}\cdot\ell^{-1/2}\cdot\ell^{-\beta/2})$,
by Lemma 2 and the choices of $|A|$, $|B|$, $|C|$, $|D|$. This runtime is
dominated by that of Line LABEL:alg:packed-rep-ov:1.

  * •

Lines LABEL:alg:packed-rep-ov:4 to LABEL:alg:packed-rep-ov:9 take time
$\widetilde{O}(k^{\prime\prime}(n,\,\ell))=\widetilde{\Theta}(2^{n/2}\cdot\ell^{-1/2}\cdot\ell^{-((1-H(\frac{1+\varepsilon_{2}}{4})-\varepsilon_{1}/2)\cdot\beta-\lambda)})$.

Lines LABEL:alg:packed-rep-ov:4 iterates Lines LABEL:alg:packed-rep-ov:5 to
LABEL:alg:packed-rep-ov:7 a total of
$|W(D)\bmod\bm{p}|\leq|D|+1=O(\log\ell)=O(\log n)$ times,
because all integers in $\bm{D}$ are congruent modulo $\bm{p}$ by construction
(Line LABEL:alg:packed-rep-ov:0).
Here each iteration takes time
$\widetilde{O}(\sum_{\bm{r}}(|\bm{R}_{A,\,t^{\prime},\,\bm{r}}|+|\bm{R}_{B,\,t^{\prime},\,\bm{r}}|))=\widetilde{O}(k^{\prime\prime}(n,\,\ell))$,
by Lemma 13 and the classic merge sort algorithm (of depth $\log
s^{\prime\prime}(\ell)=O(\log\ell)=O(\log n)$).

Line LABEL:alg:packed-rep-ov:8 iterates Line LABEL:alg:packed-rep-ov:9 a total
of $2^{|D|}=\ell$ times, by the choice of $|D|$.
Here each iteration takes time
$\widetilde{O}(k^{\prime\prime}(n,\,\ell)\cdot\ell^{-1})$, by Lemma 14.

Thus we achieve a speedup of
$\widetilde{\Omega}(\ell^{1/2+\gamma^{\prime\prime}_{*}})$, where the

$\displaystyle\gamma^{\prime\prime}_{*}~{}=~{}\gamma^{\prime\prime}_{*}(\rho)$
$\displaystyle\textstyle~{}:=~{}\min\big{\\{}\,\frac{\lambda}{2},\quad\frac{1-H((1-\varepsilon_{1})/2)}{2}\cdot\beta,\quad(1-H(\frac{1+\varepsilon_{2}}{4})-\frac{\varepsilon_{1}}{2})\cdot\beta-\lambda\,\big{\\}}$
$\displaystyle\textstyle~{}\phantom{:}=~{}\frac{\lambda}{2}~{}=~{}(1-10^{-5})\cdot\frac{1-\varepsilon_{1}}{4}\cdot(1-H(\frac{1-\varepsilon_{2}}{2}))\cdot\beta~{}\geq~{}9.0324\times
10^{-3}\cdot\beta.$

Here, we know that $\frac{\lambda}{2}$ is the minimum term for our chosen
values of $\varepsilon_{1}$, $\varepsilon_{2}$ and $\lambda$ by Equation 5.

Worst Case. Overall, we achieve a speedup of $\Omega(\ell^{1/2+\gamma})$ for
any constant $\gamma\in(0,\,\gamma_{*})$. In particular, the constants
$\gamma_{*}=\gamma_{*}(\rho):=\min\\{\gamma_{*}^{\prime},\,\gamma_{*}^{\prime\prime}\\}$,
$\beta=\beta(\rho)$, $\varepsilon^{\prime}_{1}=\varepsilon^{\prime}_{1}(\rho)$
are the solutions to the following chain of equations:

$\displaystyle\gamma_{*}(\rho)~{}=~{}9.0324\times
10^{-3}\cdot\beta(\rho)~{}=~{}\textstyle\frac{1-H((1-\varepsilon^{\prime}_{1}(\rho))/2)}{4}\cdot\rho~{}=~{}\textstyle\frac{4-2H(1/4)-\varepsilon^{\prime}_{1}(\rho)}{4}\cdot\rho-\frac{1}{2}-\frac{\beta(\rho)}{4}.$
(6)

Alternatively, we can write the speedup as $\Omega(n^{\alpha})$ for
$\alpha=\frac{1+2\gamma}{2\rho}\in(0,\,\alpha_{*}(\rho))$ and
$\alpha_{*}(\rho):=\frac{1+2\gamma_{*}(\rho)}{2\rho}$.

In the density range $(2-H(1/4))^{-1}<\rho\leq 1+\Theta(\frac{1}{\log n})$,
all expressions $\alpha_{*}(\rho)$, $\gamma_{*}(\rho)$, $\beta(\rho)$,
$\varepsilon^{\prime}_{1}(\rho)$ are demonstrated in LABEL:fig:main. In
particular, the boundary $(2-H(1/4))^{-1}\approx 0.8412$ is the solution to
the equation $\alpha_{*}(\rho)=1/(2\rho)$. The minimum speedup is a factor of
$\widetilde{\Omega}(n^{\alpha_{*}(1)})\geq\Omega(n^{0.5023})$ for linear word
length $\ell=\Theta(n)$, and the maximum speedup is a factor of
$\widetilde{\Omega}(n^{(2-H(1/4))/2})\geq\Omega(n^{0.5943})$ for slightly
superlinear word length $\ell=\Theta(n^{2-H(1/4)})\approx\Theta(n^{1.1887})$.

In the other density range $0<\rho\leq(2-H(1/4))^{-1}\approx 0.8412$, as
mentioned, we can gain a better speedup
$\widetilde{\Omega}(n^{1/(2\rho)})\geq\widetilde{\Omega}(n^{(2-H(1/4))/2})\geq\Omega(n^{0.5943})$
by naively simulating 3. ∎

###  5.1 Auxiliary Lemmas

######  Lemma 9 (Finding a Subset $C$ with Large $W(C)$).

Given as input a modulus $p$ and a size-$n$ multiset $Y$ such that $|Y\bmod
p|>\ell^{\rho}/\log\ell$, there always exists a
size-$(\frac{1}{2}\log(\ell^{\rho}/\log\ell))$ subset $C\subseteq Y$ such that
$|W(C)\bmod p|=2^{|C|}$, and such a set $C$ can be found in time
$\mathrm{poly}(\ell)=\mathrm{poly}(n)$.

###### Proof.

We create the subset $C\subseteq Y$ using a simple greedy algorithm: starting
with $C_{0}=\emptyset$, for $i\in[\frac{1}{2}\log(\ell^{\rho}/\log\ell)]$,
select any $y_{i}\in(Y\setminus C_{i-1})$ such that
$y_{i}\not\equiv_{p}(c^{\prime}-c^{\prime\prime})$ for any two
$c^{\prime},\,c^{\prime\prime}\in W(C_{i-1})$, and then augment
$C_{i}:=C_{i-1}\bigcup\\{y_{i}\\}$. The existence of such an element $y_{i}$
at each stage is ensured, since any intermediate subset $C_{i-1}$ has at most
$|W(C_{i-1})|\leq 2^{i-1}$ subset sums, and thus
$|\\{(c^{\prime}-c^{\prime\prime})\bmod p\mid c^{\prime},\,c^{\prime\prime}\in
C_{i-1}\\}|\leq\ell^{\rho}/\log\ell<|Y\bmod p|.$ ∎

######  Lemma 10 (Finding a Subset $D$ with Small $W(D)$).

Given as input a modulus $p=\Theta(\ell^{1+\beta/2})$ and a size-$\Theta(n)$
multiset $Y$, there always exists a size-$((2-\rho+\beta/2)\log\ell)$ subset
$D\subseteq Y$ such that $|W(D)\bmod p|=\widetilde{O}(\ell^{1-\rho+\beta/2})$,
and such a subset $D$ can be found in time
$\mathrm{poly}(\ell)=\mathrm{poly}(n)$.

###### Proof.

Given a small enough $q=\Theta(n/\log\ell)=\Theta(\ell^{\rho}/\log\ell)$,
partition $[p]=\bigcup_{j\in[q]}P_{j}$ into arithmetic progressions
$P_{j}:=\\{r\in[p]\mid r\equiv_{q}j\\}$ for $j\in[q]$, each of which contains
$\lceil p/q\rceil$ or $\lfloor p/q\rfloor$ many residues. By the pigeonhole
principle, at least one of these progressions $P_{j^{*}}$ involves at least
$|Y_{j^{*}}|\geq|Y|/q>(2-\rho+\beta/2)\log\ell$ many integers
$Y_{j^{*}}\subseteq Y$, where $Y_{j^{*}}:=\\{y\in Y\mid y\in
P_{j^{*}}\pmod{p}\\}$. We can find such a progression $P_{j^{*}}$ and the
corresponding subset $Y_{j^{*}}$ in time
$\mathrm{poly}(\ell)=\mathrm{poly}(n)$.

We select $D=\\{y_{i}\\}_{i\in[|D|]}$ to be any
$((2-\rho+\beta/2)\log\ell)$-integer subset of $Y_{j^{*}}$. Each selected
$y_{i}$ has the residue $(y_{i}\bmod p)=q\cdot k_{i}+j^{*}$, where
$k_{i}:=\lfloor(y_{i}\bmod p)/q\rfloor\leq p/q$. Thus this subset $D$ has

$\displaystyle|W(D)\bmod
p|\leq|W(\\{k_{i}\\}_{i\in[|D|]})|\cdot|D|\leq\Sigma(\\{k_{i}\\}_{i\in[|D|]})\cdot|D|\leq
p/q\cdot|D|^{2}=O(\ell^{1-\rho+\beta/2}\cdot\log^{3}(\ell))$

distinct subset sums modulo $p$, as desired. ∎

Below, Lemmas 11 and 12 are refinements of Lemmas 5 and 6, respectively, which
leverage bit packing tricks used in the 3 algorithm (recall Figure 3).

######  Lemma 11 (Speedup via Additive Structure).

Let $(X,\,t)$ be a Subset Sum instance. Given a subset $Y\subseteq X$ of size
$|Y|\leq\frac{n-\log\ell}{2}$ such that $|W(Y)|\leq
2^{|Y|}\cdot\ell^{-\varepsilon}$ for some constant
$0<\varepsilon<|Y|/\log\ell$, the instance $(X,\,t)$ can be solved in time
$\widetilde{O}(2^{n/2}\cdot\ell^{-(1+\varepsilon)/2})$ with arbitrarily high
constant probability and with no false positives.

###### Proof.

Fix any partition $X=A\cup B\cup D$ such that $|D|=\log\ell$,
$|A|=\frac{n-(1-\varepsilon)\log\ell}{2}$ with $A\supseteq Y$, and
$|B|=\frac{n-(1+\varepsilon)\log\ell}{2}$. We have $|W(A)|\leq 2^{|A\setminus
Y|}\cdot|W(Y)|\leq 2^{n/2}\cdot\ell^{-(1+\varepsilon)/2}$ and $|W(B)|\leq
2^{n/2}\cdot\ell^{-(1+\varepsilon)/2}$. Using Lemmas 2, 3 and 1, it takes
expected time $O(2^{n/2}\cdot\ell^{-(1+\varepsilon)/2}\cdot\log\ell)$ to
create the sorted lists $L_{A}$, $L_{B}$ and to run 3.

Cutting off the algorithm if it takes longer than a large constant times the
expected runtime yields an one-sided error Monte Carlo algorithm by Markov’s
inequality. ∎

######  Lemma 12 (Speedup via Unbalanced Solutions).

Let $(X,\,t)$ be a Subset Sum instance that has a solution. Given $Y\subseteq
X$ of size $|Y|=c\log\ell$ such that some solution $S\subseteq X$ satisfies
$|S\cap Y|\notin(1\pm\varepsilon)\frac{|Y|}{2}$ for some constants
$c>0,\varepsilon\in(0,\,1)$, the solution $S$ can be found in time
$\widetilde{O}(2^{n/2}\cdot\ell^{-(1+\delta)/2})$, where
$\delta:=(1-H(\frac{1-\varepsilon}{2}))\cdot c$, with arbitrarily high
constant probability.

###### Proof.

The proof is a straightforward combination of the proofs of Lemmas 6 and 11. ∎

Subroutine $\textup{\text{\tt Sample-
Packing}}(\\{R_{A,\,t^{\prime},\,r}\\}_{r},h_{m})$ Input: A sorted list
$R_{A,\,t^{\prime}}$ containing elements in the sum-collection couple format
$(a^{\prime},\,\mathcal{Q}_{a^{\prime}})$, and a hash function $h_{m}$.
Output: A hashed and packed list $H_{A,\,t^{\prime}}$. 7(a) Initialize indices
$i,\,j:=0$. While $i<|R_{A,\,t^{\prime}}|$, set three words of
$H_{A,\,t^{\prime}}$ as follows: 7(b) $H_{A,\,t^{\prime}}[3j]:=a^{\prime}_{i}$
stores the full integer $a^{\prime}_{i}$, the smallest not-yet-packed sum.
7(c)
$H_{A,\,t^{\prime}}[3j+1]:=((h_{m}(a^{\prime}_{i}),\,\mathcal{Q}_{a^{\prime}_{i}}),\,(h_{m}(a^{\prime}_{i+1}),\,\mathcal{Q}_{a^{\prime}_{i+1}}),\,\dots)$
packs as many
hash-collection couples as will fit into a single $\ell$-bit word.
Update $i$ to the index of the next not-yet-packed sum in
$R_{A,\,t^{\prime}}$. 7(d) $H_{A,\,t^{\prime}}[3j+2]:=a^{\prime}_{i-1}$ stores
the full integer $a^{\prime}_{i-1}$, the largest already-packed sum. 7(e)
Increment $j\leftarrow j+1$. Figure 6: The Sample-Packing subroutine.

######  Lemma 13 (Hashing and Packing; Line LABEL:alg:packed-rep-ov:7).

In the context of LABEL:alg:packed-rep-ov:
Line LABEL:alg:packed-rep-ov:7 uses the subroutine 6 to create lists
$\bm{H}_{\bm{A},\,t^{\prime}}$ and $\bm{H}_{\bm{B},\,t^{\prime}}$ in time
$\widetilde{O}(k(n,\,\ell))$ and to store these lists in
$|\bm{H}_{\bm{A},\,t^{\prime}}|+|\bm{H}_{\bm{B},\,t^{\prime}}|=\widetilde{O}(k(n,\,\ell)\cdot\ell^{-1})$
many words.

###### Proof.

Line LABEL:alg:packed-rep-ov:7 creates $\bm{H}_{\bm{A},\,t^{\prime}}$,
$\bm{H}_{B,\,t^{\prime}}$ using the subroutine 6 (Figure 6). The claimed
runtime $\widetilde{O}(k(n,\,\ell))$ follows from the fact that the input list
$\bm{R}_{\bm{A},\,t^{\prime}}$ contains
$|\bm{R}_{\bm{A},\,t^{\prime}}|\leq\sum_{a^{\prime}}|\bm{\mathcal{Q}}_{a^{\prime}}|\leq
k(n,\,\ell)$ sum-collection couples by construction (Lemma 8 and Line
LABEL:alg:packed-rep-ov:5), and 6 goes through it once, spending time
$O(\log\ell)$ on each couple to compute the hash $\bm{h}_{m}(a^{\prime})$.

To see that the output list $\bm{H}_{\bm{A},\,t^{\prime}}$ is stored in
$\widetilde{O}(k(n,\,\ell)\cdot\ell^{-1})$ many $\ell$-bit words, we first
observe that a single hash-collection couple
$(\bm{h}_{m}(a^{\prime}),\,\bm{\mathcal{Q}}_{a^{\prime}})$ takes at most

$m+|\bm{\mathcal{Q}}_{a^{\prime}}|\cdot|\bm{C}|~{}\leq~{}m+|\bm{\mathcal{Q}}^{+e_{3}}(\bm{C})|\cdot|\bm{C}|~{}\leq~{}m+2^{|\bm{C}|}\cdot|\bm{C}|~{}=~{}\widetilde{O}(\ell^{1/2})~{}=~{}o(\ell)$

many bits, for $m=3\log\ell$ and
$|\bm{C}|=\max\\{\frac{1}{2}\log(\frac{\ell^{\rho}}{\log\ell}),\,\beta\log(\frac{\ell}{\beta\log\ell})\\}\leq\frac{1}{2}\log\ell$
(Line LABEL:alg:packed-rep-ov:0 and LABEL:fig:main:beta). That is, a single
word $\bm{H}_{\bm{A},\,t^{\prime}}[3j+1]$ created in Line 7(c) has at most
$o(\ell)$ many unused bits, which is negligible compared to the word length.
Moreover, all of the
$|\bm{R}_{\bm{A},\,t^{\prime}}|\leq\sum_{a^{\prime}}|\bm{\mathcal{Q}}_{a^{\prime}}|\leq
k(\ell)$ many hash-collection couples
$(\bm{h}_{m}(a^{\prime}),\,\bm{\mathcal{Q}}_{a^{\prime}})$ take a total of at
most

$\textstyle|\bm{R}_{\bm{A},\,t^{\prime}}|\cdot
m+\sum_{a^{\prime}}|\bm{\mathcal{Q}}_{a^{\prime}}|\cdot|\bm{C}|~{}\leq~{}k(n,\,\ell)\cdot
3\log\ell+k(n,\,\ell)\cdot\frac{1}{2}\log\ell~{}=~{}\widetilde{O}(k(n,\,\ell))$

many bits. Accordingly, a total of
$\widetilde{O}(k(n,\,\ell))\cdot\ell^{-1}=\widetilde{O}(k(n,\,\ell)\cdot\ell^{-1})$
many words $\bm{H}_{\bm{A},\,t^{\prime}}[3j+1]$ are created throughout all the
executions of Line 7(c). The entire output list $\bm{H}_{\bm{A},\,t^{\prime}}$
has three times as many words because of the additional elements storing the
highest and the lowest values hashed into each word
$\bm{H}_{\bm{A},\,t^{\prime}}[3j+1]$. ∎

Subroutine $\textup{\text{\tt Sample-
Searching}}(t^{\prime\prime},\,R_{A,\,t^{\prime}},\,R_{B,\,t^{\prime}},\,H_{A,\,t^{\prime}},\,H_{B,\,t^{\prime}})$
Input: A shifted target $t^{\prime\prime}$ and sorted lists
$R_{A,\,t^{\prime}}$, $R_{B,\,t^{\prime}}$, $H_{A,\,t^{\prime}}$,
$H_{B,\,t^{\prime}}$ for $t^{\prime}=(t^{\prime\prime}\bmod p)$. 9(a)
Initialize indices $i:=0$ and $j:=|H_{B,\,t^{\prime}}|-1$. While
$i<|H_{A,\,t^{\prime}}|$ and $j\geq 0$: 9(b) If the indexed words
$H_{A,\,t^{\prime}}[3i+1]$, $H_{B,\,t^{\prime}}[3j+1]$ contain hash-collection
couples
$(\bm{h}_{m}(a^{\prime}),\,\mathcal{Q}_{a^{\prime}})$,
$(\bm{h}_{m}(b^{\prime}),\,\mathcal{Q}_{b^{\prime}})$ with
$\bm{h}_{m}(a^{\prime})+\bm{h}_{m}(b^{\prime})\in\bm{h}_{m}(t^{\prime\prime})-\\{0,\,1\\}\pmod{2^{m}}$
and $Q_{a^{\prime}}\cap Q_{b^{\prime}}=\emptyset$ for some
$Q_{a^{\prime}}\in\mathcal{Q}_{a^{\prime}}$,
$Q_{b^{\prime}}\in\mathcal{Q}_{b^{\prime}}$, use Lemma 8 to search the
corresponding sublists of $R_{A,\,t^{\prime}}$, $R_{B,\,t^{\prime}}$ for a
solution as described in the proof of
Lemma 14. Halt and return “yes” if a solution is found. 9(c) If
$H_{A,\,t^{\prime}}[3i]+H_{B,\,t^{\prime}}[3j+2]<t^{\prime\prime}$, set
$i\leftarrow i+1$. Otherwise, set $j\leftarrow j-1$. Figure 7: The Sample-
Searching subroutine.

######  Lemma 14 (Searching for Solutions; Line LABEL:alg:packed-rep-ov:9).

In the context of LABEL:alg:packed-rep-ov:
(i) Line LABEL:alg:packed-rep-ov:9 finds a solution via 7, i.e., a pair of
sum-subset couples $(a^{\prime},\,Q_{1})$, $(b^{\prime},\,Q_{2})$ with
$a^{\prime}+b^{\prime}=t^{\prime\prime}$ and $Q_{1}\cap Q_{2}=\emptyset$, with
arbitrarily high constant probability, if the lists
$\bm{R}_{\bm{A},\,(t^{\prime\prime}\bmod\bm{p})}$ and
$\bm{R}_{\bm{B},\,(t^{\prime\prime}\bmod\bm{p})}$ contain such a solution.
(ii) 7 has runtime $\widetilde{O}(k(n,\,\ell)\cdot\ell^{-1})$.

###### Proof.

7 adapts the 3 algorithm (Lines 4 to 6) for the lists
$\bm{H}_{\bm{A},\,t^{\prime}}$, $\bm{H}_{\bm{B},\,t^{\prime}}$ to address two
additional issues. First, not only a hash collision but also a pair of
overlapping near-quartersets in $\bm{H}_{\bm{A},\,t^{\prime}}$,
$\bm{H}_{\bm{B},\,t^{\prime}}$ may incur a false positive. Also, each word in
$\bm{H}_{\bm{A},\,t^{\prime}}$, $\bm{H}_{\bm{B},\,t^{\prime}}$ packs an
uncertain amount of hash-collision couples (while 3 processes exactly
$(\ell/m)$ hashes per iteration).

Line 9(b) settles the first issue by modifying the “If” test in line 4 of 3.
This new test is implemented by the $(2\ell)$-bit Boolean function Hash-OV: it
takes as input two packed words
$u=((\bm{h}_{m}(a^{\prime}_{1}),\,\bm{\mathcal{Q}}_{a^{\prime}_{1}}),\,(\bm{h}_{m}(a^{\prime}_{2}),\,\bm{\mathcal{Q}}_{a^{\prime}_{2}}),\,\dots)$
and
$v=((\bm{h}_{m}(b^{\prime}_{1}),\,\bm{\mathcal{Q}}_{b^{\prime}_{1}}),\,(\bm{h}_{m}(b^{\prime}_{2}),\,\bm{\mathcal{Q}}_{b^{\prime}_{2}}),\,\dots)$,
where each $\bm{h}_{m}(a^{\prime})$, $\bm{h}_{m}(b^{\prime})$ is a hashed
value and each
$\bm{\mathcal{Q}}_{a^{\prime}},\,\bm{\mathcal{Q}}_{b^{\prime}}\subseteq\bm{\mathcal{Q}}^{+e_{3}}(\bm{C})$
is a collection of near-quartersets. ${\ref{function:packed-OV}}(u,\,v)$
returns $1$ if and only if two conditions hold: first, there is a pair of
hash-collection couples $(\bm{h}_{m}(a^{\prime}),\mathcal{Q}_{a^{\prime}})$,
$(\bm{h}_{m}(b^{\prime}),\mathcal{Q}_{b^{\prime}})$ with
$\bm{h}_{m}(a^{\prime})+\bm{h}_{m}(b^{\prime})\in\bm{h}_{m}(t^{\prime\prime})-\\{0,\,1\\}\pmod{2^{m}}$;
second, there are two disjoint near-quartersets $Q_{a^{\prime}}\cap
Q_{b^{\prime}}=\emptyset$, for $Q_{a^{\prime}}\in\mathcal{Q}_{a^{\prime}}$,
$Q_{b^{\prime}}\in\mathcal{Q}_{b^{\prime}}$, in the packed collections indexed
by $\bm{h}_{m}(a^{\prime})$, $\bm{h}_{m}(b^{\prime})$. 5.1 is an
$\mathsf{AC}^{0}$ operation on two words and takes constant time to evaluate
in the circuit RAM model, since all hash-collection couples can be checked in
parallel.

Now on comparing any two words $\bm{H}_{\bm{A},\,t^{\prime}}[3i+1]$,
$\bm{H}_{\bm{B},\,t^{\prime}}[3j+1]$, by the second condition above,
overlapping near-quartersets never incur false positives. Hence like 3, the
new “If” test in Line 9(b) is passed by every correct solution and (some of)
the hash collisions. We further verify such a potential solution by returning
back to the (unhashed) lists $\bm{R}_{\bm{A},\,t^{\prime}}$,
$\bm{R}_{\bm{B},\,t^{\prime}}$ and checking all the sum-collection couples
that are packed into $\bm{H}_{A,\,t^{\prime}}[3i+1]$,
$\bm{H}_{\bm{B},\,t^{\prime}}[3j+1]$, namely the two sorted sublists
$\\{(a^{\prime},\,\bm{\mathcal{Q}}_{a^{\prime}})\mid\bm{H}_{\bm{A},\,t^{\prime}}[3i]\leq
a^{\prime}\leq\bm{H}_{\bm{A},\,t^{\prime}}[3i+2]\\}$ and
$\\{(b^{\prime},\,\bm{\mathcal{Q}}_{b^{\prime}})\mid\bm{H}_{\bm{B},\,t^{\prime}}[3j]\leq
b^{\prime}\leq\bm{H}_{\bm{B},\,t^{\prime}}[3j+2]\\}$. Either sublist is stored
in at most $(\ell/m)$ words by construction (see 6, Line 7(c)). Hence by Lemma
8, this verification process takes time $O(\ell/m)=\mathrm{poly}(n)$.

Line 9(c) settles the second issue by replacing the test in line 6 of 3 with a
new test: If
$\bm{H}_{\bm{A},\,t^{\prime}}[3i]+\bm{H}_{\bm{B},\,t^{\prime}}[3j+2]<t^{\prime\prime}$?
By construction (6), $\bm{H}_{\bm{A},\,t^{\prime}}[3i]$ and
$\bm{H}_{\bm{B},\,t^{\prime}}[3j+2]$ are the exact values of the smallest sum
packed into $\bm{H}_{\bm{A},\,t^{\prime}}[3i+1]$ and the largest sum packed
into $\bm{H}_{\bm{B},\,t^{\prime}}[3j+1]$, respectively. By the same argument
as in the proof of correctness for 3, in a single scan of
$\bm{H}_{\bm{A},\,t^{\prime}}$ and $\bm{H}_{\bm{B},\,t^{\prime}}$, we never
miss a pair of words that packs a correct solution.

(ii). 7 performs a single scan of $\bm{H}_{\bm{A},\,t^{\prime}}$ and
$\bm{H}_{\bm{B},\,t^{\prime}}$, plus the verification of at most one correct
solution versus the hash collisions. Using the same argument as in the proof
of runtime for 3 (Line 5), the expected verification-time
$\mathrm{poly}(n)+(|\bm{H}_{\bm{A},\,t^{\prime}}|+|\bm{H}_{\bm{B},\,t^{\prime}}|)\cdot
o_{n}(1)$ is dominated by the scan-time
$=O(|\bm{H}_{\bm{A},\,t^{\prime}}|+|\bm{H}_{\bm{B},\,t^{\prime}}|)=\widetilde{O}(k(n,\,\ell)\cdot\ell^{-1})$,
given Lemma 13. ∎

######  Observation 5 (Adapting LABEL:alg:packed-rep-ov to Word RAM).

As in Section 4, to adapt LABEL:alg:packed-rep-ov to the word RAM model, we
run the algorithm as if the word length were $\ell^{\prime}:=0.1n$ and memoize
5.1 to speed up the evaluation of this function. The resulting runtime is
$O(2^{n/2}\cdot n^{-0.5023})$ for $(2-H(1/4))^{-1}<\rho<1+\Theta(1/\log n)$.
There are three additional modifications:

  1. 1.

Line 7(a) sets $\lceil\ell^{\prime}/\ell\rceil+2$ words (rather than three
words) in a single iteration, i.e., the single word set in Line 7(c) is
replaced with $\lceil\ell^{\prime}/\ell\rceil=\Theta(1)$ words (since a single
word with $\ell$ bits may be insufficient).

  2. 2.

Before the execution of Line LABEL:alg:packed-rep-ov:8, create a table
$\texttt{Hash-OV}^{\prime}$ that memoizes all input-output results of the
Boolean function 5.1, in time
$(2^{\ell^{\prime}})^{2}\cdot\mathrm{poly}(\ell^{\prime})=O(2^{0.21n})$. We
also replicate the table $\texttt{OV}^{\prime}$ described in Observation 4.
Then either table can be accessed using a
$2\lceil\ell^{\prime}/\ell\rceil=\Theta(1)$-word index in constant time.

  3. 3.

Line 9(b) replaces the functions 5.1 (used in Lemma 14) and 4 (used in Lemma
8) with constant-time lookup into the above memoized tables $\texttt{Hash-
OV}^{\prime}$ and $\texttt{OV}^{\prime}$, respectively.

Compared with running LABEL:alg:packed-rep-ov itself for $\ell^{\prime}=0.1n$,
the only significant difference of this word RAM variant is that the number of
packed words in $\bm{H}_{A,t^{\prime}}$ and $\bm{H}_{B,t^{\prime}}$ increases
by a $\Theta(1)$ factor, so we can easily check the correctness and the
(asymptotically) same runtime.

##  6 Extensions and Future Work

Our results open up several natural directions for future investigation:

  * •

Derandomization: All of the $2^{n/2}/\mathrm{poly}(n)$-time algorithms we have
given for Subset Sum use randomness. Can our results be extended to achieve
deterministic algorithms with worst-case running time
$2^{n/2}/\mathrm{poly}(n)$?

  * •

Counting: It is straightforward to modify the 2 algorithm to output a count of
the number of Subset Sum solutions in time $O(2^{n/2})$ (essentially, by
keeping track of the multiplicity with which each value occurs in each list
$L_{A},L_{B}$). Can our techniques be extended to give counting algorithms for
Subset Sum that run in time $2^{n/2}/\mathrm{poly}(n)$? In time
$2^{n/2}/n^{0.501}$?

  * •

Faster runtimes: Finally, an obvious goal is to quantitatively strengthen our
results by developing faster algorithms for worst-case Subset Sum. It would be
particularly interesting to achieve running times of the form $2^{n/2}/f(n)$
for some $f(n)=n^{\omega(1)}$.

## Acknowledgements

We would thank Martin Dietzfelbinger for pointing out the work [DHKP97].

## References

  * [AB18] Amir Abboud and Karl Bringmann.  Tighter Connections Between Formula-SAT and Shaving Logs.  In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 8:1–8:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [AKKN15] Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof.  Subset sum in the absence of concentration.  In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015.
  * [AKKN16] Per Austrin, Mikko Koivisto, Petteri Kaski, and Jesper Nederlof.  Dense subset sum may be the hardest.  33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), pages 13:1–13:14, 2016.
  * [BCJ11] Anja Becker, Jean-Sébastien Coron, and Antoine Joux.  Improved generic algorithms for hard knapsacks.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 364–385. Springer, 2011.
  * [BDP05] Ilya Baran, Erik D Demaine, and Mihai Patraşcu.  Subquadratic algorithms for 3SUM.  In Workshop on Algorithms and Data Structures, pages 409–421. Springer, 2005.
  * [Bel66] Richard Bellman.  Dynamic programming.  Science, 153(3731):34–37, 1966.
  * [CFJ+14] Marek Cygan, Fedor Fomin, Bart M.P. Jansen, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Open problems for fpt school.  Available at https://fptschool.mimuw.edu.pl/opl.pdf, 2014\.
  * [Cha13a] Timothy Chan.  The art of shaving logs.  Presentation at WADS 2013, slides available at https://tmc.web.engr.illinois.edu/talks/wads13$\\_$talk.pdf, 2013\.
  * [Cha13b] Timothy M. Chan.  The art of shaving logs.  In Frank Dehne, Roberto Solis-Oba, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures - 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings, volume 8037 of Lecture Notes in Computer Science, page 231. Springer, 2013\.
  * [CJRS22] Xi Chen, Yaonan Jin, Tim Randolph, and Rocco A Servedio.  Average-case subset balancing problems.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 743–778. SIAM, 2022.
  * [DHKP97] Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen.  A reliable randomized algorithm for the closest-pair problem.  Journal of Algorithms, 25(1):19–51, 1997.
  * [FG06] Jörg Flum and Martin Grohe.  Parameterized Complexity Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006\.
  * [GP18] Allan Grønlund and Seth Pettie.  Threesomes, degenerates, and love triangles.  J. ACM, 65(4):22:1–22:25, 2018.
  * [HGJ10] Nick Howgrave-Graham and Antoine Joux.  New generic algorithms for hard knapsacks.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 235–256. Springer, 2010.
  * [HS74] Ellis Horowitz and Sartaj Sahni.  Computing partitions with applications to the knapsack problem.  Journal of the ACM (JACM), 21(2):277–292, 1974.
  * [HW+79] Godfrey Harold Hardy, Edward Maitland Wright, et al.  An introduction to the theory of numbers.  Oxford university press, 1979.
  * [Kar72] Richard M. Karp.  Reducibility among combinatorial problems.  In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, pages 85–103. Plenum Press, New York, 1972.
  * [MNPW19] Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, and Karol Wegrzycki.  Equal-subset-sum faster than the meet-in-the-middle.  In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 73:1–73:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [NW21] Jesper Nederlof and Karol Wegrzycki.  Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors.  In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1670–1683. ACM, 2021\.
  * [Pis03] David Pisinger.  Dynamic programming on the word RAM.  Algorithmica, 35(2):128–145, 2003.
  * [SS81] Richard Schroeppel and Adi Shamir.  A $T=O(2^{n/2}),S=O(2^{n/4})$ algorithm for certain NP-complete problems.  SIAM journal on Computing, 10(3):456–464, 1981.
  * [Woe08] Gerhard J Woeginger.  Open problems around exact algorithms.  Discrete Applied Mathematics, 156(3):397–405, 2008.