icalp-supplementary

ICALP Supplementary (the body / appendix / full-version split)

ICALP gives you a 15-page body (excluding references and a clearly labelled appendix) plus an

appendix that may hold omitted proofs or a full version, read **at the program committee's

discretion. The whole game is deciding what goes where**: the body must let a referee *judge and

follow the paper; the appendix must let them verify* it. Getting this split wrong — either cramming

proofs into the body or hiding the substance in an unread appendix — is a common, avoidable weakness.

The governing principle

> The body earns the referee's belief; the appendix earns their verification.

• The body contains the model, the theorem statements, the main ideas, the key lemmas, and enough

of the central proof that a referee can see why it is true and that it is nontrivial.

• The appendix / full version contains the complete proofs, routine cases, and technical

details a referee consults to confirm correctness.

• "At the PC's discretion" means the appendix is not guaranteed to be read — so nothing whose

significance the referee must weigh may live only there.

What must be in the body

• The model and definitions needed to state the results.
• All headline theorem statements, positioned against prior bounds.
• The main technical idea — the new lemma or technique that makes the result work — at least in

proof-sketch form with the key step shown.

• Enough structure that every deferred proof has a clear pointer ("full proof in Appendix B.2").

What may be deferred to the appendix / full version

• Complete proofs whose ideas are sketched in the body.
• Routine or standard arguments, long case analyses, and calculations.
• Auxiliary lemmas whose statements the body can cite.
• Supporting computation / certificates (see icalp-experiments, icalp-reproducibility).

The two failure modes

| Failure | Symptom | Fix |

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

| Over-stuffed body | Every proof crammed into 15 pages; unreadable, over-budget | Move complete proofs to the appendix, keep sketches + key lemmas in the body |

| Hollow body | Body states theorems, all proofs (incl. the key idea) dumped in an unread appendix | Bring the central technique and the main lemma's proof idea into the body |

The hollow body is the more dangerous: referees judge on the body, and a paper whose substance they

cannot see reads as either thin or evasive, even if the appendix is perfect.

Completeness and findability

• Every deferred proof must actually exist in the appendix / full version. "Proof omitted" with no

full version is a soundness failure, not a space saving (icalp-reproducibility).

• Deferred proofs must be findable: label appendix sections to match the body's pointers so a

referee spends seconds, not minutes, locating a step.

• Keep the submission appendix and any public full version consistent in content.

Double-blind consistency

• The appendix / full version is part of the anonymous submission: no author names,

acknowledgements, grant numbers, or de-anonymizing links there either.

• If you host a full version on arXiv, refer to it as "the full version" without the identifying handle

during review (icalp-submission).

Worked split: a two-theorem paper

An algorithm (Thm 1) and a matching conditional lower bound (Thm 2). Body: the model; both theorem

statements with the prior-bound comparison; the algorithm's design and the one key invariant

proved; the reduction's construction and its intuition. Appendix / full version: the full

correctness proof and complexity analysis of the algorithm; the complete case analysis of the

reduction; a computer-checked verification of the gadget. Result: a referee can judge significance and

follow both ideas from the body, then verify every detail in the appendix.

Output format

[Body budget] <=15pp excl. refs + appendix; over/under
[In body] model / theorem statements / key technique / main-lemma idea: all present? gaps
[Deferred] complete proofs, routine cases, computation — each with a body pointer? yes/no
[Hollow-body check] is the central idea visible in the body (not only the appendix)? yes/no
[Completeness] every deferred proof actually present and findable? yes/no
[Anonymity] appendix/full version scrubbed and referenced without de-anonymizing? yes/no
[Fix queue] <ordered moves between body and appendix>