Difference between revisions of "Open Problems:10"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Created page with "{{DISPLAYTITLE:Problem 10: Multi-Round Communication of Gap-Hamming Distance}} {{Infobox |label1 = Proposed by |data1 = Ravi Kumar |label2 = Source |data2 = [[Workshops:Kanpur...")
 
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
{{DISPLAYTITLE:Problem 10: Multi-Round Communication of Gap-Hamming Distance}}
+
{{Header
{{Infobox
+
|source=kanpur06
|label1 = Proposed by
+
|who=Ravi Kumar
|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.
 +
 +
==Update==
 +
This conjecture was proved by Chakrabarti and Regev {{cite|ChakrabartiR-11}}, who showed that the communication complexity of '''Gap-Hamdist''' is $\Omega(n)$.

Latest revision as of 04:03, 28 April 2017

Suggested by Ravi Kumar
Source Kanpur 2006
Short link https://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)$ [IndykW-03,Woodruff-04]. Recently, a simpler proof was discovered using a reduction from Index [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$ [IndykW-03,Woodruff-04,BarYossefJKST-02] and entropy [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.

Update[edit]

This conjecture was proved by Chakrabarti and Regev [ChakrabartiR-11], who showed that the communication complexity of Gap-Hamdist is $\Omega(n)$.