1.2k citations · 3.7k across the 62 of their papers we have counts for
3 papers · 1 filter
Kolmogorov Random Graphs and the Incompressibility Method
Harry Buhrman, Ming Li, John Tromp +1
We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressib…
Quantum fingerprinting
Harry Buhrman, Richard Cleve, John Watrous +1
Classical fingerprinting associates with each string a shorter string (its fingerprint), such that, with high probability, any two distinct strings can be distinguished by comparin…
Time and Space Bounds for Reversible Simulation
Harry Buhrman, J. Tromp, Paul Vitanyi
We prove a general upper bound on the tradeoff between time and space that suffices for the reversible simulation of irreversible computation. Previously, only simulations using ex…