Professor D. Boris Darkhovsky

Recent The E-Complexity of Finite-Dimensional Continuous Maps


Professor D. Boris Darkhovsky

co-author Professor Alexandra Piryatinska

Chief Researcher, Institute for Systems Analysis

Federal Research Center "Computer Science and Control" of Russian Academy of Sciences

Moscow, Russia


Abstract: A concept of the ϵ-complexity of finite-dimensional continuous maps is proposed. This concept is in line with the general idea of A.N.Kolmogorov (but it is not confined to it) on the measurement of the "complexity" of an object. It is proved that the ϵ-complexity of “almost any" continuous map satisfying Holder condition can be effectively characterized by the pair of real numbers. The result is generalized on the maps given by their values on some uniform grid. The ϵ-complexity is the foundation of model-free methodology of segmentation and classification for data of arbitrary nature.

Brief Biography of the Speaker:Boris Darkhovsky has got MS degree in Mathematics at Moscow State University (Russia). He also has a PhD degree in Automatic Control and Dr. Sc. Degree (habilitation) in Mathematics. Currently, he is a Chief Researcher at Institute for Systems Analysis, FRC "Computer Science and Control" of Russian Academy of Sciences, Moscow, Russia. He also is a Professor in the Department of Control and Applied Mathematics at Moscow Institute of Physics and Technology, as well as a Professor in the Department of Computer Science at Higher School of Economics, Moscow, Russia. He was a visiting professor at University I (Lille, France), Mainz University (Germany), University of Troyes (France), University of New South Walles (Sydney, Australia), Indian Institute of Technology (Kanpur, India). His research interests are in different areas of automatic control, optimization theory, and mathematical statistics. One can mention his results on the development of the locally optimal method for automatic control of multidimensional nonlinear dynamical systems and the development of the theory of necessary and sufficient optimality conditions for semi-infinite mathematical programming problems. In mathematical statistics, his primary results are in the theory of change-point detection problems for random sequences and fields (which are presented in two books, Kluwer 1993, Kluwer 2000). Also, he developed new approaches for the sequential testing of composite hypotheses and non-asymptotic minimax estimation of functionals in noise. Since 2001, Dr. Darkhovsky was interested in the problem: is it possible and how to measure a "complexity" of a continuous function, and more generally, continuous map. As a result, approximately by 2014, the first version of the theory of the epsilon-complexity of individual continuous function was constructed. Some results of this theory have been presented at International Congress of Mathematicians (2014) and European Congress of Mathematics (2016). This theory was developed in close collaboration with Dr. Alexandra Piryatinska (San Francisco State University). Based on this theory authors developed fundamentally novel, model-free methods for segmentation of (relatively long) vector time series and classification of (relatively short) vector time series of arbitrary nature.