Check for common element in two arrays using FFT My task asks me to check whether there is a common element in two sets $\{x_1,x_2,...,x_n\}$, $\{y_1,y_2,...,y_n\}$ with $x_i,y_i\in\mathbb{N}$ using the Fast Fourier Transform (FFT).
(I'm aware that there is a simple $O(n\log(n))$ algorithm to solve this problem using sorting and binary search.)
The tasks hints that we should consider the following product to solve the problem:
$$
\prod_{1\leq i,j \leq n} (x_i-y_j)
$$
The product is obviously zero if there is a common element, but I am still not sure how I could compute it faster via FFT.
I know how to use FFT to multiply polynomials efficiently, but somehow I seem to overlook something.
This one is a bit esoteric, but:
$$
\prod_{1\leq i,j \leq n} (x_i-y_j)
$$
Could be decomposed to (as noted by @NotDijkstra)
$$
\prod_{i=1}^{n} p(x_i)
$$
where
$$
p (x) = \prod_{j=1}^{n} (x - y_j)
$$
reduces to a polynomial with roots $y_i$. Coefficients of this polynomial could be computed with FFT, see https://arxiv.org/pdf/1608.01357.pdf. It could be done even faster using divide and conquer strategy - recursively split the formula into two polynomials and multiply them with FFT (see answers).
Polynomial representation in its turn would allow fast exponentiation of x, or even multi-point evaluation
Although, I don't see any advantages over traditional approach in terms of speed or complexity except if it's implemented on specialised ASICs/FPGAs/GPUs.