Solving a system of sums-of-powers polynomials

Question

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$.

Answer 1

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$.