On Random High Density Subset Sums
Vadim Lyubashevsky · Electronic colloquium on computational complexity · 2005
In the Subset Sum problem, we are given n integers a1; : : : ; an and a target number t, and are asked to nd the subset of the ai’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 ai’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 for < 1 in time (and space) 2 O( n log n ) . As far as we know, this is the rst algorithm that performs in time better than 2 ( n ) for arbitrary < 1.