Skip to main content
3 votes

Subquadratic 3SUM when one set is in [n^1.99]

I think one can solve this problem as follows. Assume that we have three sets $A, B, C$ of integers, $|A|=|B|=|C|=n$, and $C\subseteq [n^{2-\delta}]$. We want to check whether there exist $a\in A, b \...
Alex Golovnev's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible