Bennett, Charles H.
Vitanyi, Paul M.B.
Zurek, Wojciech H.
MetadataShow full item record
Citation (published version)CH Bennett, P Gacs, M Li, FMB Vitanyi, WH Zurek. 1998. "Information distance." IEEE Transactions On Information Theory, Volume 44, Issue 4, pp. 1407 - 1423 (17).
While Kolmogorov (1965) complexity is the accepted absolute measure of information content in an individual finite object, a similarly absolute notion is needed for the information distance between two individual objects, for example, two pictures. We give several natural definitions of a universal information metric, based on length of shortest programs for either ordinary computations or reversible (dissipationless) computations. It turns out that these definitions are equivalent up to an additive logarithmic term. We show that the information distance is a universal cognitive similarity distance. We investigate the maximal correlation of the shortest programs involved, the maximal uncorrelation of programs (a generalization of the Slepian-Wolf theorem of classical information theory), and the density properties of the discrete metric spaces induced by the information distances. A related distance measures the amount of nonreversibility of a computation. Using the physical theory of reversible computation, we give an appropriate (universal, antisymmetric, and transitive) measure of the thermodynamic work required to transform one object in another object by the most efficient process. Information distance between individual objects is needed in pattern recognition where one wants to express effective notions of "pattern similarity" or "cognitive similarity" between individual objects and in thermodynamics of computation where one wants to analyze the energy dissipation of a computation from a particular input to a particular output.
Showing items related by title, author, creator and subject.
Papagiannopoulou, Dimitra; Capodanno, Giuseppe; Moreshet, Tali; Herlihy, Maurice; Bahar, R Iris (ASSOC COMPUTING MACHINERY, 2015-05-01)Embedded systems are becoming increasingly common in everyday life and like their general-purpose counterparts, they have shifted towards shared memory multicore architectures. However, they are much more resource constrained, ...
Canetti, Ran; Goldreich, Oded; Halevi, Shai (Association for Computing Machinery, 2004)We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes that result from implementing the random oracle by so called “cryptographic ...
Granger, Brian R.; Chang, Yi-Chien; Wang, Yan; DeLisi, Charles; Segre, Daniel; Hu, Zhenjun (PUBLIC LIBRARY SCIENCE, 2016-04-01)The complexity of metabolic networks in microbial communities poses an unresolved visualization and interpretation challenge. We address this challenge in the newly expanded version of a software tool for the analysis of ...