# Tag Info

7

You can write the problem as an LP, can't you? For any two vertices u, v, and any path P from u to v, the weight of P is greater than or equal to the weight of the given shortest path between u and v. These are all linear inequalities, and even though there are exponentially many, the separation problem is in P (it's just an all-pairs shortest path problem)....

6

Elaborating Paul's suggestion for a $O(n \log n)$-time algorithm: Input: Let $u \in [m]^k$ and $v \in [m]^n$ with $k \leq n$, where $U=[m]=\{1,2,\cdots,m\}$. Define polynomials $$p(x,y) = \sum_{i \in [n]} x^i y^{v_i} \qquad \text{and} \qquad q(x,y) = \sum_{j \in [k]} x^{k-j} y^{m-u_j}.$$ Compute the polynomial $$r(x,y) = p(x,y) q(x,y).$$ Then r(x,y) = \...

5

I just stumbled across this old question while conducting a lit search, and I happen to have recently gotten answers in this paper that I might as well share. I hope the combination of thread necromancy and self-promotion is forgivable. Can we produce any G that would have given these paths as the shortest in polynomial time? The weaker version: can we ...

4

The work of Berman, Raskhodnikova, and Yaroslavtsev  introduces testing of functions $f\colon [n]^d\to \mathbb{R}$ with regard to $L_p$ distances, for $p\geq 1$. It is meant to capture situations where the magnitude of the noise is what matters (rather than the more brittle Hamming distance). (Some results pertaining to $L_p$ distances can also be found ...

4

Think of the hypercube as a graph $G$. Allowing arbitrary edge lengths implies that you can use edge lengths $0$ and $\infty$ to get a minor of $G$ on which you can put edge lengths. The hypercube has sufficiently large expansion that it contains, as a minor, a clique of size about $\sqrt{N}$ (ignoring polylog factors) where $N$ is the number of nodes of the ...

4

In general there are all kinds of lower bounds for embedding an arbitrary metric on the hypercube into $\ell_1$. For example, the edit distance cannot be embedded with better than $\log n$ distortion. Note that the Hamming distance itself embeds isometrically in $\ell_1$, so you can't expect to prove any nontrivial lower bound over all metrics on the ...

4

Hausdorff distance is what you are looking for.

3

Hint: Express the binary vectors as a polynomial with coefficients in {-1,0,1} and obtain the hamming distance of u with all length k contiguous subsequences of v through a polynomial multiplication. Use Fourier transforms to improve the complexity to what you need.

3

Every $\epsilon$-biased set gives a code whose minimal relative distance is $0.5 - \epsilon$ and maximal relative distance is $0.5 + \epsilon$. To see it, write the elements of the set as the rows of a matrix, and then define the code to be the span of the columns of the matrix. The $\epsilon$-biased property of the set is equivalent to saying that the ...

1

For anyone interested: I implemented The String Edit Distance Matching Problem with Moves by Graham Cormode and S. Muthukrishnan. It essentially approximates the described metric in linear time.

Only top voted, non community-wiki answers of a minimum length are eligible