Abstract

Abstract
There are two principal notions of security for cryptographic systems. For a few systems, they can be proven to have perfect secrecy against an opponent with unlimited computational power, in terms of information theory. However, the security of most systems, including public key cryptosystems, is based on complexity theoretic assumptions. In both cases there is an implicit notion of average-case analysis. In the case of conditional security, the underlying assumption is usually average-case, not worst case hardness. And for unconditional security, entropy itself is an average case notion of encoding length. Kolmogorov complexity (the size of the smallest program that generates a string) is a rigorous measure of the amount of information, or randomness, in an individual string x. By considering the time-bounded Kolmogorov complexity (program limited to run in time t(vertical bar x vertical bar)) we can take into account the computational difficulty of extracting information. We present a new notion of security based on Kolmogorov complexity. The first goal is to provide a formal definition of what it means for an individual instance to be secure. The second goal is to bridge the gap between information theoretic security, and computational security, by using time-bounded Kolmogorov complexity. In this paper, we lay the groundwork of the study of cryptosystems from the point of view of security of individual instances by considering three types of information-theoretically secure cryptographic systems: cipher systems (such as the one-time pad), threshold secret sharing, and authentication schemes.

Abstract
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.

Abstract
PURPOSE: Disagreement on the interpretation of diagnostic tests and clinical decisions remains an important problem in medicine. As no strategy to assess agreement seems to be fail-safe to compare the degree of agreement, or disagreement, we propose a new information-based approach to assess disagreement. METHODS: The sum over all logarithms of possible outcomes of a variable is a valid measure of the amount of information contained in the variable. The proposed measure is based on the amount of information contained in the differences between two observations. This measure is normalized and satisfies the flowing properties: it is a metric, scaled invariant and it has differential weighting. RESULTS: Two real examples and a simulation were used to illustrate the usefulness of the proposed measure to compare the degree of disagreement. CONCLUSIONS: Used as complement to the existing methods, we believe our approach can be useful to compare the degree of disagreement among different populations. Ann Epidemiol 2010;20:555-561.

Abstract
Fetal heart rate (FHR) monitoring is widely used regarding the detection of fetuses in danger of death or damage. Thirty one FHR tracings acquired in the antepartum period were clustered by compression in order to identify abnormal ones. A recently introduced approach based on algorithmic information theory was used. The new method can mine patterns in completely different areas, without domain-specific parameters to set, and does not require specific background knowledge. At the highest level the FHR tracings were clustered according to an unanticipated feature, namely the technology used in signal acquisition. At the lower levels all tracings with abnormal or suspicious patterns were clustered together, independently of the technology used.

Abstract
Kolmogorov Complexity measures the amount of information in a string by the size of the smallest program that generates that string. Antunes, Fortnow, van Melkebeek, and Vinodchandran captured the notion of useful information by computational depth, the difference between the polynomial-time-bounded Kolmogorov complexity and traditional Kolmogorov complexity. We show unconditionally how to probabilistically find satisfying assignments for formulas that have at least one assignment of logarithmic depth. The converse holds under a standard hardness assumption though fails if BPP = FewP = EXP. We also prove that assuming the existence of good pseudorandom generators one cannot increase the depth of a string efficiently.