Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Maybe I did not make myself clear. My question was "given $x_1,\ldots, x_n$, what the max-deg should be". We do not get to choose where $x_1,\ldots,x_n$ are, but $y_1,\ldots, y_n$ can be arbitrary.
I am not looking for the worse case scenorios. The answer should really depend on the configuration of $x_1,\ldots,x_k$. For example, if $x_1,\ldots,x_k$ are linearly independent, we only need max-deg to be 1.
