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:

| Tier | Typical span | Contents | Reader promise |

|---|---|---|---|

| Front | pages 1-10ish | Title-page abstract, result statements, technique overview, prior-bound comparison, proof roadmap | Self-contained: a PC member can judge significance without back matter |

| Back | the rest | Full proofs in dependency order, deferred cases, calculation appendices, computational-check descriptions | Complete: no step outsourced to "standard arguments" that are not |

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

| Imported habit | Why it misfires at SODA |

|---|---|

| "Proof deferred to the supplementary material" | There is no supplement; the phrase signals template reuse from another venue |

| Squeezing to 12 pages and dropping proofs | Uncapped submission: dropped proofs read as gaps, not thrift |

| Separate anonymous ZIP with the appendix | No such upload exists; appendix rides in the PDF |

| Supplement written after the deadline | Nothing can be added after July; the PDF is the whole record |

| Appendix as a dumping ground of drafts | Referees read it; unpolished back matter damages the front matter's credibility |

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.

1. Verify every front-matter theorem has a back-matter proof and vice versa (no

orphan lemmas proving nothing that is claimed).

1. Check the dependency order: no proof uses a lemma proved later without an

explicit forward pointer.

1. Compile with links on (hyperref) and click every \ref in the appendix.
2. 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?>