icdt-experiments

ICDT Experiments

At ICDT the primary "evidence" is a proof, not a benchmark. This skill is about matching your

form of evidence to your claim: most ICDT papers are purely theoretical and need no experiments

at all, while a minority with a genuine algorithmic contribution benefit from a small, honest

evaluation. Bolting a systems-style experiment section onto a theorem paper does not raise its

standing — a loose bound or an unproved lemma will still sink it.

Match the evidence to the claim shape

| Claim shape | Primary evidence | Experiments? |

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

| Complexity of evaluating a query class | Matching upper and lower bounds, with proofs | No — the bound is the result |

| Expressiveness / separation | A construction or an Ehrenfeucht-Fraisse game establishing the separation | No — a witness, not a benchmark |

| Decidability / undecidability of a problem | An algorithm + termination proof, or a reduction from an undecidable problem | No |

| A new algorithm with a claimed practical complexity | The complexity proof plus an optional experiment showing the constants are reasonable | Optional, proportional |

| A dichotomy | Proof that each side holds and the boundary is exactly as stated | No |

The default answer is "the theorem is the evidence." Reach for experiments only when your paper

claims something about practice that the asymptotic bound alone does not settle.

Making the theoretical evidence airtight

• Tightness: if you claim a bound is tight, prove both directions and label which is the upper

and which the lower. A one-sided bound presented as a complete answer is the classic "revise."

• The right complexity measure: be explicit about data vs combined vs query complexity, and prove

the bound in the measure you claim it for.

• Worked examples and counterexamples: a small concrete database and query that illustrates the

construction, or a counterexample that rules out a tempting stronger statement, is high-value

evidence a referee can check by hand — include it in the body.

• Corner cases: state what happens at the boundaries of your class (empty instances, cyclic vs

acyclic, bounded arity) rather than leaving the referee to wonder whether a case breaks the proof.

If your paper does include an experiment

Some ICDT papers contribute an algorithm whose worst-case bound understates or overstates its

behavior on realistic inputs. If you evaluate it, do so with the rigor the theory earns:

[Purpose]     state exactly what the experiment tests that the proof does not (e.g., typical-case
              runtime, the size of the hidden constant, scaling on real query workloads)
[Subjects]    real or standard benchmark data/queries, described precisely; no cherry-picked inputs
[Baseline]    a fair comparison (a prior algorithm, a naive method) implemented honestly
[Reporting]   enough runs, hardware stated, and results that support only what you claim
[Scope]       the experiment supplements the theorem; it never substitutes for a missing proof

Keep it proportional: an ICDT experiment is a paragraph-to-a-page confirmation, not a systems-paper

evaluation. If the experiment is the contribution, the paper likely belongs at EDBT/SIGMOD, not

ICDT (see icdt-topic-selection).

Honesty and scope

• Do not report an experiment whose setup you would not want a referee to reproduce; ICDT referees

are skeptical of evaluations that appear to decorate a theorem.

• Do not claim practical impact the experiment does not show — "faster on our three instances" is not

"faster in practice."

• State the model assumptions your algorithm relies on and whether the experiment respects them.

Output format

[Claim -> evidence] <each claim -> proof (bounds/construction) or experiment>
[Tightness] bounds matched and labeled? yes/no/na
[Complexity measure] data / combined / query, proven in the claimed measure? yes/no
[Experiment] none (theory-complete) / proportional supplement / over-scoped (reroute?)
[Fix queue] <ordered: close bound gaps first, then examples, then any experiment>