Approximate counting of cell-bounded contingency tables

A contingency table is a matrix of nonnegative integers with prescribed row and column totals. If every cell has its own upper bound, can the number of feasible tables be approximated in time polynomial in the binary input and requested precision?

Why it matters and what counts as progress

Why it matters: Small numerical margins can hide the difficulty of counting large tables. Cell bounds add constraints beyond the ordinary margin-only problem.

What counts as progress: Give a randomized relative-error estimate and bound its failure probability, including when the count is zero. State which dimensions and bounds can vary and whether the running-time guarantee holds on every random run.

How the problem developed

  1. 6 Oct 2026 · Reported cell-bounded counting scheme [1]

    OpenAI’s internal model One randomized algorithm counts nonnegative integer matrices with prescribed margins and individual cell bounds, including zeros, to relative error ε\varepsilon with failure probability at most δ\delta . Both dimensions and all numeric inputs vary in binary, and runtime is polynomial in input length, ε−1\varepsilon ^{-1} and log⁡δ−1\log \delta ^{-1} on every run.

AI contribution

An FPRAS for Cell-Bounded Contingency Tables

OpenAI

One randomized algorithm counts nonnegative integer matrices with prescribed margins and individual cell bounds, including zeros, to relative error ε\varepsilon with failure probability at most δ\delta . Both dimensions and all numeric inputs vary in binary, and runtime is polynomial in input length, ε−1\varepsilon ^{-1} and log⁡δ−1\log \delta ^{-1} on every run.

AI involvementAI-led
ImportanceNotable
Technical verificationFormal (Lean)
Human understandingFew
Paper date:

Sources

  1. An FPRAS for Cell-Bounded Contingency Tables
  2. OpenAI mathematics release
  3. OpenAI’s Lean scope for this manuscript
Publication history