Probabilistic-Data-Structures

The Bernoulli Model

Random approximate computation in one model: the Bernoulli model, its preprints, the monograph that unifies them, and the prior work it builds on.

Cipher Maps: Total Functions as Trapdoor Approximations

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.

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.

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.