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

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.
2. Check the most recent STOC/FOCS/SODA accepted-paper lists — results announced there may not have preprints yet.
3. Walk the dblp pages of the five authors most active on the problem; new preprints appear there within days.
4. For each hit, classify: prior (delta must be recomputed), concurrent (comparison paragraph), or unrelated-despite-title (note why, for your own future reference).
5. 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>