Difference between revisions of "Open Problems:31"
(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...") |
|||
| Line 1: | Line 1: | ||
| − | {{ | + | {{Header |
| − | + | |title=Gap-Hamming Information Cost | |
| − | | | + | |source=kanpur09 |
| − | | | + | |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$ | 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$ | ||
Revision as of 05:25, 16 November 2012
| Suggested by | Amit Chakrabarti |
|---|---|
| Source | Kanpur 2009 |
| Short link | https://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 [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 [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.
