Editing Open Problems:25
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
{{Header | {{Header | ||
+ | |title=Communication Complexity and Metric Spaces | ||
|source=kanpur09 | |source=kanpur09 | ||
|who=T. S. Jayram | |who=T. S. Jayram | ||
Line 18: | Line 19: | ||
# 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''. | ||
− | |||
− | |||
− | |||
− |