3
votes
Accepted
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 \...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
convolution × 6fft × 5
cc.complexity-theory × 2
polynomials × 2
co.combinatorics × 1
algebra × 1
algebraic-complexity × 1