Soda Experiments

SODA Experiments

SODA's stated scope covers the design and analysis of efficient algorithms and data structures, "including theoretical analysis and experimental validation" (SIAM SODA conference pages, checked 2026-07-08) — but the reviewing center of gravity is the theorem. Experiments at SODA are admissible evidence, never the verdict. Meanwhile the same registration desk in Philadelphia hosts ALENEX, the SIAM Symposium on Algorithm Engineering and Experiments, where experiments are the verdict (ALENEX 2027: January 24-25, 2027, submissions due July 20, 2026, with formal artifact evaluation). The first decision is always routing.

The routing question

The eleven-day gap between SODA's deadline (July 9, 2026) and ALENEX's (July 20, 2026) exists to be used: the theory paper goes to SODA, and the engineering follow-up — with its own contribution, not a reformat — goes to ALENEX.

When numerics help a SODA submission

• Constant-factor sanity. A bound with towering constants invites the "galactic algorithm" objection; a small experiment showing the constants are civilized defuses it in one figure.
• Tightness illustration. Plotting measured cost against the proved bound on generated worst-case-family instances makes a tightness conjecture visible.
• Heuristic-gap motivation. When the paper's point is that theory lags practice (or vice versa), measured evidence of the gap justifies the question.
• Counterexample exhibition. A constructed instance defeating prior heuristics is stronger shown than described.

If none of these apply, include no experiments. A benchmark table bolted onto a pure-theory SODA paper signals venue confusion and spends referee goodwill.

Honest-numerics protocol

Experiments inside a theory paper are held to theory standards of precision about what they claim:

• Label the claim class explicitly: illustration (visualizing a proved fact), evidence (supporting an unproved conjecture), or motivation (documenting a phenomenon). Never let an illustration drift into implied proof.
• Generate instances from stated distributions or named public families; "random graphs" without the model named is unfalsifiable.
• Report the machine, the implementation language, and whether comparisons use your reimplementation of the baseline (say so — reimplementation fairness is the standard objection).
• Deterministic seeds, released generator scripts (soda-artifact-evaluation for anonymity-safe packaging).

Figure caption pattern (illustration class):
"Measured comparisons of Algorithm 1 on the lower-bound family of
Section 5 (n = 2^10..2^20, 50 seeds, median and quartiles), against
the proved O(n log n) curve (dashed). Instance generator and seeds:
see the verification archive. This figure illustrates Theorem 2; the
theorem's proof does not depend on it."

The final sentence of that caption is the SODA-specific move: it tells the referee the mathematics stands alone.

Instance-generation discipline

The credibility of a theory paper's numerics lives in the generator, not the plot. A generator worth releasing:

# gen_lowerbound_family.py -- worst-case family from Section 5 (fictional)
import argparse, random

def instance(n: int, seed: int):
    rng = random.Random(seed)          # single seeded source, no globals
    # ... construct the Section-5 gadget deterministically from (n, seed) ...
    return gadget

if __name__ == "__main__":
    p = argparse.ArgumentParser()
    p.add_argument("--n", type=int, required=True)
    p.add_argument("--seed", type=int, required=True)
    a = p.parse_args()
    emit(instance(a.n, a.seed))        # documented, versioned output format

Requirements the referee-side rerun imposes: the paper names the family and the parameter grid; the generator is deterministic in (n, seed); the exact seeds behind every figure are listed in the archive; and any "real-world" inputs are named public datasets with checksums, not "graphs from our collaborators."

Placement and proportion

• Experiments go in one clearly bounded section (or an appendix), after the theory, never interleaved with proofs.
• Proportion signals identity: one figure and half a page reads as a theory paper with due diligence; five tables reads as an ALENEX paper trapped in the wrong submission queue.
• The abstract mentions experiments only if they carry a claim; "we also implement our algorithm" is title-page noise at SODA.

Output format

[Routing verdict] SODA / ALENEX / SEA / split, with the deciding property
[Inclusion verdict] <which of the four helper roles applies, or none>
[Claim-class labels] <illustration/evidence/motivation per figure>
[Protocol gaps] <instance models, seeds, baseline fairness, machine specs>
[Proportion check] <experimental mass appropriate for a theorem-led paper?>