# Efficient reductions and algorithms for variants of Subset Sum ††thanks: A
preliminary version of this work has been accepted to CALDAM 2022.

Pranjal Dutta Chennai Mathematical Institute, India (and Visiting Research
Fellow, Department of CSE, IIT Kanpur). Email<EMAIL_ADDRESS>Mahesh
Sreekumar Rajasree Department of CSE, IIT Kanpur. Email:
<EMAIL_ADDRESS>
###### Abstract

Given $(a_{1},\dots,a_{n},t)\in\mathbb{Z}_{\geq 0}^{n+1}$, the Subset Sum
problem ($\mathsf{SSUM}$) is to decide whether there exists $S\subseteq[n]$
such that $\sum_{i\in S}a_{i}=t$. There is a close variant of the
$\mathsf{SSUM}$, called $\mathsf{Subset~{}Product}$. Given positive integers
$a_{1},\ldots,a_{n}$ and a target integer $t$, the $\mathsf{Subset~{}Product}$
problem asks to determine whether there exists a subset $S\subseteq[n]$ such
that $\prod_{i\in S}a_{i}=t$. There is a pseudopolynomial time dynamic
programming algorithm, due to Bellman (1957) which solves the $\mathsf{SSUM}$
and $\mathsf{Subset~{}Product}$ in $O(nt)$ time and $O(t)$ space.

In the first part, we present search algorithms for variants of the Subset Sum
problem. Our algorithms are parameterized by $k$, which is a given upper bound
on the number of realisable sets (i.e., number of solutions, summing exactly
$t$). We show that $\mathsf{SSUM}$ with a unique solution is already
$\NP$-hard, under randomized reduction. This makes the regime of parametrized
algorithms, in terms of $k$, very interesting.

Subsequently, we present an $\tilde{O}(k\cdot(n+t))$ time deterministic
algorithm, which finds the hamming weight of all the realisable sets for a
subset sum instance. We also give a $\poly(knt)$-time and $O(\log(knt))$-space
deterministic algorithm that finds all the realisable sets for a subset sum
instance.

In the latter part, we present a simple and elegant randomized algorithm for
$\mathsf{Subset~{}Product}$ in $\tilde{O}(n+t^{o(1)})$ expected-time.
Moreover, we also present a $\poly(nt)$ time and $O(\log^{2}(nt))$ space
deterministic algorithm for the same. We study these problems in the unbounded
setting as well. Our algorithms use multivariate FFT, power series and number-
theoretic techniques, introduced by Jin and Wu (SOSA’19) and Kane (2010).

Keywords. subset sum, subset product, power series, isolation lemma, hamming
weight, interpolation, logspace, Newton’s identities, simultaneous, FFT,
pseudo-prime-factor

###### Contents

  1. 1 Introduction
    1. 1.1 Variants of Subset Sum
    2. 1.2 Our results
      1. 1.2.1 Time-efficient algorithms for variants of Subset Sum
      2. 1.2.2 Space-efficient algorithms for variants of Subset Sum
      3. 1.2.3 Reductions among variants of Subset Sum
    3. 1.3 Related works
  2. 2 Preliminaries and Notations
  3. 3 Hardness results
  4. 4 Time-efficient algorithms
    1. 4.1 Time-efficient algorithm for $\mathsf{Hamming}-k-\mathsf{SSSUM}$
  5. 5 Time-efficient algorithm for $\mathsf{Subset~{}Product}$
    1. 5.1 Proof of Theorem 2
  6. 6 Space-efficient algorithms
    1. 6.1 Space-efficient algorithm for $k-\mathsf{SSSUM}$
    2. 6.2 Space-efficient algorithm for $\mathsf{Subset~{}Product}$
  7. 7 An efficient reduction from $\mathsf{Subset~{}Product}$ to $\mathsf{SimulSubsetSum}$
    1. 7.1 Polynomial time algorithm for computing pseudo-prime-factors
  8. 8 Extending Theorem 1 and 2 to Unbounded Subset Sum
  9. 9 Conclusion
  10. A Generalizing Jin and Wu’s technique [JW18] to different settings
    1. A.1 Revisiting [JW18] with weighted coefficient
    2. A.2 Fast multivariate polynomial multiplication
    3. A.3 Solving linear recurrence: Tool for subsection 4.1
  11. B Algorithms
    1. B.1 Trivial solution for $k-\mathsf{SSSUM}$
    2. B.2 Trivial dynamic algorithm for $\mathsf{SimulSubsetSum}$
  12. C Dynamic programming approach for $\mathsf{Subset~{}Product}$

##  1 Introduction

The Subset Sum problem ($\mathsf{SSUM}$) is a well-known $\NP$-complete
problem [Lew83, p. 226], where given $(a_{1},\dots,a_{n},t)\in\mathbb{Z}_{\geq
0}^{n+1}$, the problem is to decide whether there exists $S\subseteq[n]$ such
that $\sum_{i\in S}\,a_{i}=t$. In the recent years, provable-secure
cryptosystems based on $\mathsf{SSUM}$ such as private-key encryption schemes
[LPS10], tag-based encryption schemes [FMV16], etc have been proposed. There
are numerous improvements made in the algorithms that solve the
$\mathsf{SSUM}$ problem in both the classical [BW21, Bri17, JW18, JVW21, EM20]
and quantum world [BJLM13, HM18, LL19]. One of the first algorithms was due to
Bellman [Bel57] who gave a $O(nt$) time (pseudo-polynomial time) algorithm
which requires $\Omega(t)$ space. In this paper, we give efficient algorithms
for interesting variants of subset sum.

###  1.1 Variants of Subset Sum

To begin with, one can ask for a search version of the subset sum problem,
i.e., to output all the solutions. Since there can be exponentially many
solutions, it could take $\exp(n)$-time (and space), to output them. This
motivates our first problem defined below.

######  Problem 1 ($k-\mathsf{SSSUM}$).

Given $(a_{1},\dots,a_{n},t)\in\mathbb{Z}_{\geq 0}^{n+1}$, the $k$-solution
$\mathsf{SSUM}$ $(k-\mathsf{SSSUM})$ problem asks to output all
$S\subseteq[n]$ such that $\sum_{i\in S}\,a_{i}=t$ provided with the guarantee
that the number of such subsets is at most $k$.

$\blacktriangleright$ Remark. We denote $1-\mathsf{SSSUM}$ as unique Subset
Sum problem ($\mathsf{uSSSUM}$). In stackexchange, a more restricted version
was asked where it was assumed that $k=1$, for any realizable $t$. Here we
just want $k=1$ for some fixed target value $t$ and we do not assume anything
for any other value $t^{\prime}$.

Now, we consider a different restricted version of the $k-\mathsf{SSSUM}$,
where we demand to output only the hamming weights of the $k$-solutions (we
call it $\mathsf{Hamming}-k-\mathsf{SSSUM}$, for definition see 2). By hamming
weight of a solution, we mean the number of $a_{i}$’s in the solution set
(which sums up to exactly $t$). In other words, if $\vec{a}\cdot\vec{v}=t$,
where $\vec{a}=(a_{1},\ldots,a_{n})$ and $\vec{v}\in\\{0,1\\}^{n}$, we want
$|v|_{1}$, the $\ell_{1}$-norm of the solution vector.

######  Problem 2 ($\mathsf{Hamming}-k-\mathsf{SSSUM}$).

Given an instance of the $k-\mathsf{SSSUM}$, say
$(a_{1},\dots,a_{n},t)\in\mathbb{Z}_{\geq 0}^{n+1}$, with the promise that
there are at most $k$-many $S\subseteq[n]$ such that $\sum_{i\in S}a_{i}=t$,
$\mathsf{Hamming}-k-\mathsf{SSSUM}$ asks to output all the hamming weights
(i.e., $|S|$) of the solutions.

It is obvious that solving $k-\mathsf{SSSUM}$ solves 2. Importantly, the
decision problem, namely the HWSSUM is already $\NP$-hard.

#####  HWSSUM and its $\NP$-hardness.

The HWSSUM problem is : Given an instance
$(a_{1},\ldots,a_{n},t,w)\in\mathbb{Z}_{\geq 0}^{n+2}$, decide whether there
is a solution to the subset sum with hamming weight equal to $w$. Note that,
there is a trivial Cook’s reduction from the $\mathsf{SSUM}$ to the HWSSUM:
$\mathsf{SSUM}$ decides ‘yes’ to the instance $(a_{1},\ldots,a_{n},t)$ iff at
least one of the following HWSSUM instances $(a_{1},\ldots,a_{n},t,i)$, for
$\,i\in[n]$ decides ‘yes’. Therefore, the search-version of HWSSUM, the
$\mathsf{Hamming}-k-\mathsf{SSSUM}$ problem, is already an interesting problem
and worth investigating.

In parallel, we also study a well-known variant of the subset sum, called
$\mathsf{Subset~{}Product}$.

######  Problem 3 ($\mathsf{Subset~{}Product}$).

Given $(a_{1},\dots,a_{n},t)$ $\in\mathbb{Z}_{\geq 1}^{n+1}$, the
$\mathsf{Subset~{}Product}$ problem asks to decide whether there exists an
$S\subseteq[n]$ such that $\prod_{i\in S}a_{i}=t$.

$\mathsf{Subset~{}Product}$ is also known to be $\NP$-complete [GJ79, p. 221].
Like $\mathsf{SSUM}$, it has a trivial $O(nt$) time (pseudo-polynomial time)
dynamic programming algorithm which requires $\Omega(t)$ space [Bel57].

$\mathsf{Subset~{}Product}$ has been studied and applied in many different
forms. For e.g., 1) constructing a smooth hash (VSH) by Contini, Lenstra and
Steinfeld [CLS06], 2) attack on the Naccache-Stern Knapsack (NSK) public key
cryptosystem [DMT20]. Similar problem has also been studied in optimization,
in the form of product knapsack problem [PST21], multiobjective knapsack
problem [BHV09] and so on.

Next, we define a ‘seemingly’ unrelated problem at first. It asks to decide
whether there is a ‘common’ solution to the given many instances of subset
sum. This was first introduced by [Kan10, Section 3.3] (but no formal name was
given). In this work, we study this as in intermediate problem which plays a
crucial role to study the $\mathsf{Subset~{}Product}$ problem, see section 5.

######  Problem 4 (SimulSubsetSum).

Given subset sum instances $(a_{1j},\dots,a_{nj},t_{j})$ $\in\mathbb{Z}_{\geq
0}^{n+1}$, for $j\in[k]$, where $k$ is some parameter, the Simultaneous Subset
Sum problem (in short, SimulSubsetSum) asks to decide whether there exists an
$S\subseteq[n]$ such that $\sum_{i\in S}a_{ij}=t_{j},\forall j\in[k]$.

$\blacktriangleright$ Remarks. 1. When $k$ is fixed parameter (independent of
$n$), we call this $k-\mathsf{SimulSubsetSum}$. There is a trivial
$O(n(t_{1}+1)\ldots(t_{k}+1))$ time deterministic algorithm for the
$\mathsf{SimulSubsetSum}$ problem with $k$ subset sum instances ($k$ not
necessarily a constant); for details see subsection B.2.

2\. It suffices to work with $t_{j}\geq 1,\forall j\in[k]$. To argue that, let
us assume that $t_{j}=0$ for some $j\in[k]$ and
$I_{j}:=\\{i\in[n]\,|\,a_{ij}=0\\}$. Observe that if $\mathsf{SimulSubsetSum}$
has a solution set $S\subseteq[n]$, then $S\subseteq I_{j}$. Therefore, for
every $\ell\in[k]$, instead of looking at
$(a_{1\ell},\dots,a_{n\ell},t_{\ell})$, it suffices to work with
$\\{a_{i,\ell}\,|\,i\in I_{j}\\}$ with the target $t_{\ell}$. Thus, we can
trivially ignore the $j^{th}$ $\mathsf{SSUM}$ instance.

##### Hardness depends on $k$.

4 asks to solve a system of $k$-linear equations in $n$-variables with $0/1$
constraints on the variables in a linear algebraic way. If we assume that the
set of vectors $\\{(a_{1j},\dots,a_{nj})\,|\,\forall j\in[k]\\}$ are linearly
independent; then we can perform Gaussian elimination to find a relation
between the free variables (exactly $n-k$) and dependent/leading variables.
Then, by enumerating over all possible $2^{n-k}$ values of the free variables
and finding the corresponding values for leading variables, we can check
whether there is a 0/1 solution. This takes $\poly(n,k)\cdot 2^{n-k}$ time.

In particular, when $k\geq n-O(\log(n))$, $\mathsf{SimulSubsetSum}$ (with
assuming linear independence), it has a polynomial time solution. Whereas, we
showed (in Theorem 15) that given a subset sum instance, we can convert this
into a $\mathsf{SimulSubsetSum}$ instance in polynomial time even with
$k=O(\log(n))$.

###  1.2 Our results

In this section, we briefly state our main results. The leitmotif of this
paper is to give efficient (time, space) algorithms for all the aforementioned
variants of subset sum.

####  1.2.1 Time-efficient algorithms for variants of Subset Sum

Our first theorem gives an efficient pseudo-linear $\tilde{O}(n+t)$ time
deterministic algorithm for 2, for constant $k$.

######  Theorem 1 (Algorithm for hamming weight).

There is a $\tilde{O}(k(n+t))$-time deterministic algorithm for
$\mathsf{Hamming}-k-\mathsf{SSSUM}$.

$\blacktriangleright$ Remark (Optimality). We emphasize the fact that Theorem
1 is likely to be near-optimal for bounded $k$, due to the following argument.
An $O(t^{1-\epsilon})$ time algorithm for $\mathsf{Hamming}-1-\mathsf{SSSUM}$
can be directly used to solve $1-\mathsf{SSSUM}$, as discussed above. By using
the randomized reduction (Theorem 14), this would give us a randomized
$n^{O(1)}t^{1-\epsilon}$-time algorithm for $\mathsf{SSUM}$. But, in [ABHS19]
the authors showed that $\mathsf{SSUM}$ does not have $n^{O(1)}t^{1-\epsilon}$
time algorithm unless the Strong Exponential Time Hypothesis (SETH) is false.

#####  Theorem 1 is better than the trivial.

Consider the usual ‘search-to-decision’ reduction for subset sum: First try to
include $a_{1}$ in the subset, and if it is feasible then we subtract $t$ by
$a_{1}$ and add $a_{1}$ into the solution, and then continue with $a_{2}$, and
so on. This procedure finds a single solution, but if we implement it in a
recursive way then it can find all the $k$ solutions in $k\cdot
n\cdot\text{(time complexity for decision version)}$ time; we can think about
an $n$-level binary recursion tree where all the infeasible subtrees are
pruned.Since number of solutions is bounded by $k$, choosing a prime $p>n+t+k$
suffices in [JW18], to make the algorithm deterministic. Thus, the time
complexity of the decision version is $\tilde{O}((n+t)\log k)$. Hence, from
the above, the search complexity is $\tilde{O}(kn(n+t))$ which is worse than
Theorem 1.

######  Theorem 2 (Time-efficient algorithm for $\mathsf{Subset~{}Product}$).

There exists a randomized algorithm that solves $\mathsf{Subset~{}Product}$ in
$\tilde{O}(n+t^{o(1)})$ expected-time.

Remarks. 1. The result in the first part of the above theorem is reminiscent
of the $\tilde{O}(n+t)$ time randomized algorithms for the subset sum problem
[JW18, Bri17], although the time complexity in our case is the expected time,
and ours is better.

2\. The expected time is because to factor an integer $t$ takes expected
$\exp(O(\sqrt{\log(t)\log\log(t)}))$ time [LP92]. If one wants to remove
expected time analysis (and do the worst case analysis), the same problem can
be solved in $\tilde{O}(n^{2}+t^{o(1)})$ randomized-time. For details, see the
end of subsection 5.1.

3\. While it is true that Bellman’s algorithm gives $O(nt)$ time algorithm,
the state-space of this algorithm can be improved to (expected)
$nt^{o(1)}$-time for $\mathsf{Subset~{}Product}$, using a similar dynamic
algorithm with a careful analysis. For details, see C.

####  1.2.2 Space-efficient algorithms for variants of Subset Sum

######  Theorem 3 (Algorithms for finding solutions in low space).

There is a $\poly(knt)$-time and $O(\log(knt))$-space deterministic algorithm
which solves $k-\mathsf{SSSUM}$.

$\blacktriangleright$ Remark. When considering low space algorithms outputting
multiple values, the standard assumption is that the output is written onto a
one-way tape which does not count into the space complexity; so an algorithm
outputting $kn\log n$ bits (like in the above case) could use much less
working memory than $kn\log n$; for a reference see McKay and Williams [MW18].

#####  Theorem 3 is better than the trivial.

Let us again compare with the trivial search-to-decision reduction time
algorithm, as mentioned in subsubsection 1.2.1. For solving the decision
problem in low space, we simply use Kane’s $O(\log(nt))$-space
$\poly(nt)$-time algorithm [Kan10]. As explained (and improved) in [JVW21],
the time complexity is actually $O(n^{3}t)$ and the extra space usage is
$\tilde{O}(n)$ for remembering the recursion stack. Thus the total time
complexity is $O(kn^{4}t)$ and it takes $\tilde{O}(n)+O(\log t)$ space. While
Theorem 3 takes $O(\log(knt))$ space and $\poly(knt)$ time. Although our time
complexity is worse 111Thm. 3 is not about time complexity; as long as it is
pseudopolynomial time it’s ok., when $k\leq 2^{O((n\log t)^{1-\epsilon})}$,
for $\epsilon>0$, our space complexity is better.

######  Theorem 4.

(Algorithm for $\mathsf{Subset~{}Product}$) $\mathsf{Subset~{}Product}$ can be
solved deterministically in $O(\log^{2}(nt))$ space and $\poly(nt)$-time.

$\blacktriangleright$ Remark. We cannot directly invoke the theorem in [Kan10,
Section 3.3] to conclude, since the reduction from $\mathsf{Subset~{}Product}$
to $\mathsf{SimulSubsetSum}$ requires $O(n\log(nt))$ space. Essentially, we
use the same identity lemma as [Kan10] and carefully use the space; for
details see subsection 6.2.

####  1.2.3 Reductions among variants of Subset Sum

Using a pseudo-prime-factorization decomposition, we show that given a target
$t$ in $\mathsf{Subset~{}Product}$, it suffices to solve
$\mathsf{SimulSubsetSum}$ with at most $\log t$ many instances, where each of
the targets are also ‘small’, at most $O(\log\log t)$ bits.

######  Theorem 5 (Reducing $\mathsf{Subset~{}Product}$ to
$\mathsf{SimulSubsetSum}$).

There is a deterministic polynomial time reduction from
$\mathsf{Subset~{}Product}$ to $\mathsf{SimulSubsetSum}$.

