Pods Experiments

PODS Experiments

Use this before submission when the technical story is not yet locked. For PODS the "experiments" are mostly analyses and proofs, because the reviewers are theoreticians and the evidence is a theorem, not a benchmark. The organizing principle is rigor proportional to the claim — the analysis must establish exactly what the paper asserts, in the model it names, with no hidden gap.

Analysis audit

• Match the analysis to the claim shape. A claim of optimality needs a matching lower bound; a claim of a classification needs completeness (every case decided); a claim of efficiency needs an exact complexity in a stated measure (data vs. combined), not an asymptotic hand-wave.
• Close the upper/lower-bound gap, or state it. An upper bound without a lower bound is not optimality; if the gap is open, say so precisely rather than implying tightness.
• State every complexity assumption. Conditional hardness (ETH, SETH, OMv, the exponential-time hypothesis, P ≠ NP, #P-hardness) must be named where the bound is stated; never dress a conditional lower bound as unconditional.
• Check the model does not smuggle the result. A cost model, a data model restriction, or an encoding choice can trivialize or inflate a bound; make the modeling assumptions explicit and defend them as realistic for data management.
• Handle constants and parameters honestly. Hidden dependence on the query size, the schema, or a fixed parameter can turn a "linear" claim into something else; state what is held constant.
• When you claim practicality, show it — carefully. PODS papers occasionally include a small empirical validation to illustrate that the theory's constants are reasonable. If you do, it is a supporting illustration, not the contribution: report it modestly, and never let a benchmark stand in for a missing proof.

Claim-to-rigor design table

Assumption and model discipline

[Complexity measure]  data complexity / combined complexity / parameterized — state which and stay consistent
[Cost model]          RAM / arithmetic / communication (MPC rounds) — fix it before stating a bound
[Conjectures]         name each (ETH/SETH/OMv/#P) exactly where a conditional bound depends on it
[Encoding]            make input encoding explicit when it affects the bound (unary vs. binary, etc.)
[Parameters]          say what is fixed and what varies; expose hidden query-size dependence

Optional empirical validation (when a paper claims practicality)

• Keep it small and clearly secondary; state the implementation and inputs so the illustration is reproducible, but do not turn the paper into a systems submission.
• Never use measured speed to substitute for an unproven bound — a PODS reviewer reads that as a gap.
• If the practical behavior diverges from the worst-case theory, say so; the honesty strengthens the paper.

Vignette: proving an algorithm optimal

Suppose the paper claims a new join-evaluation algorithm is worst-case optimal. The matching plan: state the exact output-size bound the algorithm meets; prove the running-time upper bound in the stated cost model; prove a matching lower bound showing no algorithm in the model beats it (or cite the known information-theoretic bound and prove your algorithm meets it); and state precisely the class of queries and inputs for which optimality holds, flagging what is left open — every step in the body or the at-submission appendix.

Rigor reporting floor

• A matching lower bound for every optimality claim, or an explicit open-gap statement.
• Every conditional result labeled with its assumption at the point of statement.
• The complexity measure and cost model fixed once and used consistently.

Output format

[Rigor readiness] strong / adequate / gap present
[Claim -> rigor map] <claim: upper bound / lower bound / completeness / assumption>
[Tightness] <matching bound present? or open gap stated precisely?>
[Assumptions] <every conditional bound labeled with ETH/OMv/#P/etc.? yes/no>
[Model check] <cost/data model explicit and not smuggling the result? yes/no>
[Decision-critical next step] <the one proof to finish or the one bound to match>