Complexity of approximate realizations of Lipschitz functions by schemes in continuous bases

What is it about?

We show that any function satisfying the Lipschitz condition on a given closed interval can be approximately computed by a scheme (nonbranching program) in the basis composed of functions x−y,|x|,x∗y=min(max(x,0),1)min(max(y,0),1), x−y,|x|,x∗y=min(max(x,0),1)min(max(y,0),1), and all constants from the closed interval [0, 1]; here the complexity of the scheme is O(1/\sqrt{ε}) , where ɛ is the accuracy of the approximation. This estimate of complexity, is in general, order-sharp.

Featured Image