$\blacktriangleright$ Remark. The reduction uses $\tilde{O}(n\log t)$ space as
opposed to the following chain of reductions:
$\mathsf{Subset~{}Product}\leq_{\P}\mathsf{SSUM}\leq_{\P}\mathsf{SimulSubsetSum}$.
The first reduction is a natural reduction, from an input
$(a_{1},\ldots,a_{n},t)$, which takes $\log$ both sides and adjust (multiply)
a ‘large’ $M$ (it could be $O(n\log t)$ bit [KP10, PST21]) with $\log a_{i}$,
to reduce this to a $\mathsf{SSUM}$ instance with $b_{i}:=\lfloor M\log
a_{i}\rfloor$. Therefore, the total space required could be as large as
$\tilde{O}(n^{2}\log t)$. The second reduction follows from Theorem 15.
Therefore, ours is more space efficient. Motivated thus, we give an efficient
randomized algorithm for $\mathsf{SimulSubsetSum}$.

${\mathsf{HWSSUM}}$${\mathsf{SimulSubsetSum}}$${\mathsf{SSUM}}$${\mathsf{SSSUM}}$${\mathsf{UBSSUM}}$
Figure 1: Reductions among variants of the Subset Sum problem

In the latter part, we present few reductions among $\mathsf{SSUM}$,
$k-\mathsf{SSSUM}$ and $\mathsf{SimulSubsetSum}$ problems. We also extend 1-2
to the unbounded version of the Subset Sum problem ($\mathsf{UBSSUM}$) and
show similar theorems as above. For details, see section 7-8.

###  1.3 Related works

Before going into the details, we briefly review the state of the art of the
problems (& its variants). After Bellman’s $O(nt)$ dynamic solution [Bel57],
Pisinger [Pis99] first improved it to $O(nt/\log t)$ on word-RAM models.
Recently, Koiliaris and Xu gave a deterministic algorithm [KX19, KX18] in time
$\tilde{O}(\sqrt{n}t)$, which is the best deterministic algorithm so far.
Bringmann [Bri17] & Jin et.al. [JW18] later improved the running time to
randomized $\tilde{O}(n+t)$. All these algorithms require $\Omega(t)$ space.
Moreover, most of the recent algorithms solve the decision versions. Here we
remark that in [ABHS19], the authors showed that $\mathsf{SSUM}$ has no
$t^{1-\epsilon}n^{O(1)}$ time algorithm for any $\epsilon>0$, unless the
Strong Exponential Time Hypothesis (SETH) is false. Therefore, the
$\tilde{O}(n+t)$ time bound is likely to be near-optimal.

There have been a very few attempts to classically solve
$\mathsf{Subset~{}Product}$ or its variants. It is known to be $\NP$-complete
and the reduction follows from the Exact Cover by 3-Sets (X3C) problem [GJ79,
p. 221]. Though the knapsack and its approximation versions have been studied
[KP10, PST21], we do not know many classical algorithms and attempts to solve
this, unlike the recent attention for the subset sum problem [Bri17, JW18,
JVW21, BW21].

In [KX19] (also see [KX18, Lemma 2]), the authors gave a deterministic
$\tilde{O}(nt)$ algorithm that finds all the hamming weights for all
realisable targets less than equal to $t$. Their algorithm does not depend on
the number of solutions for a particular target. Compared to this, our Theorem
1 is faster when $k=o(n/(\log n)^{c})$, for a large constant $c$. Similarly,
with the ‘extra’ information of $k$, we give a faster deterministic algorithm
(which even outputs all the hamming weights of the solutions) compared to
$\tilde{O}(\sqrt{n}t)$ decision algorithm in [KX18, KX19] (which outputs all
the realisable subset sums $\leq t$), when $k=o(\sqrt{n}/(\log n)^{c})$, for a
large constant $c$. Here we remark that the $O(nt)$-time dynamic programming
algorithm [Bel57] can be easily modified to find all the solutions, but this
gives an $O(n(k+t))$-time (and space) algorithm solution (for more details,
see subsection B.1).

On the other hand, there have been quite some work on solving $\mathsf{SSUM}$
in $\mathsf{LOGSPACE}$. Elberfeld, Jakoby, and Tantau [EJT10], and Kane[Kan10]
(2010) gave $O(\log nt)$ space $\poly(nt)$-time deterministic algorithm, which
have been very recently improved to $\tilde{O}(n^{2}t)$-time and
$\poly\log(nt)$ space. On the other hand, Bringmann [Bri17] gave a
$nt^{1+\epsilon}$ time, $O(n\log t)$ space randomized algorithm, which have
been improved to $O(\log n\log\log n+\log t)$ space by Jin et.al.[JVW21].
Again, most of the algorithms are decision algorithms and do not output the
solution set. In contrast to this, our algorithm (algorithm 2) in Theorem 3
uses only $O(\log(knt))$ and outputs all the solution sets, which is near-
optimal.

Since subset sum can be solved in randomized $\tilde{O}(n+t)$ time [JW18], as
mentioned before, one obvious way to solve $\mathsf{Subset~{}Product}$ would
be to work with $b_{i}:=\lfloor M\log a_{i}\rfloor$ and a $\mathcal{R}$, a
range of target values $t^{\prime}$ which could be as large as $M\log t$ such
that $\mathsf{Subset~{}Product}$ is YES iff subset sum instance with $b_{i}$
and $t^{\prime}\in\mathcal{R}$ is YES. But $M$ could be as large as
$O(n\cdot\left(\prod_{i}a_{i}\right)^{1/2})$. Therefore, although there is a
randomized near-linear time algorithm for subset sum, when one reduces the
instance of $\mathsf{Subset~{}Product}$ to a subset sum instance, the target
becomes very large, failing to give an $\tilde{O}(n+t)$ algorithm.

Moreover, the general techniques, used for subset sum [Bri17, JW18, JVW21]
seem to fail to ‘directly’ give algorithms for $\mathsf{Subset~{}Product}$.
This is exactly why, in this work, the efficient algorithms have been
indirect, via solving $\mathsf{SimulSubsetSum}$ instances.

##  2 Preliminaries and Notations

Notations. $\mathbb{N},\mathbb{Z}$ and $\mathbb{Q}$ denotes the set of all
natural numbers, integers and rational numbers respectively. Let $a,b$ be two
$m$-bit integers .Then, $a//b$ denotes $a/b^{e}$ where $e$ is the largest non-
negative integer such that $b^{e}\,|\,a$. Observe that $a//b$ is not divisible
by $b$ and the time to compute $a//b$ is $O(m\log(m)\cdot\log(e))$.

For any positive integer $n>0$, $[n]$ denotes the set $\\{1,2,\dots,n\\}$
while $[a,b]$ denotes the set of integers $i$ s.t. $a\leq i\leq b$. Also,
$2^{[n]}$ denotes the set of all subsets of $[n]$, while $\log$ denotes
$\log_{2}$. A weight function $w\,:\,[n]\,\longrightarrow\,[m]$, can be
naturally extended to a set $S\in 2^{[n]}$, by defining $w(S)\,:=\,\sum_{i\in
S}\,w(i)$. We also denote $\tilde{O}(g)$ to be $g\cdot\poly(\log g)$.

$\mathbb{F}[x_{1},\dots,x_{k}]$ denotes the ring of $k$-variate polynomials
over field $\mathbb{F}$ and $\mathbb{F}[[x_{1},\dots,x_{k}]]$ is the ring of
power series in $k$-variables over $\mathbb{F}$. We will use the short-hand
notation ${\boldsymbol{x}}$ to denote the collection of variables
$(x_{1},\dots,x_{k})$ for some $k$. For any non-negative integer vector
$\overline{e}\in\mathbb{Z}^{k}$, ${\boldsymbol{x}}^{\overline{e}}$ denotes
$\prod_{i=1}^{k}x_{i}^{e_{i}}$. Using these notations, we can will write any
polynomial $f({\boldsymbol{x}})\in\mathbb{Z}[{\boldsymbol{x}}]$ as
$f({\boldsymbol{x}})=\sum_{\overline{e}\in
S}f_{e}\cdot{\boldsymbol{x}}^{\overline{e}}$ for some suitable set $S$.

We denote $\textup{{coef}}_{{\boldsymbol{x}}^{{\boldsymbol{e}}}}(f)$, as the
coefficient of ${\boldsymbol{x}}^{{\boldsymbol{e}}}$ in the polynomial
$f({\boldsymbol{x}})$ and $\deg_{x_{i}}(f)$ as the highest degree of $x_{i}$
in $f({\boldsymbol{x}})$. Sparsity of a polynomial
$f(x_{1},\ldots,x_{k})\in\mathbb{F}[x_{1},\ldots,x_{k}]$ over a field
$\mathbb{F}$, denotes the number of nonzero terms in $f$.

######  Definition 1 (Subset Sum problem ($\mathsf{SSUM}$)).

Given $(a_{1},\dots,a_{n},t)\in\mathbb{Z}_{\geq 0}^{n+1}$, the subset sum
problem is to decide whether $t$ is a realisable target with respect to
$(a_{1},\dots,a_{n})$, i.e., there exists $S\subseteq[n]$ such that
$\sum_{i\in S}a_{i}=t$. Here, $n$ is called the size, $t$ is the target and
any $S\subseteq[n]$ such that $\sum_{i\in S}a_{i}=t$ is a realisable set of
the subset sum instance.

Assumptions. Throughout the paper, we assume that $t\geq\max a_{i}$ for
simplicity.

######  Lemma 6 ([MVV87, Isolation Lemma]).

Let $n$ and $N$ be positive integers, and let $\mathcal{F}$ be an arbitrary
family of subsets of $[n]$. Suppose $w(x)$ is an integer weight given to each
element $x\in[n]$ uniformly and independently at random from $[N]$. The weight
of $S\in\mathcal{F}$ is defined as $w(S)=\sum_{x\in S}w(x)$. Then, with
probability at least $1-n/N$, there is a unique set $S^{\prime}\in\mathcal{F}$
that has the minimum weight among all sets of $\mathcal{F}$.

######  Lemma 7 (Kane’s Identity [Kan10]).

Let $f(x)=\sum_{i=0}^{d}c_{i}x^{i}$ be a polynomial of degree at most $d$ with
coefficients $c_{i}$ being integers. Let $\mathbb{F}_{q}$ be the finite field
of order $q=p^{k}>d+2$. For $0\leq t\leq d$, define

$r_{t}=\sum_{x\in\mathbb{F}_{q}^{*}}x^{q-1-t}f(x)=-c_{t}\in\mathbb{F}_{q}$

Then, $r_{t}=0\iff c_{t}$ is divisible by $p$.

######  Lemma 8 (Newton’s Identities).

Let $X_{1},\ldots,X_{n}$ be $n\geq 1$ variables. Let
$P_{m}(X_{1},\dots,X_{n})=\sum_{i=1}^{n}X_{i}^{m}$, be the $m$-th power sum
and $E_{m}(X_{1},\ldots,X_{n})$ be the $m$-th elementary symmetric
polynomials, i.e., $E_{m}(x_{1},\ldots,x_{n})=\sum_{1\leq j_{1}\leq\ldots\leq
j_{m}\leq n}\,X_{j_{1}}\cdots X_{j_{m}}$, then

$m\cdot
E_{m}(X_{1},\dots,X_{n})\;=\;\sum_{i=1}^{m}(-1)^{i-1}E_{m-i}(X_{1},\dots,X_{n})\cdot
P_{i}(X_{1},\dots,X_{n})\;.$

######  Remarks 1.

$E_{m}(X_{1},\ldots,X_{n})=0$ when $m>n$ (for a quick recollection, see wiki).

######  Lemma 9 (Vieta’s formulas).

Let $f(x)=\prod_{i=1}^{n}(x-a_{i})$ be a monic polynomial of degree $n$. Then,
$f(x)=\sum_{i=0}^{n}c_{i}x^{i}$ where
$c_{n-i}=(-1)^{i}E_{i}(a_{1},\dots,a_{n}),\forall 1\leq i\leq n$ and
$c_{n}=1$.

######  Lemma 10 (Polynomial division with remainder [VZGG13, Theorem 9.6]).

Given a $d$-degree polynomial $f$ and a linear polynomial $g$ over a finite
field $\mathbb{F}_{p}$, there exists a deterministic algorithm that finds the
quotient and remainder of $f$ divided by $g$ in $\tilde{O}(d\log p)$-time.

Next, we define ord${}_{p}(a)$; this notion will be important later.

######  Definition 2 (Order of a number $\bmod~{}p$).

The order of $a~{}(\bmod~{}p)$, denoted as ord${}_{p}(a)$ is defined to be the
smallest positive integer $m$ such that $a^{m}\equiv 1~{}\bmod~{}p$.

######  Theorem 11 ([Shp96]).

There exists a $\tilde{O}(p^{1/4+\epsilon})$ time algorithm to
determinstically find a primitive root over $\mathbb{F}_{p}$.

######  Theorem 12 ([Nag52]).

For $n\geq 25$, there is a prime in the interval $[n,\frac{6}{5}\cdot n]$.

The following is a naive bound, but it is sufficient for our purpose.

######  Lemma 13.

For integers $a\geq b\geq 1$, we have $(a/b)^{b}\leq 2^{2\sqrt{ab}}$.

###### Proof.

Let $x=\sqrt{a/b}$. We need to show that $x^{2b}\leq 2^{2bx}$, which is
trivially true since $x\leq 2^{x}$, for $x\geq 1$. ∎

##  3 Hardness results

In this section, we prove some hardness results. These proofs are very
standard, still after different feedback and reviews, we give the details for
the brevity.

Some of the algorithms presented in this paper consider that the number of
solutions is bounded by a parameter $k$. This naturally raises the question
whether the $\mathsf{SSUM}$ problem is hard, when the number of solutions is
bounded. We will show that this is true even for the case when $k=1$, i.e.,
$\mathsf{uSSSUM}$ is NP-hard under randomized reduction.

######  Theorem 14 (Hardness of $\mathsf{uSSSUM}$).

There exists a randomized reduction which takes a $\mathsf{SSUM}$ instance
$\mathcal{M}=(a_{1},\dots,a_{n},t)\in\mathbb{Z}_{\geq 0}^{n+1}$, as an input,
and produces multiple $\mathsf{SSUM}$ instances
$\mathcal{SS}_{\ell}=(b_{1},\dots,b_{n},t^{(\ell)})$, where $\ell\in[2n^{2}]$,
such that if

  * •

$\mathcal{M}\text{ is a YES instance of
$\mathsf{SSUM}$}\implies\exists\ell\text{ such that $\mathcal{SS}_{\ell}$ is a
YES instance of $\mathsf{uSSSUM}$}$;

  * •

$\mathcal{M}\text{ is a NO instance of
$\mathsf{SSUM}$}\implies\forall\ell,\mathcal{SS}_{\ell}\text{ is a NO instance
of $\mathsf{uSSSUM}$}$.

###### Proof.

The core of the proof is based on the 6 (Isolation lemma). The reduction is as
follows. Let $w_{1},\dots,w_{n}$ be chosen uniformly at random from $[2n]$. We
define $b_{i}=4n^{2}a_{i}+w_{i},\forall i\in[n]$ and the $\ell^{th}$
$\mathsf{SSUM}$ instance as
$\mathcal{SS}_{\ell}=(b_{1},\dots,b_{n},t^{(\ell)}=4n^{2}t+\ell)$. Observe
that all the new instances are different only in the target values
$t^{(\ell)}$.

Suppose $\mathcal{M}$ is a YES instance, i.e., $\exists S\subseteq[n]$ such
that $\sum_{i\in S}a_{i}=t$. Then, for $\ell=\sum_{i\in S}w_{i}$, the
$\mathcal{SS}_{\ell}$ is a YES instance, because

$\sum_{i\in S}b_{i}-t^{(\ell)}\,=\,4n^{2}\left(\sum_{i\in
S}a_{i}-t\right)\,-\,\left(\ell-\sum_{i\in S}w_{i}\right)\,=\,0\;.$

If $\mathcal{M}$ is a NO instance, consider any $\ell$ and $S\subseteq[n]$.
Since $\mathcal{M}$ is a NO instance, $4n^{2}(\sum_{i\in S}a_{i}-t)$ is a non-
zero multiple of $4n^{2}$, whereas $|\ell-\sum_{i\in S}w_{i}|<4n^{2}$, which
implies that

$4n^{2}(\sum_{i\in S}a_{i}-t)-(\ell-\sum_{i\in S}w_{i})\neq
0\implies\sum_{i\in S}b_{i}\neq t^{(\ell)}\;.$

Hence, $\mathcal{SS}_{\ell}$ is also a NO instance.

We now show that if $\mathcal{M}$ is a YES instance, then one of
$\mathcal{SS}_{\ell}$ is a $\mathsf{uSSSUM}$. Let $\mathcal{F}$ contain all
the solutions to the $\mathsf{SSUM}$ instance $\mathcal{M}$, i.e.,
$\mathcal{F}=\\{S|S\subseteq[n],\sum_{i\in S}a_{i}=t\\}$. Since $w_{i}$’s are
chosen uniformly at random, 6 says that there exists a unique
$S\in\mathcal{F}$, such that $w(S)=\sum_{i\in S}w_{i}$, is minimal with
probability at least $1/2$. Let us denote this minimal value $w(S)$ as
$\ell^{*}$. Then, $\mathcal{SS}_{\ell^{*}}$ is $\mathsf{uSSSUM}$ because $S$
is the only subset such that $\sum_{i\in S}w_{i}=\ell^{*}$. ∎

Next, we present a simple deterministic Cook’s reduction from $\mathsf{SSUM}$
to $2-\mathsf{SimulSubsetSum}$. It is obvious to see that
$2-\mathsf{SimulSubsetSum}\in\NP$ which implies that
$2-\mathsf{SimulSubsetSum}$ is NP-complete.

######  Theorem 15 (Hardness of $2-\mathsf{SimulSubsetSum}$).

There is a deterministic polynomial time reduction from $\mathsf{SSUM}$ to
$2-\mathsf{SimulSubsetSum}$.

###### Proof.

Let $(a_{1},\dots,a_{n},t)$ be an instance of $\mathsf{SSUM}$. Consider the
following $2-\mathsf{SimulSubsetSum}$ instances,
$\mathcal{S}_{b}=[(a_{1},\ldots,a_{n},t),\,(1,0,\dots,0,b)]$, where
$b\in\\{0,1\\}$. If the $\mathsf{SSUM}$ instance is NO, then both the
$2-\mathsf{SimulSubsetSum}$ are also NO. If the $\mathsf{SSUM}$ instance is a
YES, then we argue that one of the $S_{b}$ instance must be YES. If
$\mathsf{SSUM}$ instance has a solution which contains $a_{1}$, then
$\mathcal{S}_{1}$ is a YES instance whereas if it does not contain $a_{1}$,
then $S_{0}$ is a YES instance. ∎

##### Extension to $\log-\mathsf{SimulSubsetSum}$.

The above reduction can be trivially extended to reduce $\mathsf{SSUM}$ to
$\mathsf{SimulSubsetSum}$, with number of $\mathsf{SSUM}$ instances $k=O(\log
n)$. In that case we will work with instances $S_{\boldsymbol{b}}$, for
${\boldsymbol{b}}\in\\{0,1\\}^{k}$. Since the number of instances is
$2^{k}=\poly(n)$, the reduction goes through.

