# Questions tagged [metrics]

The tag has no usage guidance.

25 questions
Filter by
Sorted by
Tagged with
78 views

205 views

### Quicksort optimal partition

Has the question been studied, how to find the shortest sequence of partition choices so that a quick-sort algorithm can sort a set? To be clear, I'm not interested in quick sort per se, but in ...
• 211
1k views

### Min Hamming distance of a given string from substrings of another string

Let $U$ be a small finite set. Consider the following problem: Input: two strings $u \in U^k$ and $v\in U^n$ with $k \leq n$. Output: a (contiguous) substring of $v$ of length $k$ with the minimum ...
• 113
192 views

### Are there Similar Distance Binary Error Correcting Codes?

I'm trying to find a low distortion embedding of the trivial metric space into hamming space. It seems this should be doable by using a large set of low dimensional vectors, with approximately equal ...
• 778
188 views

### L1 - embeddability of metrics supported on the Hypercube

I am quite new to the area of metric embeddings so this question might turn out to be extremely easy. Consider a metric supported on the edges of a boolean hypercube. By supported I mean every edge ...
• 656
81 views

• 9,800
261 views

### Counting Metrics

Say that I have a set of $n$ points $N$, and am interested in metrics $d:N\times N \rightarrow \mathbb{R}$ over $N$. Let $M$ denote the set of all metrics over $N$. Now let me define the distance ...
• 9,800
1k views

### Deciding whether a metric is a tree metric

An n-point metric space is a tree metric if it isometrically embeds into the shortest path metric of a tree (with nonnegative edge weights). Tree metrics can be characterized by the 4 point property, ...
313 views

### Extracting Independent Information About Sequences

Related to this question, but asked in a different way. For the purposes of a text-based implementation of a fuzzy vault, what metrics can we take on Sequences that are isolated such that the set of ...
• 179
442 views

### In domain theory, what can the extra structure present in metric spaces be used for?

Smyth's chapter in the handbook of logic in computer science and other references describe how metric spaces can be used as domains. I do understand that complete metric spaces give unique fixed ...
• 791
487 views

### Dimensionality reduction with slack?

The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log n/\epsilon^2)$ ...
• 9,800
There is a large literature on "property testing" -- the problem of making a small number of black box queries to a function $f\colon\{0,1\}^n \to R$ to distinguish between two cases: $f$ is a ...