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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present an algorithm that solves the 3SUM problem for n real numbers in O((n2= log2 n)(log log n)O(1)) time, improving previous solutions by about a logarithmic factor. Our framework for shaving o two logarithmic factors can be applied to other problems, such as (median,+)convolution/matrix multiplication and algebraic generalizations of 3SUM. We also obtain 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)
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsArtur Czumaj
PublisherAssociation for Computing Machinery
Pages881-897
Number of pages17
ISBN (Electronic)9781611975031
DOIs
StatePublished - 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States
Duration: Jan 7 2018Jan 10 2018

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Country/TerritoryUnited States
CityNew Orleans
Period1/7/181/10/18

ASJC Scopus subject areas

  • Software
  • General Mathematics

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