Kolmogorov complexity and combinatorial methods in communication complexity

We introduce a method based on Kolmogorov complexity to prove lower bounds on communication complexity. The intuition behind our technique is close to information theoretic methods.We use Kolmogorov complexity for three different things: first, to give a general lower bound in terms of Kolmogorov mutual information; second, to prove an alternative to Yao’s minmax principle based on Kolmogorov complexity; and finally, to identify hard inputs.We show that our method implies the rectangle and corruption bounds, known to be closely related to the subdistribution bound. We apply our method to the hidden matching problem, a relation introduced to prove an exponential gap between quantum and classical communication. We then show that our method generalizes the VC dimension and shatter coefficient lower bounds. Finally, we compare one-way communication and simultaneous communication in the case of distributional communication complexity and improve the previous known result.     

Kolmogorov complexity of enumerating finite sets

Solovay [R.M. Solovay, On random R.E. sets, in: A.I. Arruda, N.C.A. da Costa, R. Chaqui (Eds.), Non-Classical Logics, Model Theory and Computability, North-Holland, Amsterdam, 1977, pp. 283-307] has proved that the minimal length of a program enumerating a set A is upper bounded by 3 times the negative logarithm of the probability that a random program will enumerate A. It is unknown whether one can replace the constant 3 by a smaller constant. In this paper, we show that the constant 3 can be replaced by the constant 2 for finite sets A.     

Constructive dimension equals Kolmogorov complexity

We derive the coincidence of Lutz's constructive dimension and Kolmogorov complexity for sets of infinite strings from Levin's early result on the existence of an optimal left computable cylindrical semi-measure M via simple calculations.     

On data mining,compression, and Kolmogorov complexity

Will we ever have a theory of data mining analogous to the relational algebra in databases? Why do we have so many clearly different clustering algorithms? Could data mining be automated? We show that the answer to all these questions is negative, because data mining is closely related to compression and Kolmogorov complexity; and the latter is undecidable. Therefore, data mining will always be an art, where our goal will be to find better models (patterns) that fit our datasets as best as possible.     

Kolmogorov random graphs only have trivial stable colorings

In this paper, we prove that random graphs only have trivial stable colorings. Our result improves Theorem 4.1 in [Proc. 20th IEEE Symp. on Foundations of Comput. Sci., 1979, pp. 39-46]. It can be viewed as an effective version of Corollary 2.13 in [SIAM J. Comput. 29 (2) (2000) 590-599]. As a byproduct, we also give an upper bound of the size of induced regular subgraphs in random graphs.     

Detecting Distributed Denial-of-Service Attacks Using Kolmogorov Complexity Metrics

This paper describes an approach to detecting distributed denial of service (DDoS) attacks that is based on fundamentals of Information Theory, specifically Kolmogorov Complexity. A theorem derived using principles of Kolmogorov Complexity states that the joint complexity measure of random strings is lower than the sum of the complexities of the individual strings when the strings exhibit some correlation. Furthermore, the joint complexity measure varies inversely with the amount of correlation. We propose a distributed active network-based algorithm that exploits this property to correlate arbitrary traffic flows in the network to detect possible denial-of-service attacks. One of the strengths of this algorithm is that it does not require special filtering rules and hence it can be used to detect any type of DDoS attack. We implement and investigate the performance of the algorithm in an active network. Our results show that DDoS attacks can be detected in a manner that is not sensitive to legitimate background traffic.This research has been funded by the Defense Advanced Research Projects Agency (DARPA) contract F30602-01-C-0182 and managed by the Air Force Research Laboratory (AFRL) Information Directorate.General Electric Global Research Center, Niskayuna, New York.     

Predictive complexity and information

The notions of predictive complexity and of corresponding amount of information are considered. Predictive complexity is a generalization of Kolmogorov complexity which bounds the ability of any algorithm to predict elements of a sequence of outcomes. We consider predictive complexity for a wide class of bounded loss functions which are generalizations of square-loss function. Relations between unconditional KG(x) and conditional KG(x|y) predictive complexities are studied. We define an algorithm which has some “expanding property”. It transforms with positive probability sequences of given predictive complexity into sequences of essentially bigger predictive complexity. A concept of amount of predictive information IG(y:x) is studied. We show that this information is noncommutative in a very strong sense and present asymptotic relations between values IG(y:x), IG(x:y), KG(x) and KG(y).     

NL-printable sets and nondeterministic Kolmogorov complexity

P-printable sets were defined by Hartmanis and Yesha and have been investigated by several researchers. The analogous notion of L-printable sets was defined by Fortnow et al.; both P-printability and L-printability were shown to be related to notions of resource-bounded Kolmogorov complexity. Nondeterministic logspace (NL)-printability was defined by Jenner and Kirsig, but some basic questions regarding this notion were left open. In this paper we answer a question of Jenner and Kirsig by providing a machine-based characterization of the NL-printable sets.     

Computational depth: Concept and applications

We introduce Computational Depth, a measure for the amount of “nonrandom” or “useful” information in a string by considering the difference of various Kolmogorov complexity measures. We investigate three instantiations of Computational Depth:

•$•$

Basic Computational Depth, a clean notion capturing the spirit of Bennett's Logical Depth. We show that a Turing machine M runs in time polynomial on average over the time-bounded universal distribution if and only if for all inputs x, M uses time exponential in the basic computational depth of x.     

Algorithmic randomness and monotone complexity on product space

We study algorithmic randomness and monotone complexity on product of the set of infinite binary sequences. We explore the following problems: monotone complexity on product space, Lambalgen’s theorem for correlated probability, classification of random sets by likelihood ratio tests, decomposition of complexity and independence, and Bayesian statistics for individual random sequences. Formerly Lambalgen’s theorem for correlated probability is shown under a uniform computability assumption in [H. Takahashi Inform. Compt. 2008]. In this paper we show the theorem without the assumption.     

混沌时间序列的Kolmogorov熵的应用研究

论文提出了一种在m维相空间中计算混沌时间序列的Kolmogorov熵的方法,以Rossler混沌系统和Lorenz混沌系统为例验证了算法的准确性,其仿真结果与系统本身具有基本相同的计算精度;分析了噪声对这种方法的影响,结果表明这种算法可以有效克服采样过程中常常出现的噪声对信号的干扰,得到较为满意的结果。将其应用于脑血管血流动力学中,得到了与理论分析相一致的结果。     

Depth as Randomness Deficiency

Depth of an object concerns a tradeoff between computation time and excess of program length over the shortest program length required to obtain the object. It gives an unconditional lower bound on the computation time from a given program in absence of auxiliary information. Variants known as logical depth and computational depth are expressed in Kolmogorov complexity theory. We derive quantitative relation between logical depth and computational depth and unify the different depth notions by relating them to A. Kolmogorov and L. Levin’s fruitful notion of randomness deficiency. Subsequently, we revisit the computational depth of infinite strings, study the notion of super deep sequences and relate it with other approaches.     

A finite difference method for a boundary value problem related to the Kolmogorov equation

We propose an explicit and an implicit difference scheme for a boundary value problem related to the Kolmogorov equation. Stability conditions and convergence results are given.