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

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

• What is correct reference for the $O(r\cdot n^{1/(k(1+\lg r))})$ algorithm? – user34945 May 25 '16 at 19:18
• actually that cant be right it is sublinear and we need at least linear time to read the data. – user34945 May 25 '16 at 19:23
• @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$. – D.W. May 25 '16 at 20:42
• 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? – user34945 May 25 '16 at 21:23
• @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). – D.W. May 25 '16 at 22:10
{"ft_lang_label":"__label__en","ft_lang_prob":0.84467745,"math_prob":0.9974224,"size":1736,"snap":"2019-43-2019-47","text_gpt3_token_len":496,"char_repetition_ratio":0.108545035,"word_repetition_ratio":0.042704627,"special_character_ratio":0.29896313,"punctuation_ratio":0.1640625,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9997212,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-11-18T04:11:02Z\",\"WARC-Record-ID\":\"<urn:uuid:0f11ed58-6723-4168-97e7-6d1e71eb8635>\",\"Content-Length\":\"140029\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:ff2e6176-9ba6-4424-9c8e-9b8663419028>\",\"WARC-Concurrent-To\":\"<urn:uuid:ba304ff9-8c4e-4391-8287-81d2eb5d5d0f>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://cstheory.stackexchange.com/questions/34767/complexity-of-r-sum-as-a-function-of-integer-sizes\",\"WARC-Payload-Digest\":\"sha1:TYRPWO6PNCPAD6ENGVDUSXYMTG4TFJDF\",\"WARC-Block-Digest\":\"sha1:UREAXXCSJUXNGL6IXPRFBMFE4XTKMXK2\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-47/CC-MAIN-2019-47_segments_1573496669431.13_warc_CC-MAIN-20191118030116-20191118054116-00323.warc.gz\"}"}