A Communication Approach to the Superposition Problem

• Autorzy: Ablayev F. , Ablayeva S.
• Języki publikacji: EN

Abstrakty

EN

In function theory the superposition problem is known as the problem of representing a continuous function f(x1, . . . , xk) in k variables as the composition of "simpler”"functions. This problem stems from the Hilbert’s thirteenth problem. In computer science good formalization for the notion of composition of functions is formula. In the paper we consider real-valued continuous functions in k variables in the cube [0, 1]k from the class [...] with ω_p a special modulus of continuity (measure the smoothness of a function) defined in the paper. [...] is a superset of Hölder class of functions. We present an explicit function [...] 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 {x1, . . . , xk} (different input gates can be associated with the same variable xi . {x1, . . . , xk}), on the first level of the formula, arbitrary number s ≥1 of t variable functions from [...] for t < k are allowed, while the second (output) level may compute any s variable H¨older function. We apply communication complexity for constructing such hard explicit function. Notice that one can show the existence of such function using the "non constructive" proof method known in function theory as Kolmogorov's entropy method.

Słowa kluczowe

EN

Hilbert 13th problem; superposition of continuous functions; communication complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 3
• Strony: 185--200
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Ablayev F.

autor

Ablayeva S.

• Department of Theoretical Cybernetics, Kazan State University, Kremlevskaia str. 18, Kazan, 42008, Russia,

Bibliografia

• [1] Ablayev, F., Ablayeva, S.: A Discrete Approximation and Communication Complexity Approach to the Superposition Problem, Electronic Colloquium in Computational Complexity, TR98-050, 1998.
• [2] Ablayev, F., Ablayeva, S.: A Discrete Approximation and Communication Complexity Approach to the Superposition Problem, Proc. Fundamentals of Computation Theory, (R. Freivalds, Ed.), LNCS 2138, Springer-Verlag, Berlin, 2001.
• [3] Arnold, V.: On functions of Three Variables, Dokladi Akademii Nauk, 114, 1958, 679-681.
• [4] Beiu, V., Zawadzki, A.: Why VLSI/NANO Library Design Should Use Kolmogorov's Superpositons, Proc. Nano and Giga Challenges in Microelectronic NGCM, 2004.
• [5] Beiu, V., Zawadski, A., Andonie, R., Aunet, S.: Using Kolmogorov Inspired Gates for Low Power Nanoelectronics, Proc. International Work-Conference on Artificial Neural Networks (J. Cabestany, A. Prieto, F. Herna'ndez Eds.) LNCS 3512, Springer-Verlag, Berlin, 2005.
• [6] Bläser, M., Vicari, E.: Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity, Proc. the 1st International Symposium on Algorithmic Game Theory (B. Monien, U. Schroeder Eds.) LNCS 4997 Springer-Verlag, Berlin, 2008.
• [7] Hansen, K., Lachish, O., Miltersen, P.: Hilbert's thirteenth problem and circuit complexity The 20th International Symposium on Algorithms and Complexity December 2009, (To appear in Proceedings)
• [8] Grigoriev, D.: Probabilisitc Communication Complexity Over the Reals, Computational Complexity Theoretical Computer Science, 17(536-548), 2008.
• [9] Hilbert,D.: Mathematische Probleme, Nachr. Akad. Wiss, Gottingen, 253-297, 1900.
• [10] Hromkovich, J.: Communication complexity and parallel computing, Speinger-Verlag, Berlin, 1997.
• [11] Jukna, S.: Entropy of operators or why matrix multiplication is hard for small depth circuits, Electronic Colloquium in Computational Complexity, TR08-019, 2008.
• [12] Kolmogorov, A.: On Representation of Continuous Functions of Several Variables by a superposition of Continuous Functions of one Variable and Sum Operation. Dokladi Akademii Nauk, 114, (953-956), 1957.
• [13] Kolmogorov, A.: Different approaches on the estimation of hardness of defining and computing of functions, Proc. of the International Congress of Mathematicians, Stockholm, (352-356), 1963.
• [14] Kushilevitz, E., Nisan, N.: Communication complexity, Cambridge University Press, 1997.
• [15] Lorentz, G.: Metric entropy and approximation Bulletin of American Mathematical Society 72, (903-937), 1966.
• [16] Marchenkov, S.: On One Method of Analysis of superpositions of Continuous Functions, Problemi Kibernetici, 37, (5-17), 1980.
• [17] Timan, A.: Theory of approximation of functions of a real variables, Oxford Pergammon Press, 1963.
• [18] Vitushkin, A.: On Representation of Functions by Means of Superpositions and Related Topics, L'Enseignement mathematique, 23, (255-320), 1977.
• [19] Yao, A.: Some Complexity Questions Related to Distributive Computing, Proc. of ACM Symposium on the Theory of Computing, 11, (209-213), 1979.