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

Lane	Where it lives	What referees check
Direct predecessors	SODA/STOC/FOCS/ESA/ICALP proceedings, arXiv	Is the displaced bound the true state of the art?
Journal consolidations	SICOMP, JACM, ACM ToA, Algorithmica	Did the journal version strengthen the bound you quote?
Lower bounds / hardness	Same venues + ITCS, CCC	Does a conditional lower bound cap your claimed improvement's meaning?
Concurrent arXiv postings	arXiv (last ~18 months)	Anything simultaneous that changes the delta
Adjacent-model results	Distributed (PODC/DISC), parallel (SPAA), geometry (SoCG), dynamic/streaming lines	Incomparable-but-related results a subreviewer will ask about

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>