Open Problems:48 - Revision history

Krzysztof Onak: updated header

2013-03-07T01:55:51Z

updated header

Andoni at 16:50, 13 December 2012

2012-12-13T16:50:02Z

Krzysztof Onak: 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_{ \..."

2012-11-17T04:29:47Z

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_{ \..."

New page

{{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_{ \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 {{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}}.

← Older revision		Revision as of 16:50, 13 December 2012
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}}.

@@ Line 1: / Line 1: @@
 {{Header
 |source=bertinoro11
 |who=Alexandr Andoni