Tag Info

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 \...
• 2,743
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 ...
• 2,313
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 ...
• 5,190

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,341