Comment by stephen_cagle
2 hours ago
The full title is "Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs". Is that the same thing as getting subqudratic time in general 3SUM? How much carrying is the Sparse Lopsided Graph doing here?
The idea is that you can solve 3SUM by solving an instance of Triangles in Sparse Graphs, but 3SUM produces instances where those graphs are lopsided (i.e., tripartite graphs where one of the parts is much smaller than the other two). They found an efficient algorithm for those kinds of instances, and therefore an efficient algorithm for 3SUM.
Oh wow, that is truly awesome then! I thought it was a qualifier, but it actually is the means of solution (yeah, confusing title).
Yeah, I found that tricky to parse too. But what they mean is that "Triangles in Sparse Lopsided Graphs" is the technique they used to exhibit "Truly Subquadratic 3SUM and Truly Subcubic APSP"