0
$\begingroup$

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-$?

$\endgroup$
2
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is correct reference for the $O(r\cdot n^{1/(k(1+\lg r))})$ algorithm? $\endgroup$ – user34945 May 25 '16 at 19:18
  • $\begingroup$ actually that cant be right it is sublinear and we need at least linear time to read the data. $\endgroup$ – user34945 May 25 '16 at 19:23
  • $\begingroup$ @Student., it's not necessary to read all of the data because it's likely a solution can be found before you've read it all. See the prior paragraph about $r=2$ for an easier-to-understand algorithm; then note that the 2nd paragraph is the special case of the 3rd paragraph for the case $r=2$. $\endgroup$ – D.W. May 25 '16 at 20:42
  • $\begingroup$ I missed the random part. So this is not deterministic? So for deterministic we cannot do any better than best algorithm for absolute value $2^n$ bounded integers? $\endgroup$ – user34945 May 25 '16 at 21:23
  • $\begingroup$ @Student., yes, some of the algorithms I present are randomized. I don't know whether they can be derandomized or not; they were motivated by cryptographic applications, where there's really no reason to worry about whether the algorithm is randomized or deterministic or not (as in practice randomness is readily available). $\endgroup$ – D.W. May 25 '16 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy