Reproduce “Beyond 3SUM-Hardness for Geometric Problems” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Nick Fischer
The paper establishes conditional quadratic-time lower bounds for 19 geometric problems by replacing 3SUM-based reductions with reductions from k-AP detection. It maps equally spaced integer progressions to collinear points on parallel lines, then uses aligned wall openings to encode a rod-passage problem. If the k-AP Hypothesis holds for some fixed k ≥ 4, these problems admit no O(n^(2−ε)) algorithms for constant ε > 0; this conditional result covers only listed reductions.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.