Problem 48: Sketching Shift Metrics

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].