Geodesic
Superposition Problem of Continuous Functions. A Communication Approach
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 150 (2008) no. 1, pp. 5-18 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

In function theory the superposition problem is the problem of representing a continuous function $f(x_1,\dots,x_k)$ in $k$ variables as a composition of “simpler” functions. This problem stems from Hilbert's thirteenth problem. In computer science, good formalization for the notion of function composition is a formula. The article considers real-valued continuous functions in $k$ variables in the cube $[0,1]^k$ from the class $\mathcal H^k_{\omega_p}$ with a special modulus of continuity $\omega_p$ defined in the article. $\mathcal H^k_{\omega_p}$ is a superset of Lipschitz' class of functions. An explicit function $f\in\mathcal H^k_{\omega_p}$ is presented, which is hard in the sense that it cannot be represented in the following way as a formula: zero level (input) gates associated with variables $\{x_1,\dots,x_k\}$ (different input gates can be associated with the same variable $x_i\in\{x_1,\dots,x_k\}$), on the first level of the formula, arbitrary $t$ variable functions from $\mathcal H^t_{\omega_p}$ for $t are allowed, while the second (output) level may compute any Lipschitz' function. We apply communication complexity for constructing such a hard explicit function. Remarkably, one can show the existence of such a function using the “non constructive” proof method known in the function theory as Kolmogorov's entropy method.
Keywords: superposition problem of continuous functions, Lipschitz function, Dini function, discrete approximation of continuous functions, communication complexity. 
@article{UZKU_2008_150_1_a0,
     author = {F. M. Ablayev and S. G. Ablaeva},
     title = {Superposition {Problem} of {Continuous} {Functions.} {A~Communication} {Approach}},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {5--18},
     year = {2008},
     volume = {150},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2008_150_1_a0/}
}
TY  - JOUR
AU  - F. M. Ablayev
AU  - S. G. Ablaeva
TI  - Superposition Problem of Continuous Functions. A Communication Approach
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2008
SP  - 5
EP  - 18
VL  - 150
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/UZKU_2008_150_1_a0/
LA  - ru
ID  - UZKU_2008_150_1_a0
ER  - 
%0 Journal Article
%A F. M. Ablayev
%A S. G. Ablaeva
%T Superposition Problem of Continuous Functions. A Communication Approach
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2008
%P 5-18
%V 150
%N 1
%U http://geodesic.mathdoc.fr/item/UZKU_2008_150_1_a0/
%G ru
%F UZKU_2008_150_1_a0
F. M. Ablayev; S. G. Ablaeva. Superposition Problem of Continuous Functions. A Communication Approach. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 150 (2008) no. 1, pp. 5-18. http://geodesic.mathdoc.fr/item/UZKU_2008_150_1_a0/

[1] Hilbert D., “Mathematische Probleme”, Nachr. Akad. Wiss. Gottingen, 1900, 253–297 ; Gesammelete Abhandlungen, 3 (1935), 290–329 | Zbl

[2] P. S. Aleksandrov(red.), Problemy Gilberta, Nauka, M., 1969, 240 pp. | MR

[3] Vitushkin A. G., “K trinadtsatoi probleme Gilberta”, Dokl. AN SSSR, 95:4 (1954), 243–250

[4] Kolmogorov A. N., “Otsenki minimalnogo chisla elementov $\varepsilon$-setei v razlichnykh funktsionalnykh klassakh i ikh primenenie k voprosu o predstavimosti funktsii neskolkikh peremennykh superpozitsiyami funktsii menshego chisla peremennykh”, UMN, 10:1 (1955), 192–194 | Zbl

[5] Tikhomirov V. M., Nekotorye voprosy teorii priblizhenii, Izd-vo Mosk. un-ta, M., 1976, 304 pp. | MR

[6] Marchenkov S. S., “Ob odnom metode analiza superpozitsii nepreryvnykh funktsii”, Problemy kibernetiki, 37 (1980), 5–17 | MR | Zbl

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

[8] Gashkov S. B., Slozhnost priblizhennogo vychisleniya deistvitelnykh chisel, nepreryvnykh funktsii i lineinykh funktsionalov, Avtoref. dis. $\ldots$ d-ra fiz.-matem. nauk, Mosk. gos. un-t, M., 1992

[9] Yao A., “Some Complexity Questions Related to Distributive Computing”, Proc. of the 11th ACM Symposium on the Theory of Computing, 1979, 209–213

[10] Kolmogorov A. N., “Razlichnye podkhody k otsenke trudnosti priblizhennogo zadaniya i vychisleniya funktsii”, Proc. of Internat. Congress of Mathrmaticians (1962), Stockholm, 1963, 352–356 | MR

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

[12] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, M., 1986, 384 pp. | MR

[13] Timan A. F., Teoriya priblizhenii funktsii deistvitelnogo peremennogo, Nauka, M., 1960, 624 pp.

[14] Arnold V. I., “O funktsiyakh trekh peremennykh”, Dokl. AN SSSR, 114:4 (1957), 679–681 | MR

[15] Kolmogorov A. N., “O predstavlenii nepreryvnykh funktsii neskolkikh peremennykh v vide superpozitsii nepreryvnykh funktsii odnogo peremennogo i slozheniya”, Dokl. AN SSSR, 114:5 (1957), 953–956 | MR

[16] Lorentz G., “Metric Entropy, Widths and Superpositions Functions”, Amer. Math. Monthly, 69:6 (1962), 469–485 | DOI | MR | Zbl