# Finding 3SUM witness when promised a solution

Suppose we have a 3SUM instance given with the promise that there exists at least one solution. Is the trivial $$O(n^2)$$ (modulo logarithmic improvements) solution still the best algorithm or is there a sub-quadratic algorithm known?

• If an algorithm works with such a promise, then it also works without a promise (we can check in contant time whether solution produced by an algorithm is correct). – Sasha Kozachinskiy Mar 31 '19 at 15:12