Finding witness in minkowski sum of integers Let $A$ and $B$ be subsets of $\{0,\ldots,n\}$. We are interested in finding the Minkowski sum $A+B=\{a+b~|~a\in A,b\in B\}$.

$\chi_X:\{0,\ldots,2n\}\to \{0,1\}$ is a characteristic function of $X$ if $$\chi_X(x) = \begin{cases} 1 \text{ if } x\in X\\ 0 \text{ otherwise}\end{cases}$$

Let $f$ be the discrete convolution of $\chi_A$ and $\chi_B$, then $x\in A+B$ if and only if $f(x)&gt; 0$. Hence $A+B$ can be computed in $O(n\log n)$ time by discrete convolution via FFT.

Sometimes it is important to find out the actual pair $a\in A$ and $b\in B$ that sums to $x$. $a\in A$ is called a witness of $x$, if there exist $b\in B$ such that $a+b=x$. A function $w:A+B\to A$ is called a witness function if $w(x)$ is a witness of $x$.


  Is it possible to compute a witness function in $O(n\log n)$ time?
Ok, I've been holding off since really Sariel should get credit for an answer, but I'm tired of waiting, so here is my cut at a near-linear randomized algorithm.


By choosing samples of $n(1-\epsilon)^i$ points, $i=0,1,\dots$, you can get a logarithmic number of subproblems such that each sum from the original problem has constant probability of being represented uniquely in one of the subproblems (the one where the sampling cuts down the expected number of representations to near 1).
By repeating the sampling process a logarithmic number of times you can get all sums to have unique representations with high probability.
If you have a partition of $A$ and $B$ into two subsets, then by multiplying the numbers by four, adding 2 to the numbers in one of the subsets in $A$, and adding 1 to the numbers in one of the subsets in $B$, you can read off from the mod-4 values of the achievable sums which of the two subsets their summands come from.
By repeating the partition process a logarithmic number of times, using each bit position of the binary representations of the values or indices in the subproblems to select the partitions in each step, you can uniquely identify the summands of every uniquely-represented sum.


This blows up the running time by three logarithmic factors; probably that can be reduced.