Stoc Experiments

STOC Experiments

The ground truth about this venue: STOC papers are accepted on the strength of theorems, and the STOC 2026 Call for Papers asks for original research on the theory of computation with no empirical-evaluation requirement of any kind (checked 2026-07-08). Most STOC papers contain zero computation. The question this skill answers is not "how do I run experiments for STOC" but "does this computation have a legitimate job in a STOC paper, and if so, which job?"

The three legitimate jobs of computation

The fourth row is the routing trap. A STOC submission whose contribution needs runtime tables to be convincing is announcing that its theorems do not stand alone; committees read that accurately.

Constructive search, done credibly

Computer search that finds mathematical objects is a quiet workhorse of modern combinatorics and complexity papers. The credibility rules:

• Whatever the search finds must be verified by something other than the search: a short analytical argument, or a tiny independent checking program whose correctness is inspectable.
• Report the search honestly as heuristic ("found by simulated annealing over weight assignments") — the found object is the contribution, so the finder needs no rigor, but pretending the finder is exhaustive when it is not would be a false completeness claim.
• If the paper claims no object exists below some size, that is a proof step, not discovery; it jumps to row one of the table with all its obligations.

# Independent checker pattern: ~30 lines, no dependencies, verifies the
# certificate that the (arbitrarily messy) search produced.
import itertools

def is_valid_gadget(g):            # transcribes Definition 4.1 literally
    return all(constraint(g, s) for s in itertools.product([0, 1], repeat=k))

g = load("gadget.json")            # the object the paper's Lemma 4.2 uses
assert is_valid_gadget(g)          # a reader re-runs this in seconds
print("certificate valid: gadget satisfies Definition 4.1")

The checker transcribes a definition from the paper; anyone can audit 30 lines against Definition 4.1. That closure — messy finder, trivial checker — is what lets a theory reviewer accept a computed object without trusting your code.

Illustrations, if you must

A figure can help a cross-area committee member see a phenomenon (a threshold, a tradeoff curve, the shape of a potential function). Norms for keeping it from harming the paper:

• Caption it as illustration explicitly; never write "experiments confirm our theory" — theorems are not confirmed by samples, and the phrasing invites the benchmark framing you are avoiding.
• Keep it small: one figure, placed near the concept it illuminates, with the generation procedure in one appendix paragraph (instances, sizes, seed).
• Spend no guaranteed-read space on it. The first twelve pages are for theorem statements and proof overview; a decorative figure inside that window costs real estate the reading contract makes precious.
• Ask the deletion question: if the figure vanished, would any reviewer miss it? If not, delete it and reclaim the page.

Vignette: an illustration earning its page

A submission proves that a new local-search rule escapes a known family of bad local optima. The authors add one figure: the objective-value trajectory of the old rule and the new rule on the lower-bound instance from their own Section 5, showing the old rule plateauing exactly where Theorem 5.2 says it must and the new rule passing through. Why this works as illustration rather than benchmark: the instance is the paper's own analyzed object, not a dataset; the phenomenon shown is the theorem's content, not a performance claim; the caption states the instance parameters and that the plot is illustrative; and the figure sits in the appendix with a one-line pointer from the body, spending no guaranteed-read space. The same figure drawn on "20 standard TSPLIB instances" would have been a benchmark — and an invitation to review the paper as an experimental contribution it never intended to be.

Signals you are at the wrong venue

• The abstract's strongest sentence cites a speedup factor, not a theorem.
• Reviewers would need the code to evaluate the contribution.
• The natural comparison set is prior implementations rather than prior bounds.
• The result's interest depends on real-world input distributions rather than worst-case, average-case, or smoothed analysis.

Any two of these: run stoc-topic-selection and look hard at SODA, ALENEX, ESA, or an applied venue where empirical craft is rewarded instead of tolerated.

Cycle-volatility warnings

• The theorems-first culture is structural, but scope sentences are rewritten each cycle; check the live CFP's topics list before arguing fit (待核实).
• Subcommunities differ: algorithmic game theory and quantum papers at STOC carry numerics somewhat more often than complexity papers do. Calibrate against recent accepted-paper lists (acm-stoc.org/stoc2026/accepted-papers.html).

Output format

[Computation verdict] none needed / proof step / discovery / illustration / benchmark <- re-route
[Proof-step obligations] certificate + independent checker in place? yes / no / n.a.
[Illustration budget] <figures, placement outside the 12-page window?>
[Deletion test] <what is lost if all numerics are removed>
[Venue signal] STOC-shaped / drifting empirical (target: <venue>)

Source: brycewang-stanford/Awesome-Journal-Skills → STOC-Skills/skills/stoc-experiments/SKILL.md