--- name: soda-related-work description: Use when positioning a SODA (ACM-SIAM Symposium on Discrete Algorithms) paper in the algorithms literature — tracing bound lineages across SODA/STOC/FOCS/ESA/ICALP and journals, handling arXiv-first priority culture, citing conference versus journal versions correctly, and self-citation under lightweight double-blind rules. --- # 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`): ```text 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: ```bibtex % 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 ```text [Lineage verdict] Sound / Gaps / Mis-stated bounds found [Lane sweep] [Version errors] [Self-citation audit] [Table repairs] ```