Cell-probe lower bounds for the partial match problem

T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Given a database of n points in {0, 1} d, the partial match problem is: In response to a query x in {0, 1, *} d, find a database point y such that for every i whenever x i ≠ *, we have x i = y i. In this paper we show randomized lower bounds in the cell-probe model for this well-studied problem. Our lower bounds follow from a two-party asymmetric randomized communication complexity near-optimal lower bound for this problem, where we show that either Alice has to send Ω(d/log n) bits or Bob has to send Ω(n 1-0(1)) bits. When applied to the cell-probe model, it means that if the number of cells is restricted to be poly(n, d) where each cell is of size poly (log n,d), then Ω(d/log 2n) probes are needed. This is an exponential improvement over the previously known lower bounds for this problem. Our lower bound also leads to new and improved lower bounds for related problems including a lower bound for the l c-nearest neighbor problem for c < 3 and an improved communication complexity lower bound for the exact nearest neighbor problem.

Original languageEnglish (US)
Title of host publicationConference Proceedings of the Annual ACM Symposium on Theory of Computing
Number of pages6
StatePublished - 2003
Event35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 9 2003Jun 11 2003


Other35th Annual ACM Symposium on Theory of Computing
Country/TerritoryUnited States
CitySan Diego, CA


  • Algorithms
  • Theory

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Cell-probe lower bounds for the partial match problem'. Together they form a unique fingerprint.

Cite this