__
TR05-007 | 15th December 2004 00:00
__

#### On Random High Density Subset Sums

**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.