Complexity of $r$-sum as a function of integer sizes Given $n$ distinct integers whose absolute value is of size $c_{n,k}=\lceil n^{1/k}\rceil$ bits ($c_{n,k}$th bit position is always $1$ for absolute value) we know that using dynamic programming we can find if there is a subset that sums to $0$ in $2^{O(n^{1/k})}$ time.

Given $r\in\Bbb N$ what is best known algorithm for complexity of $r$-sum on such situations for case (1) fixed $k&gt;1$ and for case (2) $k=\theta((\log n)^\alpha)$ for some fixed $\alpha\in(0,1)$?

What happens at limit $\alpha\rightarrow1-$?
There is a straightforward dynamic programming algorithm with complexity $n \times 2^{O(r \cdot n^{1/k})}$.  This is pretty slow.

For $r=2$, you can use algorithms for the birthday paradox to find a solution in time $O(n)$, if a solution exists.  A solution will exist with high probability.  In fact, for $r=2$, with high probability a solution will exist within the first $n^{1/2k}$ numbers, and we can find a solution in expected running time $O(n^{1/(2k)})$.

There is an algorithm with complexity $O(r \cdot n^{1/(k(1+\lg r))})$.  You start by finding pairs (2-sums) whose sum has many of their high bits equal to zero (by combining pairs of elements, using algorithms for the birthday paradox); then look for 4-sums whose sum has a (slightly smaller) number of high bits equal to zero (by combining pairs of 2-sums); then look for 8-sums (by combining pairs of 4-sums); and so on.  The running time comes from optimizing the exact number of high bits that you ask to be zero at each stage.

For instance, for the case $r=4$, there is an algorithm with complexity $O(n^{1/(3k)})$ for finding at least one such solution.

As far as I know, it is an open problem whether one can do better than this.

See also the following research papers:


A. Blum, A. Kalai, H. Wasserman. "Noise-tolerant learning, the parity problem, and the statistical query model".  JACM, 50(4):506-519, 2003.
P. Camion, J. Patarin.  "The Knapsack hash function proposed at Crypto'89 can be broken".  EUROCRYPT '91, pp.39-53.
R. Schroeppel, A. Shamir.  "A T = O(2^n/2), S = O(2^n/4) algorithm for certain NP-Complete problems".  SIAM J. Computing,  10(3):456--464.
P. Chose, A. Joux, M. Mitton.  "Fast Correlation Attacks: an algorithmic point of view".  EUROCRYPT 2002.