| name | stoc-reproducibility |
| description | Use when hardening a STOC (ACM Symposium on Theory of Computing) paper so its results can be independently checked — proof completeness across the extended-abstract/full-version split, single-source builds that prevent statement drift between the two documents, and determinism for any computation a claim relies on. |
STOC Reproducibility
For a proofs-only venue, "reproducible" means a third party can verify every
claimed theorem without contacting the authors. STOC's structure makes this a
two-document problem that pure-appendix venues do not have: the committee
reads a 12-page guaranteed window, the community reads the arXiv/ECCC full
version, and the paper is only as checkable as the pair is consistent. No
checklist form enforces any of this — the STOC 2026 CFP contains none (checked
2026-07-08) — so the discipline below is self-imposed or absent.
Statement drift: the STOC-specific failure
Whenever the same theorem exists in two documents, the versions decay apart:
a hypothesis strengthened during a proof repair gets updated in one file only; a
constant improves in the full version while the abstract still advertises the old
one; numbering shifts and cross-references silently point at the wrong lemma.
Drift is not cosmetic — a reader who finds Theorem 2's statement differing
between the proceedings and arXiv cannot tell which one is proved.
The mechanical cure is a single-source build: one repository of statement
files included by both documents, so a statement physically cannot fork.
% statements/thm-main.tex (the only copy of the claim, ever)
\begin{theorem}[Main; restated in the full version as Theorem~\ref{thm:main}]
\label{thm:main}
Under Assumption~\ref{ass:degree}, there is a deterministic
$O(m \log^{3} n)$-time algorithm computing a $(1+\varepsilon)$-approximate
solution for every fixed $\varepsilon > 0$.
\end{theorem}
% extended-abstract.tex % full-version.tex
\input{statements/thm-main} % \input{statements/thm-main}
\begin{proofsketch} ... \end{proofsketch} % \begin{proof} ... \end{proof}
An \iffull toggle in a shared preamble achieves the same with one master file;
either way, the invariant is one copy of every statement on disk.
Checkability audit before submission
| Question a verifier will ask | Passing standard |
|---|
| Is every claim in the first 12 pages proved somewhere I can reach? | Each theorem carries a forward pointer (appendix section or full-version anchor) |
| Do the two documents state identical theorems? | Single-source statements, or a diff run over extracted statement blocks |
| Are all hypotheses visible at the statement? | No condition introduced only inside a proof ("assume wlog the graph is connected" that is not wlog) |
| Do invoked external theorems apply? | Citation with result number, plus a line confirming your setting meets its hypotheses |
| Can the parameter trail be followed? | Constants named where they first appear; "for sufficiently large n" bounded explicitly at least once |
| Are "standard" steps actually standard? | Anything a second-year graduate student cannot fill in gets written out |
Computation that claims depend on
If any theorem rests on a machine check (case enumeration, solver certificate,
verified numerics), reproducibility requirements sharpen from "nice" to
"load-bearing":
- Determinism: the run must be exactly repeatable — fixed enumeration order,
no wall-clock cutoffs deciding mathematical facts, solver versions pinned.
- Independence: publish the certificate and a separate checker, so trust does
not reduce to trusting your search program (see
stoc-artifact-evaluation
for packaging mechanics).
- Description: the paper itself must specify the computation precisely enough
that someone could rewrite it from scratch; code is evidence, prose is the
specification.
Illustrative-only plots and timing anecdotes carry no proof weight and need only
honesty: seed and instance disclosure, no claims beyond what is proved
(stoc-experiments covers when to include them at all).
Verification workflow for the author team
- Freeze statements four weeks out; from then on, statement edits require a
team-visible diff, because every edit can invalidate a downstream proof.
- Assign each theorem a verifier who did not write its proof; record
pass/fail per proof section, and treat any "I believe it but cannot check
line 5" as a fail.
- Grep both documents for confessions:
wlog, clearly, standard,
similar, it is easy to see — each hit either survives justification or
gets expanded.
- Re-derive the main constant chain once, by hand, on paper, from the final
text only. This catches the strengthened-hypothesis-updated-once bug that
review will otherwise catch for you.
- After camera-ready, keep the full version live-maintained: arXiv revision
with a dated changelog is the community's accepted correction channel.
Vignette: how drift actually happens
A team submits in November with Theorem 2 requiring subgaussian noise. In
December a reviewer-anticipating coauthor realizes the proof of Lemma 7 uses a
fourth-moment bound that subgaussianity gives but the written hypothesis does
not state; she patches the full-version draft to "subgaussian with parameter
$\sigma$" and adjusts two constants. The extended abstract is not touched —
nobody is editing a submitted file. At camera-ready in March, the proceedings
version is produced from the submitted sources, and the published extended
abstract now states a theorem the team knows is proved only under the amended
hypothesis. Nothing dishonest happened at any step; the pipeline had two copies
of one statement and no synchronization rule. The single-source layout above
makes this sequence structurally impossible, which is why it is worth the
Makefile friction.
Cycle-volatility warnings
- If a future CFP introduces any structured checklist, code policy, or
supplementary channel, it will say so; the 2026 cycle had none (待核实 yearly).
- The 12-page guaranteed window and the full-version expectation are 2026
wording; both shape where proofs must live, so re-read the live CFP before
restructuring.
Output format
[Checkability verdict] verifiable end-to-end / gaps found
[Statement-drift control] single-source / manual sync (risk) / diverged <- fix
[Hypothesis visibility] clean / hidden conditions at: <list>
[External results] all hypothesis-checked / unchecked: <citations>
[Load-bearing computation] none / deterministic + certified / unreproducible <- blocker
