stoc-related-work

STOC Related Work

Theory positioning is quantitative: reviewers expect the paper to place its

bounds in an explicit lineage ("[A] gave $O(n^2)$; [B] improved to

$O(n \log n)$ under assumption X; we remove X and reach $O(n)$"), and they

check the lineage against their own memory of it. Errors here — a missed

improvement, a misquoted exponent, a result attributed to the journal version's

year instead of the conference announcement — are among the fastest credibility

losses available at this venue.

The lanes a STOC reviewer checks

| Lane | What must be covered | Typical miss |

|---|---|---|

| The direct lineage | Every prior bound on your exact problem, with its model | Quoting the weakest prior bound to inflate the delta |

| The barrier literature | Known obstructions your result confronts (relativization, natural proofs, hardness reductions, integrality gaps) | Claiming a breakthrough while silent on why the barrier does not apply |

| Neighboring models | The same question in weaker/stronger models (randomized vs. deterministic, static vs. dynamic, classical vs. quantum) | "First" claims that are only first in one cell of the model grid |

| Technique ancestry | Where your machinery comes from, even from other subfields | Reviewers who invented the machinery are plausibly your reviewers |

| Concurrent work | Recent arXiv/ECCC preprints on the problem | The subreviewer knows about last month's preprint; your draft predates it |

Version-aware citation, a theory-specific craft

Most important theory results exist as a conference extended abstract, a later

journal version, and a preprint — and they can differ mathematically (bounds

improve; bugs get fixed in the journal version). House rules:

• Cite the version whose statement you actually use. If you invoke the

strengthened journal bound, cite the journal paper, possibly alongside the

conference announcement.

• Date claims by first announcement (conference or preprint), attribute proofs

by where the complete proof appears.

• Keep both versions in the entry when the community habitually does:

@inproceedings{ST01-smoothed,
  author    = {Spielman, Daniel A. and Teng, Shang-Hua},
  title     = {Smoothed Analysis of Algorithms: Why the Simplex Algorithm
               Usually Takes Polynomial Time},
  booktitle = {Proc. 33rd ACM Symposium on Theory of Computing (STOC)},
  pages     = {296--305},
  year      = {2001},
  note      = {Journal version: J. ACM 51(3), 2004}
}

• dblp is the community's canonical metadata source; export entries from it

rather than hand-typing venues, and prefer its conference/journal splitting

over publisher aggregator records.

Concurrent and independent work

The arXiv/ECCC-first culture means collisions are visible within days, not

years. Norms as practiced:

• A concurrent preprint (posted around your submission, obtained independently)

gets a clearly flagged paragraph — "Independently and concurrently, [Z]

obtained..." — with an honest comparison of strength, generality, and

technique. Committees routinely accept both papers when the note is fair.

• A prior preprint you missed is not concurrent work; the delta must be

recomputed against it, sometimes fatally. Run a fresh arXiv/ECCC sweep the

week before the deadline, and again before camera-ready.

• If a collision surfaces mid-review, current practice varies on whether and

how to notify the chair; check the cycle's instructions (待核实) rather than

improvising contact with the PC.

Double-blind self-positioning

STOC 2026 was double-blind (checked 2026-07-08). Your prior work is often the

nearest related work, so:

• Cite yourself in third person, with no ownership markers ("building on the

framework of [7]" — not "our framework [7]").

• Do not cite an unpublished manuscript of yours that only the authors could

possess; if the submission genuinely depends on it, it must be publicly

posted (anonymity-compatibly) or its content inlined.

• Acknowledgement-style thanks to collaborators on adjacent work wait for

camera-ready.

Building the comparison honestly

• State comparisons in the prior work's own parameterization before yours;

translating everything into the units most flattering to your bound is

spotted immediately by the lane-one reviewer.

• When your result is incomparable to a prior one (better dependence on $n$,

worse on $\varepsilon$), say "incomparable" and give the crossover point —

that sentence pre-empts the review question (stoc-author-response's

objection ledger).

• A small comparison table in the introduction (result, model, bound, source)

is house-standard for crowded problems and often becomes the most-read

object in the paper.

The deadline-week sweep, as a procedure

1. Search arXiv (cs.DS, cs.CC, and your problem's other categories) and

ECCC for the problem's standard names and their variants; theory titles are

conventional enough that keyword search works.

1. Check the most recent STOC/FOCS/SODA accepted-paper lists — results

announced there may not have preprints yet.

1. Walk the dblp pages of the five authors most active on the problem; new

preprints appear there within days.

1. For each hit, classify: prior (delta must be recomputed), concurrent

(comparison paragraph), or unrelated-despite-title (note why, for your own

future reference).

1. Re-run the same sweep before camera-ready; the February-to-March window

regularly produces new lineage entries that the full version should cite.

Cycle-volatility warnings

• Anonymity rules for citing your own preprints follow the live CFP's

double-blind wording (待核实 per cycle; the policy is new at STOC and may be

refined).

• Deadline-week literature sweeps must include ECCC and the current FOCS/SODA

accepted-paper lists, which shift the frontier between CFPs.

Output format

[Lineage table] complete / gaps: <missing bounds or models>
[Barrier account] addressed / silent <- fix before review
[Version hygiene] statements matched to cited versions? dblp-verified?
[Concurrency] <preprints found in final sweep; comparison note drafted?>
[Self-citation] double-blind-safe / leaks: <list>