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>1$ and for case (2) $k=\theta((\log n)^\alpha)$ for some fixed $\alpha\in(0,1)$?What happens at limit $\alpha\rightarrow1-$?
Complexity of $r$-sum as a function of integer sizes
cc.complexity theory;subset sum
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.