Information-Theory

Bits Follow Types

Codecs are not ad-hoc bit formats. They are constructions on the algebraic structure of types.

When Lists Become Bits

Prefix-freeness is the property that lifts the free-monoid construction into bit space.

Oblivious Computing: Privacy Through Approximation

Information Theory, Inference, and Learning Algorithms

What I Learned by Analyzing My Own Research as Data

I asked an AI to analyze 140+ repos and 50+ papers as a dataset. The unifying thesis it found: compositional abstractions for computing under ignorance.

Arithmetic Coding

Arithmetic coding closes the gap between Huffman's per-symbol integer lengths and true entropy. A single number in the unit interval encodes an entire sequence; 32-bit integer arithmetic makes it practical.

All Induction Is the Same Induction

Solomonoff induction, MDL, speed priors, and neural networks are all special cases of one Bayesian framework with four knobs.

Huffman Coding

Given a finite distribution, Huffman's algorithm builds the prefix-free code with minimum expected length. It is the first entropy-optimal code in this series.

The Beautiful Deception: How 256 Bits Pretend to be Infinity

Cryptographic theory assumes random oracles with infinite output. We have 256 bits. This paper explores how we bridge that gap, and what it means that we can.

VByte / Varint

VByte trades bit-level precision for byte-alignment, and that trade wins in practice. Most production columnar databases and network protocols use VByte for integer encoding.

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.

Perfect Hashing: Space Bounds, Entropy, and Cryptographic Security

Space bounds, entropy requirements, and cryptographic security properties of perfect hash functions.

Rice / Golomb

Rice and Golomb codes are parametric: a single parameter k (or m) tunes the code to a specific geometric distribution. Choosing k is choosing your prior precisely.

Fibonacci Coding

Fibonacci coding uses Zeckendorf's representation to produce self-synchronizing codewords. Every codeword ends in two consecutive ones; a single bit flip corrupts at most two codewords.

Elias Delta and Omega

Elias delta and omega extend Elias gamma by recursively encoding the length prefix. Each step yields shorter codewords for large integers at a small constant cost for small ones.

Unary and Elias Gamma

Unary and Elias gamma are the two simplest universal codes. Unary encodes n in n bits; gamma in 2 log2(n)+1 bits. Each implies a different prior over the integers.

Universal Codes as Priors

Every prefix-free code is a hypothesis about the source. The codeword lengths determine an implicit probability distribution; the code is optimal when that prior matches the true source.

McMillan's Converse

Any length vector satisfying Kraft has a prefix-free code. Here is the construction.

Kraft's Inequality

Which codeword-length vectors are achievable by prefix-free codes? Kraft's inequality is the answer.

Packed Containers: Zero-Waste Bit-Level Storage in C++

What if containers wasted zero bits? A C++ library for packing arbitrary value types at the bit level using pluggable codecs.

Introduction to Sequential Prediction

The problem of predicting what comes next, from compression to language models