Editing Open Problems:25

{{DISPLAYTITLE:Problem 25: Communication Complexity and Metric Spaces}}
{{Infobox
|label1 = Proposed by
|data1 = T. S. Jayram
|label2 = Source
|data2 = [[Workshops:Kanpur_2009|Kanpur 2009]]
|label3 = Short link
|data3 = http://sublinear.info/25
}}
== Poincaré Inequalities ==
Alice and Bob are given two points $x$ and $y$, respectively, from a specific metric space $\mathcal M$. We are interested in deciding whether $d_{\mathcal M}(x,y) \le R$ or $d_{\mathcal M}(x,y) \ge \alpha R$, where $d_{\mathcal M}$ is the distance function of $\mathcal M$, $R > 0$, and $\alpha > 1$. What amount of information must be exchanged in order to solve this problem? Answering this question is interesting in any standard communication model: unrestricted communication between the players, one-way communication, sketching, etc.

The above question can partially be answered if the metric satisfies a specific &ldquo;gap&rdquo; Poincaré inequality {{cite|AndoniJP-10}}. It is known that another kind of Poincaré inequality is equivalent to non-embeddability into $\ell_2^2$ {{cite|Matousek-02}}, but it is not known if non-embeddability into $\ell_2^2$ implies lower bounds for communication complexity. Can one show a formal connection between the communication complexity for approximating the distance between two points and non-embeddability into $\ell_2^2$?

== Product Metrics ==
We are also interested in the following general class of metrics. Let each $\mathcal M_i= \langle S_i, d_i\rangle$, $1 \le i \le k$, be a metric space on a set $S_i$ with a distance function $d_i$. A ''product metric space'' $\bigoplus_{i=1}^{k} \mathcal M_i$ is defined on the product $S_1 \times \ldots \times S_k$ with the distance function
$$d\left((x_1,\ldots,x_k),(y_1,\ldots,y_k)\right) = \operatorname{\bf op}\left(d_1(x_1,y_1),\ldots,d_k(x_k,y_k)\right),$$
where ${\bf op}$ is a symmetric operator. For instance, $\bigoplus_{i=1}^{k} \mathcal M_i$ is a proper metric space if ${\bf op}$ is the maximum operator or the $p$-th norm for any $p \in [1,\infty)$. The case when $\bigoplus_{i=1}^{k} \mathcal M_i$ is not necessarily a metric space also finds applications.

Applications of product metric spaces include a nearest neighbor data structure for Ulam distance {{cite|AndoniIK-09}}, and a near-linear time subpolynomial-approximation algorithm for edit distance {{cite|AndoniO-09}}.

The following questions arise in the context of product spaces:
# Can one design efficient communication protocols for computing the distance between a pair of points? Suppose that there is an efficient communication protocol for each $\mathcal M_i$. What is the communication complexity for computing the distance between two points in $\bigoplus_{i=1}^{k}\mathcal M_i$? Andoni, Jayram, and Pătraşcu {{cite|AndoniJP-10}} prove lower bounds for some product metrics. Jayram and Woodruff {{cite|JayramW-09}} show streaming algorithms which yield communication protocols.
# Can one design efficient streaming algorithms and data structures for product metric spaces? In particular, can one efficiently compute the distance between a pair of points? Jayram and Woodruff {{cite|JayramW-09}} consider the related question of computing ''cascaded norms''.