Geodesic
Complexity of Approximate Realizations of Lipschitz Functions by Schemes in Continuous Bases
Matematičeskie zametki, Tome 92 (2012) no. 1, pp. 27-43.

Voir la notice de l'article provenant de la source Math-Net.Ru

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,\quad |x|,\quad 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{\varepsilon})$, where $\varepsilon$ is the accuracy of the approximation. This estimate of complexity, is in general, order-sharp.
Keywords: Lipschitz function, (Lipshitz) continuous basis, Lipschitz condition, complexity of the approximate realization of functions, polynomial basis. 
@article{MZM_2012_92_1_a2,
     author = {Ya. V. Vegner and S. B. Gashkov},
     title = {Complexity of {Approximate} {Realizations} of {Lipschitz} {Functions} by {Schemes} in {Continuous} {Bases}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {27--43},
     publisher = {mathdoc},
     volume = {92},
     number = {1},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2012_92_1_a2/}
}
TY  - JOUR
AU  - Ya. V. Vegner
AU  - S. B. Gashkov
TI  - Complexity of Approximate Realizations of Lipschitz Functions by Schemes in Continuous Bases
JO  - Matematičeskie zametki
PY  - 2012
SP  - 27
EP  - 43
VL  - 92
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2012_92_1_a2/
LA  - ru
ID  - MZM_2012_92_1_a2
ER  - 
%0 Journal Article
%A Ya. V. Vegner
%A S. B. Gashkov
%T Complexity of Approximate Realizations of Lipschitz Functions by Schemes in Continuous Bases
%J Matematičeskie zametki
%D 2012
%P 27-43
%V 92
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2012_92_1_a2/
%G ru
%F MZM_2012_92_1_a2
Ya. V. Vegner; S. B. Gashkov. Complexity of Approximate Realizations of Lipschitz Functions by Schemes in Continuous Bases. Matematičeskie zametki, Tome 92 (2012) no. 1, pp. 27-43. http://geodesic.mathdoc.fr/item/MZM_2012_92_1_a2/

[1] S. B. Gashkov, “O slozhnosti priblizhennoi realizatsii nepreryvnykh funktsii skhemami i formulami v polinomialnykh i nekotorykh drugikh bazisa”, Matematicheskie voprosy kibernetiki, 5, Nauka, M., 1994, 144–207 | MR | Zbl

[2] S. B. Gashkov, “O slozhnosti priblizhennoi realizatsii funktsionalnykh kompaktov v nekotorykh prostranstvakh i o suschestvovanii funktsii s zadannoi po poryadku slozhnostyu”, Fundament. i prikl. matem., 2:3 (1996), 675–774 | MR | Zbl

[3] O. B. Lupanov, Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo Mosk. un-ta, M., 1984

[4] A. N. Kolmogorov, V. M. Tikhomirov, “$\varepsilon$-entropiya i $\varepsilon$-emkost mnozhestv v funktsionalnykh prostranstvakh”, UMN, 14:2 (1959), 3–86 | MR | Zbl

[5] S. B. Gashkov, “O slozhnosti priblizhennoi realizatsii analiticheskikh funktsii skhemami i formulami”, Vestn. Mosk. un-ta. Ser. 1. Matem., mekh., 1983, no. 4, 36–43 | MR | Zbl

[6] S. B. Gashkov, “O slozhnosti priblizhennoi realizatsii nekotorykh klassov differentsiruemykh funktsii odnoi peremennoi skhemami iz funktsionalnykh elementov”, Vestn. Mosk. un-ta. Ser. 1. Matem., mekh., 1984, no. 3, 35–41 | MR | Zbl

[7] S. B. Gashkov, “O slozhnosti priblizhennoi realizatsii nekotorykh klassov differentsiruemykh funktsii odnoi peremennoi formulami v nepreryvnykh bazisakh”, Vestn. Mosk. un-ta. Ser. 1. Matem., mekh., 1984, no. 6, 53–58 | MR | Zbl

[8] S. B. Gashkov, “O slozhnosti priblizhennoi realizatsii nekotorykh klassov differentsiruemykh funktsii mnogikh peremennykh pri pomoschi skhem i formul v nekotorykh bazisakh, sostoyaschikh iz nepreryvnykh funktsii”, Vestn. Mosk. un-ta. Ser. 1. Matem., mekh., 1986, no. 3, 48–57 | MR | Zbl

[9] S. B. Gashkov, “O slozhnosti priblizhennoi realizatsii nepreryvnykh funktsii i o kontinualnykh analogakh effekta Shennona”, Vestn. Mosk. un-ta. Ser. 1. Matem., mekh., 1986, no. 6, 25–33 | MR | Zbl

[10] S. B. Gashkov, “On the complexity of approximate realization of continuous functions by schemes and formulas in continuous bases”, Fundamentals of Computation Theory, Lecture Notes in Comput. Sci., 278, Springer-verlag, 140–144 | DOI | Zbl

[11] S. B. Gashkov, “O slozhnosti priblizhennoi realizatsii funktsii, udovletvoryayuschikh usloviyu Lipshitsa, skhemami v nepreryvnykh bazisakh”, Matem. zametki, 43:4 (1988), 543–557 | MR | Zbl

[12] S. B. Gashkov, “Slozhnost realizatsii bulevykh funktsii skhemami iz funktsionalnykh elementov i formulami v bazisakh, elementy kotorykh realizuyut nepreryvnye funktsii”, Problemy kibernetiki, 37 (1980), 57–118 | MR | Zbl

[13] I. G. Petrovskii, Izbrannye trudy. Sistemy uravnenii s chastnymi proizvodnymi. Algebraicheskaya geometriya, Nauka, M., 1986 | MR | Zbl

[14] A. G. Vitushkin, Otsenka slozhnosti zadachi tabulirovaniya, Sovremennye problemy matematiki, Fizmatgiz, M., 1959 | MR | Zbl

[15] M. Ben-Or, “Lower bounds for algebraic computation trees”, Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, ACM, New York, 1983, 80–86 | DOI

[16] J. Milnor, “On the Betti numbers of real varieties”, Proc. Amer. Math. Soc., 15, 1964, 275–280 | MR | Zbl

[17] S. B. Gashkov, “O slozhnosti priblizhennoi realizatsii nekotorykh klassicheskikh funktsii”, Diskretnyi analiz, Tr. in-ta matem. SO RAN, 127, In-t matem. SO RAN, Novosibirsk, 1994, 14–33 | MR | Zbl

[18] A. N. Kolmogorov, “Razlichnye podkhody k otsenke trudnosti priblizhennogo zadaniya i vychisleniya funktsii”, Proc. Internat. Congr. Mathematicians (Stockholm, 1962), Inst. Mittag-Leffler, Djursholm, 1963, 351–356 | MR | Zbl

[19] E. A. Asarin, “O slozhnosti ravnomernykh priblizhenii nepreryvnykh funktsii”, UMN, 39:3 (1984), 157–169 | MR | Zbl

[20] S. B. Gashkov, Ya. V. Vegner, “O slozhnosti priblizhennoi realizatsii lipshitsevykh funktsii”, Vestn. Mosk. un-ta. Ser. 1. Matem., mekh., 2008, no. 4, 49–51

[21] G. Turán, F. Vatan, “On the computation of Boolean functions by analog circuits of bounded fan-in”, J. Comput. System Sci., 54:1 (1997), 199–212 | DOI | MR | Zbl