Soda Related Work

SODA Related Work

Positioning at SODA is quantitative: the related-work section's job is to establish, bound by bound, exactly where your result sits in a lineage the referees already know. The most common positioning failure is not a missing citation but a mis-stated bound — quoting a superseded conference version, missing a stronger journal version, or comparing against the randomized bound when a better deterministic one exists.

The five lanes to sweep

The concurrent lane is the one that changes late: re-sweep arXiv in the final week before the July deadline and again before the September rebuttal — a concurrent improvement discovered by the referee but unacknowledged by you turns a coexistence story into a credibility problem.

Bound-lineage verification recipe

For every row of your comparison table (soda-writing-style):

1. Find the paper's dblp entry (dblp.org) — canonical venue + year.
2. Check for a journal version listed alongside the conference version;
   if one exists, read ITS abstract for the strongest stated bound.
3. Check the arXiv page for post-publication revisions or errata.
4. Quote: strongest bound, both versions cited ("[SODA 2019; SICOMP 2021]"),
   with the model/caveat column filled from the actual theorem statement.
5. If two papers claim the same bound, cite both and let dblp dates
   order them — do not adjudicate priority disputes in your paper.

arXiv-first culture and priority

The algorithms community treats arXiv posting as the priority event and the conference as certification. Consequences for positioning:

• Cite arXiv preprints of results you use or displace — refusing to engage with a well-known preprint because it is "unpublished" reads as gamesmanship. Distinguish status in the bibliography (arXiv:2401.xxxxx, preprint).
• If your result was scooped between writing and deadline, the honest structure is a "concurrent and independent work" paragraph stating both results' deltas — PCs routinely accept parallel discoveries when the relationship is cleanly disclosed.
• Your own posting strategy: SODA permits arXiv dissemination before and during review (2027 CFP, checked 2026-07-08), so establishing priority early is free.

Self-citation under lightweight double-blind

SODA's double-blind rules explicitly require that important references not be omitted or anonymized (soda-submission). So:

• Cite your prior work in third person, fully: "extending the decomposition of [14]" — never "our decomposition [14]," and never a blanked "[anonymized]."
• A direct predecessor paper of yours belongs in the comparison table like anyone else's; suppressing it to "look more novel" is the actual violation.
• Do not cite an in-submission companion manuscript that referees cannot read; if the companion is load-bearing, post it to arXiv first.

Bibliography mechanics for dual-version results

The conference/journal duality has a concrete BibTeX answer — cite both, quote the strongest:

% Conference announcement:
@inproceedings{HLRW24soda, ... booktitle = {SODA}, year = {2024}, ... }
% If a journal version exists, add and PREFER its bound:
@article{HLRW26sicomp, ... journal = {SIAM J. Comput.}, ... }
% In text: "achieves O(m log^2 n) [HLRW24soda; journal version HLRW26sicomp]"

Hygiene rules that referees notice when violated:

• Never cite an arXiv identifier for a result that has a published version — it suggests the sweep stopped at the preprint.
• Never quote a bound from a paper's abstract; abstracts round. Quote the theorem, with its number if your comparison is load-bearing.
• Keep dblp keys or DOIs in comments next to each entry so the September rebuttal and the October camera-ready don't re-litigate attribution.
• Alphabetic-initial citation labels ([HLRW24]) are house convention in theory bibliographies; numeric labels work, but author-initial labels make your comparison table readable without flipping to the references.

Positioning prose patterns

• Lineage sentence: "For dynamic connectivity, worst-case bounds improved from O(sqrt n) [F] through n^{o(1)} [NSW] to the current polylog amortized bounds [HdLT; journal version]." Three citations, one sentence, and the referee knows you know the field.
• Incomparability paragraph: for results that trade parameters ("faster but randomized," "deterministic but amortized"), state the trade explicitly instead of claiming dominance.
• Technique genealogy: name where your tools come from ("our charging argument adapts [X]'s token scheme") — theory culture rewards disclosed intellectual debts and punishes discovered ones.

Output format

[Lineage verdict] Sound / Gaps / Mis-stated bounds found
[Lane sweep] <per-lane findings, incl. concurrent arXiv window>
[Version errors] <rows quoting superseded or weaker versions>
[Self-citation audit] <third-person compliance; nothing omitted or anonymized>
[Table repairs] <rows to add, bounds to correct, caveats to co-locate>