Probabilistic Data Structures

Bernoulli Sets: A Comprehensive Statistical Framework for Probabilistic Set Membership

Bernoulli Types: A New Foundation for Approximate and Oblivious Computing

I’ve been working on a series of papers that develop a unified theoretical framework for approximate and oblivious computing, centered around what I call Bernoulli types. These papers explore how we can build rigorous foundations for systems …

Cipher Maps: A Unified Framework for Oblivious Function Approximation Through Algebraic Structures and Bernoulli Models

Encrypted Search with Oblivious Bernoulli Types: Information-Theoretic Privacy through Controlled Approximation

Hash-Based Bernoulli Constructions: Space-Optimal Probabilistic Data Structures

Hash-Based Oblivious Sets: A Practical Framework for Privacy-Preserving Set Operations with Probabilistic Guarantees

The Latent/Observed Duality: A Unified Theory of Approximate Computing

Bloom Filters and the Art of Probabilistic Certainty

One of the most elegant ideas I encountered during my CS masters work is the Bloom filter—a data structure that gives you probabilistic membership testing with extraordinary space efficiency.

The Core Insight

A Bloom filter can tell you two things: …