Campus Event Calendar
Event Entry
What and Who
Deterministic Schemes for Membership in the Bitprobe Model
Patrick Nicholson
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 10 October 2013
13:00
30 Minutes
E1 4
024
Saarbrücken
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.
Contact
Patrick Nicholson
--email hidden
passcode not visible
logged in users only
Patrick Nicholson, 09/19/2013 13:29 -- Created document.