Complexity of finite sequences of zeros and ones and geometry of finite spaces of functions

The sequence 001 001 001 001 is simpler than 01 001 0111 001. We present a formal mathematical theory that gives an exact meaning to the preceding (intuitively clear) statement. Supported in part by the RFBR (Grant No. 05-01-00104). Read at the Moscow Mathematical Society meeting 22 November 2005, homepage: .     

有预算限制的最大多种物资流问题

研究有预算限制的最大多种物资流问题,给出了这个问题的不依赖物资数k的全多项式时间近似算法,其算法复杂性是O~(-ε2m2).同时,利用有预算限制的最大多种物资流问题的研究结果,我们也得到了费用最小的最大多种物资流问题的近似算法和算法复杂性.     

What is the complexity of a distributed computing system?

Distributed computing systems are becoming bigger and more complex. Although the complexity of large‐scale distributed systems has been acknowledged to be an important challenge, there has not been much work in defining or measuring system complexity. Thus, today, it is difficult to compare the complexities of different systems, or to state that one system is easier to program, to manage, or to use than another. In this article, we try to understand the factors that cause computing systems to appear very complex to people. We define different aspects of system complexity and propose metrics for measuring these aspects. We also show how these aspects affect different kinds of people—viz. developers, administrators, and end‐users. On the basis of the aspects and metrics of complexity that we identify, we propose general guidelines that can help reduce the complexity of systems. © 2007 Wiley Periodicals, Inc. Complexity 12: 37–45, 2007     

Approximation by Conic Splines

We show that the complexity of a parabolic or conic spline approximating a sufficiently smooth curve with non-vanishing curvature to within Hausdorff distance ɛ is c ₁ɛ^−1/4 + O(1), if the spline consists of parabolic arcs, and c ₂ɛ^−1/5 + O(1), if it is composed of general conic arcs of varying type. The constants c ₁ and c ₂ are expressed in the Euclidean and affine curvature of the curve. We also show that the Hausdorff distance between a curve and an optimal conic arc tangent at its endpoints is increasing with its arc length, provided the affine curvature along the arc is monotone. This property yields a simple bisection algorithm for the computation of an optimal parabolic or conic spline. The research of SG and GV was partially supported by grant 6413 of the European Commission to the IST-2002 FET-Open project Algorithms for Complex Shapes in the Sixth Framework Program.     

C_0复杂度的改进及其在证券市场中的应用

系统地分析了Lemple-Ziv复杂性度量方法的应用过程中,将实际信号(时间序列)转变成符号序列的诸多方法中存在的一些问题,提出了更合理兼容法.该方法可以有效地刻划各种时间序列的复杂度.文章最后动态地分析了中国证券市场的复杂性.     

Simple Explanation of the No-Free-Lunch Theorem and Its Implications

The no-free-lunch theorem of optimization (NFLT) is an impossibility theorem telling us that a general-purpose, universal optimization strategy is impossible. The only way one strategy can outperform another is if it is specialized to the structure of the specific problem under consideration. Since optimization is a central human activity, an appreciation of the NFLT and its consequences is essential. In this paper, we present a framework for conceptualizing optimization that leads to a simple but rigorous explanation of the NFLT and its implications.     

Spatiotemporal and statistical symmetries

The notion of symmetries, either statistical or deterministic, can be useful for the characterization of complex systems and their bifurcations. In this paper, we investigate the connection between the (microscopic) spatiotemporal symmetries of a space-time functionu(x, t), on the one hand, and the (macroscopic) symmetries of statistical quantities such as the spatial (resp. temporal) two-point correlations and the spatial (resp. temporal) average, on the other hand. We show, how, under certain conditions, these symmetries are related to the symmetries of the orbits described byu(x, t) in the characteristic (phase) spaces. We also determine the largest group of spatiotemporal symmetries (in the sense introduced in our earlier work) satisfied by a given space-time functionu(x, t) and indicate how to extract the subgroups of point symmetries, namely those directly implemented on the space and time variables. Conversely, we determine all the functions invariant by a given space-time symmetry group. Finally, we illustrate all the previous points with specific examples.     

Discrete symmetry groups of vertex models in statistical mechanics

We analyze discrete symmetry groups of vertex models in lattice statistical mechanics represented as groups of birational transformations. They can be seen as generated by involutions corresponding respectively to two kinds of transformations onq×q matrices: the inversion of theq×q matrix and an (involutive) permutation of the entries of the matrix. We show that the analysis of the factorizations of the iterations of these transformations is a precious tool in the study of lattice models in statistical mechanics. This approach enables one to analyze two-dimensionalq ⁴-state vertex models as simply as three-dimensional vertex models, or higher-dimensional vertex models. Various examples of birational symmetries of vertex models are analyzed. A particular emphasis is devoted to a three-dimensional vertex model, the 64-state cubic vertex model, which exhibits a polynomial growth of the complexity of the calculations. A subcase of this general model is seen to yield integrable recursion relations. We also concentrate on a specific two-dimensional vertex model to see how the generic exponential growth of the calculations reduces to a polynomial growth when the model becomes Yang-Baxter integrable. It is also underlined that a polynomial growth of the complexity of these iterations can occur even for transformations yielding algebraic surfaces, or higher-dimensional algebraic varieties.     

Quantum Pseudo-Telepathy

Quantum information processing is at the crossroads of physics, mathematics and computer science. It is concerned with what we can and cannot do with quantum information that goes beyond the abilities of classical information processing devices. Communication complexity is an area of classical computer science that aims at quantifying the amount of communication necessary to solve distributed computational problems. Quantum communication complexity uses quantum mechanics to reduce the amount of communication that would be classically required. Pseudo-telepathy is a surprising application of quantum information processing to communication complexity. Thanks to entanglement, perhaps the most nonclassical manifestation of quantum mechanics, two or more quantum players can accomplish a distributed task with no need for communication whatsoever, which would be an impossible feat for classical players. After a detailed overview of the principle and purpose of pseudo-telepathy, we present a survey of recent and not-so-recent work on the subject. In particular, we describe and analyse all the pseudo-telepathy games currently known to the authors. Supported in Part by Canada’s Natural Sciences and Engineering Research Council (NSERC), the Canada Research Chair programme and the Canadian Institute for Advanced Research (CIAR). Supported in part by a scholarship from Canada’s NSERC. Supported in part by Canada’s NSERC Québec’s Fonds de recherche sur la nature et les technologies (FQRNT), the CIAR and the Mathematics of Information Technology and Complex Systems Network (MITACS).     

C0复杂度的数学基础

对于许多同时具有强烈非线性和非平稳性的连续生物医学信号来说，计算其复杂度往往要求：1）在数据长度比较短的情况下也可以得出比较鲁棒的估计值；2）无需对原始信号作像二值化这样的过分的粗粒化，我们以前所提出的C0复杂度就是这样的一种度量，但是这种度量缺乏严格的数学基础，因而影响到它的应用，提出了一种改进形式，并严格证明了它的重要性质。从而表明这个量在一定条件下可以作为时间序列随机程度的指标，因而在随机性复杂度的意义下也可作为复杂性的一个定量指标，由于这个量有计算速度快的优点，因此特别适合于一些需要大量计算复杂度的场合，例如计算长时间过程中滑动窗口中复杂度的动态变化。