Hot answers tagged

6 votes
Accepted

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 \...
user avatar
  • 2,743
5 votes
Accepted

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 ...
user avatar
  • 2,313
4 votes
Accepted

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 ...
user avatar
  • 5,190
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 ...
user avatar
  • 4,341
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. ...
user avatar
  • 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.
user avatar

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