4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – jbapple Dec 24 '14 at 16:41
  • 2
    $\begingroup$ Yeap, all you need is en.wikipedia.org/wiki/Power_sum_symmetric_polynomial Coefficients of $\chi$ will be values of elementary symmetric polynomials. $\endgroup$ – Vsevolod Oparin Dec 24 '14 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.