<p>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.</p>

<ul>
<li>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).</li>
<li>By repeating the sampling process a logarithmic number of times you can get all sums to have unique representations with high probability.</li>
<li>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.</li>
<li>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.</li>
</ul>

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

CC BY-SA 3.0
2015-07-23T19:26:37.227Z
Ha ha ;). I was in the middle of writing it, and then went to lunch...
Sariel Har-Peled
CC BY-SA 3.0
2015-07-23T18:06:53.673Z
2015-07-23T22:16:11.183Z
2015-07-23T22:16:11.183Z
David Eppstein
<p>This answer gives a determinstic $O(n~\mathrm{polylog} n)$ algorithm. </p>

<p>It appears that Sariel and David's algorithm can be derandomized through an <a href="http://www.tau.ac.il/~nogaa/PDFS/witf8.pdf" rel="noreferrer">approach similar to this paper</a>. [2] While going through the process I found there is a more general problem that implies this result.</p>

<blockquote>
  <p><strong>The $k$-reconstruction problem</strong></p>
  
  <p>There are hidden sets $S_1,\ldots,S_n \subset \{1,\ldots,m\}$, we have two
  oracles $Size$ and $Sum$ that take a query set $Q$.</p>
  
  <ol>
  <li>$Size(Q)$ returns $(|S_1\cap Q|,|S_2\cap Q|,\ldots,|S_n\cap Q|)$, the size of each intersection.</li>
  <li>$Sum(Q)$ returns $(\sum_{s\in S_1\cap Q} s,\sum_{s\in S_2\cap Q} s,\ldots,\sum_{s\in S_n\cap Q} s)$, the sum of elements in each intersection.</li>
  </ol>
  
  <p>The $k$-reconstruction problem asks one to find $n$ subsets $S_1',\ldots,S_n'$ such
  that $S_i'\subset S_i$ and $|S_i'|=\min(k,|S_i|)$ for all $i$.</p>
</blockquote>

<p>Let $f$ be the running time of calling the oracles, and assume $f=\Omega(m+n)$, then one can find the sets in deterministic $O(f k  \log n~\mathrm{polylog}(m))$ time. [1]</p>

<p>Now we can reduce the finding witness problem to $1$-reconstruction problem. Here $S_1,\ldots,S_{2n}\subset \{1,\ldots,2n\}$ where $S_i = \{a|a+b = i, a\in A, b\in B\}$. </p>

<p>Define the polynomials $\chi_Q(x) = \sum_{i \in Q} x^i$, $I_Q(x) = \sum_{i \in Q}  i x^i$</p>

<p>The coefficient for $x^i$ in $\chi_Q\chi_B(x)$ is $|S_i\cap Q|$ and in $I_Q\chi_B(x)$ is $\sum_{s\in S_i\cap Q} s$. Hence the oracles take $O(n\log n)$ time per call.</p>

<p>This gives us an $O(n~\mathrm{polylog}(n))$ time deterministic algorithm.</p>

<p>[1] Yonatan Aumann, Moshe Lewenstein, Noa Lewenstein, Dekel Tsur:
<a href="http://www.cs.bgu.ac.il/~dekelts/publications/peeling.pdf" rel="noreferrer">Finding witnesses by peeling</a>. ACM Transactions on Algorithms 7(2): 24 (2011)</p>

<p>[2] Noga Alon, Moni Naor: <a href="http://www.tau.ac.il/~nogaa/PDFS/witf8.pdf" rel="noreferrer">Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions</a>. Algorithmica 16(4-5) (1996)</p>

CC BY-SA 3.0
2015-08-05T21:53:03.537Z
2015-08-05T21:53:03.537Z
Chao Xu
<p>Here I am explaining how to get $O(n *\mathrm{polylog} n)$ randomized running time. We need a sequence of observations:</p>

