Hot answers tagged

6 votes

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

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 \...
  • 2,793
5 votes

Axioms for Shortest Paths

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 ...
  • 2,333
4 votes

Are there Similar Distance Binary Error Correcting Codes?

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 ...
  • 5,290
4 votes

Property testing in other metrics?

The work of Berman, Raskhodnikova, and Yaroslavtsev [1] 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 ...
  • 4,381
3 votes

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

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. ...
  • 131
1 vote

How to calculate this string-dissimilarity function efficiently?

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 scored, non community-wiki answers of a minimum length are eligible