Pseudo-random graphs and bit probe schemes with one-sided error

Andrei Romashchenko

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 ty…