We will now show that $2-\mathsf{SimulSubsetSum}$ reduces to $\mathsf{SSUM}$
which again can be generalised to $\mathsf{SimulSubsetSum}$, for any number of
$\mathsf{SSUM}$ instances $k$.

######  Theorem 16 ($2-\mathsf{SimulSubsetSum}$ is easier than
$\mathsf{SSUM}$).

There is a deterministic polynomial time reduction from
$2-\mathsf{SimulSubsetSum}$ to $\mathsf{SSUM}$.

###### Proof.

Let $[(a_{1},\dots,a_{n},t_{1}),(b_{1},\dots,b_{n},t_{2})]$ be a
$2-\mathsf{SimulSubsetSum}$ instance where without loss of generality
$t_{1}\leq t_{2}$. Also, we can assume that $t_{1}\leq\sum_{i=1}^{n}a_{i}$,
otherwise it does not have a solution.

Now, consider the $\mathsf{SSUM}$ instance $(\gamma b_{1}+a_{1},\dots,\gamma
b_{n}+a_{n},\gamma t_{2}+t_{1})$, where $\gamma:=1+\sum_{i=1}^{n}a_{i}$. If
the $2-\mathsf{SimulSubsetSum}$ instance is YES, this implies that there exist
$S\subseteq[n]$ such that $\sum_{i\in S}a_{i}=t_{1}$ and $\sum_{i\in
S}b_{i}=t_{2}$. This implies that $\sum_{i\in S}\gamma b_{i}+a_{i}=\gamma
t_{2}+t_{1}$ and hence the $\mathsf{SSUM}$ instance is also YES.

Now, assume that the $\mathsf{SSUM}$ instance is YES, i.e., there exists
$S\subseteq[n]$ such that $\sum_{i\in S}\gamma b_{i}+a_{i}=\gamma
t_{2}+t_{1}$. This implies that $\gamma(t_{2}-\sum_{i\in
S}b_{i})+(t_{1}-\sum_{i\in S}a_{i})=0$. If $t_{1}\neq\sum_{i\in S}a_{i}$, then
from the previous equality, $(t_{1}-\sum_{i\in S}a_{i})$ is a non-zero
multiple of $\gamma\implies|\,t_{1}-\sum_{i\in S}a_{i}\,|\geq\gamma$. However,
by our assumption,

$t_{1}\;\leq\;\sum_{i=1}^{n}a_{i}\;\implies\;t_{1}-\sum_{i\in
S}a_{i}\;\leq\;\sum_{i\in[n]\setminus
S}a_{i}\;<\;1+\sum_{i\in[n]}a_{i}\;=\;\gamma\;.$

Moreover, $t_{1}-\sum_{i\in S}a_{i}>-\gamma$, holds trivially, since
$\gamma>\sum_{i\in[n]}a_{i}$ and $t_{1}>0$. Therefore, $|\,t_{1}-\sum_{i\in
S}a_{i}\,|<\gamma$ which implies that both $t_{1}-\sum_{i\in S}a_{i}=0$ and
$t_{2}-\sum_{i\in S}b_{i}=0$. Hence, the $2-\mathsf{SimulSubsetSum}$ instance
is also YES. ∎

##  4 Time-efficient algorithms

###  4.1 Time-efficient algorithm for $\mathsf{Hamming}-k-\mathsf{SSSUM}$

In this section, we present an $\tilde{O}(k(n+t))$-time deterministic
algorithm for outputting all the hamming weight of the solutions, given a
$\mathsf{Hamming}-k-\mathsf{SSSUM}$ instance, i.e., there are only at most
$k$-many solutions to the $\mathsf{SSUM}$ instance
$(a_{1},\ldots,a_{n},t)\in\mathbb{Z}_{\geq 0}^{n+1}$. The basic idea is
simple: We want to create a polynomial whose roots are of the form
$\mu^{w_{i}}$, so that we can first find the roots $\mu^{w_{i}}$ (over
$\mathbb{F}_{q}$), and from them we can find $w_{i}$. To achieve that, we work
with $k$-many polynomials $f_{j}:=\prod_{i=1}^{n}(1+\mu^{j}\cdot x^{a_{i}})$,
for $j\in[k]$. Note that the coefficient of $x^{t}$ in $f_{j}$ is of the form
$\sum_{i\leq k}\lambda_{i}\cdot\mu^{jw_{i}}$ (18). By Newton’s Identities (8)
and Vieta’s formulas (9), we can now efficiently construct a polynomial whose
roots are $\mu^{w_{i}}$. The details are given below.

###### Proof of Theorem 1.

We start with some notations that we will use throughout the proof.

##### Basic notations.

Assume that the $\mathsf{SSUM}$ instance
$(a_{1},\dots,a_{n},t)\in\mathbb{Z}_{\geq 0}^{n+1}$ has exactly $m\ (m\leq k)$
many solutions, and they have $\ell$ many distinct hamming weights
$w_{1},\ldots,w_{\ell}$; since two solutions can have same hamming weight,
$\ell\leq m$. Moreover, assume that there are $\lambda_{i}$ many solutions
which appear with hamming weight $w_{i}$, for $i\in[\ell]$. Thus,
$\sum_{i\in[\ell]}\lambda_{i}=m\leq k$.

##### Choosing prime $q$ and a primitive root $\mu$.

We will work with a fixed $q$ in this proof, where $q>n+k+t:=M$ (we will
mention why such a requirement later). We can find a prime $q$ in
$\tilde{O}(n+k+t)$ time, since we can go over every element in the interval
$[M,6/5\cdot M]$, in which we know a prime exists (Theorem 12) and primality
testing is efficient [AKS04]. Once we find $q$, we choose $\mu$ such that
$\mu$ is a primitive root over $\mathbb{F}_{q}$, i.e., ord${}_{q}(\mu)=q-1$.
This $\mu$ can be found in $\tilde{O}((n+k+t)^{1/4+\epsilon})$ time using
Theorem 11. Thus, the total time complexity of this step is
$\tilde{O}(n+k+t)$.

##### The polynomials.

Define the $k$-many univariate polynomials as follows:

$f_{j}(x)\;:=\;\prod_{i\in[n]}\,(1+\mu^{j}x^{a_{i}})\;,\,\forall\,j\,\in\,[k]\;.$

We remark that we do not know $\ell$ apriori, but we can find $m$ efficiently.

######  Claim 17 (Finding the exact number of solutions).

Given a $\mathsf{Hamming}-k-\mathsf{SSSUM}$ instance, one can find the exact
number of solutions, $m$, deterministically, in $\tilde{O}((n+t))$ time.

###### Proof.

Use [JW18] (see 30, for the general statement) which gives a deterministic
algorithm to find the coefficient of $x^{t}$ of
$\prod_{i\in[n]}\,(1+x^{a_{i}})$ over $\mathbb{F}_{q}$; this takes time
$\tilde{O}((n+t))$. ∎

Since we know the exact value of $m$, we will just work with $f_{j}$ for
$j\in[m]$, which suffices for our algorithmic purpose. Here is an important
claim about coefficients of $x^{t}$ in $f_{j}$’s.

######  Claim 18.

$C_{j}=\textup{{coef}}_{x^{t}}(f_{j}(x))\;=\;\sum_{i\in[\ell]}\,\lambda_{i}\cdot\mu^{jw_{i}}$,
for each $j\in[m]$.

###### Proof.

If $S\subseteq[n]$ is a solution to the instance with hamming weight, say $w$,
then this will contribute $\mu^{jw}$ to the coefficient of $x^{t}$ of
$f_{j}(x)$. Since, there are $\ell$ many weights $w_{1},\ldots,w_{\ell}$ with
multiplicity $\lambda_{1},\ldots,\lambda_{\ell}$, the claim easily follows. ∎

Using 30, we can find $C_{j}~{}\bmod~{}q$ for each $j\in[m]$ in
$\tilde{O}((n+t\log(\mu j)))$ time, owing total $\tilde{O}(k(n+t))$, since
$q=O(n+k+t)$, $\mu\leq q-1$, and $\sum_{j\in[m]}\log
j=\log(m!)\leq\log(k!)=\tilde{O}(k)$.

Using the Newton’s Identities (8), we have the following relations, for
$j\in[m]$:

$E_{j}\left(\mu^{w_{1}},\ldots,\mu^{w_{\ell}}\right)\,\equiv\,j^{-1}\cdot\left(\sum_{i=1}^{j}(-1)^{i-1}\,E_{j-i}\left(\mu^{w_{1}},\dots,\mu^{w_{k}}\right)\cdot
P_{i}\left(\mu^{w_{1}},\ldots,\mu^{w_{\ell}}\right)\right)\;\bmod~{}q\,.$ (1)

In the above, by $E_{j}(\mu^{w_{1}},\ldots,\mu^{w_{\ell}})$, we mean
$E_{j}(\underbrace{\mu^{w_{1}},\ldots,\mu^{w_{1}}}_{\lambda_{1}~{}\text{times}},\underbrace{\mu^{w_{2}},\ldots,\mu^{w_{2}}}_{\lambda_{2}~{}\text{times}},\ldots,\underbrace{\mu^{w_{\ell}},\ldots,\mu^{w_{\ell}}}_{\lambda_{\ell}~{}\text{times}})$,
and similar for $P_{j}$. Since $q>k$, $j^{-1}\bmod~{}q$ exists, and thus the
above relations are valid. Here is another important and obvious observation,
just from the definition of $P_{j}$’s:

######  Observation 1.

For $j\in[k]$, $C_{j}\equiv
P_{j}\left(\mu^{w_{1}},\ldots,\mu^{w_{\ell}}\right)\bmod~{}q$.

Note that we know $E_{0}=1$ and $P_{j}$’s (and $j^{-1}\bmod q$) are already
computed. To compute $E_{j}$, we need to know $E_{1},\ldots,E_{j-1}$ and
additionally we need $O(j)$ many additions and multiplications. Suppose,
$T(j)$ is the time to compute $E_{1},\ldots,E_{j}$. Then, the trivial
complexity is $T(m)\leq\tilde{O}(k^{2})+\tilde{O}(k(n+t))$. But one can do
better than $\tilde{O}(k^{2})$ and make it $\tilde{O}(k)$ (i.e solve the
recurrence, using FFT), owing the total complexity to
$T(m)\leq\tilde{O}(k(n+t))$ (since $q=O(n+k+t)$). For details, see subsection
A.3.

Once, we have computed $E_{j}$, for $j\in[m]$, define a new polynomial

$g(x)\;:=\;\sum_{j=0}^{m}\,(-1)^{j}\cdot
E_{j}(\mu^{w_{1}},\ldots,\mu^{w_{\ell}})\cdot x^{j}\;.$

Using 9, it is immediate that
$g(x)=\prod_{i=1}^{\ell}(x-\mu^{w_{i}})^{\lambda_{i}}$. Further, by
definition, deg$(g)=m$. From $g$, now we want to extract the roots, namely
$\mu^{w_{1}},\ldots,\mu^{w_{\ell}}$ over $\mathbb{F}_{q}$. We do this, by
checking whether $(x-\mu^{i})$ divides $g$, for $i\in[n]$ (since $w_{i}\leq
n$). Using 10, a single division with remainder takes $\tilde{O}(k)$,
therefore, the total time to find all the $w_{i}$ is
$\tilde{O}(nk)=\tilde{O}(nk)$.

Here, we remark that we do not use the determinstic root finding or factoring
algorithms (for e.g. [Sho90, BKS15]), since it takes
$\tilde{O}(mq^{1/2})=\tilde{O}(k\cdot(k+t)^{1/2})$ time, which could be larger
than $\tilde{O}(k(n+t))$.

##### Reason for choosing $q$ and $\mu$.

In the hindsight, there are three important properties of the prime $q$ that
will suffice to successfully output the $w_{i}$’s using the above described
steps:

  1. 1.

Since, 30 requires to compute the inverses of numbers upto $t$, hence, we
would want $q>t$.

  2. 2.

While computing $E_{j}(\mu^{w_{1}},\dots,\mu^{w_{k}})$ using 8 in the above,
one should be able to compute the inverse of all $j$’s less than equal to $m$.
So, we want $q>m$,.

  3. 3.

To obtain $w_{i}$ from $\mu^{w_{i}}\bmod~{}q$, we want ord${}_{q}(\mu)>n$ (for
definition see 2). Since, $w_{i}\leq n$, this would ensure that we have found
the correct $w_{i}$.

Here, we remark that we do not need to concern ourselves about the ‘largeness’
of the coefficients of $C_{j}$ and make it nonzero $\bmod~{}q$, as required in
[JW18]. For the first two points, it suffices to choose $q>k+t$. Since $\mu$
is a primitive root over $\mathbb{F}_{q}$, this guarantees that
ord${}_{q}(\mu)=q-1>n$ and thus we will find $w_{i}$ from $\mu^{w_{i}}$
correctly.

##### Total time complexity.

The complexity to find the correct $m,q$ and $\mu$ is $\tilde{O}(n+k+t)$.
Finding the coefficients of $g$ takes $\tilde{O}(k(n+t))$ and then finding
$w_{i}$ from $g$ takes $\tilde{O}(nk)$ time. Thus, the total complexity
remains $\tilde{O}(k(n+t))$. ∎

$\blacktriangleright$ Remark. The above algorithm can be extended to find the
multiplicities $\lambda_{i}$’s in $\tilde{O}(k(n+t)+k^{3/2})$ by finding the
largest $\lambda_{i}$, by binary search, such that
$(x-\mu^{w_{i}})^{\lambda_{i}}$ divides $g(x)$. Finding each $\lambda_{i}$
takes $\tilde{O}(m\log(\lambda_{i}))$ over $\mathbb{F}_{q}$, for the same $q$
as above, since the polynomial division takes $\tilde{O}(m)$ time and binary
search introduces a multiplicative $O(\log(\lambda_{i}))$ term. Since,
$\sum_{i\in[\ell]}\log(\lambda_{i})=\log\left(\prod_{i\in[\ell]}\lambda_{i}\right)$,
using AM-GM, $\prod_{i\in[\ell]}\lambda_{i}\leq(m/\ell)^{\ell}$, which is
maximized at $\ell=\sqrt{m}\leq\sqrt{k}$, implying
$\sum_{i\in[\ell]}\log(\lambda_{i})\leq O(\sqrt{k}\log k)$. Since, $m\leq k$,
this explains the additive $k^{3/2}$ term in the complexity.

1

Input: A $k-\mathsf{SSSUM}$ instance $a_{1},\dots,a_{n},t$

Output: Hamming weights of all subsets $S\subseteq[n]$ such that $\sum_{i\in
S}a_{i}=t$

2

3Using 30, find the number of solutions $m$ for the $k-\mathsf{SSSUM}$
instance $a_{1},\dots,a_{n},t$ and terminate if $m=0$;

4 Choose a prime $q$ from the interval $[k+t,6/5\cdot(k+t)]$ ;

5 Find a primitive root $\mu$ over $\mathbb{F}_{q}$;

6 for  _$j\in[m]$_ do

7 Using $q$ in 30, find $C_{j}=\textup{{coef}}_{x^{t}}(f_{j}(x))$ where
$f_{j}(x)=\prod_{i\ =n}(1+\mu^{j}x^{a_{i}})$;

8

9 end for

10Compute $E_{0},E_{1},\dots,E_{m}$ from $P_{1},\dots,P_{m}$ where
$P_{i}\equiv C_{i}\mod{q}$ using FFT;

11 $W=\\{\\}$;

12 for  _$i\in[n]$_ do

13 if  _$(x-\mu^{i})\ |\ g(x)$_ then

14 $W=W\cup\\{i\\}$;

15

16 end if

17

18 end for

19return $W$;

Algorithm 1 Algorithm for $\mathsf{Hamming}-k-\mathsf{SSSUM}$

##  5 Time-efficient algorithm for $\mathsf{Subset~{}Product}$

In this section, we give a randomized $\tilde{O}(n+t^{o(1)})$ expected time
algorithm for $\mathsf{Subset~{}Product}$. Essentially, we factor all the
entries in the instance in $\tilde{O}(n+t^{o(1)})$ expected time. Once we have
the exponents, it suffices to solve the corresponding
$\mathsf{SimulSubsetSum}$ instance. Now, we can use the efficient randomized
algorithm for $\mathsf{SimulSubsetSum}$ (Theorem 19) to finally solve
$\mathsf{Subset~{}Product}$. So, first we give an efficient algorithm for
$\mathsf{SimulSubsetSum}$.

######  Theorem 19 (Algorithm for $\mathsf{SimulSubsetSum}$).

There is a randomized $\tilde{O}(kn+\prod_{i\in[k]}(2t_{i}+1))$-time algorithm
that solves $\mathsf{SimulSubsetSum}$, with target instances
$t_{1},\ldots,t_{k}$.

###### Proof.

Let us assume that the input to the $\mathsf{SimulSubsetSum}$ problem are $k$
$\mathsf{SSUM}$ instance of the form $(a_{1j},\ldots,a_{nj},t_{j})$, for
$j\in[k]$. Define a $k$-variate polynomial $f({\boldsymbol{x}})$, where
${\boldsymbol{x}}=(x_{1},\dots,x_{k})$, as follows:

$f({\boldsymbol{x}})\;=\;\prod_{i=1}^{n}\,\left(1\,+\,\prod_{j=1}^{k}\,x_{j}^{a_{ij}}\right)\;.$

Here is an immediate but important claim. We denote the monomial
$\boldsymbol{m}:=\prod_{i=1}^{k}x_{i}^{t_{i}}$ and
$\textup{{coef}}_{\boldsymbol{m}}(f)$ as the coefficient of $\boldsymbol{m}$
in the polynomial $f({\boldsymbol{x}})$.

######  Claim 20.

There is a solution to the $\mathsf{SimulSubsetSum}$ instance, i.e., $\exists
S\subseteq[n]$ such that $\sum_{i\in S}a_{ij}=t_{j},\forall j\in[k]$ iff
$\textup{{coef}}_{\boldsymbol{m}}(f({\boldsymbol{x}}))\neq 0$.

Therefore, it is enough to compute the coefficient of $f({\boldsymbol{x}})$.
The rest of the proof focuses on computing $f({\boldsymbol{x}})$ efficiently,
to find $\textup{{coef}}_{\boldsymbol{m}}(f)$.

Let $p$ be prime such that $p\in[N+1,(n+N)^{3}]$, where
$N:=\prod_{i=1}^{k}(2t_{i}+1)$. Define an ideal $\mathcal{I}$, over
$\mathbb{Z}[{\boldsymbol{x}}]$ as follows: $\mathcal{I}:=\langle
x_{1}^{t_{1}+1},\ldots,x_{k}^{t_{k}+1},p\rangle$. Since, we are interested in
$\textup{{coef}}_{\boldsymbol{m}}(f)$, it suffices to compute
$f({\boldsymbol{x}})\bmod~{}\langle
x_{1}^{t_{1}+1},\ldots,x_{k}^{t_{k}+1}\rangle$, and we do it over a field
$\mathbb{F}_{p}$ (which introduces error); for details, see the proof in the
end (Randomness and error probability paragraph).

