Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation

The authors of ``A note on the complexity of a phaseless polynomial interpolation’’ have shown that phaseless polynomial interpolation over $\mathbf{Q}$ is possible with $n+2$ points, where $n$ is the upper-bound on the degree of a polynomial. Nonetheless, their reconstruction algorithm and the method of adaptively choosing evaluation points are exponential time. On the other hand, they have also shown that given $2n+1$ points, the polynomial can be reconstructed in a polynomial time. A conjecture have been put forward, namely that the reconstruction problem from such $n+2$ points is exponential time. Moreover, a question about the number of points sufficient for polynomial time reconstruction have been posed. In this paper, we answer these questions – we show that (1) reconstruction problem from $2n-k$ for any constant $k$ is polynomial time, (2) reconstruction problem from $(1+c)n+2$ points for any constant $c\in [0,1)$ is NP-Complete, (3) evaluation points admitting a unique solution can be chosen in polynomial time.