Publication
STOC 1978
Conference paper

Exact and approximate membership testers

Download paper

Abstract

In this paper we consider the question of how much space is needed to represent a set. Given a finite universe U and some subset V (called the vocabulary), exact membership tester is a procedure that for each element s in U determines if s is in V. An approximate membership tester is allowed to make mistakes: we require that the membership tester correctly accepts every element of V, but we allow it to also accept a small fraction of the elements of U - V.

Date

01 May 1978

Publication

STOC 1978

Authors

Resources

Share