Didn’t realize 3SUM could be done faster then N^2 until I did this interview

“Threesomes, Degenerates, and Love Triangles”, 2014 paper if you want more details: https://t.co/2AYc6rBgRb

@rrwilliams Explains some high level approaches in the clip & the pod https://t.co/oSEyDt9GVy

Threesomes, Degenerates, and Love Triangles

Source: https://arxiv.org/abs/1404.0799 View PDF

Abstract:The 3SUM problem is to decide, given a set of n real numbers, whether any three sum to zero. It is widely conjectured that a trivial O\(n^2\)-time algorithm is optimal and over the years the consequences of this conjecture have been revealed. This 3SUM conjecture implies \\Omega\(n^2\) lower bounds on numerous problems in computational geometry and a variant of the conjecture implies strong lower bounds on triangle enumeration, dynamic graph algorithms, and string matching data structures. In this paper we refute the 3SUM conjecture. We prove that the decision tree complexity of 3SUM is O\(n^\{3/2\}\\sqrt\{\\log n\}\) and give two subquadratic 3SUM algorithms, a deterministic one running in O\(n^2 / \(\\log n/\\log\\log n\)^\{2/3\}\) time and a randomized one running in O\(n^2 \(\\log\\log n\)^2 / \\log n\) time with high probability. Our results lead directly to improved bounds for k-variate linear degeneracy testing for all odd k\\ge 3. The problem is to decide, given a linear function f\(x\_1,\\ldots,x\_k\) = \\alpha\_0 \+ \\sum\_\{1\\le i\\le k\} \\alpha\_i x\_i and a set A \\subset \\mathbb\{R\}, whether 0\\in f\(A^k\). We show the decision tree complexity of this problem is O\(n^\{k/2\}\\sqrt\{\\log n\}\). Finally, we give a subcubic algorithm for a generalization of the \(\\min,\+\)-product over real-valued matrices and apply it to the problem of finding zero-weight triangles in weighted graphs. We give a depth-O\(n^\{5/2\}\\sqrt\{\\log n\}\) decision tree for this problem, as well as an algorithm running in time O\(n^3 \(\\log\\log n\)^2/\\log n\).

Submission history

From: Seth Pettie [view email] **[v1]**Thu, 3 Apr 2014 08:30:03 UTC (17 KB) **[v2]**Thu, 29 May 2014 10:02:28 UTC (57 KB) **[v3]**Fri, 30 May 2014 19:46:20 UTC (57 KB)

Ryan Peterman (@ryanlpeterman): Ryan Williams (@rrwilliams) is a professor at MIT and the winner of the Gödel Prize in theoretical computer science. I interviewed him all about his work starting by asking him a popular Leetcode question (3 SUM).

In this episode:

• Solving Leetcode faster than popular