brycewang-stanford ICALP Experiments (proof strategy, and computation in service of proofs)
At ICALP there is usually no experiment section — the evidence for the claim is the proof. This
skill is therefore about matching the argument to the claim shape, and about the narrow, real
cases where computation supports a theorem (a computer-assisted proof, an SMT-checked base case, an
exhaustive small-case verification). It is deliberately not an empirical-evaluation guide: a paper
whose contribution is a benchmark result is mis-routed (icalp-topic-selection).
Match the argument to the claim
| Claim shape | The argument that fits | Common failure caught by referees |
|---|---|---|
| Upper bound / faster algorithm | Algorithm + correctness proof + complexity analysis | Correctness hand-waved; complexity ignores a hidden cost |
| Approximation ratio | An analysis bounding cost vs optimum, with a tight example | Ratio proved only on the easy case; no tight instance |
| Lower bound (unconditional) | A reduction, adversary, or information-theoretic argument | Model too weak to be interesting, or gap left open |
| Conditional lower bound | A fine-grained reduction from SETH/3SUM/APSP | Wrong assumption invoked; reduction loses a factor |
| Decidability / complexity (Track B) | A decision procedure + matching hardness | Procedure sketched; hardness for a different fragment |
| Dichotomy / characterization | Exhaustive case analysis with each case proved | A case silently dropped; "similarly" hiding a hard case |
When computation legitimately supports a theorem
Some ICALP results genuinely rely on computation. It must be rigorous and checkable, not suggestive:
- Exhaustive small-case verification — checking a property for all objects up to size k as a base case of an induction. State the exact range, the encoding, and make the search reproducible.
- SAT/SMT-certified steps — using a solver to verify a finite gadget or unsatisfiability. Ship the encoding and, where possible, an independently checkable certificate (UNSAT proof, Farkas witness), not just "the solver said so."
- Computer-assisted case analysis — a program enumerating cases in a proof. The program is part of the proof; its logic must be described and its output verifiable.
The bar: a referee (or a reader of the full version) must be able to re-run or independently check the computation. A number a solver produced with no reproducible input is not a proof step.
Keep it a proof paper, not an experiment paper
- Supporting computation certifies a step; it does not replace the theorem. If the only evidence for the main claim is "it worked on our instances," the paper is experimental and belongs elsewhere.
- Do not add a benchmark table to a theory paper to look more complete — ICALP referees read it as either irrelevant or as a signal the theorem is weak.
- Running time measured is not running time proved. The contribution is the provable bound.
Reproducibility of the computational part
If computation backs a proof, treat it like the full version (see icalp-reproducibility):
- Provide the code and inputs (or precise pseudocode) in the appendix / full version or a public repository referenced at camera-ready.
- Provide certificates an independent checker can verify where the technique allows.
- Pin versions (solver, seed if randomized search) so the check is deterministic.
Worked vignette: a dichotomy with a computer-checked base
A Track B paper proves a dichotomy over a family of constraint languages: tractable vs NP-hard. The inductive step is by hand; the base cases (finitely many small languages) are verified by an exhaustive program. To meet the bar: state the finite base set precisely, describe the enumeration, ship the code and its output in the full version, and — for the hardness base cases — include reductions a referee can check by hand rather than leaving them to the program alone. State clearly which cases are machine-verified and which are proved analytically.
Output format
[Claim shape] upper / approximation / lower (uncond) / lower (conditional) / decidability / dichotomy
[Argument fit] the proof strategy matches the claim? gaps: <where>
[Computation role] none / base-case check / solver-certified step / computer-assisted cases
[Checkability] certificate or reproducible input provided? independent check possible? yes/no
[Not-an-experiment guard] is the theorem the evidence (not benchmark performance)? yes/no
[Fix queue] <ordered: proof gaps, missing certificates, mis-routed empirical framing>