### 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms |

Publisher | Association for Computing Machinery (ACM) |

Pages | 346-354 |

Number of pages | 9 |

ISBN (Print) | 9780898716801 |

DOIs | |

State | Published - 2009 |

Externally published | Yes |

Event | 20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, United States Duration: Jan 4 2009 → Jan 6 2009 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 20th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country | United States |

City | New York, NY |

Period | 1/4/09 → 1/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

*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