39 citations · 89 across the 25 of their papers we have counts for
10 papers · 1 filter
When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument
Johannes Lengler, Anders Martinsson, Angelika Steger
Hillclimbing is an essential part of any optimization algorithm. An important benchmark for hillclimbing algorithms on pseudo-Boolean functions are (s…
The "No Justice in the Universe" phenomenon: why honesty of effort may not be rewarded in tournaments
Peter Hegarty, Anders Martinsson, Edvin Wedin
In 2000 Allen Schwenk, using a well-known mathematical model of matchplay tournaments in which the probability of one player beating another in a single match is fixed for each pai…
A linear threshold for uniqueness of solutions to random jigsaw puzzles
Anders Martinsson
We consider a problem introduced by Mossel and Ross [Shotgun assembly of labeled graphs, arXiv:1504.07682]. Suppose a random jigsaw puzzle is constructed by independent…
Shotgun edge assembly of random jigsaw puzzles
Anders Martinsson
In recent work by Mossel and Ross, it was asked how large has to be for a random jigsaw puzzle with different shapes of "jigs" to have exactly one solution. The jigs are as…
Most edge-orderings of have maximal altitude
Anders Martinsson
Suppose the edges of the complete graph on vertices are assigned a uniformly chosen random ordering. Let denote the corresponding number of Hamiltonian paths that are incre…
Segregating Markov chains
Timo Hirscher, Anders Martinsson
Dealing with finite Markov chains in discrete time, the focus often lies on convergence behavior and one tries to make different copies of the chain meet as fast as possible and th…
First-passage percolation on Cartesian power graphs
Anders Martinsson
We consider first-passage percolation on the class of "high-dimensional" graphs that can be written as an iterated Cartesian product of some ba…
Accessibility percolation and first-passage site percolation on the unoriented binary hypercube
Anders Martinsson
Inspired by biological evolution, we consider the following so-called accessibility percolation problem: The vertices of the unoriented -dimensional binary hypercube are assigne…
Unoriented first-passage percolation on the n-cube
Anders Martinsson
The -dimensional binary hypercube is the graph whose vertices are the binary -tuples and where two vertices are connected by an edge if they differ at exactly on…
On the existence of accessible paths in various models of fitness landscapes
Peter Hegarty, Anders Martinsson
We present rigorous mathematical analyses of a number of well-known mathematical models for genetic mutations. In these models, the genome is represented by a vertex of the -dim…