Soda Supplementary

SODA Supplementary Material

SODA has no supplementary upload: no ZIP slot, no separate appendix deadline, no reviewer-optional attachments. One PDF on HotCRP, with no page limit, carries everything (2027 cycle, checked 2026-07-08 via the SIAM SODA27 submission page). So "supplementary material" at SODA is an internal layout question: how to architect a 40-80 page document so that a triaging PC member, a assigned referee, and a rebuttal-window author can each navigate it.

The two-tier document

Think of the submission as front matter (what every reader reads) and back matter (what the assigned referee verifies), with an explicit contract between them:

The contract fails in both directions: front matter that cannot be judged alone reads as disorganized; back matter that a referee cannot verify reads as wrong.

Appendix architecture rules

• Order by dependency, not by section of first mention. A referee verifies linearly; forward references inside proofs multiply their working memory.
• Restate before proving. Use thm-restate or manual restatements so each appendix proof begins with the exact claim, eliminating page-flipping:

\usepackage{thm-restate}
% Front matter:
\begin{restatable}{theorem}{maindet}\label{thm:main}
  There is a deterministic $O(m\log^3 n)$-time algorithm for ...
\end{restatable}
% Back matter:
\maindet*   % restates Theorem 1 verbatim, then the full proof follows
\begin{proof} ... \end{proof}

• One notation table, early. Long documents die by drifting notation; a table after the introduction, and a rule that appendices introduce no new symbols without it, keeps a 60-page argument navigable.
• Name the appendices by claim, not "Omitted Proofs": "Appendix C: Proof of the Lower Bound (Theorem 3)" lets the referee jump straight from the rebuttal ledger to the page.
• Case-heavy arguments get a case index: a small table listing each case, its page, and its one-line resolution.

What lives outside the PDF

Only material that cannot be prose belongs elsewhere, referenced from the paper:

• Machine-verification archives (certificates, checkers) at an anonymity-safe URL — see soda-artifact-evaluation for packaging and the anonymity rules.
• Implementation companions with benchmark data, if any — the paper cites them as color, and reviewers owe them nothing.
• The arXiv full version is not an external supplement at submission time: what you submit to HotCRP must itself be complete. Never write "see the full version" in a SODA submission — you are already submitting it.

Navigation aids for a long reviewed document

An uncapped PDF is read on screens, out of order, by people hunting specific claims during rebuttal season. Invest in navigability the way capped-venue authors invest in compression:

\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue]{hyperref}
\usepackage[capitalize,nameinlink]{cleveref}   % "Lemma 4.2" links whole
% After the introduction:
\tableofcontents                                % legitimate in an uncapped venue
% In the appendix preamble, a claim index:
% Theorem 1  -> proved in Appendix B (p. 24)
% Theorem 2  -> proved in Appendix C (p. 31), uses Lemmas C.1-C.4
% Lemma 4.1  -> proved inline (p. 12)

• A table of contents is not decoration here — it is the referee's map, and its section titles should narrate the argument ("Bounding the recourse of the overlay"), not name genres ("Analysis, continued").
• The claim index (theorem → proof location) is the same artifact as the claims ledger in soda-reproducibility; generate both from one source.
• PDF bookmarks come free with hyperref; check they render, since some reviewers navigate exclusively through them.

Habits imported from capped venues that misfire here

Pre-upload back-matter audit

1. Grep the PDF text for "full version," "supplementary," and "omitted" — each hit is either a broken promise or a leftover from another venue's template.
2. Verify every front-matter theorem has a back-matter proof and vice versa (no orphan lemmas proving nothing that is claimed).
3. Check the dependency order: no proof uses a lemma proved later without an explicit forward pointer.
4. Compile with links on (hyperref) and click every \ref in the appendix.
5. Confirm the whole document — appendices included — passes the anonymity sweep.

Output format

[Back-matter verdict] Navigable / Needs restructuring / Incomplete
[Contract check] <front matter self-contained? back matter complete?>
[Orphans] <claims without proofs; proofs without claims>
[Ordering] <dependency violations found>
[External references] <archives cited; anonymity-safe? necessary?>