62 citations · 63 across the 4 of their papers we have counts for
6 papers · 1 filter
Three Approaches to the Quantitative Definition of Information in an Individual Pure Quantum State
Paul Vitanyi
In analogy of classical Kolmogorov complexity we develop a theory of the algorithmic information in bits contained in any one of continuously many pure quantum states: quantum Kolm…
Space-Efficient Routing Tables for Almost All Networks and the Incompressibility Method
Harry Buhrman, Jaap-Henk Hoepman, Paul Vitanyi
We use the incompressibility method based on Kolmogorov complexity to determine the total number of bits of routing information for almost all network topologies. In most models fo…
A Discipline of Evolutionary Programming
Paul Vitanyi
Genetic fitness optimization using small populations or small population updates across generations generally suffers from randomly diverging evolutions. We propose a notion of hig…
Mutual Search
Harry Buhrman, Matthew Franklin, Juan A. Garay +3
We introduce a search problem called ``mutual search'' where \agents, arbitrarily distributed over sites, are required to locate one another by posing queries of the form `…
The Average-Case Area of Heilbronn-Type Triangles
Tao Jiang, Ming Li, Paul Vitanyi
From among triangles with vertices chosen from points in the unit square, let be the one with the smallest area, and let be the area of . Heilbronn'…
Average-Case Complexity of Shellsort
Tao Jiang, Ming Li, Paul Vitanyi
We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a -pass Shellsort for any incremental…