Using 32, we can compute all the coefficient of
$\ln(f({\boldsymbol{x}}))\,\bmod\,\mathcal{I}$ in time
$\tilde{O}(kn+\prod_{i=1}^{k}t_{i})$. It is easy to see that the following
equalities hold.

$f({\boldsymbol{x}})~{}\bmod~{}\mathcal{I}\;\equiv\;\exp\left(\ln(f({\boldsymbol{x}}))\right)~{}\bmod~{}\mathcal{I}\;\equiv\;\exp\left(\ln(f({\boldsymbol{x}}))\bmod\,\mathcal{I}\right)~{}\bmod~{}\mathcal{I}\;.$

Since, we have already computed
$\ln(f({\boldsymbol{x}}))\,\bmod\,\mathcal{I}$, the above equation implies
that it is enough to compute the exponential which can be done using 31. This
also takes time $\tilde{O}(kn+\prod_{i=1}^{k}(2t_{i}+1))$.

##### Randomness and error probability.

Note that there are $\Omega(n+N)^{2}$ primes in the interval
$[N+1,(n+N)^{3}]$. Moreover, since $\textup{{coef}}_{\boldsymbol{m}}(f)\leq
2^{n}$, at most $n$ prime factors can divide
$\textup{{coef}}_{\boldsymbol{m}}(f({\boldsymbol{x}}))$. Therefore, we can
pick a prime $p$ randomly from this interval in $\poly(\log(n+N))$ time and
the the probability of $p$ dividing the coefficient is $O(n+N)^{-1}$. In other
words, the probability that the algorithm fails is bounded by
$O\left((n+N)^{-1}\right)$. This concludes the proof. ∎

∎

We now compare the above result with some obvious attempts to solve
$\mathsf{SimulSubsetSum}$, before moving into solving
$\mathsf{Subset~{}Product}$.

A detailed comparison with time complexity of [Kan10]. Kane [Kan10, Section
3.3] showed that the above problem can be solved deterministically in
$C^{O(k)}$ time and $O(k\log C)$ space, where
$C:=\sum_{i,j}a_{ij}+\sum_{j}t_{j}+1$, which could be as large as
$(n+1)\cdot(\sum_{j\in[k]}t_{j})+1$, since $a_{ij}$ can be as large as
$t_{j}$. As argued in [JVW21, Corollary 3.4 and Remark 3.5], the constant in
the exponent, inside the order notation, can be as large as $3$ (in fact
directly using [Kan10] gives larger than $3$; but modified algorithm as used
in [JVW21] gives $3$). Use AM-GM inequality to get

$\left((n+1)\cdot(\sum_{j}t_{j})+1\right)^{3k}\,>\,\left(\frac{2}{k}\cdot\sum_{j}t_{j}+1\right)^{3k}\;\stackrel{{\scriptstyle\text{AM-
GM}}}{{\geq}}\;\prod_{j=1}^{k}\,\left(2t_{j}+1\right)^{3}\;.$

Assuming $N=\prod_{j=1}^{k}\,(2t_{j}+1)$, our algorithm is near-linear in $N$
while Kane’s algorithm [Kan10] takes at $O(N^{3})$ time; thus ours is almost a
cubic improvement.

Comparison with the trivial algorithm. It is easy to see that a trivial
$O(n\cdot(t_{1}+1)(t_{2}+1)\ldots(t_{k}+1))$ time deterministic algorithm for
$\mathsf{SimulSubsetSum}$ exists. Since, $t_{i}\geq 1$, we have

$\frac{n}{2}\cdot\prod_{i\in[k]}(1+t_{i})\,\geq\,\frac{n}{2}\cdot
2^{k}\,\geq\,kn\,,\;\;\text{and}\;\;\frac{n}{2}\cdot\prod(1+t_{i})\,\geq\,\frac{n}{2^{k+1}}\cdot\prod(2t_{i}+1)\,.$

Here, we used $2(1+x)>(2x+1)$, for any $x\geq 1$. Therefore,
$n\cdot\prod_{i\in[k]}(1+t_{i})\geq kn+n/2^{k+1}\cdot\prod(2t_{i}+1)$. Thus,
when $k=o(\log n)$, our complexity is better.

###  5.1 Proof of Theorem 2

Once we have designed the algorithm for $\mathsf{SimulSubsetSum}$, we design
time-efficient algorithm for Theorem 2.

###### Proof.

Let $(a_{1},\dots,a_{n},t)\in\mathbb{Z}_{\geq 0}^{n+1}$ be the input for
$\mathsf{Subset~{}Product}$ problem. Without loss of generality, we can assume
that all the $a_{i}$ divides $t$ because if some $a_{i}$ does not divide $t$,
it will never be a part of any solution and we can discard it. Let us first
consider the prime factorization of $t$ and $a_{j}$, for all $j\in[n]$. We
will discuss about its time complexity in the next paragraph. Let

$t\;=\;\prod_{j=1}^{k}\,p_{j}^{t_{j}}\,,~{}~{}~{}~{}a_{i}\;=\;\prod_{j=1}^{k}\,p_{j}^{e_{ij}},\,\forall\,i\,\in\,[n]\,,$

where $p_{j}$ are distinct primes and $t_{j}$ are positive integers and
$e_{ij}\in\mathbb{Z}_{\geq 0}$. Since, $p_{i}\geq 2$, trivially,
$\sum_{i=1}^{k}t_{i}\leq\log(t)$, and
$\sum_{i=1}^{k}e_{ij}\leq\log(t),j\in[n]$. Also, the number of distinct prime
factors of $t$ is at most $O(\log(t)/\log\log(t))$; therefore,
$k=O(\log(t)/\log\log(t))$.

##### Time complexity of factoring

To find all the primes that divides $t$, we will use the factoring algorithm
given by Lenstra and Pomerance [LP92] which takes expected $t^{o(1)}$
222Expected time complexity is $\exp(O(\sqrt{\log t\log\log t}))$, which is
smaller than $t^{O(1/\sqrt{\log\log t})}=t^{o(1)}$, which will be the time
taken in the next step. Moreover, we are interested in randomized algorithms,
hence expected run-time is time to completely factor $t$ into prime factors
$p_{j}$ (including the exponents $t_{j}$). Using the primes $p_{j}$ and the
fact that $0\leq e_{ij}\leq\log(t)$, computing $e_{ij}$ takes
$\log^{2}(t)\log\log(t)$ time, by performing binary search to find the largest
$x$ such that $p_{j}^{x}\,|\,a_{i}$. So, the time to compute all exponents
$e_{i,j},\forall i\in[n],j\in[k]$ is $O(nk\log^{2}(t)\log\log(t))$. Since,
$k\leq O(\log t/\log\log(t))$, the total time complexity is
$\tilde{O}(n+t^{o(1)})$.

##### Setting up $\mathsf{SimulSubsetSum}$

Now suppose that $S\subseteq[n]$ is a solution to the
$\mathsf{Subset~{}Product}$ problem, i.e., $\prod_{i\in S}a_{i}=t$. This
implies that

$\sum_{i\in S}\,e_{ij}\;=\;t_{j}\,,~{}~{}\forall\,j\,\in\,[k]\;.$

In other words, we have a $\mathsf{SimulSubsetSum}$ instance where the
$j^{th}$ $\mathsf{SSUM}$ instance is $(e_{1j},e_{2j},\dots,e_{nj},t_{j})$, for
$j\in[k]$. The converse is also trivially true. We now show that there exists
an $\tilde{O}(kn+\prod_{i\in[k]}(2t_{i}+1))$ time algorithm to solve
$\mathsf{SimulSubsetSum}$.

##### Randomized algorithm for $\mathsf{Subset~{}Product}$

Using Theorem 19, we can decide the $\mathsf{SimulSubsetSum}$ problem with
targets $t_{1},\dots,t_{k}$ in $\tilde{O}(kn+\prod_{i\in[k]}(2t_{i}+1))$ time
(randomized) while working over $\mathbb{F}_{p}$ for some suitable $p$ (we
point out towards the end). Since $k\leq O(\log(t)/\log\log(t))$, we need to
bound the term $\prod_{i\in[k]}(2t_{i}+1)$. Note that,

$\displaystyle\prod_{i\in[k]}\,(2t_{i}+1)$
$\displaystyle\;=\;\sum_{S\subseteq[k]}\,2^{|S|}\cdot\left(\prod_{i\in
S}\,t_{i}\right)$
$\displaystyle\;\leq\;2^{2k}\cdot\left(\prod_{i\in[k]}t_{i}\right)\;.$

We now focus on bounding the term $\prod_{i\in[k]}t_{i}$. By AM-GM,

$\displaystyle\prod_{i\in[k]}t_{i}\leq\left(\dfrac{\sum_{i\in[k]}t_{i}}{k}\right)^{k}$
$\displaystyle\leq\left(\dfrac{\log(t)}{k}\right)^{k}$ $\displaystyle\leq
2^{O\left(\sqrt{k\log(t)}\right)}~{}~{}~{}~{}[Lemma~{}\ref{lem:inequality}]$
$\displaystyle\leq 2^{O\left(\sqrt{\log(t)^{2}/\log\log(t)}\right)}$
$\displaystyle\leq t^{O(1/\sqrt{\log\log(t)})}=t^{o(1)}$

Note that the prime $p$ in the Theorem 19 was $p\in[N+1,(n+N)^{3}]$, where
$N:=\prod_{i=1}^{k}(2t_{i}+1)-1$. As shown above, we can bound $N=t^{o(1)}$.
Thus, $p\leq O((n+t^{o(1)})^{3})$, as desired. Therefore, the total time
complexity is
$\tilde{O}(n\log(t)/\log\log(t)+t^{o(1)})=\tilde{O}(n+t^{o(1)})$. This
finishes the proof. ∎∎

##### Removing the expected-time

