About this document
Refuting the 3SUM Conjecture by lovethailand20241225 is a document available to read on EtoBox.
This paper refutes the widely held 3SUM conjecture by proving that the decision tree complexity of the 3SUM problem is O(n^{3/2} log n) and presents two subquadratic algorithms for solving it. Additionally, it provides improved bounds for k-variate linear degeneracy testing and introduces a new product of three real-valued matrices, leading to subcubic bounds for the ZeroTriangle problem. The results challenge the optimality of many existing algorithms in computational geometry and related fields.
- Author
- lovethailand20241225
- Language
- EN