62 citations · 63 across the 4 of their papers we have counts for
Showing 2002Show all
3 papers · 1 filter
cs.CC2002
Kolmogorov's Structure Functions and Model Selection
Nikolai Vereshchagin, Paul Vitanyi
In 1974 Kolmogorov proposed a non-probabilistic approach to statistics and model selection. Let data be finite binary strings and models be finite sets of binary strings. Consider…
cs.DC2002
On the Importance of Having an Identity or, is Consensus really Universal?
Harry Buhrman, Alessandro Panconesi, Riccardo Silvestri +1
We show that Naming-- the existence of distinct IDs known to all-- is a hidden but necessary assumption of Herlihy's universality result for Consensus. We then show in a very preci…
cs.DC2002
Simple Optimal Wait-free Multireader Registers
Paul Vitanyi
Multireader shared registers are basic objects used as communication medium in asynchronous concurrent computation. We propose a surprisingly simple and natural scheme to obtain se…