Open Problems:10 - Revision history

Krzysztof Onak at 04:03, 28 April 2017

2017-04-28T04:03:44Z

Sassadi at 14:26, 20 April 2017

2017-04-20T14:26:55Z

Krzysztof Onak at 01:40, 7 March 2013

2013-03-07T01:40:12Z

Krzysztof Onak at 05:04, 16 November 2012

2012-11-16T05:04:12Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:50Z

1 revision

Krzysztof Onak: 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..."

2012-10-01T17:38:58Z

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..."

New page

{{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)$.

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.

@@ Line 6: / Line 6: @@
 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)$.

← Older revision		Revision as of 14:26, 20 April 2017
Line 6:		Line 6:

	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 in {{cite\|ChakrabartiR-11}}, showing that communication complexity of '''Gap-Hamdist''' is $\Omega(n)$.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur06
 |who=Ravi Kumar

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 10: Multi-Round Communication of Gap-Hamming Distance}}
+{{Header
-{{Infobox
+|title=Multi-Round Communication of Gap-Hamming Distance
-|label1 = Proposed by
+|source=kanpur06
-|data1 = Ravi Kumar
+|who=Ravi Kumar
 }}
 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.

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