More logarithmic-factor speedups for 3sum, (median,+)-convolution, and some geometric 3sum-hard problems

Research output: Contribution to journalArticlepeer-review

Abstract

This article presents an algorithm that solves the 3SUM problem for n real numbers in O((n2/ log2 n) (log logn)O(1) ) time, improving previous solutions by about a logarithmic factor. Our framework for shaving off two logarithmic factors can be applied to other problems, such as (median,+)-convolution/matrix multiplication and algebraic generalizations of 3SUM. This work also obtains the first subquadratic results on some 3SUM-hard problems in computational geometry, for example, deciding whether (the interiors of) a constant number of simple polygons have a common intersection.

Original languageEnglish (US)
Article number7
JournalACM Transactions on Algorithms
Volume16
Issue number1
DOIs
StatePublished - Nov 2019

Keywords

  • 3SUM
  • Computational geometry
  • Convolution
  • Matrix multiplication

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint Dive into the research topics of 'More logarithmic-factor speedups for 3sum, (median,+)-convolution, and some geometric 3sum-hard problems'. Together they form a unique fingerprint.

Cite this