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>