Abstract:
In the Subset Sum problem, we are given n integers a_1,...,a_n and a target number t, and are asked to find the subset of the a_i's such that the sum is t. A version of the subset sum problem is the Random Modular Subset Sum problem. In this version, the a_i's are generated randomly in the range [0,M), and we are asked to produce a subset of them such that the sum is t(mod M). The hardness of RMSS depends on the relationship between the parameters M and n. When M=2^{O(n^2)}, RMSS can be solved in polynomial time by a reduction to the shortest vector problem. When M=2^{O(log{n})}, the problem can be solved in polynomial time by dynamic programming, and recently an algorithm was proposed that solves the problem in polynomial time for M=2^{O(log^2{n})}. In this work, we present an algorithm that solves the Random Modular Subset Sum problem for parameter M=2^{n^c} for c<1 in time (and space) $2^{O((n^c)/log(n)))}$. As far as we know, this is the first algorithm that performs in time better than $2^{Omega(n^c)}$ for arbitrary c<1.