Deterministic Schemes for Membership in the Bitprobe Model

Event type: 
HIIT seminar
Event time: 
17.12.2013 - 10:15 - 11:00
Lecturer : 
Patrick Nicholson
Exactum, B119

Deterministic Schemes for Membership in the Bitprobe Model

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.

03.12.2013 - 18:54 Brandon Malone
03.12.2013 - 18:54 Brandon Malone