4 citations · 4 across the 1 of their papers we have counts for
5 papers
On the Complexity of Several Haplotyping Problems
Rudi Cilibrasi, Leo van Iersel, Steven Kelk +1
In this paper we present a collection of results pertaining to haplotyping. The first set of results concerns the combinatorial problem of reconstructing haplotypes from incomplete…
Limits of Rush Hour Logic Complexity
John Tromp, Rudi Cilibrasi
Rush Hour Logic was introduced in [Flake&Baum99] as a model of computation inspired by the ``Rush Hour'' toy puzzle, in which cars can move horizontally or vertically within a park…
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…
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…
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 `…