<ol>
<li><p>A <em>witness</em> of a value $v$ is a pair of numbers $(a,b) \in A \times B$ such that $a+b=v$. Let $P_A(x) = \sum_{i \in A} x^i$ and $P_B(x)$ be defined analogously. Observe that  the coefficient of $x^v$ in $P_A(x) * P_B(x)$ is the number of witnesses there are for the value $v$.</p></li>
<li><p>Assume $v$ has a single witness $(a,b) \in A \times B$, and consider the the polynomial $Q_A(x) = \sum_{i \in A} i*x^i$. Clearly, the coefficient of $x^v$ in $Q_A(x)*P_B(x)$ is $a$, and as such we now know the pair $(a,v-a)$ and we are done.</p></li>
<li><p>So, we are done with the case that there is a single witness. So consider the case that $v$ has $k$ witnesses $(a_1, b_1),\ldots, (a_k,b_k)$. Let $i(k) = \lceil{\lg \sqrt{k}}\rceil$. Observe that $2^{i(k)-1} \leq \sqrt{k} \leq 2^{i(k)}$.
Next, let $R_j = (A_j, B_j)$, for $j=1,\ldots, m$, for $m=O(\log n)$ be random samples, such that each element of $A$ is choosen into  $A_i$ with probability $p = 1/2^{i(k)}$. The probability that $v$ has a single witness in $R_j$ is $\alpha = \binom{k}{1}p^2 (1-p^2)^{k-1}$, since the witness are disjoint pairs of numbers (since the sum of each pair is $v$). It is easy to verify that $\alpha$ is a constant in $(0,1)$ independent of the value of $k$. As such, it must be, with high probability, that $v$ has a single witness in one of the samples $R_1, \ldots, R_{m}$. As such, by computing the two polynomials associated with with such sample, as described above, in $O(n \log n)$ time (per sample), using FFT, we can decide this in constant time.</p></li>
<li><p>We are almost done. Compute the above random samples for resolutions $i=1,\ldots, \lceil\lg n\rceil$. For each such resolution compute the random samples and associated polynomials. Also, compute the associated polynomial for $A$ and $B$. This preprocessing naively takes $O(n \log^3 n)$, but I suspect that being slightly more careful a $\log n$ factor should be  removable.</p></li>
<li><p>The algorithm: For every value $v$, compute how many witness, say k, it has in constant time, by consulting the polynomial $Q_A(x)*P_B(x)$. Next, go to the relevant data-structure for $i(k)$. Then, it finds the random sample that has it as a single witness, and it extract the pair that is this witness in constant time.</p></li>
<li><p>Strangely enough, the preprocessing time is $O(n \log^3 n)$, but the expected time to find the witness themselves take only $O(n)$ time, since one can stop the search as soon as one find a witness. This suggests that this algorithm should be improveable. In particular, for $i(k) \ll \lg n$, the polynomials generated are very sparse, and one should be able to do much faster FFT. </p></li>
</ol>

CC BY-SA 3.0
2015-07-23T19:24:27.203Z
2015-07-23T19:30:11.943Z
2015-07-23T19:30:11.943Z
Sariel Har-Peled
<p>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\}$.</p>

<p>$\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}$$</p>

<p>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.</p>

<p>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 <em>witness</em> of $x$, if there exist $b\in B$ such that $a+b=x$. A function $w:A+B\to A$ is called a <em>witness function</em> if $w(x)$ is a witness of $x$.</p>

<blockquote>
  <p>Is it possible to compute a witness function in $O(n\log n)$ time?</p>
</blockquote>

