Deterministic Integer 3SUM in O(n^1.999017) Time via a Sharper Binomial-Tail Analysis
We refine the analysis of the deterministic integer 3SUM algorithm of Alman and Vassilevska Williams (arXiv:2610.06783v1). Within their framework of thin matrix products and reductions through Exact Triangle, we obtain a worst-case running time of O(n^1.999017) for polynomially bounded integer inputs on a word RAM with O(log n)-bit words. The main refinement retains the binomial tail in the preprocessing cost instead of replacing it immediately by a uniform geometric bound. An entropy estimate yields a strictly larger preprocessing saving exponent, while preserving the query algorithm and…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00221
curl -X POST /api/v1/records/hexagon/2610.00221/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00221/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'