- A-212 (STCS Seminar Room)
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).