Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BLOOM FILTER:
Reports tagged with bloom filter:
TR10-087 | 17th May 2010
Shachar Lovett, Ely Porat

A lower bound for dynamic approximate membership data structures

An approximate membership data structure is a randomized data
structure for representing a set which supports membership
queries. It allows for a small false positive error rate but has
no false negative errors. Such data structures were first
introduced by Bloom in the 1970's, and have since had numerous
applications, ... more >>>


TR25-043 | 5th April 2025
Shlomi Dolev

Towards EXPTIME One Way Functions Bloom Filters, Succinct Graphs & Self Masking

Consider graphs of n nodes and use a Bloom filter of length 2 log3 n bits. An edge between nodes i and j, with i < j, turns on a certain bit of the Bloom filter according to a hash function on i and j. Pick a set of log ... more >>>




ISSN 1433-8092 | Imprint