Consider a set of $N$ points $(x_i , y_i)$. I want to find a $d$ degree polynomial $P_d(x)$ that will minimize the error, $$ e_d = max_{i \in [N]} ~|P_d(x_i) - y_i| $$
The question I have is about upper bounds on the optimal value of $e_d$, i.e.
$$e_d^* = min_{P_d \in \Pi_d}~ max_{i \in [N]} ~|P_d(x_i) - y_i| . $$
where $\Pi_d$ is the set of degree $d$ polynomials. Obviously $e^*_N = 0$. But how does $e^*_d$ scale with general $d$?
Considering the practical importance of this question and also the considerable amount of work on polynomial approximation of functions I am guessing that this question has a well defined answer. But I haven't been able to find any good references for this.