4 citations · 4 across the 1 of their papers we have counts for
Showing 2001Show all
2 papers · 1 filter
math.CO2001
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…
cs.DC2001
Randomized Two-Process Wait-Free Test-and-Set
John Tromp, Paul Vitanyi
We present the first explicit, and currently simplest, randomized algorithm for 2-process wait-free test-and-set. It is implemented with two 4-valued single writer single reader at…