Skip to main content
← All Series

Bernoulli Types

Introductory posts on the Bernoulli model: noisy Booleans, Bloom filters as the one-sided special case, and computing with known false-positive and false-negative rates. The research hub and the monograph hold the full treatment.

2 parts

A Bernoulli type is a value you observe through a known, noisy channel: a Boolean that is wrong with a false-positive rate on one side and a false-negative rate on the other. A Bloom filter is the familiar special case, with the false-negative rate pinned to zero. The posts in this series are the on-ramp: what the model says, and why approximate answers are often the right trade.

Where the full treatment lives

  • The Bernoulli Model research hub is the front door. It lists the preprints, credits the prior work the model builds on, links the software, and tracks every related post, including the ones outside this series (noisy gates, entropy maps, perfect hashing, the trapdoor Boolean algebra).
  • The monograph, Bernoulli Types: Two-Sided Error in Approximate Membership, Retrieval, and Computation, builds the model from a single noisy bit outward to sets, maps, relations, and types. Read it online or as a PDF.

The Bernoulli model is also the error model for Trapdoor Computing, which uses the same algebra for computing on opaque encodings.

Author

Alexander Towell, metafunctor.com

Posts in this Series

Showing 2 of 2 posts