CC BY-SA 3.0
2015-07-21T04:40:04.283Z
$O( n polylog n )$ is not especially hard.
Sariel Har-Peled
CC BY-SA 3.0
2015-07-21T06:36:24.540Z
You can use binary search.  e.g., partition $A$ into two roughly-equal-sized-sets $A_L,A_R$, and compute $A_L+B$ and $A_R+B$; check which of those $x$ is in; and recurse.  This will get you something like $O(n \lg^2 n)$.
D.W.
CC BY-SA 3.0
2015-07-21T16:23:42.517Z
@D.W. This can only find a witness for a single $x$, but we want a witness for each element in $A+B$. (my wording seems to be unclear, so I just updated the question)
Chao Xu
CC BY-SA 3.0
2015-07-21T17:28:20.053Z
But are you interested in O(n polylog n) solution?
Sariel Har-Peled
CC BY-SA 3.0
2015-07-21T17:41:06.750Z
@SarielHar-Peled yes, I'm also interested in deterministic $O(n polylog n)$ algorithm.
Chao Xu
CC BY-SA 3.0
2015-07-22T02:17:54.070Z
Sorry. I know only a randomized solution. Let me know if you want me to describe it.
Sariel Har-Peled
CC BY-SA 3.0
2015-07-22T04:54:24.770Z
@SarielHar-Peled, I don't know about Chao, but I'm intrigued -- I think that'd make an interesting and useful answer.  Thanks for your notes!
D.W.
CC BY-SA 3.0
2015-07-22T18:05:44.563Z
Hint: use a collection of random samples of the input of exponentially varying densities to make it likely that each sum has a unique representation in one of the samples.
David Eppstein
CC BY-SA 3.0
2015-07-22T23:55:37.793Z
@SarielHar-Peled yeah, I would like to see the randomized version, too.
Chao Xu
<convolution><fft>
Finding witness in minkowski sum of integers
Chao Xu
# Finding witness in minkowski sum of integers

(Asked by: username_0 on 2015-07-20)

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)> 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?

**Tags:** convolution, fft
> **Comments:**
> **username_1**: $O( n polylog n )$ is not especially hard.  
> **username_2**: You can use binary search.  e.g., partition $A$ into two roughly-equal-sized-sets $A_L,A_R$, and compute $A_L+B$ and $A_R+B$; check which of those $x$ is in; and recurse.  This will get you something like $O(n \lg^2 n)$.  
> **username_0**: @D.W. This can only find a witness for a single $x$, but we want a witness for each element in $A+B$. (my wording seems to be unclear, so I just updated the question)  
> **username_1**: But are you interested in O(n polylog n) solution?  
> **username_0**: @SarielHar-Peled yes, I'm also interested in deterministic $O(n polylog n)$ algorithm.  
> **username_1**: Sorry. I know only a randomized solution. Let me know if you want me to describe it.  
> **username_2**: @SarielHar-Peled, I don't know about Chao, but I'm intrigued -- I think that'd make an interesting and useful answer.  Thanks for your notes!  
> **username_3**: Hint: use a collection of random samples of the input of exponentially varying densities to make it likely that each sum has a unique representation in one of the samples.  
> **username_0**: @SarielHar-Peled yeah, I would like to see the randomized version, too.  

---

## 3 answers

### Answer by username_1 on 2015-07-23. Score: 11 | Accepted answer

Here I am explaining how to get $O(n \*\mathrm{polylog} n)$ randomized running time. We need a sequence of observations:

1. A *witness* of a value $v$ is a pair of numbers $(a,b) \in A \times B$ such that $a+b=v$. Let $P\_A(x) = \sum\_{i \in A} x^i$ and $P\_B(x)$ be defined analogously. Observe that the coefficient of $x^v$ in $P\_A(x) \* P\_B(x)$ is the number of witnesses there are for the value $v$.
2. Assume $v$ has a single witness $(a,b) \in A \times B$, and consider the the polynomial $Q\_A(x) = \sum\_{i \in A} i\*x^i$. Clearly, the coefficient of $x^v$ in $Q\_A(x)\*P\_B(x)$ is $a$, and as such we now know the pair $(a,v-a)$ and we are done.
3. So, we are done with the case that there is a single witness. So consider the case that $v$ has $k$ witnesses $(a\_1, b\_1),\ldots, (a\_k,b\_k)$. Let $i(k) = \lceil{\lg \sqrt{k}}\rceil$. Observe that $2^{i(k)-1} \leq \sqrt{k} \leq 2^{i(k)}$.
   Next, let $R\_j = (A\_j, B\_j)$, for $j=1,\ldots, m$, for $m=O(\log n)$ be random samples, such that each element of $A$ is choosen into $A\_i$ with probability $p = 1/2^{i(k)}$. The probability that $v$ has a single witness in $R\_j$ is $\alpha = \binom{k}{1}p^2 (1-p^2)^{k-1}$, since the witness are disjoint pairs of numbers (since the sum of each pair is $v$). It is easy to verify that $\alpha$ is a constant in $(0,1)$ independent of the value of $k$. As such, it must be, with high probability, that $v$ has a single witness in one of the samples $R\_1, \ldots, R\_{m}$. As such, by computing the two polynomials associated with with such sample, as described above, in $O(n \log n)$ time (per sample), using FFT, we can decide this in constant time.
