Richard M. Karp, Raymond E. Miller
Journal of Computer and System Sciences
Our topic is the uniform approximation of xk by polynomials of degree n (n<k) on the interval [-1, 1]. Our major result indicates that good approximation is possible when k is much smaller than n2 and not possible otherwise. Indeed, we show that the approximation error is of the exact order of magnitude of a quantity, pk,n, which can be identified with a certain probability. The number pk,n is in fact the probability that when a (fair) coin is tossed k times the magnitude of the difference between the number of heads and the number of tails exceeds n. © 1976 Birkhäuser Verlag.
Richard M. Karp, Raymond E. Miller
Journal of Computer and System Sciences
Imran Nasim, Michael E. Henderson
Mathematics
Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum
Andrew Skumanich
SPIE Optics Quebec 1993