Pseudo-Random Graphs and Bit Probe Schemes with One-Sided Error

We study probabilistic bit-probe schemes for the membership problem. Given a set A of at most n elements from the universe of size m we organize such a structure that queries of type “x∈A??” can be answered very quickly. H. Buhrman, P.B. Miltersen, J. Radhakrishnan, and S. Venkatesh proposed a randomized bit-probe scheme that needs space of O(nlogm) bits. That scheme has a randomized algorithm processing queries; it needs to read only one randomly chosen bit from the memory to answer a query. For every x the answer is correct with high probability (with two-sided errors). In this paper we slightly modify the bit-probe model of Buhrman et al. and consider schemes with a small auxiliary information in “cache” memory. In this model, we show that for the membership problem there exists a bit-probe scheme with one-sided error that needs space of O(nlog² m+poly(logm)) bits, which cannot be achieved in the model without cache. We also obtain a slightly weaker result (space of size n ^1+δ poly(logm) bits and two bit probes for every query) for a scheme that is effectively encodable.