On the power of two, three and four probes

Noga Alon, Uriel Feige

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

21 Scopus citations

Abstract

An adaptive (n, m, s, t)-scheme is a deterministic scheme for encoding a vector X of m bits with at most n ones by a vector Y of s bits, so that any bit of X can be determined by t adaptive probes to Y. A non-adaptive (n, m, s, t)-scheme is defined analogously. The study of such schemes arises in the investigation of the static membership problem in the bitprobe model. Answering a question of Buhrman, Miltersen, Radhakrishnan and Venkatesh [SICOMP 2002] we present adaptive (n, m, s, 2) schemes with s < m for all n satisfying 4n 2 + 4n < m and adaptive (n, m, s, 2) schemes with s = o(m) for all n = o(log m). We further show that there are adaptive (n, m, s, 3)-schemes with s = o(m) for all n = o(m), settling a problem of Radhakrishnan, Raman and Rao [ESA 2001], and prove that there are non-adaptive (n, m, s, 4)-schemes with s = o(m) for all n = o(m). Therefore, three adaptive probes or four non-adaptive probes already suffice to obtain a significant saving in space compared to the total length of the input vector. Lower bounds are discussed as well.

Original languageEnglish (US)
Title of host publicationProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherAssociation for Computing Machinery (ACM)
Pages346-354
Number of pages9
ISBN (Print)9780898716801
DOIs
StatePublished - 2009
Externally publishedYes
Event20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, United States
Duration: Jan 4 2009Jan 6 2009

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other20th Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityNew York, NY
Period1/4/091/6/09

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'On the power of two, three and four probes'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., & Feige, U. (2009). On the power of two, three and four probes. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 346-354). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery (ACM). https://doi.org/10.1137/1.9781611973068.39