Editing Open Problems:59
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| Line 3: | Line 3: | ||
|who=Hossein Jowhari | |who=Hossein Jowhari | ||
}} | }} | ||
| β | Let $T = \bigcup_{i=1}^{n} \{0,1\}^i$. For | + | Let $T = \bigcup_{i=1}^{n} \{0,1\}^i$. For pair of strings $(x,y) \in T \times T$ let $ed(x,y)$ denote the edit distance between $x$ and $y$ which is defined as the minimum number of character insertion, deletion and substitution needed for converting $x$ into $y$. |
| β | '''Question | + | '''Question''': is there a mapping $f:T \rightarrow \{0,1\}^{m}$ satisfying the following conditions |
* $f$ is injective, i.e. it does not map different inputs to the same point. | * $f$ is injective, i.e. it does not map different inputs to the same point. | ||
* $m=O(n^c)$ for some constant $c \geq 1$. | * $m=O(n^c)$ for some constant $c \geq 1$. | ||
| β | * For strings with $ | + | * For strings with $ed(x,y)=1$ we have $\mathcal{H}(f(x),f(y)) \le C$ for $C=o(\log n)$. |
The same question holds for randomized mappings as long as they map different $x$ and $y$ to different points with high probability. Currently the best upper bound on $C$ is $O(\log n\log^*n)$ achieved through a randomized mapping that deploys the Locally Consistent Parsing method {{cite|CormodePSV-00}}. For non-repetitive strings (the Ulam distance) there is a deterministic mapping with $C\leq 6$ and $c=2$. Preferably we would like to have mappings that are efficiently computable and are equipped with polynomial time decoding algorithms ($x$ can be obtained from $f(x)$ efficiently). See {{cite|Jowhari-12}} for motivations on the problem. | The same question holds for randomized mappings as long as they map different $x$ and $y$ to different points with high probability. Currently the best upper bound on $C$ is $O(\log n\log^*n)$ achieved through a randomized mapping that deploys the Locally Consistent Parsing method {{cite|CormodePSV-00}}. For non-repetitive strings (the Ulam distance) there is a deterministic mapping with $C\leq 6$ and $c=2$. Preferably we would like to have mappings that are efficiently computable and are equipped with polynomial time decoding algorithms ($x$ can be obtained from $f(x)$ efficiently). See {{cite|Jowhari-12}} for motivations on the problem. | ||
