arXiv preprint ·
Beyond 3SUM-Hardness for Geometric Problems
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Since the early days of fine-grained complexity, many geometric problems have been shown to require quadratic time under the 3SUM Hypothesis. But as the 3SUM Hypothesis was recently refuted, these lower bounds have lost their foundation. In this note we point out that many of them can be recovered under an alternative hardness assumption, the $k$-AP Hypothesis. The required changes to the proofs are trivial, so the lower bounds remain just as easy to teach.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Approximation algorithms for identical parallel machine scheduling with assignment costs
The Exact Robustness of Smith's Rule with Predicted Processing Times
A Factor-6 Truthful-in-Expectation Mechanism for Cascade Position Auctions
Exact Algorithms and Complexity of the Smallest Grammar Problem
Engineering Lightweight Burrows-Wheeler Transform Construction on the GPU via Prefix-Free Parsing
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.