Difference between revisions of "Open Problems:48"
(Created page with "{{Header |title=Sketching Shift Metrics |source=bertinoro11 |who=Alexandr Andoni }} For any $x,y \in \{0,1\}^n$, define the ''shift metric'' \[\operatorname{sh}(x,y)=\min_{ \...") |
|||
| Line 15: | Line 15: | ||
'''Question:''' Is there a sketching scheme for $P_c$ where $c=O(1)$ and $s=O(1)$? | '''Question:''' Is there a sketching scheme for $P_c$ where $c=O(1)$ and $s=O(1)$? | ||
| − | '''Background:''' If the shift metric is replaced by Hamming metric, one can achieve $s=O(1)$ using random sampling {{cite|KushilevitzOR-00}}. The actual problem can be solved for $c=O(\log^2 n)$ and $s=O(1)$ {{cite|AndoniIK-08}}. The algorithm proceeds by embedding the shift metric into Hamming metrics, and it is known that this step must induce $\Omega(\log n)$ distortion {{cite|KhotN-06}}. | + | '''Background:''' If the shift metric is replaced by Hamming metric, one can achieve $s=O(1)$ using random sampling {{cite|KushilevitzOR-00}}. The actual problem can be solved for $c=O(\log^2 n)$ and $s=O(1)$ {{cite|AndoniIK-08}}. The algorithm proceeds by embedding the shift metric into Hamming metrics, and it is known that this step must induce $\Omega(\log n)$ distortion {{cite|KhotN-06}}. There's also a solution for $c=1+\epsilon$ and $s=\tilde{O}(\epsilon^{-2}\sqrt{n})$ {{cite|CrouchM-11}}. |
Revision as of 16:50, 13 December 2012
| Suggested by | Alexandr Andoni |
|---|---|
| Source | Bertinoro 2011 |
| Short link | https://sublinear.info/48 |
For any $x,y \in \{0,1\}^n$, define the shift metric \[\operatorname{sh}(x,y)=\min_{ \sigma} H(x, \sigma(y)), \] where $\sigma$ ranges over all $n$ cyclic permutations of $\{1 \ldots n\}$, and $H()$ is the hamming distance.
For any $c>20$, the promise problem $P_c$ is to distinguish whether $\operatorname{sh}(x,y)>n/10$ or $\operatorname{sh}(x,y)<n/c$. Consider probabilistic mappings $L_c: \{0,1\}^n \to \{0,1\}^s$. We say that $L_c$ is a sketching scheme for $P_c$ if there is an algorithm that, for any $x,y \in \{0,1\}^n$ satisfying the promise of $P_c$, given $L_c(x)$ and $L_c(y)$, solves $P_c$ with probability at least $0.9$.
Question: Is there a sketching scheme for $P_c$ where $c=O(1)$ and $s=O(1)$?
Background: If the shift metric is replaced by Hamming metric, one can achieve $s=O(1)$ using random sampling [KushilevitzOR-00]. The actual problem can be solved for $c=O(\log^2 n)$ and $s=O(1)$ [AndoniIK-08]. The algorithm proceeds by embedding the shift metric into Hamming metrics, and it is known that this step must induce $\Omega(\log n)$ distortion [KhotN-06]. There's also a solution for $c=1+\epsilon$ and $s=\tilde{O}(\epsilon^{-2}\sqrt{n})$ [CrouchM-11].
