soda-writing-style

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:

1. 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.
2. Technique narrative with a running example — a small concrete instance walked through the new algorithm beats three pages of notation.
3. Proof roadmap — lemma dependency sketch, so the back matter reads as planned architecture (soda-supplementary).
4. 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:

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:

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

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>