A New Algorithm for Solving the rSUM Problem

EasyChair Preprint 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, Structure of sumsets, computational complexity, computational geometry, knapsack problem, number theory

@booklet{EasyChair:8271,
  author    = {Valerii Sopin},
  title     = {A New Algorithm for Solving the rSUM Problem},
  howpublished = {EasyChair Preprint 8271},
  year      = {EasyChair, 2022}}