If one wants to understand the worst-case analysis, we can use the polynomial
time reduction from $\mathsf{Subset~{}Product}$ to $\mathsf{SimulSubsetSum}$
in section 7. Of course, we will not get prime factorization; but the pseudo-
prime factors will also be good enough to set up the $\mathsf{SimulSubsetSum}$
with similar parameters as above, and the $\mathsf{SimulSubsetSum}$ instance
can be similarly solved in $\tilde{O}(n+t^{o(1})$ time. Since the reduction
takes $n^{2}\poly(\log t)$ time, the total time complexity becomes
$\tilde{O}(n^{2}+t^{o(1)})$.

##  6 Space-efficient algorithms

###  6.1 Space-efficient algorithm for $k-\mathsf{SSSUM}$

In this section, we will present a low space algorithm (algorithm 2) for
finding all the realisable sets for $k-\mathsf{SSSUM}$. Unfortunately, proof
of Theorem 1 fails to give a low space algorithm, since 30 requires
$\Omega(t)$ space (eventually it needs to store all the coefficients
$\bmod~{}x^{t+1}$). Instead, we work with a multivariate polynomial
$f(x,y_{1},\dots,y_{n})=\prod_{i=1}^{n}(1+y_{i}x^{a_{i}})$ over
$\mathbb{F}_{q}$, for a large prime $q=O(nt)$ and its multiple evaluations
$f(\alpha,c_{1},\ldots,c_{n})$, where
$(\alpha,c_{1},\ldots,c_{n})\in\mathbb{F}_{q}^{n+1}$.

Observe that, the coefficient of $x^{t}$ in $f$ is a multivariate polynomial
$p_{t}(y_{1},\dots,y_{n})$; each of its monomial carries the necessary
information of a solution, for the instance $(a_{1},\dots,a_{n},t)$. More
precisely, $S$ is a realisable set of $(a_{1},\dots,a_{n},t)\iff\prod_{i\in
S}y_{i}$ is a monomial in $p_{t}$. And, the sparsity (number of monomials) of
$p_{t}$ is at most $k$. Therefore, it boils down to reconstruct the
multivariate polynomial $p_{t}$ efficiently. We cannot use the trivial
multiplication since it takes $\tilde{O}(2^{n}t)$ time! Instead, we use ideas
from [Kan10] and [KS01].

###### Proof of Theorem 3.

Here are some notations that we will follow throughout the proof.

##### Basic notations.

Let us assume that there are exactly $m\ (m\leq k)$ many realisable sets
$S_{1},\ldots,S_{m}$, each $S_{i}\subseteq[n]$. We remark that for our
algorithm we do not need to apriori calculate $m$.

##### The multivariate polynomial.

For our purpose, we will be working with the following $(n+1)$-variate
polynomial:

$f(x,y_{1},\ldots,y_{n})\;:=\;\prod_{i\in[n]}\,\left(1+y_{i}x^{a_{i}}\right)\;.$

Since, we have a $k-\mathsf{SSSUM}$ instance $(a_{1},\ldots,a_{n},t)$,
$\textup{{coef}}_{x^{t}}(f)$ has the following properties.

  1. 1.

It is an $n$-variate polynomial $p_{t}(y_{1},\dots,y_{n})$ with sparsity
exactly $m$.

  2. 2.

$p_{t}$ is a multilinear polynomial in $y_{1},\dots,y_{n}$, i.e., individual
degree of $y_{i}$ is at most $1$.

  3. 3.

The total degree of $p_{t}$ is at most $n$.

  4. 4.

if $S\subseteq[n]$ is a realisable set, then ${\mathbf{y}}_{S}:=\prod_{i\in
S}y_{i}$, is a monomial in $p_{t}$.

In particular, the following is an immediate but important observation.

######  Observation 2.

$p_{t}(y_{1},\ldots,y_{n})\,=\,\sum_{i\in[m]}\,{\boldsymbol{y}}_{S_{i}}$ .

Therefore, it suffices to know the polynomial $p_{t}$. However, we cannot
treat $y_{i}$ as new variables and try to find the coefficient of $x^{t}$
since the trivial multiplication algorithm (involving $n+1$ variables) takes
$\exp(n)$-time. This is because, $f(x,y_{1},\ldots,y_{n})~{}\bmod~{}x^{t+1}$
can have $2^{n}\cdot t$ many monomials as coefficient of $x^{i}$, for any
$i\leq t$ can have $2^{n}$ many multilinear monomials.

However, if we substitute $y_{i}=c_{i}\in\mathbb{F}_{q}$, for some prime $q$,
we claim that we can figure out the value $p_{t}(c_{1},\ldots,c_{n})$ from the
coefficient of $x^{t}$ in $f(x,c_{1},\ldots,c_{n})$ efficiently (see 22). Once
we have figured out, we can simply interpolate using the following theorem to
reconstruct the polynomial $p_{t}$. Before going into the technical details,
we state the sparse interpolation theorem below; for simplicity we consider
multilinearity (though [KS01] holds for general polynomials as well).

######  Theorem 21 ([KS01]).

Given a black box access to a multilinear polynomial $g(x_{1},\dots,x_{n})$ of
degree $d$ and sparsity at most $s$ over a finite field $\mathbb{F}$ with
$|\mathbb{F}|\geq(nd)^{6}$, there is a $\poly(snd)$-time and
$O(\log(snd))$-space algorithm that outputs all the monomials of $g$.

$\blacktriangleright$ Remark. We represent one monomial in terms of indices
(to make it consistent with the notion of realisable set), i.e., for a
monomial $x_{1}x_{5}x_{9}$, the corresponding indices set is $\\{1,5,9\\}$.
Also, we do not include the indices in the space complexity, as mentioned
earlier.

##### Brief analysis on the space complexity of [KS01].

Klivans and Spielman [KS01], did not explicitly mention the space complexity.
However, it is not hard to show that the required space is indeed
$O(\log(snd))$. [KS01] shows that substituting $x_{i}=y^{k^{i-1}\bmod p}$, for
some $k\in[2s^{2}n]$ and $p>2s^{2}n$, makes the exponents of the new
univaraite polynomial (in $y$) distinct (see [KS01, Lemma 3]); the algorithm
actually tries for all $k$ and find the correct $k$. Note that the degree
becomes $O(s^{2}nd)$. Then, it tries to first find out the coefficients by
simple univariate interpolation [KS01, Section 6.3] . Since we have blackbox
access to $g(a_{1},\ldots,a_{n})$, finding out a single coefficient, by
univariate interpolation (which basically sets up linear equations and solve)
takes $O(\log(snd))$ space and $\poly(snd)$ time only. In the last step, to
find one coefficient, we can use the standard univariate interpolation
algorithm which uses the Vandermonde matrices and one entry of the inverse of
the Vandermonde is $\log$-space computable 333In fact Vandermonde determinant
and inverse computations are in $\TC^{0}\subset$ $\mathsf{LOGSPACE}$, see
[MT98]..

At this stage, we know the coefficients (one by one), but we do not know which
monomials the coefficients belong. However, it suffices to substitute
$x_{i}=2y^{k^{i-1}\bmod~{}p}$. Using this, we can find the the correct value
of the first exponent in the monomial. For eg. if after the correct
substitution, $y^{10}$ appears with coefficient say $5$, next step, when we
change just $x_{1}$, if it does not affect the coefficient $5$, $y_{1}$ is not
there in the monomial corresponding to the monomial which has coefficient $5$,
otherwise it is there (here we also use that it is multilinear and hence the
change in the coefficient must be reflected). This step again requires
univariate interpolation, and one has to repeat this experiment wrt each
variable to know the monomial exactly corresponding to the coefficient we are
working with. We can reuse the space for interpolation and after one round of
checking with every variable, it outputs one exponent at this stage. This
requires $O(\log(snd)$-space and $\poly(snd)$ time.

With a more careful analysis, one can further improve the field requirement to
$|\mathbb{F}|\geq(nd)^{6}$ only (and not dependent on $s$); for details see
[KS01, Thm. 5 & 11].

Now we come back to our subset sum problem. Since we want to reconstruct an
$n$-variate $m$ sparse polynomial $p_{t}$ which has degree at most $n$, it
suffices to work with $|\mathbb{F}|\geq n^{12}$. However, we also want to use
Kane’s identity (7), which requires $q>\deg(f(x,c_{1},\ldots,c_{n}))+2$, and
$\deg(f(x,c_{1},\ldots,c_{n}))\leq nt$. Denote $M:=\max(nt+3,n^{12})$. Thus,
it suffices to we work with $\mathbb{F}=\mathbb{F}_{q}$ where
$q\in[M,(6/5)\cdot M]$, such prime exists (Theorem 12) and easy to find
deterministically in $\poly(nt)$ time and $O(\log(nt))$ space using [AKS04].
In particular, we will substitute $y_{i}=c_{i}\in[0,q-1]$.

######  Claim 22.

Fix $c_{i}\in[0,q-1]$, where $q\in[M,(6/5)\cdot M]$. Then, there is a
$\poly(nt)$-time and $O(\log(nt))$ space algorithm which computes
$p_{t}(c_{1},\ldots,c_{n})$ over $\mathbb{F}_{q}$.

###### Proof.

Note that, we can evaluate each $1+c_{i}x^{a_{i}}$, at some
$x=\alpha\in\mathbb{F}_{q}$, in $\tilde{O}(\log nt)$ time and $O(\log(nt))$
space. Multiplying $n$ of them takes $\tilde{O}(n\log(nt))$-time and
$O(\log(nt))$ space.

Once we have computed $f(\alpha,c_{1},\ldots,c_{n})$ over $\mathbb{F}_{q}$,
using Kane’s identity (7), we can compute $p_{t}(c_{1},\ldots,c_{n})$, since

$p_{t}(c_{1},\ldots,c_{n})\;=\;-\,\sum_{\alpha\in\mathbb{F}_{q}^{*}}\,\alpha^{q-1-t}f(\alpha,c_{1},\ldots,c_{n})\;.$

As each evaluation $f(\alpha,c_{1},\ldots,c_{n})$ takes $\tilde{O}(n\log(nt))$
time, and we need $q-1$ many additions, multiplications and modular
exponentiations, total time to compute is $\poly(nt)$. The required space
still remains $O(\log(nt))$. ∎

Once, we have calculated $p_{t}(c_{1},\ldots,c_{n})$ efficiently, now we try
different values of $(c_{1},\ldots,c_{n})$ to reconstruct $p_{t}$ using
Theorem 21. Since, $p_{t}$ is a $n$-variate at most $k$ sparse polynomial with
degree at most $n$, it still takes $\poly(knt)$ time and $O(\log(knt))$ space.
This finishes the proof. ∎

Input: A $k-\mathsf{SSSUM}$ instance $a_{1},\dots,a_{n},t$

Output: All realisable subsets $S\subseteq[n]$ such that $\sum_{i\in
S}a_{i}=t$

1

2Pick a prime $q\in\\{M,(6/5)\cdot M\\}$ where $M=max(nt+3,n^{12})$;

3 Let $\mathcal{O}$ be the algorithm mentioned in Theorem 21;

4 for  _each $p_{t}(c_{1},\dots,c_{n})$ query requested by $\mathcal{O}$_ do

5 Send
$-(\underset{\alpha\in\mathbb{F}_{q}^{*}}{\sum}\alpha^{q-1-t}f(\alpha,c_{1},\dots,c_{n}))$
to $\mathcal{O}$;

6

7 end for

8$p_{t}$ be the polynomial return by $\mathcal{O}$;

9 $\mathcal{F}=\\{\\}$;

10 for  _each monomial ${\boldsymbol{y}}_{S}$ in $p_{t}$_ do

11 $\mathcal{F}=\mathcal{F}\cup\\{S\\}$

12 end for

13return $\mathcal{F}$;

14

Algorithm 2 Algorithm for $k-\mathsf{SSSUM}$

###  6.2 Space-efficient algorithm for $\mathsf{Subset~{}Product}$

The proof of Theorem 4 uses the idea of reducing $\mathsf{Subset~{}Product}$
to $\mathsf{SimulSubsetSum}$ and then solving $\mathsf{SimulSubsetSum}$ by
computing the coefficient of
$f({\boldsymbol{x}})=\prod_{i=1}^{n}\,\left(1\,+\,\prod_{j=1}^{k}\,x_{j}^{a_{ij}}\right)$
where ${\boldsymbol{x}}=(x_{1},\ldots,x_{k})$ using an extension of 7. We
cannot directly use [Kan10] as it requires large space ($O(n\log(nt))$ space
to be precise) to store the $\mathsf{SimulSubsetSum}$ instance. Instead we
compute the coefficient of $f({\boldsymbol{x}})$ without storing the
$\mathsf{SimulSubsetSum}$ instance using 23.

The low space algorithm presented in this proof depends on the generalisation
of 7. Here we present Kane’s identity for bivariate polynomials which can be
easily extended to $k$-variate polynomials.

######  Lemma 23 (Identity lemma [Kan10]).

Let $f(x,y)=\sum_{i=0}^{d_{1}}\sum_{j=0}^{d_{2}}c_{i,j}x^{i}y^{j}$ be a
polynomial of degree at most $d_{1}+d_{2}$ with coefficients $c_{i,j}$ being
integers. Let $\mathbb{F}_{q}$ be the finite field of order
$q=p^{m}>\max(d_{1},d_{2})+1$. For $0\leq t_{1}\leq d_{1},0\leq t_{2}\leq
d_{2}$, define

$r_{t_{1},t_{2}}=\sum_{x\in\mathbb{F}_{q}^{*}}\sum_{y\in\mathbb{F}_{q}^{*}}x^{q-1-t_{1}}y^{q-1-t_{2}}f(x,y)=c_{t_{1},t_{2}}\in\mathbb{F}_{q}$

###### Proof.

Let $n$ be a positive integer, then the two following identities hold:

  1. Identity 1.

$\sum_{x\in\mathbb{F}_{q}^{*}}x^{n}=-1$ if $q-1\,|\,n$ because
$x^{n}=x^{(q-1)m}=1$ due to Fermat’s Little theorem.

  2. Identity 2.

$\sum_{x\in\mathbb{F}_{q}^{*}}x^{n}=0$, if $q-1\nmid\,n$. This is because we
can rewrite the summation as $\sum_{i=0}^{q-2}g^{i\cdot
n}=\dfrac{g^{n(q-1)}-1}{g^{n}-1}=0$ where $g$ is a generator of
$\mathbb{F}_{q}^{*}$.

Let us now consider
$\sum_{x\in\mathbb{F}_{q}^{*}}\sum_{y\in\mathbb{F}_{q}^{*}}x^{q-1-t_{1}}y^{q-1-t_{2}}f(x,y)$.

$\displaystyle\sum_{x\in\mathbb{F}_{q}^{*}}\sum_{y\in\mathbb{F}_{q}^{*}}x^{q-1-t_{1}}y^{q-1-t_{2}}f(x,y)$
$\displaystyle=\sum_{x\in\mathbb{F}_{q}^{*}}\sum_{y\in\mathbb{F}_{q}^{*}}x^{q-1-t_{1}}y^{q-1-t_{2}}\left(\sum_{i=0}^{d_{1}}\sum_{j=0}^{d_{2}}c_{i,j}x^{i}y^{j}\right)$
$\displaystyle=\sum_{i=0}^{d_{1}}\sum_{j=0}^{d_{2}}c_{i,j}\left(\sum_{x\in\mathbb{F}_{q}^{*}}\sum_{y\in\mathbb{F}_{q}^{*}}x^{q-1-t_{1}+i}y^{q-1-t_{2}+j}\right)$
$\displaystyle=\sum\limits_{\begin{subarray}{c}i\in[0,d_{1}]\setminus\\{t_{1}\\}\\\
j\in[0,d_{2}]\setminus\\{t_{2}\\}\end{subarray}}c_{i,j}\left(\sum_{x\in\mathbb{F}_{q}^{*}}\sum_{y\in\mathbb{F}_{q}^{*}}x^{q-1-t_{1}+i}y^{q-1-t_{2}+j}\right)$
$\displaystyle\;\;\;\;+c_{t_{1},t_{2}}$ $\displaystyle=c_{t_{1},t_{2}}$

Observe that when $i\in[0,d_{1}]\setminus\\{t_{1}\\}$, we have
$\sum_{x\in\mathbb{F}_{q}^{*}}x^{q-1-t_{1}+i}=0$ because $|i-t_{1}|\leq
d_{1}<q-1\implies q-1+i-t_{1}$ is not a multiple of $q-1$. The same goes for
$j\in[0,d_{2}]\setminus\\{t_{2}\\}$.

∎

$\blacktriangleright$ Remark. 23 can be easily extended to $k$ variables which
was used by the authors of [Kan10] to solve $\mathsf{SimulSubsetSum}$ with $k$
many $\mathsf{SSUM}$ instances in space $O(k\log(n\sum_{i=1}^{k}t_{i}))$ and
time $(poly(n,t_{1},\dots,t_{k}))^{O(k)}$. In this case, the order of the
finite field must be greater than $\max(d_{1},\ldots,d_{k})+1$ where $d_{i}$’s
are the individual degrees of the polynomial.

##### Issue with directly invoking [Kan10].

Using Theorem 5, we can reduce a $\mathsf{Subset~{}Product}$ instance
$(a_{1},\dots,a_{n},t)$ to a $\mathsf{SimulSubsetSum}$ instance containing $k$
$\mathsf{SSUM}$ instances $(e_{1i},\dots,e_{ni},t_{i}),\forall i\in[k]$ where
$k\leq\log(t)$. The space required for the $\mathsf{SimulSubsetSum}$ instance
is the number of bits in $e_{ij},t_{j}$. We know that
$a_{i}=\prod_{j=1}^{k}p_{i}^{e_{ij}}\implies
2^{\sum_{j=1}^{k}\log(e_{ij})}\leq 2^{\sum_{j=1}^{k}e_{ij}}\leq a_{i}$ because
$p_{i}\geq 2,\forall i\in[k]$. Therefore, we have
$\sum_{i,j}\log(e_{i,j})\leq\sum_{i=1}^{n}\log(a_{i})\leq n\log(t)$.
Similarly, $\sum_{i}\log(t_{i})\leq\log(t)$. Therefore, the space required for
the $\mathsf{SimulSubsetSum}$ is $O(n\log(t))$. And, if we directly use the
low-space algorithm for $\mathsf{SimulSubsetSum}$ from [Kan10], the total
space complexity would become $O((n+\log(nt))\cdot\log(t))$.

To avoid the $n$-factor in the space complexity, we will not be storing the
entire $\mathsf{SimulSubsetSum}$ instance. Instead, for each summation in the
$k$ variate version of 23, we will compute the values of $e_{ij}$ and $t_{j}$
and discard them after using it. To be precise, for
$\overline{g}=(t_{1},\dots,t_{k})$, we have

$c_{\overline{g}}=(-1)^{k}\sum_{{\boldsymbol{x}}\in(\mathbb{F}_{q}^{*})^{k}}f({\boldsymbol{x}})\cdot\prod_{i=1}^{k}x_{i}^{q-1-t_{i}}$

where
$f({\boldsymbol{x}})=\prod_{i=1}^{n}\left(1+\prod_{j=1}^{k}x_{j}^{e_{ij}}\right)$
and $c_{\overline{g}}=\textup{{coef}}_{\overline{g}}(f({\boldsymbol{x}}))$.
The values of $e_{ij}$ and $t_{i}$ is only required in $f({\boldsymbol{x}})$
and $\prod_{i=1}^{k}x_{i}^{q-1-t_{i}}$ respectively. Since, $e_{ij}$ and
$t_{i}$ are the powers of $p_{i}$ in $a_{j}$ and $t$ respectively, we can’t
use pseudo-prime-factorization as this would require us to use $O(n\log(t))$
space to compute a pseudo-prime-factor set. Therefore, we will use naive
prime-factorization algorithm that runs in $\tilde{O}(t)$ time which is
affordable because we are interested in $\poly(knt)$.

##### Choosing the prime $q$.

Observe that the total degree of $f({\boldsymbol{x}})$ is $\sum_{ij}e_{ij}\leq
n\cdot(\sum_{i}t_{i})\leq n\log t$ because $0\leq e_{ij}\leq t_{j}$ and
$\sum_{i}t_{i}\leq\log(t)$. Therefore, the maximum individual degree is
bounded by $n\log(t)$. Since, 23 requires a prime $q$ that depends on the
maximum individual degree of the polynomial, it suffices to work with
$N=\lceil n\log(t)\rceil$ and $q>N$. Observe that we need to compute the
coefficient modulo $q$, therefore, we need to ensure that $q$ does not divide
the coefficient. To achieve this, we will use 23 for different primes
$q\in[N+1,(n+N)^{3}]$ which contains $\Omega(n+N)^{2}$ prime. This works
because the coefficient can be at most $2^{n}$, therefore, it will have at
most $n$ prime factors. So, at least one prime in the range will not divide
the coefficient.

##### Computing $f({\boldsymbol{x}})$ and $\prod_{i=1}^{k}x_{i}^{q-1-t_{i}}$
using low space.

We will make sure that $t_{i}$ is the exponent of the $i^{th}$ smallest prime
factor of $t$. To find an $e_{ij}$, we will first find the $i^{th}$ smallest
prime $p_{i}$ that divides $t$ and then compute the largest power of $p_{i}$
that divides $a_{j}$. Once, we find $e_{ij}$, we can use it to compute
$\prod_{j=1}^{k}x_{j}^{e_{ij}}$ part of $f({\boldsymbol{x}})$ and discard it
as shown in algorithm 3. Similarly, we can compute
$\prod_{i=1}^{k}x_{i}^{q-1-t_{i}}$.

##### Space and Time complexity.

Observe that algorithm 3 uses only $O(\log(nt))$ space for variables that are
used through out the algorithm and reuses $O(\log(t))$ space while computing
$t_{i},e_{ij},p_{\ell}$ values. It uses $k\log(nt)=O(\log^{2}(nt))$ space for
$\overline{y}$, therefore, the total space complexity is $O(\log^{2}(nt))$.
Whereas the time complexity is $\poly(nt)$ because each loop runs for
$\poly(nt)$ iterations and finding the exponents take $\tilde{O}(t)$ time.

Input: A $\mathsf{Subset~{}Product}$ instance
$(a_{1},\dots,a_{n},t)\in\mathbb{N}^{n+1}$

Output: Decides whether the $\mathsf{Subset~{}Product}$ instance has a
solution

1

2$k=0$;

3 for  _each prime $p_{i}\,|\,t$_ do

4 $k=k+1$;

5

6 end for

7$N=\lceil n\log(t)\rceil$;

8

9for  _each prime $q\in[N+1,(n+N)^{3}]$_ do

10 $c_{g}=1$;

11 for  _each $\overline{y}\in(\mathbb{F}_{q}^{*})^{k}$_ do

12 $prodx_{1}=1$;

13 for  _$i\in[k]$_ do

14 Compute $i^{th}$ smallest prime that divides $t$ and find $t_{i}$;

15 $prodx_{1}=prodx_{1}*y_{i}^{q-1-t_{i}}$;

16 Discard $t_{i}$;

17

18 end for

19

20 $f=1$;

21 for  _$i\in[n]$_ do

22 $prodx_{2}=1$;

23 for  _$j\in[k]$_ do

24 Compute $j^{th}$ smallest prime $p_{j}$ that divides $t$;

25 Using $p_{j}$ compute $e_{ij}$ which is the largest integer such that
$p_{j}^{e_{ij}}\,|\,a_{i}$;

26 $prodx_{2}=prodx_{2}*y_{j}^{e_{ij}}$;

27 Discard $p_{j}$ and $e_{ij}$;

28

29 end for

30 $f=f*(1+prodx_{2})$;

31

32 end for

33 $c_{g}=f*prodx_{1}$;

34

35 end for

36 if  _$c_{g}\neq 0$_ then

37 return True;

38

39 end if

40

41 end for

42

43return False;

44

Algorithm 3 Algorithm for solving $\mathsf{Subset~{}Product}$ using low space

##  7 An efficient reduction from $\mathsf{Subset~{}Product}$ to
$\mathsf{SimulSubsetSum}$

In this section, we will present a deterministic polynomial time reduction
from $\mathsf{Subset~{}Product}$ to $\mathsf{SimulSubsetSum}$. In section 5,
we have given a pseudo-polynomial time reduction from
$\mathsf{Subset~{}Product}$ to $\mathsf{SimulSubsetSum}$ by performing prime-
factorization of the input $(a_{1},\dots,a_{n},t)$. The polynomial time
reduction also requires to factorize the input, but the factors are not
necessarily prime. To be precise, we define pseudo-prime-factorization which
can be achieved in polynomial time.

######  Definition 3 (Pseudo-prime-factorization).

A set of integers $\mathcal{P}\subset\mathbb{N}$ is said to be pseudo-prime-
factor set of $(a_{1},\dots,a_{n})\in\mathbb{N}^{n}$ if

  1. 1.

the elements of $\mathcal{P}$ are pair-wise coprime, i.e., $\forall
p_{1},p_{2}\in\mathcal{P},gcd(p_{1},p_{2})=1$,

  2. 2.

there are only non-trivial factors of $a_{i}$’s in $\mathcal{P}$, i.e.,
$\forall p\in\mathcal{P},\exists i\in[n]$ such that $p\,|\,a_{i}$,

  3. 3.

every $a_{i}$’s can be uniquely expressed as product of powers of elements of
$\mathcal{P}$, i.e., $\forall
i\in[n],a_{i}=\prod_{p\in\mathcal{P}}p^{e_{p}},\forall i\in[n]$ where
$e_{p}\geq 0$.

For a given $(a_{1},\ldots,a_{n})$, $\mathcal{P}$ may not be unique. A trivial
example of a pseudo-prime-factor set of $\mathcal{P}$ for
$(a_{1},\dots,a_{n})$ is the set of all distinct prime factors of
$\prod_{i=1}^{n}a_{i}$. The following is an important claim which will be used
to give a polynomial time reduction from $\mathsf{Subset~{}Product}$ to
$\mathsf{SimulSubsetSum}$.

######  Claim 24.

For any pseudo-prime-factor set $\mathcal{P}$ of $(a_{1},\dots,a_{n})$, we
have $|\mathcal{P}|\leq k$ where $k$ is the number of distinct prime factors
of $\prod_{i=1}^{n}a_{i}$.

###### Proof.

The proof is using a simple pigeonhole principle argument. Let
$g_{1},\dots,g_{k}$ be the distinct prime factors of $\prod_{i=1}^{n}a_{i}$.
From the definition of $\mathcal{P}$, we know that $g_{1},\dots,g_{k}$ are the
only distinct prime factors of $\prod_{p\in\mathcal{P}}p$. Therefore, if there
are more than $k$ numbers in $\mathcal{P}$, then there must exist
$p_{1},p_{2}\in\mathcal{P}$ such that $gcd(p_{1},p_{2})\neq 1$ which violates
pair-wise coprime property of $\mathcal{P}$. ∎

$\blacktriangleright$ Constructing $\mathcal{P}$ suffices. We now show that
having a pseudo-prime-factor set $\mathcal{P}$ for $(a_{1},\dots,a_{n},t)$
helps us to reduce a $\mathsf{Subset~{}Product}$ instance
$(a_{1},\dots,a_{n},t)$ to $\mathsf{SimulSubsetSum}$ with number of instances
$|\mathcal{P}|$, in polynomial time. Wlog, we can assume that $a_{i}\,|\,t$
and $a_{i},t\leq 2^{m},\forall i\in[n]$ for some $m$. Trivially, $m\leq\log
t$. So, using 24, we have $|\mathcal{P}|\leq(n+1)\cdot m=\poly(n\log t)$.

From 3, we have unique non-negative integers $e_{ij}$ and $t_{j}$ such that
$t=\prod_{j\in|\mathcal{P}|}p_{j}^{t_{j}}$ and
$a_{i}=\prod_{j\in|\mathcal{P}|}p_{j}^{e_{ij}},\forall i\in[n]$. Since,
$a_{i}\,|\,t$, we have $e_{ij}\leq t_{j}\leq m,\forall
i\in[n],j\in[|\mathcal{P}|]$ and they can be computed in $\poly(m,n)$ time.

Let us consider the $|P|-\mathsf{SimulSubsetSum}$ instance where the $i^{th}$
$\mathsf{SSUM}$ instance is $(e_{1i},e_{2i},\dots,e_{ni},t_{i})$. Then, due to
unique factorization property of $\mathcal{P}$, the
$\mathsf{Subset~{}Product}$ instance is YES, i.e., $\exists S\in[n]$ such that
$\prod_{i\in S}a_{i}=t$ iff the $\mathsf{SimulSubsetSum}$ instance with number
of instances ${|\mathcal{P}|}$, is a YES.

###  7.1 Polynomial time algorithm for computing pseudo-prime-factors

We will now present a deterministic polynomial time algorithm for computing a
pseudo-prime-factor set $\mathcal{P}$ for $(a_{1},\dots,a_{n})$. We will use
the notation $\mathcal{P}(a_{1},\dots,a_{n})$ to denote a pseudo-prime-factor
set for $(a_{1},\dots,a_{n})$. Also, let $\mathcal{S}(a_{1},\ldots,a_{n})$ be
the set of all pseudo-prime-factor sets; this is a finite set.

The following lemma is a crucial component in algorithm 4. We use $a//b$ to
denote $a/b^{e}$ such that $b^{e+1}\nmid a$.

######  Lemma 25.

Let $(a_{1},\dots,a_{n})$ be $n$ integers. Then,

  1. 1.

If $a_{1}$ is coprime with $a_{i},\forall i>1$, then for any
$\mathcal{P}(a_{2},\dots,a_{n})\in\mathcal{S}(a_{2},\dots,a_{n})$,
$\mathcal{P}(a_{2},\dots,a_{n})\cup\\{a_{1}\\}\in\mathcal{S}(a_{1},\dots,a_{n})$.

  2. 2.

$\mathcal{P}(g,a_{1}//g,a_{2}//g,\dots,a_{n}//g)\in\mathcal{S}(a_{1},\ldots,a_{n})$,
for given $a_{i}$, $i\in[n]$ and any factor $g$ of some $a_{i}$.

###### Proof.

The first part of the lemma is trivial. For the second part, let $g$ be a non-
trivial factor of some $a_{i}$ and

$\mathcal{P}\;:=\;\\{p_{1},\dots,p_{k}\\}\;\in\;\mathcal{S}(g,a_{1}//g,a_{2}//g,\dots,a_{n}//g)\,,$

be any pseudo-prime-factor set. Then, $p_{i}$’s are pair-wise coprime and
since each $p_{i}$ divides either $g$ or $a_{i}//g$ for some $i\in[n]$, it
also divides some $a_{i}$ because $g$ is a factor of some $a_{i}$. Also, we
have unique non-negative integers $e_{ip},e_{gp}$ s.t.

$a_{i}//g=\prod_{p\in\mathcal{P}}p^{e_{ip}},\forall i\in[n]\text{ and
}g=\prod_{p\in\mathcal{P}}p^{e_{gp}}\;.$

Combining these equation, we get
$a_{i}=a_{i}//g*g^{f_{ig}}=\prod_{p\in\mathcal{P}}p^{e_{ip}+e_{gp}*f_{ig}}$.
Here $f_{ig}$ is the maximum power of $g$ that divides $a_{i}$. Therefore,
$\\{p_{1},\dots,p_{k}\\}$ is also a pseudo-prime-factor set for
$(a_{1},\dots,a_{n})$. ∎

##### Pre-processing.

Using 25, algorithm 4 performs a divide-and-conquer approach to find
$\mathcal{P}(a_{1},\dots,a_{n})$. Observe that we can always remove duplicate
elements and $1$’s from the input since it does not change the pseudo-prime-
factors. Also, we can assume without loss of generality that
$a_{i}//a_{1}=:a_{i},\forall i>1$ because of the second part in 25, with
$g=a_{1}$, since it gives us $\mathcal{P}(a_{1},a_{2}//g,\ldots,a_{n}//g)$ and
we know it suffices to work with these inputs.

If $a_{1}$ is coprime to the rest of the $a_{i}$’s, then the algorithm will
recursively call itself on $(a_{2},\dots,a_{n})$ and combine
$\mathcal{P}(a_{2},\dots,a_{n})$ with $\\{a_{1}\\}$. Else, there exist an
$i>1$ such that $gcd(a_{1},a_{i})\neq 1$. So, the algorithm finds a factor $g$
of $a_{1}$ using Euclid’s GCD algorithm and computes
$\mathcal{P}(g,a_{1}//g,\dots,a_{n}//g)$. At every step we remove duplicates
and $1$’s. Hence, the correctness of algorithm 4 is immediate assuming it
terminates.

To show the termination and time complexity of algorithm 4, we will use the
‘potential function’ $\mathbb{P}(I):=\prod_{a\in I}a$, where $I$ is the input
and show that at each recursive call, the value of the potential function is
halved. Initially, the value of the potential function is
$\prod_{i=1}^{n}a_{i}$. We also remark that since the algorithm removes
duplicates and $1$’s; the potential function can never increase by the removal
step and so it never matters in showing the decreasing nature of $\mathbb{P}$.

  1. 1.

$a_{1}$ is corpime to the rest of the $a_{i}$’s: In this case, the recursive
call has input $(a_{2},\dots,a_{n})$. Since, $a_{1}\geq 2$, the value of
potential function is

$\mathbb{P}(a_{2},\ldots,a_{n})\;=\;\prod_{i=2}^{n}a_{i}\;<\;(\prod_{i=1}^{n}a_{i})/2\;=\;\mathbb{P}(a_{1},\ldots,a_{n})/2\,.$

  2. 2.

$a_{1}$ shares a common factor with some $a_{i}$. Let $g=gcd(a_{1},a_{i})\neq
1$. Since, we have assumed $a_{i}//a_{1}=a_{i}$, this implies that $a_{i}$ is
not a multiple of $a_{1}$. This implies that $2\leq g\leq a_{1}/2$. Therefore,
the new value of potential function is

$\displaystyle\mathbb{P}(g,a_{1}//g,\ldots,a_{n}//g)\;$
$\displaystyle=\;g\prod_{j=1}^{n}a_{j}//g$
$\displaystyle\;\leq\;(a_{1}//g)\times\left((a_{i}//g)\times
g\right)\times\prod_{j\in[n]\setminus\\{1,i\\}}a_{j}$
$\displaystyle\;\leq\;\dfrac{a_{1}}{g}\cdot\prod_{j=2}^{n}a_{j}$
$\displaystyle\;\leq\;(\prod_{j=1}^{n}a_{j})/2\;=\;\mathbb{P}(a_{1},\dots,a_{n})/2\;.$

We used the fact that since, $2\leq g\,|\,a_{i}$, therefore,
$g\times(a_{i}//g)\leq a_{i}$.

##### Time complexity.

In both the cases, the value of the potential function is halved. So, the
depth of the recursion tree (in-fact, it is just a line) is at most
$\log(\prod_{i=1}^{n}a_{i})\leq m\cdot n$. Also, in each recursive call, the
input size is increased at most by one but the integers are still bounded by
$2^{m}$. This implies that input size, for any recurrence call, can be at most
$(m+1)\cdot n$. Since there is no branching, the total time complexity is
$\poly(m,n)=\poly(\log t,n)$.

Input: $(a_{1},a_{2}\dots,a_{n})\in\mathbb{N}^{n}$ which are $m$-bit integers
such that $a_{i}//a_{1}=a_{i}>1,\forall i>1$

Output: Pseudo-prime-factor set $\mathcal{P}$ for $(a_{1},a_{2},\dots,a_{n})$

1 if  _n == 0_ then

2 return $\emptyset$;

3

4 end if

5if  _$\exists i >1$ such that $gcd(a_{1},a_{i})\neq 1$_ then

6 $g=gcd(a_{1},a_{i})$;

7 $I=\\{g\\}$;

8 for  _$i\in[n]$_ do

9 $a_{i}^{\prime}=a_{i}//g$;

10 if  _$a_{i}^{\prime}\notin I$ and $a_{i}^{\prime}\neq 1$_ then

11 $I=I\cup\\{a_{i}^{\prime}\\}$

12 end if

13

14 end for

15 return $\mathcal{P}(I)$;

16

17 end if

18else

19 return $\mathcal{P}(a_{2},\dots,a_{n})\cup\\{a_{1}\\}$;

20

21 end if

Algorithm 4 Algorithm for Pseudo-prime-factor set

##  8 Extending Theorem 1 and 2 to Unbounded Subset Sum

In this section, we efficient algorithm for $\mathsf{UBSSUM}$. The
$\mathsf{UBSSUM}$ is an unbounded variant of $\mathsf{SSUM}$ problem, which is
also NP-hard [Joh85].

######  Definition 4 (Unbounded Subset Sum $(\mathsf{UBSSUM})$).

Given $(a_{1},\dots,a_{n},t)\in\mathbb{Z}_{\geq 0}^{n+1}$, the
$\mathsf{UBSSUM}$ problem asks whether there exists
$\beta_{1},\dots,\beta_{n}$ such that $\beta_{i}$ are non-negative integers
and $\sum_{i=1}^{n}\beta_{i}a_{i}=t$.

Similar to the $\mathsf{SSUM}$, the $\mathsf{UBSSUM}$ problem also has a
$O(nt)$ dynamic programming algorithm. Interestingly, this problem has a
$O(n+\min_{i}a_{i}^{2})$-time determinstic algorithm [HR96]. Recently,
Bringmann [Bri17] gave an $\tilde{O}(t)$ deterministic algorithm for
$\mathsf{UBSSUM}$. We now define two variants of the $\mathsf{UBSSUM}$ problem
which is very similar to $k-\mathsf{SSSUM}$ and
$\mathsf{Hamming}-k-\mathsf{SSSUM}$.

######  Problem 5 ($k-\mathsf{SUBSSUM}$).

Given $(a_{1},\dots,a_{n},t)\in\mathbb{Z}_{\geq 0}^{n+1}$, the
$k-\mathsf{SUBSSUM}$ problem asks to output all $(\beta_{1},\dots,\beta_{n})$
where $\beta_{i}$ are non-negative integers and
$\sum_{i=1}^{n}\beta_{i}a_{i}=t$ provided the number of such solutions is at
most $k$.

######  Problem 6 ($\mathsf{Hamming}-k-\mathsf{SUBSSUM}$).

Given a $k-\mathsf{SUBSSUM}$ instance
$(a_{1},\dots,a_{n},t)\in\mathbb{Z}_{\geq 0}^{n+1}$,
$\mathsf{Hamming}-k-\mathsf{SUBSSUM}$ asks to output all the hamming weights
of the solutions, i.e., $\sum_{i=1}^{n}\beta_{i}$.

######  Remarks 2.

We want $\vec{a}\cdot\vec{v}=t$, where $\vec{v}\in\mathbb{Z}_{\geq 0}^{n}$.
Similarly, like in the $\mathsf{SSUM}$ case (i.e., $\vec{v}\in\\{0,1\\}^{n}$),
we want $|v|_{1}$, which is exactly the quantity $\sum_{i}\beta_{i}$, as
above. Thus, this definition can be thought as a natural extension of the
hamming weight of the solution, in the unbounded regime.

We will present a deterministic polynomial time reduction from
$\mathsf{UBSSUM}$ to $\mathsf{SimulSubsetSum}$ which will be used latter in
this section.

######  Theorem 26 ($\mathsf{UBSSUM}$ reduces to $\mathsf{SimulSubsetSum}$).

There exists a deterministic polynomial time reduction from $\mathsf{UBSSUM}$
to $\mathsf{SimulSubsetSum}$.

###### Proof.

Let $(a_{1},\dots,a_{n},t)\in\mathbb{Z}_{\geq 0}^{n+1}$ be an instance of
$\mathsf{UBSSUM}$. The reduction generates the following $\mathsf{SSUM}$
instance
$(\underbrace{a_{1},2a_{1},4a_{1},\dots,2^{\gamma}a_{1}}_{\gamma+1~{}\text{entries}},\underbrace{a_{2},2a_{2},\dots,2^{\gamma}a_{2}}_{\gamma+1~{}\text{entries}},\dots,\underbrace{a_{n},2a_{n},\dots,2^{\gamma}a_{n}}_{\gamma+1~{}\text{entries}},t)$
of size $n(\gamma+1)$ where $\gamma=\lfloor\log(t)\rfloor$.

Let $(\beta_{1},\dots,\beta_{n})$ be a solution to the $\mathsf{UBSSUM}$
instance, i.e., $\sum_{i=1}^{n}\beta_{i}a_{i}=t$. Since, $\beta_{i},a_{i},t$
are all non-negative integers, we have $\beta_{i}\leq t,\forall i\in[n]$.
Therefore, $\beta$ is at most $(\gamma+1)$-bit integer. Let $\beta_{i}^{(j)}$
be the $j^{th}$ bit of $\beta_{i}$, then we have

$t=\sum_{i=1}^{n}\beta_{i}a_{i}=\sum_{i=1}^{n}\left(\sum_{j=0}^{\gamma}\beta_{i}^{(j)}2^{j}\right)\cdot
a_{i}=\sum_{i=1}^{n}\sum_{j=0}^{\gamma}\beta_{i}^{(j)}\cdot(2^{j}a_{i})$

which implies that the $\mathsf{SSUM}$ instance also has a solution.
Similarly, we can show the reverse direction, i.e., if $\mathsf{SSUM}$
instance has a solution, then $\mathsf{UBSSUM}$ is also has a solution. This
concludes the proof. ∎

$\blacktriangleright$ Remark. Observe that in Theorem 26, there is a one-to-
one correspondence between the solutions of the $\mathsf{UBSSUM}$ and the
solutions of the $\mathsf{SimulSubsetSum}$ instance. Therefore, the reduction
preserves the number of solutions. Also, any $T(n,t)$ time algorithm that
solve $\mathsf{SSUM}$ gives an $T(n\log(t),t)$-time algorithm to solve
$\mathsf{UBSSUM}$.

We will now show that the Theorem 1-3 can be extended to, in the
$\mathsf{UBSSUM}$ regime.

######  Theorem 27.

There is an $\tilde{O}(k(n+t))$-time deterministic algorithm for
$\mathsf{Hamming}-k-\mathsf{SUBSSUM}$.

Proof sketch. The algorithm is almost similar to algorithm 1, except the
definitions of the polynomials $f_{j}(x)$. Here also, we fix $q$ and $\mu$
similarly. We require the exact number of solutions $m(m\leq k)$ in subsection
4.1 (see 17). To do that, define the polynomial $f_{0}$:

$\displaystyle
f_{0}(x)\;:=\;\prod_{i=1}^{n}\,\left(\dfrac{1}{1-x^{a_{j}}}\right)\,=\,\left(\prod_{i=1}^{n}\,\left(1-x^{a_{i}}\right)\right)^{-1}\,$
$\displaystyle=\,\left(\prod_{i=1}^{n}\,\left(1+x^{a_{i}}+x^{2a_{i}}+\ldots\right)\right)$
$\displaystyle=:\,(h_{0}(x))^{-1}\;.$

In the above, we used the inverse identity $1/(1-x)\,=\,\sum_{i\geq
0}\,x^{i}$. Expanding the above, is easy to see that
$\textup{{coef}}_{x^{t}}(f_{0}(x))=m$, where $m$ is the exact number of
solutions to the $k-\mathsf{SUBSSUM}$. Note that, we can compute
$f_{0}^{-1}=h_{0}(x)\bmod x^{t+1}$, over $\mathbb{F}_{q}$ efficiently in
$\tilde{O}(k+t)$ time. Finding inverse is easy and can be done efficiently
(see [VZGG13, Theorem 9.4]).

Once, we know $m$, we define $m$ many polynomials $f_{j}$, for $j\in[m]$, as
follows.

$f_{j}(x)\;:=\;\prod_{i=1}^{n}\,\left(\dfrac{1}{1-\mu^{j}x^{a_{j}}}\right)\,=\,\left(\prod_{i=1}^{n}\,\left(1-\mu^{j}x^{a_{i}}\right)\right)^{-1}\,=:\,(h_{j}(x))^{-1}$

It is not hard to observe that
$\textup{{coef}}_{x^{t}}(f_{j}(x))=\sum_{i\in[\ell]}\lambda_{i}\cdot\mu^{jw_{i}}$,
where $w_{1},\ldots,w_{\ell}$ are the distinct hamming weights with
multiplicities $\lambda_{1},\ldots,\lambda_{\ell}$ (similar to 1). To find the
coefficients of $f_{j}(x)$, we first compute the coefficients of $h_{j}(x)$,
using 30, in $\tilde{O}(k(n+t))$ time and find its inverses, using [VZGG13,
Theorem 9.4], which can again be done in $\tilde{O}(k(n+t))$ time. Once we
have computed the coefficients of $f_{j}(x)$, the rest proceeds same as
subsection 4.1.

######  Theorem 28.

There is a $\poly(knt)$-time and $O(\log(knt))$-space deterministic algorithm
which solves $k-\mathsf{SUBSSUM}$.

Proof idea. The algorithm first reduces $\mathsf{UBSSUM}$ to $\mathsf{SSUM}$
using Theorem 26 which preserves the number of solutions but the size of the
$\mathsf{SSUM}$ instance is now $n\log t$. Then, it runs algorithm 2 on the
$\mathsf{SSUM}$ instance to find all its solutions. From the solutions of the
$\mathsf{SSUM}$ instance, it constructs all the solutions of the
$\mathsf{UBSSUM}$ instance. This gives $\poly(knt)$-time and $O(\log(knt\log
t))=O(\log(knt))$-space algorithm.

##  9 Conclusion

This work introduces some interesting search versions of variants of
$\mathsf{SSUM}$ problem and gives efficient algorithms for each of them. This
opens a variety of questions which require further rigorous investigations.

  1. 1.

Can we improve the time complexity of the algorithm 2? Because of using
Theorem 21, the complexity for interpolation is already cubic. Whether some
other algebraic (non-algebraic) techniques can improve the time complexity,
while keeping it low space, is not at all clear.

  2. 2.

Can we use these algebraic-number-theoretic techniques, to give a
deterministic $\tilde{O}(n+t)$ algorithm for decision version of
$\mathsf{SSUM}$?

  3. 3.

Can we improve subsection 4.1 to find both the hamming weights $w_{i}$ as well
as the multiplicities $\lambda_{i}$, in $\tilde{O}(k(n+t))$?

  4. 4.

Can we improve the complexity of Theorem 19 to
$\tilde{O}(kn+\prod_{i=1}^{k}t_{i})$? Note that we cannot avoid the $kn$ term
in the time complexity because the number of bits in a
$\mathsf{SimulSubsetSum}$ instance is at least $kn$.

  5. 5.

What can we say about the hardness of $\mathsf{SimulSubsetSum}$ with $k$
subset sum instances where $k=\omega(\log(n))$?

  6. 6.

Set Cover Conjecture (SeCoCo) [CDL+16] states that given $n$ elements and $m$
sets and for any $\epsilon>0$, there is a $k$ such that Set Cover with sets of
size at most $k$ cannot be computed in time $2^{(1-\epsilon)n}\cdot\poly(m)$
time. Can we show that SeCoCo implies there is no $t^{1-\epsilon}\poly(n)$
time solution to $\mathsf{Subset~{}Product}$?

Acknowledgement. PD thanks Department of CSE, IIT Kanpur for the hospitality,
and acknowledges the support of Google Ph. D. Fellowship. MSR acknowledges the
support of Prime Minister’s Research Fellowship. The authors would like to
thank Dr. Santanu Sarkar (Dept. of Mathematics, IIT Madras) for introducing us
to various algorithms for subset sum. The authors would also like to thank the
anonymous reviewers for the suggestions to improve some parts of the
presentation.

## References

  * [ABHS19] Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay.  Seth-based lower bounds for subset sum and bicriteria path.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 41–57. SIAM, 2019.
  * [AKS04] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena.  Primes is in p.  Annals of mathematics, pages 781–793, 2004.
  * [Bel57] Richard E. Bellman.  Dynamic programming, 1957.
  * [BHV09] Cristina Bazgan, Hadrien Hugot, and Daniel Vanderpooten.  Solving efficiently the 0–1 multi-objective knapsack problem.  Computers & Operations Research, 36(1):260–279, 2009.
  * [BJLM13] Daniel J Bernstein, Stacey Jeffery, Tanja Lange, and Alexander Meurer.  Quantum algorithms for the subset-sum problem.  In International Workshop on Post-Quantum Cryptography, pages 16–33. Springer, 2013.
  * [BKS15] Jean Bourgain, Sergei Konyagin, and Igor Shparlinski.  Character sums and deterministic polynomial root finding in finite fields.  Mathematics of Computation, 84(296):2969–2977, 2015.
  * [Bre76] Richard P Brent.  Multiple-precision zero-finding methods and the complexity of elementary function evaluation.  In Analytic computational complexity, pages 151–176. Elsevier, 1976\.
  * [Bri17] Karl Bringmann.  A near-linear pseudopolynomial time algorithm for subset sum.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1073–1084. SIAM, 2017.
  * [BW21] Karl Bringmann and Philip Wellnitz.  On near-linear-time algorithms for dense subset sum.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1777–1796. SIAM, 2021.
  * [CDL+16] Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström.  On problems as hard as cnf-sat.  ACM Transactions on Algorithms (TALG), 12(3):1–24, 2016.
  * [CLRS09] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  Introduction to algorithms.  MIT press, 2009.
  * [CLS06] Scott Contini, Arjen K Lenstra, and Ron Steinfeld.  Vsh, an efficient and provable collision-resistant hash function.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 165–182. Springer, 2006.
  * [DMT20] Konstantinos A Draziotis, V Martidis, and S Tiganourias.  Product subset problem: Applications to number theory and cryptography.  arXiv preprint arXiv:2002.07095, 2020.
  * [EJT10] Michael Elberfeld, Andreas Jakoby, and Till Tantau.  Logspace versions of the theorems of bodlaender and courcelle.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 143–152. IEEE, 2010.
  * [EM20] Andre Esser and Alexander May.  Low weight discrete logarithm and subset sum in 20. 65n with polynomial memory.  memory, 1:2, 2020.
  * [FMV16] Sebastian Faust, Daniel Masny, and Daniele Venturi.  Chosen-ciphertext security from subset sum.  In Public-Key Cryptography–PKC 2016, pages 35–46. Springer, 2016\.
  * [GJ79] Michael R Garey and David S Johnson.  Computers and intractability, volume 174.  freeman San Francisco, 1979.
  * [HM18] Alexander Helm and Alexander May.  Subset sum quantumly in 1.17^ n.  In 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [HR96] Paul Hansen and Jennifer Ryan.  Testing integer knapsacks for feasibility.  European journal of operational research, 88(3):578–582, 1996.
  * [Joh85] David S Johnson.  The np-completeness column: an ongoing guide.  Journal of Algorithms, 6(3):434–451, 1985.
  * [JVW21] Ce Jin, Nikhil Vyas, and Ryan Williams.  Fast low-space algorithms for subset sum.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1757–1776. SIAM, 2021.
  * [JW18] Ce Jin and Hongxun Wu.  A simple near-linear pseudopolynomial time randomized algorithm for subset sum.  arXiv preprint arXiv:1807.11597, 2018.
  * [Kan10] Daniel M Kane.  Unary subset-sum is in logspace.  arXiv preprint arXiv:1012.1336, 2010.
  * [KP10] Mikhail Y Kovalyov and Erwin Pesch.  A generic approach to proving np-hardness of partition type problems.  Discrete applied mathematics, 158(17):1908–1912, 2010.
  * [KS01] Adam R Klivans and Daniel Spielman.  Randomness efficient identity testing of multivariate polynomials.  In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 216–223, 2001.
  * [KX18] Konstantinos Koiliaris and Chao Xu.  Subset sum made simple.  arXiv preprint arXiv:1807.08248, 2018.
  * [KX19] Konstantinos Koiliaris and Chao Xu.  Faster pseudopolynomial time algorithms for subset sum.  ACM Transactions on Algorithms (TALG), 15(3):1–20, 2019.
  * [Lew83] Harry R Lewis.  Computers and intractability. a guide to the theory of np-completeness, 1983.
  * [LL19] Yang Li and Hongbo Li.  Improved quantum algorithm for the random subset sum problem.  arXiv preprint arXiv:1912.09264, 2019.
  * [LP92] Hendrik W Lenstra and Carl Pomerance.  A rigorous time bound for factoring integers.  Journal of the American Mathematical Society, 5(3):483–516, 1992\.
  * [LPS10] Vadim Lyubashevsky, Adriana Palacio, and Gil Segev.  Public-key cryptographic primitives provably as secure as subset sum.  In Theory of Cryptography Conference, pages 382–400. Springer, 2010\.
  * [MT98] Alexis Maciel and Denis Therien.  Threshold circuits of small majority-depth.  Information and Computation, 146(1):55–83, 1998.
  * [MVV87] Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani.  Matching is as easy as matrix inversion.  In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 345–354, 1987.
  * [MW18] Dylan M McKay and Richard Ryan Williams.  Quadratic time-space lower bounds for computing natural functions with a random oracle.  In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [Nag52] Jitsuro Nagura.  On the interval containing at least one prime number.  Proceedings of the Japan Academy, 28(4):177–181, 1952.
  * [Pis99] David Pisinger.  Linear time algorithms for knapsack problems with bounded weights.  Journal of Algorithms, 33(1):1–14, 1999.
  * [PST21] Ulrich Pferschy, Joachim Schauer, and Clemens Thielen.  Approximating the product knapsack problem.  Optimization Letters, pages 1–12, 2021.
  * [Sho90] Victor Shoup.  On the deterministic complexity of factoring polynomials over finite fields.  Information Processing Letters, 33(5):261–267, 1990.
  * [Shp96] Igor Shparlinski.  On finding primitive roots in finite fields.  Theoretical computer science, 157(2):273–275, 1996.
  * [VZGG13] Joachim Von Zur Gathen and Jürgen Gerhard.  Modern computer algebra.  Cambridge university press, 2013.

##  Appendix A Generalizing Jin and Wu’s technique [JW18] to different
settings

###  A.1 Revisiting [JW18] with weighted coefficient

In [JW18, Lemma 5], Jin and Wu established the main lemma which shows that one
can compute

$A(x)\;:\equiv\;\prod_{i\in[n]}\,(1+x^{a_{i}})\,\bmod\,\langle
x^{t+1},p\rangle\;,\text{for any prime}\,p\,\in\,[t+1,(n+t)^{3}]\,,$

in $\tilde{O}(t)$ time. Further, choosing a random $p$, one can decide
nonzeroness of $\textup{{coef}}_{x^{t}}(A(x))$, with high probability. In this
paper, we will work with a more general polynomial

$G(x)\;:\equiv\;\prod_{i\in[n]}\,(1+W^{b}\cdot x^{a_{i}})\,\bmod\,\langle
x^{t+1},p\rangle\;,$

for some integer $W$, not necessarily $1$ and $b\in\mathbb{Z}_{\geq 0}$.
Therefore, the details slightly differ. For the completeness, we give the
details. But before going into the details, we define some basics of power
series and expansion of $\exp$ (respectively $\ln$), which will be crucially
used in the proof of 30. In general, we will be working with primes $p$ such
that $\log(p)=O(\log(n+t))$, thus $\log(p)$ terms in the complexity can be
subsumed in $\tilde{O}$ notation.

Basic Power series tools. We denote $\mathbb{F}[x]$ as the ring of polynomials
over a field $\mathbb{F}$, and $\mathbb{F}[[x]]$ denote the ring of formal
power series over $\mathbb{F}$ which has elements of the form $\sum_{i\geq
0}a_{i}x^{i}$, for $a_{i}\in\mathbb{F}$. Two important power series over
$\mathbb{Q}[[x]]$ are:

$\ln(1+x)\;=\;\sum_{k\geq
1}\,\frac{(-1)^{k-1}x^{k}}{k}\,,\;\;\text{and}\;\;\exp(x)\;=\;\sum_{k\geq
0}\,\frac{x^{k}}{k!}\;.$

They are inverse to each other and satisfy the basic properties:

$\exp\left(\ln\left(1+f(x)\right)\right)=1+f(x),\;\;\text{and}\;\;\ln\left((1+f(x))\cdot(1+g(x))\right)=\ln(1+f(x))+\ln(1+g(x))\;,$

for every $f(x),g(x)\in x\mathbb{Q}[x]$ (i.e., constant term is $0$). Here is
an important lemma to compute $\exp(f(x))\bmod x^{t+1}$; for details see
[Bre76]; for an alternative proof, see [JW18, Lemma 2].

######  Lemma 29 ([Bre76]).

Given a polynomial $f(x)\in x\mathbb{F}[x]$ of degree at most $t(t<p)$, one
can compute a polynomial $g(x)\in\mathbb{F}_{p}[x]$ in $\tilde{O}(t)$ time
such that $g(x)\equiv\exp(f(x))~{}\bmod~{}\langle x^{t+1},p\rangle$.

Here is the most important lemma, which is an extension of [JW18, Lemma 4],
where the authors considered the simplest form. In this paper, we need the
extensions for the ‘robust’ usage of this lemma (in subsection 4.1).

######  Lemma 30 (Coefficient Extraction Lemma).

Let $A(x)=\prod_{i\in[n]}(1+W^{b}\cdot x^{a_{i}})$, for any non-negative
integers $a_{i},b$ and $W\in\mathbb{Z}$. Then, for a prime $p>t$, one can
compute $\textup{{coef}}_{x^{r}}(A(x))\,\bmod\,p$ for all $0\leq r\leq t$, in
time $\tilde{O}((n+t\log(Wb)))$.

###### Proof.

Let us define $B(x):=\ln(A(x))\in\mathbb{Q}[[x]]$. By definition,

$B(x)\,=\,\ln\left(\prod_{i\in[n]}\,\left(1+W^{b}\cdot
x^{a_{i}}\right)\right)\,=\,\sum_{i\in[n]}\,\ln\left(1+W^{b}\cdot
x^{a_{i}}\right)\,=\,\sum_{i\in[n]}\sum_{j=1}^{\infty}\,\frac{(-1)^{j-1}}{j}\cdot
W^{jb}\cdot x^{a_{i}j}\;.$

Let $B_{t}(x):=B(x)\bmod\langle x^{t+1},p\rangle$. Define $S_{k}:=\\{i\mid
a_{i}=k\\}$. Moreover, let us define

$d_{k,j}:=\begin{cases}\sum_{i\in
S_{k}}W^{jb},&\;\text{if}\;S_{k}\,\neq\,\phi\,,\\\
0,&\text{otherwise}\,.\end{cases}$

Then, rewriting the above expression, we get

$B_{t}(x)\,\equiv\,\sum_{i\in[n]}\sum_{j=1}^{\lfloor
t/a_{i}\rfloor}\,\frac{(-1)^{j-1}}{j}\cdot W^{jb}\cdot
x^{a_{i}j}\,\equiv\,\sum_{k\in[t]}\sum_{j=1}^{\lfloor
t/k\rfloor}\,\frac{(-1)^{j-1}\cdot d_{k,j}}{j}\cdot x^{jk}~{}~{}\bmod~{}p\;.$

Since $p>t$, $j^{-1}\bmod p$ exists, for $j\in[t]$. So we pre-compute all
$j^{-1}\bmod p$, which takes total $\tilde{O}(t)$ time. Further, we can pre-
compute $|S_{k}|,\,\forall\,k\in[t]$ in $\tilde{O}((n+t))$ time, just by a
linear scan.

Moreover, computing each $d_{k,j}=|S_{k}|\cdot W^{jb}$, takes
$\tilde{O}(\log(Wbt))$ time, since $j\leq t$ (assuming we have computed
$|S_{k}|$). Thus, the total time complexity to compute coefficients of
$B_{t}(x)$ is

$\tilde{O}((n+t))+\tilde{O}(t)+\sum_{k\in[t]}\sum_{j\in\lfloor
t/k\rfloor}\,\tilde{O}(\log(Wbt)\cdot)\,=\,\tilde{O}((n+t\log(Wb)))\,.$

In the last, we use that $\sum_{k=1}^{\lfloor t/k\rfloor}1=O(t\log t)$, which
gives the sum to be $\tilde{O}((n+t\log(Wb)))$ ($\log t$ is absorbed inside
the $\tilde{O}$).

The last step is to compute $A(x)\equiv\exp(B_{t}(x))\bmod\langle
x^{t+1},p\rangle$. Since one can compute $B_{t}(x)$ in time
$\tilde{O}((n+t\log(Wb)))$, using 29, one concludes to compute the
coefficients of $x^{r}$ of $A(x)$, $0\leq r\leq t$, over $\mathbb{F}_{p}$ in
similar time of $\tilde{O}((n+t\log(Wb)))$. ∎

$\blacktriangleright$ Remark. When $|W|=1$, it is exactly [JW18, Lemma 5]. One
can also work with $A(x)=\prod_{i\in[n]}(1-W^{b}\cdot x^{a_{i}})$; the
negative sign does not matter since we can use $\ln(1-x)=-\sum_{i\geq
1}\,-x^{i}/i$ and the proof goes through.

###  A.2 Fast multivariate polynomial multiplication

In this section, we will study the time required to compute

$A(x_{1},\dots,x_{k})\;:\equiv\;\prod_{i=1}^{n}\,\left(1+\prod_{j=1}^{k}x_{j}^{a_{ij}}\right)\,\bmod\,\langle
x_{1}^{t_{1}+1},x_{2}^{t_{2}+1},\dots,x_{k}^{t_{k}+1},p\rangle$

for some prime $p$. The case when $k=1$ has been studied in [JW18, Lemma 5]
where the authors gave an $\tilde{O}(n+t_{1})$ time algorithm for
$p\in[t_{1}+1,(n+t_{1})^{3}]$. Here we will present the generalisation of this
lemma which is used in Theorem 19 using multivariate FFT.

######  Lemma 31 (Fast multivariate exponentiation).

Let ${\boldsymbol{x}}=(x_{1},\ldots,x_{k})$ and
$f({\boldsymbol{x}})=\sum_{i=1}^{t_{1}}f_{i}({\boldsymbol{x}})\cdot
x_{1}^{i}\in\mathbb{F}_{p}[{\boldsymbol{x}}]$ where
$f_{i}({\boldsymbol{x}})\in\mathbb{F}_{p}[x_{2},\dots,x_{k}]$ such that

  1. 1.

$f({\boldsymbol{x}})~{}\bmod~{}\langle x_{1},\ldots,x_{k}\rangle=0$, i.e., the
constant term of $f({\boldsymbol{x}})$ is $0$, and,

  2. 2.

$\deg_{x_{j}}(f)=t_{j}$, for positive integers $t_{j}$.

Then, there is an $\tilde{O}(\prod_{i=1}^{k}(2t_{i}+1))$ time deterministic
algorithm that computes a polynomial
$g({\boldsymbol{x}})\in\mathbb{F}_{p}[{\boldsymbol{x}}]$ such that
$g({\boldsymbol{x}})\equiv\exp(f({\boldsymbol{x}}))\,\bmod\,\langle
x_{1}^{t_{1}+1},\dots,x_{k}^{t_{k}+1}\rangle$ over $\mathbb{F}_{p}$.

###### Proof.

Let
$g({\boldsymbol{x}})=\exp(f({\boldsymbol{x}}))=\sum_{i=0}^{\infty}g_{i}(x_{2},\dots,x_{k})\cdot
x_{1}^{i}$, where $g_{i}\in\mathbb{F}_{p}[[x_{2},\ldots,x_{k}]]$.
Differentiate wrt $x_{1}$ to get:

$g^{\prime}({\boldsymbol{x}})\;:=\;\dfrac{\partial
g({\boldsymbol{x}})}{\partial
x_{1}}\;=\;g({\boldsymbol{x}})\cdot\dfrac{\partial
f({\boldsymbol{x}})}{\partial x_{1}}\;.$

By comparing the coefficients of $x_{1}^{i}$ on both sides, we get (over
$\mathbb{F}_{p}$):

$g_{i}\;\equiv\;i^{-1}\cdot\sum_{j=0}^{i-1}f_{i-j}\cdot
g_{j}\;~{}\bmod~{}\langle x_{2}^{t_{2}+1},\ldots,x_{k}^{t_{k}+1}\rangle\,,$

∎

where $g_{0}=1$. By initializing $g_{0}=1$, the rest $g_{i}$ to 0 and calling
$Compute(0,t_{1})$ procedure in algorithm 5, we can compute all the
coefficients up to $x_{1}^{t_{1}}$, in the polynomial
$g({\boldsymbol{x}})~{}\bmod~{}\langle
x_{2}^{t_{2}+1},\ldots,x_{k}^{t_{k}+1}\rangle$, over $\mathbb{F}_{p}$.

Input: integers $\ell,r$ and polynomials $f_{i},g_{i}$

Output: Updated values of $g_{i}$

1

2if  _$\ell <r$_ then

3 $m=\lfloor(\ell+r)/2\rfloor$;

4 $Compute(\ell,m)$;

5 for  _$i\in\\{m+1,\dots,r\\}$_ do

6 $g_{i}=g_{i}+i^{-1}\sum_{j=\ell}^{m}(i-j)f_{i-j}g_{j}\,\mod\,\langle
x_{2}^{t_{2}+1},x_{3}^{t_{3}+1},\dots,x_{k}^{t_{k}+1},p\rangle$;

7

8 end for

9 $Compute(m+1,r)$;

10

11 end if

12return $g_{\ell},\dots,g_{r}$;

Algorithm 5 Algorithm for $Compute(\ell,r)$

To speed up this algorithm, we can set
$A({\boldsymbol{x}})=\sum_{i=0}^{r-\ell}if_{i}x_{1}^{i}$ and
$B({\boldsymbol{x}})=\sum_{i=0}^{m-\ell}g_{i+\ell}x_{1}^{i}$; here the $f_{i}$
and $g_{i+\ell}$ have been computed modulo $\langle
x_{2}^{t_{2}+1},\ldots,x_{k}^{t_{k}+1}\rangle$ already. Use multidimensional
FFT [CLRS09, Chapter 30] to compute
$C({\boldsymbol{x}})=A({\boldsymbol{x}})B({\boldsymbol{x}})$ to speed up the
for loop which takes
$O(\prod_{i=1}^{k}(2t_{i}+1)\log(\prod_{i=1}^{k}(2t_{i}+1)))$ time.

Observe that $\sum_{j=\ell}^{m}(i-j)f_{i-j}g_{j}$ is the coefficient of
$x_{1}^{i-\ell}$ in $C({\boldsymbol{x}})$; importantly $\deg_{x_{i}}(C)\leq
2t_{i}$, for $i\geq 2$. The extraction of the coefficient of $x_{1}^{i}$ in
$C({\boldsymbol{x}})$ for all $i$, $\bmod~{}\langle
x_{2}^{t_{2}+1},x_{3}^{t_{3}+1},\dots,x_{k}^{t_{k}+1}\rangle$ can be performed
in $O(\prod_{i=1}^{k}(2t_{i}+1))$ time. This is done by traversing through the
polynomial and collecting coefficient along with monomials having the same
$x_{1}^{i}$ term (and there can be at most $\prod_{i=2}^{k}(2t_{i}+1)$ many
terms). Thus, the total time complexity of computing
$g({\boldsymbol{x}})\bmod~{}\langle
x_{2}^{t_{2}+1},x_{3}^{t_{3}+1},\dots,x_{k}^{t_{k}+1}\rangle$ is

$T(t_{1},t_{2},\dots,t_{k})\;=\;2T(t_{1}/2,t_{2},\dots,t_{k})\,+\,\tilde{O}(\prod_{i=1}^{k}(2t_{i}+1))\;=\;\tilde{O}(\prod_{i=1}^{k}(2t_{i}+1))\;,$

as desired.

######  Lemma 32 (Fast logarithm computation).

Let
$A({\boldsymbol{x}})\,=\,\prod_{i=1}^{n}\,\left(1+\prod_{j=1}^{k}x_{j}^{a_{ij}}\right)$.
Then, there exists an $\tilde{O}(kn+\prod_{i=1}^{k}t_{i})$ time deterministic
algorithm that computes
$\textup{{coef}}_{{\boldsymbol{x}}^{{\boldsymbol{e}}}}(\ln(A({\boldsymbol{x}})))\,\mod\,p$
for all ${\boldsymbol{e}}$, such that ${\boldsymbol{e}}=(e_{1},\ldots,e_{k})$
with $e_{i}\leq t_{i}$.

###### Proof.

Let us define $B({\boldsymbol{x}})\,:=\,\ln(A({\boldsymbol{x}}))$. Then,

$\displaystyle B({\boldsymbol{x}})$
$\displaystyle=\ln\left(\prod_{i=1}^{n}\,(1+\prod_{j=1}^{k}x_{j}^{a_{ij}})\right)$
$\displaystyle=\sum_{i=1}^{n}\,\ln\left(1+\prod_{j=1}^{k}x_{j}^{a_{ij}}\right)$
$\displaystyle=\sum_{i=1}^{n}\sum_{\ell=1}^{\infty}\left(\dfrac{(-1)^{\ell-1}}{\ell}(\prod_{j=1}^{k}x_{j}^{a_{ij}})^{\ell}\right)\;.$

Without loss of generality, we can assume that $t_{1}\leq t_{i},\forall i>1$.
Let $C({\boldsymbol{x}})\,:=B({\boldsymbol{x}})\,\mod\,\langle
x_{1}^{t_{1}+1},\dots,x_{k}^{t_{k}+1},p\rangle$. Since, we are interested
where the individual degree of $x_{j}$ can be at most $t_{j}$, the index
$\ell$ in the above equation (for a fixed $i$) must satisfy
$a_{ij}\cdot\ell\leq t_{j}$ for each $j\in[k]$. This implies $\ell\leq
t_{j}/a_{ij}$, for $j\in[k]$. Therefore, define $M_{i}:=min_{j=1}^{k}\lfloor
t_{j}/a_{ij}\rfloor$. Now, one can express $C({\boldsymbol{x}})$ using $M_{i}$
since it suffices to look the index $\ell$ till $M_{i}$ (for a fixed $i$), as
argued before.

Importantly, note that the above equation involves
$\prod_{j=1}^{k}x_{j}^{a_{ij}\ell}$ which has individual degree $>0$, since
both $a_{ij},\ell\geq 1$. Thus, define
$T:=\\{{\boldsymbol{e}}=(e_{1},\ldots,e_{k})\in\mathbb{Z}^{k}\,|\,1\leq
e_{i}\leq t_{i},\forall i\in[k]\\}$. Then,

$\displaystyle C({\boldsymbol{x}})\;$
$\displaystyle=\;\sum_{i=1}^{n}\sum_{\ell=1}^{M_{i}}\left(\dfrac{(-1)^{\ell-1}}{\ell}(\prod_{j=1}^{k}x_{j}^{a_{ij}})^{\ell}\right)$
$\displaystyle=\;\sum_{\overline{e}\in
T}\sum_{\ell=1}^{t_{1}/e_{1}}\left(\dfrac{s_{\overline{e}}\times(-1)^{\ell-1}}{\ell}\prod_{j=1}^{k}x_{j}^{e_{i}\ell}\right)\;,$

where
$s_{\overline{e}}=|\,\\{i\in[n]\,|\,(a_{i1},\dots,a_{ik})=\overline{e}\\}\,|$.
Essentially, for a given $s_{{\boldsymbol{e}}}$, the quantity computes how
many times $a_{ij}$ is equal to $e_{j}$, for all $j\in[k]$. Using
$s_{{\boldsymbol{e}}}$, we can interchange the order of the summation as shown
above. Moreover, we can pre-compute $s_{{\boldsymbol{e}}}$, for all
${\boldsymbol{e}}\in T$ in time $O\left(kn+\prod_{i=1}^{k}t_{i}\right)$.

Observe that
$\textup{{coef}}_{{\boldsymbol{x}}^{{\boldsymbol{e}}}}(B({\boldsymbol{x}}))=\textup{{coef}}_{{\boldsymbol{x}}^{{\boldsymbol{e}}}}(C({\boldsymbol{x}}))$,
for any $(e_{1},\dots,e_{k})\in T$. Since, $\ell\leq t_{1}<p$, $\ell^{-1}$
exists and can be pre-computed in $\tilde{O}(t_{1})$.

##### Time complexity.

Observe that we have

$\displaystyle C({\boldsymbol{x}})\;$ $\displaystyle=\;\sum_{\overline{e}\in
T}\sum_{\ell=1}^{t_{1}/e_{1}}\left(\dfrac{s_{\overline{e}}\times(-1)^{\ell-1}}{\ell}\prod_{j=1}^{k}x_{j}^{e_{i}\ell}\right)$
$\displaystyle=\;\sum_{e_{2}=1}^{t_{2}}\sum_{e_{3}=1}^{t_{3}}\dots\sum_{e_{k}=1}^{t_{k}}\left(\sum_{e_{1}=1}^{t_{1}}\sum_{\ell=1}^{t_{1}/e_{1}}\left(\dfrac{s_{\overline{e}}\times(-1)^{\ell-1}}{\ell}\prod_{j=1}^{k}x_{j}^{e_{i}\ell}\right)\right)$

The time taken to compute all
$\textup{{coef}}_{{\boldsymbol{x}}^{{\boldsymbol{e}}}}(C({\boldsymbol{x}}))$,
given $s_{{\boldsymbol{e}}}$, is the number of iterations over all
$(e_{2},\ldots,e_{k})$, for $1\leq e_{i}\leq t_{i}$, $i>1$ and
$\ell\in[t/e_{1}]$, which is atmost $\sum_{j=1}^{t_{1}}\lfloor
t_{1}/j\rfloor\times\prod_{i=2}^{k}t_{i}=\tilde{O}(\prod_{i=1}^{k}t_{i})$,
since $\sum_{j=1}^{t_{1}}t_{1}/j=O(t_{1}\log t_{1})$. Thus, the total time is
$\tilde{O}(kn+\prod_{i=1}^{k}t_{i})$. ∎

###  A.3 Solving linear recurrence: Tool for subsection 4.1

In this section, we briefly sketch how to speed up the algorithm of computing
$E_{i}$, for $i\in[m]$, using FFT, rather than just going through one by one.
Equation 1 gives the following relation:

$E_{j}\equiv j^{-1}\cdot\left(\sum_{i\in[j]}\,(-1)^{j-i-1}E_{i}\cdot
P_{j-i}\right)~{}\bmod~{}q\;.$

Here, by $E_{j}$ (respectively $P_{j}$), we mean
$E_{j}(\mu^{w_{1}},\ldots,\mu^{w_{\ell}})$ (respectively $P_{j}$). We can
assume that $P_{j}$’s are already pre-computed and hence contributes to the
complexity only once. This calculation is very similar to [JW18, Lemma 2],
with a similar relation. But we give the details, for the completeness.

Eventually, once we have computed $P_{j}$’s, we can use FFT (algorithm 6) to
find $E_{j}$’s, which eventually gives $T(m)\leq\tilde{O}(k(n+t))$.

To elaborate, in the for-loop 7-8 in algorithm 6, we want to find
$\sum_{i=\ell}^{s}(-1)^{j-i}E_{i}\cdot P_{j-i}$ for all
$j\in\\{s+1,\dots,u\\}$. To achieve this, we define the polynomials:

$F(x)\,:=\,\sum_{k=0}^{u-\ell}(-1)^{k-1}P_{k}x^{k},~{}~{}\text{and}~{}~{}G(x)\,:=\,\sum_{j=0}^{s-\ell}E_{j+\ell}x^{j}\;.$

Note that our $F(x)$ is different than used in [JW18], because of slightly
different recurrence relation. We can compute $H(x)=F(x)\cdot G(x)$, in time
$\tilde{O}((u-\ell))$. Observe that
$\sum_{i=\ell}^{u}\,(-1)^{j-i-1}P_{j-i}\cdot
E_{i}=\textup{{coef}}_{x^{j-\ell}}(H(x))$ because
$(-1)^{j-i-1}P_{j-i}=\textup{{coef}}_{x^{j-i}}(F(x))$ and
$E_{i}=\textup{{coef}}_{x^{i-\ell}}(G(x))$. Therefore, the inner for loop can
be computed in $\tilde{O}((u-\ell))$ time.

##### Final time complexity.

Let $T^{\prime}(m)$ is the complexity of computing $E_{1},\ldots,E_{m}$
assuming precomputations of $P_{j}$ and $j^{-1}$. Then,

$T^{\prime}(m)\;\leq\;2T^{\prime}(m/2)\,+\,\tilde{O}(m)\;\implies\;T^{\prime}(m)\,\leq\,\tilde{O}(m)\;.$

Therefore, the total complexity of computing $E_{1},\ldots,E_{m}$, is
$T(m)=T^{\prime}(m)+\tilde{O}(k(n+t))$, where $\tilde{O}(k(n+t))$ is for the
time for computing $P_{j}$’s (and $j^{-1}$). Since, $q=O(n+k+t)$ and $m\leq
k$, we get $T(m)=\tilde{O}(k(n+t))$, as we wanted.

Input: $P_{i}$, for $i\in[m]$, $q$ and $E_{0}=1$

Output: $E_{i}$ for $i\in[m]$

1 Initialize $E_{j}\leftarrow 0$, for $j\in[m]$;

2 return Compute$(0,m)$;

3

4Procedure Compute$(\ell,u)~{}\triangleright$ the values returned by
Compute$(\ell,u)$ are the final values $E_{\ell},\ldots,E_{u}$ are computed;

5 for  _$\ell <u$ _ do

6 $s\leftarrow\lfloor\frac{\ell+u}{2}\rfloor$

7 Compute$(\ell,s)$;

8 for  _$j\leftarrow s+1,\ldots,u$_ do

9 $E_{j}\leftarrow
E_{j}+j^{-1}\cdot\left(\sum_{i=\ell}^{s}\,(-1)^{j-i}E_{i}\cdot
P_{j-i}\right)~{}\bmod~{}q$;

10

11 end for

12 Compute$(s+1,u)$

13 end for

14return $E_{\ell},\dots,E_{u}$;

Algorithm 6 Algorithm for computing $E_{i}$

##  Appendix B Algorithms

###  B.1 Trivial solution for $k-\mathsf{SSSUM}$

Bellman’s dynamic programming solution for the decision version of
$\mathsf{SSUM}$ is based on the recurrence relation
$S((a_{1},\dots,a_{n}),t)=S((a_{1},\dots,a_{n-1}),t)\oplus
S((a_{1},\dots,a_{n-1}),t-a_{n})$ where
$S((a_{1},\dots,a_{j}),t^{\prime})=1\iff t^{\prime}$ is a realisable target of
$(a_{1},\dots,a_{j})$. Using this relation, the algorithm needs to store only
the values of $S((a_{1},\dots,a_{j-1}),t^{\prime})$ for all $1\leq
t^{\prime}\leq t$ to compute $S((a_{1},\dots,a_{j}),t^{\prime\prime})$ for all
$1\leq t^{\prime\prime}\leq t$. So, the time complexity is $O(nt)$ whereas the
space complexity is $\Omega(t)$.

For finding all the solutions, we modify the above algorithm by adding a
pointer from $S((a_{1},\dots,a_{j}),t^{\prime})$ to
$S((a_{1},\dots,a_{j-1}),t-a_{j})$ when both are equal to 1. The same is done
for $S((a_{1},\dots,a_{j}),t^{\prime})$ and $S((a_{1},\dots,a_{j-1}),t)$.
Apart from these, we also add a pointer from $S({a_{i}},a_{i})$ to a new node
$S(\\{\\},0)$ where $1\leq i\leq n$. This gives a directed graph of size
$O(nt)$ because the out-degree of each node is at most 2. To find all the
solutions to the $\mathsf{SSUM}$ , we simply run a modified version of DFS
algorithm444The graph is a directed acyclic one and we can use the algorithm
mentioned in https://stackoverflow.com/questions/20262712/enumerating-all-
paths-in-a-directed-acyclic-graph on this graph to finds all the paths from
$S((a_{1},\dots,a_{n}),t)$ to $S(\\{\\},0)$.

It is evident that if the number of solutions to the $\mathsf{SSUM}$ instance
is $k$, then the number of paths is also $k$. The modified DFS algorithm goes
through all the neighbouring vertices of a given vertex, no matter if they are
visited or not. Furthermore, any path that starts from
$S((a_{1},\dots,a_{n}),t)$ will end at $S(\\{\\},0)$.

Clearly, this algorithm will terminate because the graph is directed acyclic.
The running time and space of the modified DFS algorithm is $O(nk)$ because
each path is of length at most $n$ and the algorithm traverses through each
path at most twice (the first traversal ends at $S(\\{\\},0)$ which finds the
path and the second one is backtracking). Therefore, the total time and space
complexity is $O(n(t+k))$.

###  B.2 Trivial dynamic algorithm for $\mathsf{SimulSubsetSum}$

In this section, we sketch a dynamic pseudo-polynomial time algorithm which
solves $\mathsf{SimulSubsetSum}$, with targets $t_{1},\ldots,t_{k}$, in
$O(n(t_{1}+1)\ldots(t_{k}+1))$ time. This is a direct generalization of
Bellman’s work [Bel57].

The algorithm considers an $n\times(t_{1}+1)\times\dots\times(t_{k}+1)$
boolean matrix $M$ and populates it with 0/1 entries.
$M[i,j_{1},j_{2},\dots,j_{k}]$ has 1 iff the $\mathsf{SimulSubsetSum}$
instance with $\ell^{th}$ $\mathsf{SSUM}$ instance
$(a_{1\ell},a_{2\ell},\dots,a_{i\ell},j_{i})$ has a solution. Here $i\in[n]$
and $j_{i}\in[0,t_{i}]$. Even though we have remarked that wlog $t_{i}\geq
1,\forall i\in[n]$, we cannot do the same for $a_{ij}$’s. This forces us to
look at $j_{i}\in[0,t_{i}],\forall i\in[k]$. The algorithm starts by setting
$M[1,a_{11},a_{12},\dots,a_{1k}]=1$ and $M[1,j_{1},j_{2},\dots,j_{k}]=0$ for
the rest. Then, using the following recurrence relation, the algorithm
populates the rest of the matrix.

$M[i,j_{1},j_{2},\dots,j_{k}]=M[i-1,j_{1},j_{2},\dots,j_{k}]+M[i-1,j_{1}-a_{i1},j_{2}-a_{i2},\dots,j_{k}-a_{ik}]$

i.e., $M[i,j_{1},j_{2},\dots,j_{k}]$ is set to 1 iff either
$M[i-1,j_{1},j_{2},\dots,j_{k}]=1$ or
$M[i-1,j_{1}-a_{i1},j_{2}-a_{i2},\dots,j_{k}-a_{ik}]=1$. Since, the size of
the matrix is $n(t_{1}+1)\dots(t_{k}+1)$, the running time of the algorithm is
$O(n(t_{1}+1)\dots(t_{k}+1))$.

##  Appendix C Dynamic programming approach for $\mathsf{Subset~{}Product}$

In this section, we will briefly discuss the modification to Bellman’s dynamic
programming approach for $\mathsf{SSUM}$ to solve $\mathsf{Subset~{}Product}$
in deterministic (expected) time $O(nt^{o(1)})$.

The algorithm starts by removing all $a_{i}$ that does not divide $t$. Then
using the factoring algorithm in [LP92], we can factor $t$ into prime factor
$p_{j}$, i.e., $t=\prod_{i\in[k]}p_{j}^{t_{j}}=t$, where
$k=O(\log(t)/\log\log(t))$. We now compute the DP table $T$ of size
$n\times(t_{1}+1)\times\dots\times(t_{k}+1)$ such that

$T[i,x_{1},\dots,x_{k}]=1,~{}\text{if and only if there
exists}~{}S\in[i],~{}\text{such that}~{}\prod_{j\in
S}a_{j}=\prod_{j\in[k]}p_{j}^{x_{j}}\;.$

Observe that the time complexity of the algorithm is the time taken to
populate the DP table with either 1 or 0. Since the size of the DP table is
$n\times\prod_{i\in[k]}(1+t_{i})$, using the similar analyse mentioned in
subsection 5.1, we can bound the term $\prod_{i\in[k]}(1+t_{i})$ by
$t^{o(1)}$. Therefore, the total time complexity is $O(nt^{o(1)})$.