A New Algorithm for Solving the rSUM Problem

EasyChair Preprint no. 8271

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.

Keyphrases: 3SUM (kSUM) problem, computational complexity, computational geometry, knapsack problem, number theory, Structure of sumsets

@Booklet{EasyChair:8271,
  author = {Valerii Sopin},
  title = {A New Algorithm for Solving the rSUM Problem},
  howpublished = {EasyChair Preprint no. 8271},

  year = {EasyChair, 2022}}