ITCS Experiments
ITCS is a pure-theory venue: the primary — usually the only — evidence for a claim is a
proof. There is no experiments requirement, no benchmark, no leaderboard, and no reviewer
expectation of an empirical section. Bringing an ML-conference or SE reflex here (a table of
numbers "showing" the method works) misreads the venue: at ITCS a theorem is proved, not
measured. This skill is about matching evidence to a theory claim and about the rare case
where a small computation genuinely helps.
Proofs are the evidence
- Every central claim is settled by a complete proof, not by examples. A pattern that "holds
in all cases we tried" is a conjecture, not a theorem — label it as such and prove or drop it.
- Match the claim shape to the argument shape: an upper bound needs a construction + analysis;
a lower bound needs an adversary/reduction; a separation needs a witness object; an
impossibility needs a contradiction from the assumption. Reviewers check that the kind of
argument fits the kind of claim.
- A new model needs an anchoring result (see
itcs-writing-style) — a separation or a surprising
possibility that proves the model is neither empty nor everything. That anchoring result is
the "experiment" an ITCS PC wants: evidence the model is alive.
Worked examples and separations as evidence
Non-proof evidence that is welcome, because it makes the mathematics concrete:
- Worked examples that instantiate a definition on a small case and show the intended
behavior — invaluable for a new model, and cheap insurance against the "is this trivial?"
objection.
- Explicit separating objects — a small graph, code, distribution, or gadget that witnesses a
gap between two settings. If finite, include the object so a reviewer verifies the separation
directly.
- Tight-example constructions showing an analysis cannot be improved — the theory analogue of
an ablation, demonstrating the bound is not loose by accident.
The rare, well-scoped computation
Some ITCS papers include a small computational component: a computer search that found a
gadget, a SAT/SMT solve certifying a finite separation, a numerically evaluated construction.
When one genuinely helps, scope it tightly:
- It supports a proved claim; it is never the claim. "A search over all graphs on <= 12
vertices found the gadget of Lemma 4, whose properties we then prove" is legitimate. "Our
method achieves 92% on a benchmark" is a category error at ITCS.
- Make it checkable without rerunning. State the exact search space, the tool and version, and
— crucially — include the finite object the search produced (the graph, certificate, code)
so verification is a static check, not a re-computation. A reviewer should be able to confirm
the object has the claimed property by hand or with a one-line check.
- Report it honestly. If a construction is only verified numerically (not proved), say so and
mark exactly which claims rest on computation versus proof.
- Keep it off the anonymity leak surface. A linked repository under a personal GitHub is a
lightweight-double-blind slip; fold the object into an appendix or host it neutrally (see
itcs-submission).
What NOT to import from empirical venues
| Empirical-venue habit |
Why it misfires at ITCS |
| A benchmark table as the main result |
ITCS proves; it does not measure. A table cannot establish a theorem |
| "Outperforms baselines by X%" framing |
There are no baselines to beat; the contribution is an idea/proof |
| Runtime plots to argue efficiency |
State and prove the asymptotic bound instead |
| An artifact/reproducibility package of code |
No artifact track exists; the "artifact" is the proof (see itcs-artifact-evaluation) |
| Statistical significance / error bars |
Irrelevant to a deterministic mathematical claim |
Decision procedure
[Claim] is it a theorem (prove it) or a pattern (label as conjecture, or prove/drop)?
[Argument fit] upper=construction+analysis / lower=adversary / separation=witness / impossibility=contradiction
[Alive] new model? -> anchoring separation or surprising-possibility result present?
[Compute?] does a small search/solve genuinely help a proved claim? if not, omit it
[Checkable] if compute used: search space + tool/version stated, finite object included?
[Honesty] each claim tagged proved vs. numerically-verified; anonymity leak surface clean?
Output format
[ITCS evidence status] proof-complete / gaps / mis-imported-empirics
[Central claims] each has a complete proof of matching shape? yes/no + list gaps
[Model alive] anchoring result present for any new model? yes/no
[Computation] present? if so: supports-a-proof only? checkable object included?
[Anonymity] no personal-repo leak from any computational content? yes/no
[Fix queue] <ordered edits>
1---2name: itcs-experiments3description: Use when deciding what counts as evidence for an ITCS theory claim — proofs as the primary evidence, worked examples and separations that make a model concrete, and the rare, well-scoped illustrative computation or simulation — and how to keep any computational content checkable and subordinate to the mathematics.4metadata:5 source: https://skillmd.com/skills/brycewang-stanford/itcs-experiments6---78# ITCS Experiments910ITCS is a **pure-theory** venue: the primary — usually the only — evidence for a claim is a11**proof**. There is no experiments requirement, no benchmark, no leaderboard, and no reviewer12expectation of an empirical section. Bringing an ML-conference or SE reflex here (a table of13numbers "showing" the method works) misreads the venue: at ITCS a theorem is proved, not14measured. This skill is about matching **evidence to a theory claim** and about the *rare* case15where a small computation genuinely helps.1617## Proofs are the evidence1819- **Every central claim is settled by a complete proof**, not by examples. A pattern that "holds20 in all cases we tried" is a conjecture, not a theorem — label it as such and prove or drop it.21- **Match the claim shape to the argument shape:** an upper bound needs a construction + analysis;22 a lower bound needs an adversary/reduction; a separation needs a witness object; an23 impossibility needs a contradiction from the assumption. Reviewers check that the *kind* of24 argument fits the *kind* of claim.25- **A new model needs an anchoring result** (see26 [`itcs-writing-style`](../itcs-writing-style/SKILL.md)) — a separation or a surprising27 possibility that proves the model is neither empty nor everything. That anchoring result *is*28 the "experiment" an ITCS PC wants: evidence the model is alive.2930## Worked examples and separations as evidence3132Non-proof evidence that *is* welcome, because it makes the mathematics concrete:3334- **Worked examples** that instantiate a definition on a small case and show the intended35 behavior — invaluable for a new model, and cheap insurance against the "is this trivial?"36 objection.37- **Explicit separating objects** — a small graph, code, distribution, or gadget that witnesses a38 gap between two settings. If finite, *include the object* so a reviewer verifies the separation39 directly.40- **Tight-example constructions** showing an analysis cannot be improved — the theory analogue of41 an ablation, demonstrating the bound is not loose by accident.4243## The rare, well-scoped computation4445Some ITCS papers include a *small* computational component: a computer search that found a46gadget, a SAT/SMT solve certifying a finite separation, a numerically evaluated construction.47When one genuinely helps, scope it tightly:4849- **It supports a proved claim; it is never the claim.** "A search over all graphs on <= 1250 vertices found the gadget of Lemma 4, whose properties we then prove" is legitimate. "Our51 method achieves 92% on a benchmark" is a category error at ITCS.52- **Make it checkable without rerunning.** State the exact search space, the tool and version, and53 — crucially — **include the finite object** the search produced (the graph, certificate, code)54 so verification is a static check, not a re-computation. A reviewer should be able to confirm55 the object has the claimed property by hand or with a one-line check.56- **Report it honestly.** If a construction is only verified numerically (not proved), say so and57 mark exactly which claims rest on computation versus proof.58- **Keep it off the anonymity leak surface.** A linked repository under a personal GitHub is a59 lightweight-double-blind slip; fold the object into an appendix or host it neutrally (see60 [`itcs-submission`](../itcs-submission/SKILL.md)).6162## What NOT to import from empirical venues6364| Empirical-venue habit | Why it misfires at ITCS |65|---|---|66| A benchmark table as the main result | ITCS proves; it does not measure. A table cannot establish a theorem |67| "Outperforms baselines by X%" framing | There are no baselines to beat; the contribution is an idea/proof |68| Runtime plots to argue efficiency | State and prove the asymptotic bound instead |69| An artifact/reproducibility package of code | No artifact track exists; the "artifact" is the proof (see itcs-artifact-evaluation) |70| Statistical significance / error bars | Irrelevant to a deterministic mathematical claim |7172## Decision procedure7374```text75[Claim] is it a theorem (prove it) or a pattern (label as conjecture, or prove/drop)?76[Argument fit] upper=construction+analysis / lower=adversary / separation=witness / impossibility=contradiction77[Alive] new model? -> anchoring separation or surprising-possibility result present?78[Compute?] does a small search/solve genuinely help a proved claim? if not, omit it79[Checkable] if compute used: search space + tool/version stated, finite object included?80[Honesty] each claim tagged proved vs. numerically-verified; anonymity leak surface clean?81```8283## Output format8485```text86[ITCS evidence status] proof-complete / gaps / mis-imported-empirics87[Central claims] each has a complete proof of matching shape? yes/no + list gaps88[Model alive] anchoring result present for any new model? yes/no89[Computation] present? if so: supports-a-proof only? checkable object included?90[Anonymity] no personal-repo leak from any computational content? yes/no91[Fix queue] <ordered edits>92```