HEXAGONbeta

Which Fine-Grained Lower Bounds Survive the Refutation of 3SUM and APSP?

A mix of human-written and AI-generated textHuman understanding: all partscs.CC — Computational Complexitycs.DS — Data Structures and Algorithmsmath.CO — Combinatorics

Contributed by Tejasvi Singh Tomar ↗

Version 1 / Nov 12, 2026 / CC BY 4.0

Abstract

Alman and Vassilevska Williams have refuted the 3SUM and APSP hypotheses. Their algorithms rest on counting the triangles through prescribed edges of lopsided tripartite graphs, whose middle part has nεn^{\varepsilon} vertices for a small ε\varepsilon. Majdoddin extended the method to every ε<ln⁡4/(5ln⁡5)≈0.172\varepsilon<\ln4/(5\ln5)\approx0.172. We determine which of the main conditional lower bounds derived from the refuted hypotheses survive. We also prove that the method extends to every ε<0.17843\varepsilon<0.17843 when the prescribed edges are known in advance and there are at most n2−ε/2n^{2-\varepsilon/2} of them, which confirms Majdoddin's numerical estimate. Whether a bound survives depends mostly on the instances that its reduction produces. The reductions behind most bounds produce instances outside the range of the new algorithms: balanced graphs, or lopsided graphs with a larger middle part. Most of the set-disjointness, dynamic-graph and triangle bounds therefore follow from hypotheses that no known algorithm contradicts. These hypotheses, however, concern mainly such instances, and for several bounds the hypothesis is the bound itself, stated for these instances. Their evidence came largely from the refuted hypotheses. A few bounds are false, among them a lower bound of Goldstein, Lewenstein and Porat for Set Disjointness over small universes; the Strong SetDisjointness Conjecture also fails at small polynomial query times. Other bounds have lost their support, such as the Set Disjointness trade-offs of Kopelowitz, Pettie and Porat over small universes apart from constant query time. Finally, we collect the known obstacles to a larger closed-form range with a different base identity and use border-rank lower bounds to exclude several natural candidates.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23716495

References

  1. A. Abboud, K. Bringmann, and N. Fischer. Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics. In STOC 2023 , pages 391--404. Full version: arXiv:2211.07058.arXiv
  2. A. Abboud, K. Bringmann, S. Khoury, and O. Zamir. Hardness of approximation in P via short cycle removal: cycle detection, distance oracles, and beyond. In STOC 2022 , pages 1487--1500. Full version: arXiv:2204.10465.arXiv
  3. A. Amir, T. M. Chan, M. Lewenstein, and N. Lewenstein. On hardness of jumbled indexing. In ICALP 2014 , LNCS 8572, pages 114--125. Full version: arXiv:1405.0189.arXiv
  4. A. Abboud, F. Grandoni, and V. Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In SODA 2015 , pages 1681--1697.
  5. J. Alman, Y. Huang, and K. Yeo. Fine-grained complexity in a world without cryptography. In EUROCRYPT 2025, Part VII , LNCS 15607, pages 375--405.
  6. A. Abboud and V. Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In FOCS 2014 , pages 434--443. Full version: arXiv:1402.0054.arXiv
  7. J. Alman and V. Vassilevska Williams. Truly subquadratic 3SUM and truly subcubic APSP via triangles in sparse lopsided graphs. arXiv:2610.06783, 2026.arXiv
  8. A. Abboud, V. Vassilevska Williams, and O. Weimann. Consequences of faster alignment of sequences. In ICALP 2014 , LNCS 8572, pages 39--51.
  9. A. Hernández Barrera. Finding an o(n2log⁡n)o(n^2\log n) algorithm is sometimes hard. In CCCG 1996 , pages 289--294.
  10. D. Bremner, T. M. Chan, E. D. Demaine, J. Erickson, F. Hurtado, J. Iacono, S. Langerman, M. Pătraşcu, and P. Taslakian. Necklaces, convolutions, and X+YX+Y. Algorithmica 69(2):294--314, 2014.
