1
$\begingroup$

Let $\mathbb{F}$ be a finite field and let $\boldsymbol{x} = (x_1, x_2, \dots, x_n)$ be $n$ pairwise distinct points in $\mathbb{F}$.

Given the vector $\boldsymbol{y} = (y_1, y_2, \dots, y_n)$, with $y_i \in \{0,1\}$, we can find a polynomial $p(x)$ such that $$p(x_i) = y_i,$$ for $i = 1, \dots, n$.

I recently discovered the DFT algorithm (here, the values $x_i$ are taken to be the powers of a primitive $n$-th root of unity) to perform this task in $\mathcal{O}(n \log n)$.

  1. There exists faster algorithms for the case where the evaluations $y_i$ are either $1$ or $0$?
  2. If not, there exists some trick to improve efficiency for this case?
Improve this question
$\endgroup$
1
  • $\begingroup$ If the set of $y_i$ for which $y_i = 1$ is sufficiently small, then you can do this quickly using Lagrange interpolation. More generally, if "most" of the $y_i$ values are equal to $0$ (without any constraint on what non-zero values $y_i$ can take), then Lagrange interpolation should be very fast. $\endgroup$ Commented Nov 23, 2021 at 16:36

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.