Given a function f from {0,1,?,n} to some subset C of the real numbers, it is a well known fact that there exists a unique interpolation polynomial for f of degree at most n. A natural question is the following: for a restricted set C, how low can the degree of an interpolation polynomial for a non-constant function from {0,1,?,n} to C be? A first result for a question of that nature that appeared in the literature (in the paper “Polynomials with Two Values by Joachim von zur Gathen and James R. Roche) handled the case C={0,1}. In this thesis we study two natural generalizations. The first concerns the restriction C = {0,1,?,c} for some natural c that may depend on n. The second generalization deals with sets C which are finite subsets of the rational numbers, which does not depend on n. In both cases we give new lower bounds. We also simplify and generalize the known results for the case C={0,1}.