Open Problems:31 - Revision history

Huy at 18:23, 27 March 2013

2013-03-27T18:23:55Z

Krzysztof Onak: updated header

2013-03-07T01:51:23Z

updated header

Krzysztof Onak at 05:25, 16 November 2012

2012-11-16T05:25:30Z

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 31: Gap-Hamming Information Cost}} {{Infobox |label1 = Proposed by |data1 = Amit Chakrabarti |label2 = Source |data2 = [[Workshops:Kanpur_2009|Kanpur 20..."

2012-11-13T01:12:20Z

Created page with "{{DISPLAYTITLE:Problem 31: Gap-Hamming Information Cost}} {{Infobox |label1 = Proposed by |data1 = Amit Chakrabarti |label2 = Source |data2 = [[Workshops:Kanpur_2009|Kanpur 20..."

New page

{{DISPLAYTITLE:Problem 31: Gap-Hamming Information Cost}}
{{Infobox
|label1 = Proposed by
|data1 = Amit Chakrabarti
|label2 = Source
|data2 = [[Workshops:Kanpur_2009|Kanpur 2009]]
|label3 = Short link
|data3 = http://sublinear.info/31
}}
In the Gap-Hamming problem, two players Alice and Bob have vectors $x,y\in \{0,1\}^n$ respectively and wish to compute the function $f$
\[
f(x,y)=
\begin{cases}
0 & \mbox{ if } \Delta(x,y) \leq n/2-\sqrt{n} \\
1 & \mbox{ if } \Delta(x,y) \geq n/2+\sqrt{n}
\end{cases}
\]
where $\Delta(x,y)=|\{i:x_i\neq y_i\}|$ is the Hamming distance between the vectors and we are promised that $|\Delta(x,y)-n/2|\geq \sqrt{n}$. The problem became interesting in the streaming community because a lower bound on the communication complexity of evaluating $f$ yields a lower bound on the space required by a streaming algorithm to estimate the number of distinct elements or the entropy of a stream. After a series of papers, it is know that evaluating $f$ requires $\Omega(n)$ communication {{cite|IndykW-03|Woodruff-04|BrodyC-09|BrodyCRVW-10|ChakrabartiR-11}} even if an unlimited number of rounds of communication are used.

An increasingly popular technique in communication complexity is to prove bounds by bounding the information cost {{cite|ChakrabartiSWY-01|BarYossefJKS-04}}. Here we consider random input $(X,Y)$ and consider the mutual information between the input and the random transcript of the protocol $\Pi(X,Y)$:
\[
I(XY;\Pi(X,Y))=H(XY)-H(XY|\Pi(X,Y)) \ .
\]
It would be interesting to prove a lower bound on the information cost for the Gap-Hamming problem for some natural input distribution.

← Older revision		Revision as of 18:23, 27 March 2013
Line 18:		Line 18:
	\]		\]
	It would be interesting to prove a lower bound on the information cost for the Gap-Hamming problem for some natural input distribution.		It would be interesting to prove a lower bound on the information cost for the Gap-Hamming problem for some natural input distribution.
		+
		+	==Update==
		+	A linear lower bound on the information cost for a certain distribution was shown by {{cite\|KerenidisLLRX-12}}. Later, {{cite\|BravermanGPW-13}} showed that a linear lower bound also holds for the uniform distribution.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur09
 |who=Amit Chakrabarti

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 31: Gap-Hamming Information Cost}}
+{{Header
-{{Infobox
+|title=Gap-Hamming Information Cost
-|label1 = Proposed by
+|source=kanpur09
-|data1 = Amit Chakrabarti
+|who=Amit Chakrabarti
 }}
 In the Gap-Hamming problem, two players Alice and Bob have vectors $x,y\in \{0,1\}^n$ respectively and wish to compute the function $f$