Show all 50 referencesShow fewer references
  1. G. Barequet and S. Har-Peled. Polygon containment and translational min-Hausdorff-distance between segment sets are 3SUM-hard. Int.\ J.\ Comput.\ Geom.\ Appl. \ 11(4):465--474, 2001.
  2. A. Backurs, P. Indyk, and L. Schmidt. Better approximations for tree sparsity in nearly-linear time. In SODA 2017 , pages 2215--2229.
  3. J. van den Brand, D. Nanongkai, and T. Saranurak. Dynamic matrix inverse: improved algorithms and matching conditional lower bounds. In FOCS 2019 , pages 456--480. Full version: arXiv:1905.05067.arXiv
  4. A. Björklund, R. Pagh, V. Vassilevska Williams, and U. Zwick. Listing triangles. In ICALP 2014 , LNCS 8572, pages 223--234.
  5. J. van den Brand, Z. Song, and T. Zhou. Algorithm and hardness for dynamic attention maintenance in large language models. In ICML 2024 , PMLR 235, pages 49008--49028.
  6. M. Cygan, M. Mucha, K. Węgrzycki, and M. Włodarczyk. On problems equivalent to (min⁡,+)(\min,+)-convolution. ACM Trans.\ Algorithms 15(1):14:1--14:25, 2019. Full version: arXiv:1702.07669.arXiv
  7. D. Coppersmith. Rapid multiplication of rectangular matrices. SIAM J.\ Comput. \ 11(3):467--471, 1982.
  8. T. M. Chan, V. Vassilevska Williams, and Y. Xu. Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV. In STOC 2022 , pages 1501--1514.
  9. T. M. Chan and Y. Xu. Simpler reductions from exact triangle. In SOSA 2024 , pages 28--38. Full version: arXiv:2310.11575.arXiv
  10. I. Dinur and A. Golovnev. Improved time-space tradeoffs for 3SUM-Indexing. arXiv:2512.04258, 2025.arXiv
  11. L. Duraj, K. Kleiner, A. Polak, and V. Vassilevska Williams. Equivalences between triangle and range query problems. In SODA 2020 , pages 30--47.
  12. J. Erickson. Lower bounds for linear satisfiability problems. Chicago J.\ Theoret.\ Comput.\ Sci. \ 1999(8).
  13. J. Erickson and R. Seidel. Better lower bounds on detecting affine and spherical degeneracies. Discrete Comput.\ Geom. \ 13:41--57, 1995.
  14. N. Fischer, P. Kaliciak, and A. Polak. Deterministic 3SUM-hardness. In ITCS 2024 , LIPIcs 287, 49:1--49:24. Full version: arXiv:2310.12913.arXiv
  15. N. Fischer, A. Polak, and J. Schmidt. 3SUM is really hard: a real-to-integer reduction. In FOCS 2026 . arXiv:2610.10153.arXiv
  16. A. Golovnev, S. Guo, T. Horel, S. Park, and V. Vaikuntanathan. Data structures meet cryptography: 3SUM with preprocessing. In STOC 2020 , pages 294--307.
  17. I. Goldstein, T. Kopelowitz, M. Lewenstein, and E. Porat. How hard is it to find (honest) witnesses? In ESA 2016 , LIPIcs 57, 45:1--45:16. Full version: arXiv:1706.05815.arXiv
  18. I. Goldstein, T. Kopelowitz, M. Lewenstein, and E. Porat. Conditional lower bounds for space/time tradeoffs. In WADS 2017 , LNCS 10389, pages 421--436. Full version: arXiv:1706.05847.arXiv
  19. I. Goldstein, M. Lewenstein, and E. Porat. On the hardness of set disjointness and set intersection with bounded universe. In ISAAC 2019 , LIPIcs 149, 7:1--7:22. Full version: arXiv:1910.00831.arXiv
  20. A. Gajentaan and M. H. Overmars. On a class of O(n2)O(n^2) problems in computational geometry. Comput.\ Geom. \ 5(3):165--185, 1995.
  21. M. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In STOC 2015 , pages 21--30.
  22. B. Haeupler, Y. Long, and T. Saranurak. Dynamic deterministic constant-approximate distance oracles with nϵn^{\epsilon} worst-case update time. In FOCS 2024 , pages 2033--2044.
  23. C. Jin and Y. Xu. Removing additive structure in 3SUM-based reductions. In STOC 2023 , pages 405--418. Full version: arXiv:2211.07048.arXiv
  24. J. King. A survey of 3SUM-hard problems. Manuscript, 2004.
  25. S. R. Karingula and S. Lovett. A simplified proof of polynomial improvements for 3SUM and APSP. arXiv:2610.15663, 2026.arXiv
  26. T. Kopelowitz and E. Porat. The strong 3SUM-INDEXING conjecture is false. arXiv:1907.11206, 2019.arXiv
  27. T. Kopelowitz, S. Pettie, and E. Porat. Dynamic set intersection. In WADS 2015 , LNCS 9214, pages 470--481. Full version: arXiv:1407.6755.arXiv
  28. T. Kopelowitz, S. Pettie, and E. Porat. Higher lower bounds from the 3SUM conjecture. In SODA 2016 , pages 1272--1287. Full version: arXiv:1407.6756v3.arXiv
  29. M. Künnemann, R. Paturi, and S. Schneider. On the fine-grained complexity of one-dimensional dynamic programming. In ICALP 2017 , LIPIcs 80, 21:1--21:15.
  30. R. LaVigne, A. Lincoln, and V. Vassilevska Williams. Public-key cryptography in the fine-grained setting. In CRYPTO 2019, Part III , LNCS 11694, pages 605--635.
  31. J. M. Landsberg and G. Ottaviani. Equations for secant varieties of Veronese and other varieties. Ann.\ Mat.\ Pura Appl. \ 192(4):569--606, 2013.
  32. A. Lincoln, A. Polak, and V. Vassilevska Williams. Monochromatic triangles, intermediate matrix products, and convolutions. In ITCS 2020 , LIPIcs 151, 53:1--53:18. Full version: arXiv:2009.14479.arXiv
  33. R. Majdoddin. Thin matrix products up to D≤N0.172D\le N^{0.172} and lossless reductions for 3SUM, Exact Triangle and APSP, with 3SUM over abelian groups and a dichotomy for coordinatewise problems. arXiv:2610.17420, 2026.arXiv
  34. M. Pătraşcu. Towards polynomial lower bounds for dynamic problems. In STOC 2010 , pages 603--610.
  35. L. Roditty and V. Vassilevska Williams. Subquadratic time approximation algorithms for the girth. In SODA 2012 , pages 833--845.
  36. shreshth-s. Thin-matrix results. Unrefereed repository, https://github.com/shreshth-s/thin-matrix-results, accessed 23 October 2026.link
  37. B. Saha and C. Ye. Simple, faster (min⁡,+)(\min,+) matrix multiplication and APSP. arXiv:2610.20297, 2026.arXiv
  38. V. Vassilevska Williams and R. Williams. Subcubic equivalences between path, matrix, and triangle problems. J.\ ACM 65(5):27:1--27:38, 2018.
  39. V. Vassilevska Williams and Y. Xu. Monochromatic triangles, triangle listing and APSP. In FOCS 2020 , pages 786--797. Full version: arXiv:2007.09318.arXiv
  40. V. Vassilevska Williams, Y. Xu, Z. Xu, and R. Zhou. New bounds for matrix multiplication: from alpha to omega. In SODA 2024 , pages 3792--3835.

Version history

  1. v1 · 23 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.23716495CurrentNov 12, 2026