Search Results

Metric embeddings into structured spaces, particularly hierarchically well-separated trees (HSTs), are a fundamental tool in the design of online algorithms. In the classical online embedding setting, points arrive sequentially and must be embedded irrevocably upon arrival, resulting in strong distortion lower bounds of Ω(min(n, log nlog Δ)), where n is the number of points and Δ their aspect ratio. We propose a novel relaxation, online monotone metric embeddings, which allows distances between embedded points in the target space to decrease monotonically over time. Such relaxed embeddings remain compatible with many online algorithms. Moreover, this relaxation breaks existing lower bound barriers, enabling embeddings into HSTs with distortion O(log² n). We also study a dynamic variant, where points may both arrive and depart, seeking distortion guarantees in terms of the maximum number l of simultaneously present points. For traditional embeddings, such bounds are impossible, and this limitation persists even for deterministic monotone embeddings. Surprisingly, probabilistic monotone embeddings allow for O(l log l) distortion, which is nearly optimal given an Ω(l) lower bound.

We study evolutionary dynamics on graphs in which each step consists of one birth and one death, referred to generally as Moran processes. In standard simplified models, there are two types of individuals: residents, who have a fitness of 1, and mutants, who have a fitness of r. Two standard update rules are used in the literature. In Birth–death (Bd), a vertex is chosen to reproduce proportional to fitness, and one of its neighbors is selected uniformly at random to die and be replaced by the offspring. In death–Birth (dB), a vertex is chosen uniformly to die, and then one of its neighbors is chosen, proportional to fitness, to place an offspring into the vacancy. Two crucial quantities are: the unconditional absorption time, which is the expected time until only residents or only mutants remain, and the fixation probability of the mutant, which is the probability that at some time the mutants occupy the whole graph. Birth-death and death-Birth rules can yield significantly different outcomes for these quantities on the same graph, rendering conclusions dependent on the update rule. We formalize and study a unified model, the λ-mixed Moran process, in which each step is independently a Bd step with probability λ ∈ [0,1] and a dB step otherwise. We analyze this mixed process and establish a few results that form a starting point for its further study. All of our results are for undirected, connected graphs. As an interesting special case, we show at λ = 1/2 for any graph that the fixation probability when r = 1 with a single mutant initially on the graph is exactly 1/n, and also at λ = 1/2 that the absorption time for any r is O_r(n⁴) (that is, with an r-dependent constant). We also show results for graphs that are "almost regular," in a manner defined in the paper. We use this to show that for suitable random graphs from G∼ G(n,p) and fixed r > 1, with high probability over the choice of graph, the absorption time is O_r(n⁴), the fixation probability is Ω_r(n^{-2}), and we can approximate the fixation probability in polynomial time. Another special case is when the graph has only two possible values for the degree {d₁, d₂} with d₁ ≤ d₂. For those graphs, we give exact formulas for fixation probabilities under r = 1 and any λ, and establish O_r(n⁴ α⁴) absorption time regardless of λ, where α = d₂/d₁. We also provide explicit formulas for the star and cycle under any r or λ.