Editing Open Problems:10
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: | ||
− | {{ | + | {{DISPLAYTITLE:Problem 10: Multi-Round Communication of Gap-Hamming Distance}} |
− | | | + | {{Infobox |
− | | | + | |label1 = Proposed by |
+ | |data1 = Ravi Kumar | ||
+ | |label2 = Source | ||
+ | |data2 = [[Workshops:Kanpur_2006|Kanpur 2006]] | ||
+ | |label3 = Short link | ||
+ | |data3 = http://sublinear.info/10 | ||
}} | }} | ||
Consider the communication problem '''Gap-Hamdist''': Alice and Bob are given length $n$ binary strings $x$ and $y$ such that either the Hamming distance $\Delta(x,y) \leq n/2$ or $\Delta(x,y)\geq n/2+\sqrt{n}$. The one-way communication complexity of '''Gap-Hamdist''' is known to be $\Omega(n)$ {{cite|IndykW-03|Woodruff-04}}. Recently, a simpler proof was discovered using a reduction from '''Index''' {{cite|JayramKS-07}}. Is the multi-round communication complexity also $\Omega(n)$? There is a $\Omega(\sqrt{n})$ lower-bound from a reduction from '''Set-Disjointness''' but we conjecture that the lower-bound is actually $\Omega(n)$. | Consider the communication problem '''Gap-Hamdist''': Alice and Bob are given length $n$ binary strings $x$ and $y$ such that either the Hamming distance $\Delta(x,y) \leq n/2$ or $\Delta(x,y)\geq n/2+\sqrt{n}$. The one-way communication complexity of '''Gap-Hamdist''' is known to be $\Omega(n)$ {{cite|IndykW-03|Woodruff-04}}. Recently, a simpler proof was discovered using a reduction from '''Index''' {{cite|JayramKS-07}}. Is the multi-round communication complexity also $\Omega(n)$? There is a $\Omega(\sqrt{n})$ lower-bound from a reduction from '''Set-Disjointness''' but we conjecture that the lower-bound is actually $\Omega(n)$. | ||
If the conjecture is true then it would imply stronger multiple-pass lower bounds for estimating $F_0$ {{cite|IndykW-03|Woodruff-04|BarYossefJKST-02}} and entropy {{cite|BhuvanagiriG-06|ChakrabartiCM-07}}. Alternatively, if the conjecture is not true then it would be interesting to see if better multi-pass algorithms exist for $F_0$ and entropy. | If the conjecture is true then it would imply stronger multiple-pass lower bounds for estimating $F_0$ {{cite|IndykW-03|Woodruff-04|BarYossefJKST-02}} and entropy {{cite|BhuvanagiriG-06|ChakrabartiCM-07}}. Alternatively, if the conjecture is not true then it would be interesting to see if better multi-pass algorithms exist for $F_0$ and entropy. | ||
− | |||
− | |||
− |