Deterministic Schemes for Membership in the Bitprobe Model

Title

Deterministic Schemes for Membership in the Bitprobe Model

 

Abstract

Buhrman, Miltersen, Radhakrishnan and Venkatesh [SICOMP 2002] initiated the study of space bounds for the membership problem in the bitprobe model, presenting both randomized and deterministic schemes for storing a set of size n from a universe of size m such that membership queries on the set can be answered in t bit probes. Since then, there have been several papers on deterministic schemes, especially for the first non-trivial case when n = 2. In this talk we survey deterministic schemes, with an emphasis on the n = 2 case.

 

About the Presenter

Patrick is a researcher in the Algorithms and Complexity department at the Max-Planck-Institut für Informatik.  He recently graduated with his Ph.D. focusing on space efficient data structures in the word-RAM and bitprobe models from the University of Waterloo.