Fitting a C^m-smooth function to data I

Suppose we are given a finite subset E ⊂ R{double struck} ⁿ and a function f: E → R{double struck}. How to extend f to a C^m function F: R{double struck} ⁿ → R{double struck} with C^m norm of the smallest possible order of magnitude? In this paper and in [20] we tackle this question from the perspective of theoretical computer science. We exhibit algorithms for constructing such an extension function F, and for computing the order of magnitude of its C^m norm. The running time of our algorithms is never more than CN log N, where N is the cardinality of E and C is a constant depending only on m and n.