7
$\begingroup$

Chan and Lewenstein (STOC 2015) said:

3SUM for three integer sets where only one set is assumed to be in $[n^{2−\delta}]$ can still be solved in subquadratic time (by doing several FFTs, without requiring additive combinatorics - a simple exercise we leave to the reader).

Note, that the other 2 sets can be from $[n^{3+o(1)}]$.

Nevertheless I have no idea how to solve this exercise. Do you have any hints? (probably you can use their paper but it looks like an overkill)

$\endgroup$
3
$\begingroup$

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 \in B, c \in C$ such that $a+b+c=0$.

First, we partition the set $A$ into $k\leq n$ sets $A_1,\ldots A_k$, where each $A_i$ contains numbers in an interval of length $n^{2-\delta}$. Now from the set $B$, we construct sets $B_1,\ldots, B_k$ as follows. $B_i$ contains numbers from $B$ in the interval $[-n^{2-\delta}-\max_{a \in A_i}{a}, -\min_{a\in A_i}a]$. This way each number from $B$ appears in at most two sets $B_i$. And now we only need to check whether for some $i$ there exists a solution in $A_i + B_i + C$.

Let $a_i=|A_i|$, $b_i=|B_i|$. If $a_i\geq n^{1-\delta/2}$ or $b_i\geq n^{1-\delta/2}$, we solve $A_i+B_i+C$ by FFT in time $O(n^{2-\delta}\log{n})$. (Because numbers in all three sets lie in intervals of length $O(n^{2-\delta})$.) Since $\sum_i a_i=n$ and $\sum_i b_i\leq 2n$, the total number of such $a_i$ and $b_i$ is at most $3n^{\delta/2}$, which means that the running time of this step is $O(n^{2-\delta/2}\log{n})$.

For the remaining values of $i$, we solve the problem by trying all $a\in A_i$ and $b \in B_i$, and looking up their sum in $C$ in logarithmic time. This step takes time $\sum a_i b_i \log{n} \leq O(n^{2-\delta/2}\log{n})$. (I believe one can shave off the $\log{n}$ factor here by using the standard 3-SUM trick.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.