Comment

Comment by gregdeon

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.
parent gregdeon 25 days ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton