Focs Related Work

FOCS Related Work

At FOCS the bibliography sits inside the guaranteed-read set — the 2026 CFP promises committee attention to the abstract, the references, and the first ten pages (checked 2026-07-08). Theory reviewers routinely open a submission's reference list first, to place the paper in a lineage they already know. This skill treats related work as lineage engineering, not as a courtesy section.

The lineage table

For each headline theorem, reconstruct its history as a table before writing a word of prose. The table becomes the skeleton of the related-work section and a private audit of your novelty claim:

Rules the table enforces: the "version of record" column forces you to learn where each proof actually lives (the conference version often omits it); the technique column reveals whether your delta is a new bound or a new method — the committee weighs those differently.

Citing theory literature correctly

• Pin versions. When a proof you rely on exists only in a preprint, cite the specific arXiv version, because v4 may have repaired — or broken — the lemma you use:

@misc{doe-widget-2024,
  author        = {Jane Doe and Wei Ren},
  title         = {Widget Sparsifiers in Almost-Linear Time},
  year          = {2024},
  eprint        = {2403.01234v3},
  archiveprefix = {arXiv},
  note          = {Full version of a FOCS 2024 paper; Lemma 5.2 cited
                   from v3 -- statement differs in v1--v2}
}

• Distinguish the twins. FOCS and STOC records are chronically confused in bibliographies; verify every conf/focs/ vs conf/stoc/ attribution on dblp rather than copying a .bib entry from a survey. A committee member who catches a misattributed classic discounts the rest of your scholarship.
• Cite both versions when both matter. Standard theory form: cite the conference announcement for priority and the journal/arXiv full version for the proofs, in one entry ("Conference version in FOCS 2019; full version in SIAM J. Comput. 2022").
• ECCC has first-class status in complexity; treat an ECCC technical report as citable and version-pinned exactly like arXiv.

Concurrent and independent work

Theory's arXiv-first culture makes collisions visible early. House norms:

• A preprint appearing before your submission date must be engaged, even if only weeks old; "we were unaware" reads as "we did not check arXiv".
• Genuine independence is stated plainly and generously: one paragraph, what they prove, what you prove, where the techniques differ. Committees reward gracious handling and punish burying.
• If the concurrent result subsumes yours, say so to yourselves honestly before the committee does — a partially-subsumed paper can survive on its technique if the overview says which parts remain novel (focs-writing-style).

Self-citation under double-blind

FOCS has run double-blind for multiple cycles. The operating rule: your own prior work is ordinary literature. Cite it in the third person, with no possessives, and never structure the paper so that understanding it requires knowing the prior paper is yours. If your submission is the strengthening of your own arXiv preprint, cite the preprint as an independent object; the CFP's stated aim is unbiased first judgment, not unbreakable anonymity — but the prose must not do the unmasking itself.

The reference list as a guaranteed-read surface

Because FOCS promises committee attention to the references themselves, treat the bibliography's form as reviewed prose:

• Consistent venue naming (decide once: "FOCS 2014" or "55th FOCS" — not both), full author lists, and no "et al." truncation in entries.
• Dead giveaways of haste — [Anonymous, 2023] placeholders, duplicate entries with different keys, arXiv entries for papers long since published — each costs credibility with the one reader who sees only abstract, references, and ten pages.
• Order citations within a bracket chronologically so lineage sentences read as history: "[12, 31, 7]" forces the reviewer to reconstruct the timeline you should have presented.
• A reference list that omits the obvious experts is also a signal — the committee infers whom you expect as reviewers, and gaps look strategic even when they are accidental.

Pre-submission citation audit

1. Every bibliography entry checked against dblp or the publisher page — no entries inherited untested from other papers' .bib files.
2. Every "best known bound" claim paired with a citation dated within the last year — improvements you missed are the most common review correction.
3. Every reliance on an external theorem carries theorem number and version (this doubles as the checkability audit in focs-reproducibility).
4. arXiv swept for the last six months of your keywords; concurrent work engaged, not omitted.