A new algorithm for solving the rSUM problem

Valerii Sopin

Paper 2022/1113

A new algorithm for solving the rSUM problem

Valerii Sopin

, Independent scientist

Abstract

A determined algorithm is presented for solving the rSUM problem for any natural r with a sub-quadratic assessment of time complexity in some cases. In terms of an amount of memory used the obtained algorithm is the nlog^3(n) order. The idea of the obtained algorithm is based not considering integer numbers, but rather k (is a natural) successive bits of these numbers in the binary numeration system. It is shown that if a sum of integer numbers is equal to zero, then the sum of numbers presented by any k successive bits of these numbers must be sufficiently "close" to zero. This makes it possible to discard the numbers, which a fortiori, do not establish the solution.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: 3SUM (kSUM) problem computational complexity computational geometry knapsack problem structure of sumsets
Contact author(s): vVs @ myself com
History: 2022-08-29: approved; 2022-08-28: received; See all versions
Short URL: https://ia.cr/2022/1113
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1113,
      author = {Valerii Sopin},
      title = {A new algorithm for solving the rSUM problem},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1113},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1113}},
      url = {https://eprint.iacr.org/2022/1113}
}