Sampling and counting contingency tables

Sampling and counting contingency tables concerns nonnegative integer matrices with prescribed row and column sums: generating such a table uniformly at random, and approximately counting them, in time polynomial in both dimensions and in the binary length of the margins. Two manuscripts dated 24 September 2026 in OpenAI's public mathematics collection (github.com/openai/math) claim an exact uniform sampler with expected polynomial bit time, an almost-uniform sampler with worst-case polynomial bit time, and a fully polynomial randomized approximation scheme for counting tables with arbitrary individual cell bounds. The collection includes a Lean formalization of these statements. This page summarizes the published claims and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper, code or a formal proof is not presented here as independent verification.

Background

As recounted in the introductions of the manuscripts:
- For two rows, Dyer and Greenhill gave polynomial-time approximate counting and sampling and Kijima and Matsui exact sampling by coupling from the past. For a fixed number of rows, Cryan and Dyer, Dyer, and Cryan, Dyer, Goldberg, Jerrum and Martin gave approximate counting, exact rejection sampling and rapid mixing, with bounds depending on the row count.
- DeSalvo and Zhao gave an exact divide-and-conquer construction whose polynomial running time is conditional on a counting conjecture. Dyer, Kannan and Mount and Morris used the geometry of the transportation polytope for dense tables, and Arman, Gao and Wormald gave exact generation for sparse margins; their survey reported that no polynomial-time approximately uniform sampler for arbitrary margins was known.
- The exact sampler uses the residual-mixture correction of Göbel, Liu, Manurangsi and Pappik.

The original results

Claims.
- Theorem 1.1 of Exact Uniform Sampling of Contingency Tables with Arbitrary Margins states that, for arbitrary nonnegative integer margins of equal total, there are an algorithm whose output law is within 2^−k of uniform in total variation, with running time polynomial in m, n, log(N + 1) and k, and an exactly uniform sampler that terminates almost surely with expected polynomial running time, both in the model of unbiased random bits and bit operations.
- Theorem 1.1 of An FPRAS for Cell-Bounded Contingency Tables states that one randomized algorithm, given margins, individual entry bounds and rational accuracy parameters, returns an estimate within relative error ε with probability at least 1 − δ, returns zero on every execution when no table exists, and has a polynomial bound on its bit operations on every execution.
Method, as described: the sampler combines a padding construction that makes completion problems dense, a dense completion routine in the tradition of Dyer–Kannan–Mount and Morris, a separate chain for cells incident to small margins, and an exact correction by a residual mixture with a rare exhaustive draw. The counting manuscript builds its estimator from scales, integer signatures and transport between signature classes.
Sources. The manuscripts Exact Uniform Sampling of Contingency Tables with Arbitrary Margins and An FPRAS for Cell-Bounded Contingency Tables at commit 1581d4c.
Formalization, as described by the repository. The scope note states that the formalization gives the exact uniform sampler with expected polynomial bit complexity, a sampler with a fixed polynomial time bound on every execution and total-variation error at most 2^−k, and the approximation scheme for counting tables with individual cell bounds, including zero bounds, with running time polynomial on every random tape. The Comparator statement is ContingencyTables.lean.

Public follow-up work

Date	Work	Relation	Public claim	Public status (checked 20 October 2026)
2026-10-07	R. Gounder, Kohze/counting-and-sampling-review, Approximate Counting and Uniform Sampling: A Critical Review of Matroid Intersections, Contingency Tables, and Graph Switch Chains	Review (narrative)	A narrative review of six counting and sampling manuscripts of the collection, including both contingency-table manuscripts, relating their stated guarantees to the earlier literature through reductions, worked probability laws and accuracy and runtime models, with reproduction scripts for a bounded-table reduction and finite examples.	GitHub repository with a manuscript; its LaTeX source includes a dedicated AI disclosure.
2026-10-08	MathVet (GitHub; review of openai/math, tables at repository commit `c76f1e4`, 14 October 2026)	Review (fidelity of the formal statements)	Rates this family "full", with the remark that the counting statement assumes equal row and column totals, so that the algorithm is not required to output zero when the totals differ and no table exists. It records a Comparator pass.	MathVet states that it does not claim any theorem false and reports what was machine-checked as stated.
2026-10-08	atimics/math2, Cross-family corollaries of openai/math, entry TC-2 (GitHub, commit `2c0f005`)	Related (containment of statements)	A written derivation that the counting scheme of the collection's polymatroid-intersection manuscript contains this family's counting scheme as a special case, by expressing cell-bounded tables as common integer points of two rank functions; it notes that the polymatroid manuscript itself imports this family's statements, and lists almost-uniform sampling as a lead.	Repository catalogue (checked 17 October 2026); it states that every entry is conditional on the OpenAI claims it cites.
2026-10-08	EcoDataLab/contingency-tables (GitHub)	Extension (formal; bounded sampler)	A research project building on this family: a Lean-checked bound of order 80,000d¹⁷ on the inverse spectral gap of an auxiliary chain, a complete bounded sampler with polynomial time on every tape and total-variation error at most 2^−h for equal-total margins, exact reference samplers and applications.	The README states that the research, implementations and reviews were produced by OpenAI Codex agents under EcoDataLab's direction, that its "independent" reviews are by separate AI agents, and that no outside human review is claimed; hosted Linux verification is recorded for a named set of declarations.
2026-10-10	cert-machine, openai/math lane K: run 38051470892	Verification (two kernels)	Records that Lean's default kernel and the nanoda kernel accept the `ContingencyTables` solution, in 3,430 s. The project reports two-kernel certification of 398 of 416 challenges of the collection.	Repository.
2026-10-10 to 2026-10-14	con-leche development journal (task #348)	Verification (second kernel)	In its run over all Comparator challenges of the collection at commit `fd4aeeb`, the journal's table of exceptions (time-outs, memory, errors) does not list `ContingencyTables`, so it was accepted by con-leche and by Lean's official kernel.	Development journal.
2026-10-16	J. Jardine, Lattice24, referee review of the sampling manuscript and of the counting manuscript in JJardine919/openai-math-audit (archived at Zenodo 10.5281/zenodo.23422995)	Review (AI-assisted audit)	Reports no gap and no minor notes in either manuscript. The reviewer states that it read every section of the sampling manuscript, and Sections 1–7 of the counting manuscript, without auditing its Section 8 on network-flow corollaries or its history section.	Part of an audit of the collection's manuscripts that the audit describes as complete. The reviews are published under CC BY 4.0.

Notes

The earlier results are due to the authors named in the Background section, as recounted by the manuscripts.
The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.