Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
For researchers in computational complexity and signal processing, this paper provides tight complexity boundaries for phaseless polynomial interpolation, settling open conjectures.
The paper resolves the complexity of phaseless polynomial interpolation, showing that reconstruction from 2n-k points (constant k) is polynomial-time, while from (1+c)n+2 points (c in [0,1)) is NP-complete, and that evaluation points for unique solution can be chosen in polynomial time.
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.