brycewang-stanford SODA Writing Style
SODA prose serves two readers with opposite budgets: a PC member triaging a record-size pool who gives you minutes, and a subreviewer in your exact niche who gives you days. The uncapped format (no page limit, full version encouraged — 2027 CFP, checked 2026-07-08) means you never trade completeness for space; the craft is entirely in layering, so the minutes-reader and the days-reader each get a document built for them.
The headline bound
An algorithms paper is quoted by its bound, so engineer the quotable sentence:
- State it with exact parameters: "a deterministic
O(m log^2 n)-time algorithm for weighted global min-cut," not "a faster deterministic algorithm." - Pair it immediately with the displaced bound: "improving the
O(m log^4 n)bound of [X, SODA 2019]." New readers calibrate by the delta. - If randomization, approximation, or model caveats qualify the bound, they appear in the same sentence — a caveat discovered on page 30 reads as concealment.
- Resist rounding up: "near-optimal" claims invite the referee to construct the regime where you are not.
The title-page abstract
SODA submissions open with a title page: title plus a one-to-two-paragraph abstract of the contributions (2027 CFP). This abstract is the PC's bidding surface — it decides who reviews you. Structure that has survived contact:
Paragraph 1 (the result):
Problem, model, headline bound, displaced prior bound, and the
open-problem citation if one exists. Numbers, not adjectives.
Paragraph 2 (the technique):
The one new idea, named concretely ("a recursive sparsifier that
tolerates deletions"), plus why known approaches get stuck —
one sentence each. This paragraph recruits the right expert.
First ten pages: the overview contract
Everything after the overview is verification; the overview itself must let a non-specialist theorist reconstruct why the result is true at cartoon resolution. Ingredients, in order of most common omission:
- Barrier paragraph — what specifically stops the previous technique. Papers that skip this get "incremental" reviews from readers who cannot see why the improvement was hard.
- Technique narrative with a running example — a small concrete instance walked through the new algorithm beats three pages of notation.
- Proof roadmap — lemma dependency sketch, so the back matter reads as
planned architecture (
soda-supplementary). - Comparison table — see below.
The prior-bound table
Algorithms referees expect the lineage as a table and will reconstruct it if you do not provide it — on their terms, not yours:
| Reference | Bound | Deterministic? | Model / caveat |
|---|---|---|---|
| [Karger-era result] | O(m log^3 n) |
randomized | Monte Carlo |
| [previous best] | O(m log^4 n) |
deterministic | — |
| This paper | O(m log^2 n) |
deterministic | — |
Rules: cite the strongest version of each prior result (journal version if it improved), include the inconvenient rows, and footnote incomparable results rather than omitting them.
Prose discipline for long documents
- Uncapped is not unedited. Every page must still earn verification effort; padding multiplies referee fatigue and referee fatigue reads as doubt.
- One notation system, declared once. Re-derivations of standard facts get a citation, not a subsection.
- Theorem statements are self-contained: model, input restrictions, and probability regime inside the statement, never "under the assumptions of Section 2" (referees quote theorems out of context; make that safe).
- Lemmas get names in comments ("the charging lemma") — PC discussion happens in nicknames, and you want yours to have them.
- Third-person self-citation throughout (lightweight double-blind,
soda-submission), but keep the citations present.
Titles that survive PC compression
The title is the unit of memory in deliberation and in citation. Patterns, with fictional examples:
| Pattern | Fictional example | When it fits |
|---|---|---|
| Bound-carrying | "Dynamic Interval Stabbing in Polylogarithmic Worst-Case Time" | The bound is the news — the default SODA choice |
| Barrier-breaking | "Breaking the sqrt(n) Barrier for Online Recoloring" | A named threshold falls; use only if prior work called it a barrier |
| Problem-resolving | "The Communication Complexity of Threshold Joins" | You close the problem (up to stated factors) |
| Technique-forward | "Deletion-Tolerant Sparsifiers and Their Applications" | Only when the tool provably outlives the application |
| Question title | "Is Sorting by Prefix Swaps Fixed-Parameter Tractable?" | Rare; only if the answer is surprising |
Anti-patterns: pun-first titles (unquotable in a review), "Towards..." (admits incompleteness), "A New Approach to..." (contains zero information), and stacked qualifiers that belong in the theorem, not the marquee.
Register calibration
| Overclaim | Calibrated version |
|---|---|
| "We settle the complexity of X" | "We resolve the deterministic time complexity of X up to log log n factors" |
| "Our technique is completely new" | "We are not aware of prior uses of deletion-tolerant sparsification in this setting" |
| "Experiments confirm our algorithm is practical" | "A preliminary implementation (not part of our claims) suggests the constants are moderate" |
| "It is easy to see" (×20) | Prove it once; "routine calculation, included for completeness, in Appendix D" |
Output format
[Style verdict] Submission-grade / Needs revision / Needs restructuring
[Headline audit] <bound stated exactly? caveats co-located? displaced bound named?>
[Abstract audit] <bidding-surface quality; expert-recruiting technique sentence present?>
[Overview audit] <barrier, running example, roadmap, table — which are missing>
[Register flags] <overclaims with suggested calibrated rewrites>