Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-007 | 15th December 2004 00:00

On Random High Density Subset Sums


Authors: Vadim Lyubashevsky
Publication: 18th January 2005 00:22
Downloads: 4215


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.

ISSN 1433-8092 | Imprint