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.

1. Technique narrative with a running example — a small concrete instance

walked through the new algorithm beats three pages of notation.

1. Proof roadmap — lemma dependency sketch, so the back matter reads as

planned architecture (soda-supplementary).

1. 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>