<p>I think your question is closely related to the <em>set reconciliation problem</em>, which is solved in this paper: <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.5338" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.5338</a></p>

<p>The problem of set reconciliation is to given two sets $A, B \subseteq [n]$ find $A \backslash B$ and $B \backslash A$ with as less communication as possible. If $B = [n]$, then you just need to find $\bar A$. Authors provide an algorithm with $O(k \log n)$ communication complexity.</p>

<p>Basic idea of the algorithm is to find small prime number $p$ greater than $4n$ and compute next two polynomials $\chi_A(x) = \prod_{a\in A} (x - a)$ and $\chi_B(x) = \prod_{b \in B} (x - b)$ in $\mathbb{F}_p$ on $2 \cdot k$ different points.</p>

<p>It can be easily shown that $$\frac{\chi_A}{\chi_B} = \frac{\chi_{A \cap B} \cdot \chi_{A \backslash B}}{\chi_{A \cap B} \cdot \chi_{B \backslash A}} = \frac{ \chi_{A \backslash B}}{ \chi_{B \backslash A}}.$$</p>

<p>If you compute these polynomials in non-zero points (for example, greater than $n$), then you obtain $2 \cdot k$ equations of the form
$$
\chi_{A \backslash B}(x_i) \cdot b_i = \chi_{B \backslash A} \cdot a_i,
$$
where $a_i$ and $b_i$ are corresponding values of $\chi_A$ and $\chi_B$ at $x_i$.</p>

<p>System of $2k$ equations with $2k$ variables over field $\mathbb{F}_p$ can be easily solved. The last thing is to factorize polynomials. The authors provide easy algorithm for this case.</p>

<p>Turning back to your first question $\chi_{\bar S}(x)$ can be expressed with your $s_i$'s for $i$ from $0$ to $k$.</p>

CC BY-SA 3.0
2014-12-24T16:41:39.227Z
I hadn't thought about the fact that $\chi_{\bar S}(x)$ could be expressed with the sums-of-powers polynomials I asked about. I was aware of the Minsky et al. paper but I was trying to understand another way to achieve the same goal without having to do the polynomial factorizing.
jbapple
CC BY-SA 3.0
2014-12-24T18:53:31.033Z
Yeap, all you need is http://en.wikipedia.org/wiki/Power_sum_symmetric_polynomial Coefficients of $\chi$ will be values of elementary symmetric polynomials.
Vsevolod Oparin
CC BY-SA 3.0
2014-12-24T15:49:23.870Z
2014-12-24T15:49:23.870Z
Vsevolod Oparin
<p>What is the complexity of calculating the values of the integers $x_i$, where $0 \leq x_1 &lt; x_2 &lt; \dots &lt; x_k &lt; n$, given only the values $s_m = \sum_{i=1}^k x_i^m$? for $1 \leq m \leq k$?</p>

<p>If this can be solved in $f(n,k)$ space, it can be used to solve the following problem:</p>

<p>Given $S \subset \mathbb{Z}_n$ where $|S| = n-k$, determine $\mathbb{Z}_n \backslash S$ in $\tilde O(f(n,k))$ space.</p>

<p>This is done by calculating $\sum_{s \in S} s^i$ for $1 \leq i \leq k$ and $\sum_{s \in \mathbb{Z}_n} s^i$ for $1 \leq i \leq k$.</p>

<ds.algorithms><algebra><nt.number-theory><comp-number-theory>
Solving a system of sums-of-powers polynomials
jbapple
# Solving a system of sums-of-powers polynomials

(Asked by: username_0 on 2014-12-24)

What is the complexity of calculating the values of the integers $x\_i$, where $0 \leq x\_1 < x\_2 < \dots < x\_k < n$, given only the values $s\_m = \sum\_{i=1}^k x\_i^m$? for $1 \leq m \leq k$?

If this can be solved in $f(n,k)$ space, it can be used to solve the following problem:

Given $S \subset \mathbb{Z}\_n$ where $|S| = n-k$, determine $\mathbb{Z}\_n \backslash S$ in $\tilde O(f(n,k))$ space.

This is done by calculating $\sum\_{s \in S} s^i$ for $1 \leq i \leq k$ and $\sum\_{s \in \mathbb{Z}\_n} s^i$ for $1 \leq i \leq k$.

**Tags:** ds.algorithms, algebra, nt.number-theory, comp-number-theory

---

## 1 answers

### Answer by username_1 on 2014-12-24. Score: 3

I think your question is closely related to the *set reconciliation problem*, which is solved in this paper: <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.5338>

The problem of set reconciliation is to given two sets $A, B \subseteq [n]$ find $A \backslash B$ and $B \backslash A$ with as less communication as possible. If $B = [n]$, then you just need to find $\bar A$. Authors provide an algorithm with $O(k \log n)$ communication complexity.

Basic idea of the algorithm is to find small prime number $p$ greater than $4n$ and compute next two polynomials $\chi\_A(x) = \prod\_{a\in A} (x - a)$ and $\chi\_B(x) = \prod\_{b \in B} (x - b)$ in $\mathbb{F}\_p$ on $2 \cdot k$ different points.

It can be easily shown that $$\frac{\chi\_A}{\chi\_B} = \frac{\chi\_{A \cap B} \cdot \chi\_{A \backslash B}}{\chi\_{A \cap B} \cdot \chi\_{B \backslash A}} = \frac{ \chi\_{A \backslash B}}{ \chi\_{B \backslash A}}.$$

If you compute these polynomials in non-zero points (for example, greater than $n$), then you obtain $2 \cdot k$ equations of the form
$$
\chi\_{A \backslash B}(x\_i) \cdot b\_i = \chi\_{B \backslash A} \cdot a\_i,
$$
where $a\_i$ and $b\_i$ are corresponding values of $\chi\_A$ and $\chi\_B$ at $x\_i$.

System of $2k$ equations with $2k$ variables over field $\mathbb{F}\_p$ can be easily solved. The last thing is to factorize polynomials. The authors provide easy algorithm for this case.

Turning back to your first question $\chi\_{\bar S}(x)$ can be expressed with your $s\_i$'s for $i$ from $0$ to $k$.

> **Comments:**
> **username_0**: I hadn't thought about the fact that $\chi_{\bar S}(x)$ could be expressed with the sums-of-powers polynomials I asked about. I was aware of the Minsky et al. paper but I was trying to understand another way to achieve the same goal without having to do the polynomial factorizing.  
> **username_1**: Yeap, all you need is http://en.wikipedia.org/wiki/Power_sum_symmetric_polynomial Coefficients of $\chi$ will be values of elementary symmetric polynomials.  

---

