Tata Institute of Fundamental Research
Data Structures for Storing Small Sets in the Bitprobe Model
Student Seminar
Speaker:
Saswata Shannigrahi
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha R
Date:
Friday, 3 Sep 2010 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
We study the following set membership problem in the bitprobe model: Given a set S from a finite universe U , represent it in memory so that membership queries of the form Is x in S? can be answered with a small number of bitprobes. We obtain explicit schemes that come close to the information theoretic lower bound of Buhrman et al. [STOC 2000, SICOMP 2002] and improve the results of Radhakrishnan et al. [ESA 2001] when the size of sets and the number of probes is small.
We show that any scheme that stores sets of size two from a universe of size m and answers membership queries using two bitprobes requires space Ω(m^(4/7)). The previous best lower bound was Ω(m^(1/2}). This is the first instance where the information theoretic lower bound is found to be not tight for adaptive schemes.
We show that any non-adaptive three probe scheme for storing sets of size two from a universe of size m requires Ω(m^(1/2}) bits of memory. This extends a result of Alon and Feige [SODA 2009] to small sets (to be presented in ESA 2010 joint work with Jaikumar Radhakrishnan and Smit Shah).
| Speaker: | Saswata Shannigrahi School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha R |
| Date: | Friday, 3 Sep 2010 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
We study the following set membership problem in the bitprobe model: Given a set S from a finite universe U , represent it in memory so that membership queries of the form Is x in S? can be answered with a small number of bitprobes. We obtain explicit schemes that come close to the information theoretic lower bound of Buhrman et al. [STOC 2000, SICOMP 2002] and improve the results of Radhakrishnan et al. [ESA 2001] when the size of sets and the number of probes is small.
We show that any scheme that stores sets of size two from a universe of size m and answers membership queries using two bitprobes requires space Ω(m^(4/7)). The previous best lower bound was Ω(m^(1/2}). This is the first instance where the information theoretic lower bound is found to be not tight for adaptive schemes.
We show that any non-adaptive three probe scheme for storing sets of size two from a universe of size m requires Ω(m^(1/2}) bits of memory. This extends a result of Alon and Feige [SODA 2009] to small sets (to be presented in ESA 2010 joint work with Jaikumar Radhakrishnan and Smit Shah).
We show that any scheme that stores sets of size two from a universe of size m and answers membership queries using two bitprobes requires space Ω(m^(4/7)). The previous best lower bound was Ω(m^(1/2}). This is the first instance where the information theoretic lower bound is found to be not tight for adaptive schemes.
We show that any non-adaptive three probe scheme for storing sets of size two from a universe of size m requires Ω(m^(1/2}) bits of memory. This extends a result of Alon and Feige [SODA 2009] to small sets (to be presented in ESA 2010 joint work with Jaikumar Radhakrishnan and Smit Shah).