4. We are almost done. Compute the above random samples for resolutions $i=1,\ldots, \lceil\lg n\rceil$. For each such resolution compute the random samples and associated polynomials. Also, compute the associated polynomial for $A$ and $B$. This preprocessing naively takes $O(n \log^3 n)$, but I suspect that being slightly more careful a $\log n$ factor should be removable.
5. The algorithm: For every value $v$, compute how many witness, say k, it has in constant time, by consulting the polynomial $Q\_A(x)\*P\_B(x)$. Next, go to the relevant data-structure for $i(k)$. Then, it finds the random sample that has it as a single witness, and it extract the pair that is this witness in constant time.
6. Strangely enough, the preprocessing time is $O(n \log^3 n)$, but the expected time to find the witness themselves take only $O(n)$ time, since one can stop the search as soon as one find a witness. This suggests that this algorithm should be improveable. In particular, for $i(k) \ll \lg n$, the polynomials generated are very sparse, and one should be able to do much faster FFT.


---

### Answer by username_3 on 2015-07-23. Score: 12

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.

> **Comments:**
> **username_1**: Ha ha ;). I was in the middle of writing it, and then went to lunch...  

---

### Answer by username_0 on 2015-08-05. Score: 5

This answer gives a determinstic $O(n~\mathrm{polylog} n)$ algorithm.

It appears that Sariel and David's algorithm can be derandomized through an [approach similar to this paper](http://www.tau.ac.il/~nogaa/PDFS/witf8.pdf). [2] While going through the process I found there is a more general problem that implies this result.

> **The $k$-reconstruction problem**
>
> There are hidden sets $S\_1,\ldots,S\_n \subset \{1,\ldots,m\}$, we have two
> oracles $Size$ and $Sum$ that take a query set $Q$.
>
> 1. $Size(Q)$ returns $(|S\_1\cap Q|,|S\_2\cap Q|,\ldots,|S\_n\cap Q|)$, the size of each intersection.
> 2. $Sum(Q)$ returns $(\sum\_{s\in S\_1\cap Q} s,\sum\_{s\in S\_2\cap Q} s,\ldots,\sum\_{s\in S\_n\cap Q} s)$, the sum of elements in each intersection.
>
> The $k$-reconstruction problem asks one to find $n$ subsets $S\_1',\ldots,S\_n'$ such
> that $S\_i'\subset S\_i$ and $|S\_i'|=\min(k,|S\_i|)$ for all $i$.

Let $f$ be the running time of calling the oracles, and assume $f=\Omega(m+n)$, then one can find the sets in deterministic $O(f k \log n~\mathrm{polylog}(m))$ time. [1]

Now we can reduce the finding witness problem to $1$-reconstruction problem. Here $S\_1,\ldots,S\_{2n}\subset \{1,\ldots,2n\}$ where $S\_i = \{a|a+b = i, a\in A, b\in B\}$.

Define the polynomials $\chi\_Q(x) = \sum\_{i \in Q} x^i$, $I\_Q(x) = \sum\_{i \in Q} i x^i$

The coefficient for $x^i$ in $\chi\_Q\chi\_B(x)$ is $|S\_i\cap Q|$ and in $I\_Q\chi\_B(x)$ is $\sum\_{s\in S\_i\cap Q} s$. Hence the oracles take $O(n\log n)$ time per call.

This gives us an $O(n~\mathrm{polylog}(n))$ time deterministic algorithm.

[1] Yonatan Aumann, Moshe Lewenstein, Noa Lewenstein, Dekel Tsur:
[Finding witnesses by peeling](http://www.cs.bgu.ac.il/~dekelts/publications/peeling.pdf). ACM Transactions on Algorithms 7(2): 24 (2011)

[2] Noga Alon, Moni Naor: [Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions](http://www.tau.ac.il/~nogaa/PDFS/witf8.pdf). Algorithmica 16(4-5) (1996)


---

