Open Problems:25 - Revision history

Andoni at 17:02, 8 November 2019

2019-11-08T17:02:31Z

Andoni: /* Update */ adding KN19

2019-11-08T17:02:13Z

‎Update: adding KN19

2601:6:1980:903:143:DBD9:5F82:D231 at 21:11, 30 November 2014

2014-11-30T21:11:50Z

Krzysztof Onak: updated header

2013-03-07T01:49:48Z

updated header

Krzysztof Onak at 05:21, 16 November 2012

2012-11-16T05:21:51Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:51Z

1 revision

Krzysztof Onak at 14:42, 19 October 2012

2012-10-19T14:42:02Z

New page

{{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 “gap” 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''.

← Older revision		Revision as of 17:02, 8 November 2019
Line 21:		Line 21:
	==Update==		==Update==

−	It has been shown {{cite\|AndoniKR-14}} that for '''normed spaces''' the above implication is true: if a snowflake of a normed space does not embed into $\ell_2$ (in fact, more generally, does not ''uniformly embed'' into a Hilbert space), then, there is a non-trivial communication lower bound for distinguishing small and large distances. ~~Furtermore~~, {{cite\|KhotN-19}} show that a similar statement is not true for metrics in general: there exist metrics which are sketchable with constant approximation and space, but do not $O(1)$-embed into $\ell_{1-\epsilon}$ for any $\epsilon<1/2$.	+	It has been shown {{cite\|AndoniKR-14}} that for '''normed spaces''' the above implication is true: if a snowflake of a normed space does not embed into $\ell_2$ (in fact, more generally, does not ''uniformly embed'' into a Hilbert space), then, there is a non-trivial communication lower bound for distinguishing small and large distances. Furthermore, {{cite\|KhotN-19}} show that a similar statement is not true for metrics in general: there exist metrics which are sketchable with constant approximation and space, but do not $O(1)$-embed into $\ell_{1-\epsilon}$ for any $\epsilon<1/2$.

← Older revision		Revision as of 17:02, 8 November 2019
Line 21:		Line 21:
	==Update==		==Update==

−	It has been shown {{cite\|AndoniKR-14}} that for '''normed spaces''' the above implication is true: if a normed space does not embed into $\ell_2^2$ (in fact, more generally, does not ''uniformly embed'' into a Hilbert space), then, there is a non-trivial communication lower bound for distinguishing small and large distances.	+	It has been shown {{cite\|AndoniKR-14}} that for '''normed spaces''' the above implication is true: if a snowflake of a normed space does not embed into $\ell_2$ (in fact, more generally, does not ''uniformly embed'' into a Hilbert space), then, there is a non-trivial communication lower bound for distinguishing small and large distances. Furtermore, {{cite\|KhotN-19}} show that a similar statement is not true for metrics in general: there exist metrics which are sketchable with constant approximation and space, but do not $O(1)$-embed into $\ell_{1-\epsilon}$ for any $\epsilon<1/2$.

← Older revision		Revision as of 21:11, 30 November 2014
Line 18:		Line 18:
	# 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 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''.		# 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''.
		+
		+	==Update==
		+
		+	It has been shown {{cite\|AndoniKR-14}} that for '''normed spaces''' the above implication is true: if a normed space does not embed into $\ell_2^2$ (in fact, more generally, does not ''uniformly embed'' into a Hilbert space), then, there is a non-trivial communication lower bound for distinguishing small and large distances.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur09
 |who=T. S. Jayram

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 25: Communication Complexity and Metric Spaces}}
+{{Header
-{{Infobox
+|title=Communication Complexity and Metric Spaces
-|label1 = Proposed by
+|source=kanpur09
-|data1 = T. S. Jayram
+|who=T. S. Jayram
 }}
 == Poincaré Inequalities ==

← Older revision	Revision as of 05:33, 8 November 2012
(No difference)