pipette
ENEnglish

3SUM Is Really Hard: A Real-to-Integer Reduction

Nick Fischer, Adam Polak, Jonas Schmidt

PreprintDice ser un gran avance

En palabras de los autores

We show that if the 3SUM problem on integer-valued inputs can be solved in truly subquadratic time, then it can also be solved in truly subquadratic time on real-valued inputs. This answers an open problem posed by Chan, Vassilevska Williams, and Xu [STOC 2022], and constitutes the first such tight real-to-integer self-reduction in fine-grained complexity. Our proof relies on a surprising combination of the Frank--Tardos theorem from optimization with Freiman-type theorems from additive combinatorics.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: To appear in FOCS 2026