Browse › Theoretical computer science › 115 Sampling and counting contingency tables with arbitrary margins
An FPRAS for Cell-Bounded Contingency Tables
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We give a fully polynomial randomized approximation scheme for counting nonnegative integer matrices with prescribed row sums, column sums, and individual entry bounds. Both dimensions vary, all numerical data are encoded in binary, and zero bounds are allowed. The algorithm uses only unbiased random bits and has a polynomial bound on its bit operations on every execution.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- EcoDataLab, contingency-tables: Open research on bounded contingency tables (GitHub repository, October 2026). Describes itself as auditing and improving OpenAI result #115, noting that the companion FPRAS "covers cell bounds and structural zeros"; it also reports a separate Lean development (1511 named declarations) for a bounded sampler, whose strict Comparator verification it says "remains open". [AI-generated per source] [family-level]
Formalization
- OpenAI math release, Sampling and counting contingency tables with arbitrary margins: Lean scope note (lean/docs/115.md, 2026). The release's scope statement for the FPRAS: binary-encoded margins and bounds, zero bounds allowed, relative error $\varepsilon$ with probability $1-\delta$, output zero when no table exists, and polynomial running time on every random tape; it shares the Comparator file
ContingencyTables.leanwith the companion sampling results. [AI-generated per source] [family-level]
Possibly relevant literature (found by the agent, not checked)
- Miller, Harrison, Exact Enumeration and Sampling of Matrices with Specified Margins (arXiv:1104.0323, 2011). Exact dynamic-programming counting of integer and binary matrices with given margins, polynomial when column sums are bounded; relevant to the account of exact versus approximate counting in Section 1.1, which does not cite it.
Digests and expositions
- Latent Seminar, Contingency tables: exact sampling and relative counting (Latent Seminar, 2026-10-07). Explains the sampling manuscript's rare residual correction and the counting manuscript's forest coordinates and multiplicity corrections, stating that it reviews selected sections rather than independently verifying the full proofs. [family-level]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 115
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:An-FPRAS-for-Cell-Bounded-Contingency-Tables-September-24-2026,
author = {{OpenAI}},
title = {{An FPRAS for Cell-Bounded Contingency Tables}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/An-FPRAS-for-Cell-Bounded-Contingency-Tables-September-24-2026/main.pdf}{OAI:An-FPRAS-for-Cell-Bounded-Contingency-Tables-September-24-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/115.md. The Lean statements have not been checked by people against the paper's claims.
Family 115: Sampling and counting contingency tables with arbitrary margins
For nonnegative integer matrices with prescribed row and column sums, gives exact uniform sampling in expected polynomial bit time and almost-uniform sampling in worst-case polynomial bit time. The dimensions and binary-encoded margins are unrestricted. Also gives a fully polynomial randomized approximation scheme for counting such tables with arbitrary individual cell bounds, including structural zeros, with polynomial cost on every execution.
Other papers in this family:
- Exact Uniform Sampling of Contingency Tables with Arbitrary Margins · September 24, 2026