Probabilistic-Data-Structures

The Bernoulli Model

Random approximate computation: the Bernoulli model, its papers, and the monograph that unifies them. Bloom filters are the special case; this is the general theory.

Bernoulli Types: Theory and Construction

Statistical Foundations and Empirical Validation

Two-Level Threshold Structures for Approximate Membership Testing

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

Entropy Maps

Entropy maps use prefix-free hash codes to approximate functions without storing the domain, achieving information-theoretic space bounds with controllable error.

Entropy Maps

Entropy maps use prefix-free hash codes to approximate functions without storing the domain, achieving information-theoretic space bounds with controllable error.

A Boolean Algebra Over Trapdoors

A Boolean algebra framework over trapdoors for cryptographic operations. Introduces a homomorphism from powerset Boolean algebra to n-bit strings via cryptographic hash functions, enabling secure computations with one-way properties.

Noisy Turing Machines: Noisy Logic Gates

Analyzing how Bernoulli Boolean types propagate through logic circuits, with correctness probabilities for noisy AND gates and interval arithmetic for composed circuits.

The Bernoulli Model: A Probabilistic Framework for Data Structures and Types

The Bernoulli Model is a framework for reasoning about probabilistic data structures by treating noisy outputs as Bernoulli-distributed approximations of latent values, from Booleans to set-indicator functions.

The Bernoulli Model: A Probabilistic Framework for Data Structures and Types

The Bernoulli Model is a framework for reasoning about probabilistic data structures by treating noisy outputs as Bernoulli-distributed approximations of latent values, from Booleans to set-indicator functions.

Boolean Algebra over Trapdoor Sets: A Practical Framework for Privacy-Preserving Set Operations with Probabilistic Guarantees

Bloom Filters

Bloom filters trade perfect recall for extraordinary space efficiency. How they work and why they matter.