# Difference between revisions of "Open Problems:10"

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== | ==Update== | ||

− | + | This conjecture was proved by Chakrabarti and Regev {{cite|ChakrabartiR-11}}, who showed that the communication complexity of '''Gap-Hamdist''' is $\Omega(n)$. | |

− | This conjecture was proved |

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