PODS Writing Style
Use this when revising the main paper. PODS papers are read by database theoreticians, so they need a
precise model and a precise result stated on the first page and proofs a reviewer can verify.
The failure this skill prevents is a paper whose interesting idea is buried under systems language or
whose theorems are stated loosely enough that no one can tell what was proved.
Revision rules
- Lead with the model and the result: the data-management problem, the exact model (data/query
model, complexity measure, cost model), the result (a bound, a dichotomy, a semantics, an optimal
algorithm), why it is tight or complete, and what it settles — all on the first page.
- State theorems precisely. Every theorem names its hypotheses, its model, and its exact
quantities (data vs. combined complexity, worst-case vs. parameterized, exact vs. approximate). A
vague "our problem is hard" is not a PODS theorem.
- Match upper and lower bounds. The strongest PODS papers close the gap; where you cannot, say so
and state the open case rather than hiding it behind "we leave this to future work" without a
precise statement.
- Every stated result has a complete proof. In the body if it fits, otherwise in the appendix
incorporated with the submission — PODS forbids online/external appendices, so a proof "omitted" or
"in the full version" with nothing in the appendix is a reject.
- Respect the acmsmall budget as a design constraint. 15 pages excluding references, plus
unlimited references, plus the appendix; the body must be a self-contained mathematical narrative,
with routine or long proofs pushed to the appendix behind clear forward references.
- Maintain lightweight double-anonymity in self-citations, named systems, acknowledgements, and
funding — phrase your own prior work in the third person.
Theory-paper skeleton
| Section |
Job it must do |
Common failure |
| Intro |
Problem, model, result, tightness, what it settles — first page |
Leads with a system or a trend, not a model and a theorem |
| Preliminaries |
Fix the data/query model, notation, and the exact problem |
Definitions too informal for the theorem to be unambiguous |
| Main results |
State each theorem precisely; give the key proof ideas |
Theorems stated so loosely the contribution is unclear |
| Upper bound |
The algorithm/construction + its correctness and complexity proof |
Complexity asserted, not proved; hidden dependence on parameters |
| Lower bound |
The hardness reduction or impossibility, with its assumptions |
No matching lower bound, so optimality is unproven |
| Related work |
Delta-first positioning against PODS/ICDT/logic literature |
A citation catalog with no contrast of results |
Sentence-level rewrites
| Draft pattern |
PODS-safe rewrite |
| "Our algorithm is very efficient." |
"runs in O(n log n) data complexity (Thm 3), matching the Ω(n log n) lower bound of §5" |
| "The problem is hard." |
"consistent query answering for this class is coNP-complete in data complexity (Thm 2)" |
| "We handle a broad class of queries." |
"we prove the dichotomy for all self-join-free conjunctive queries; self-joins remain open (§7)" |
| "Experiments confirm our approach." |
"we give a matching lower bound; a small empirical check (§6) illustrates the constants" |
| "It is easy to see that..." |
Replace with the actual argument or a pointer to the appendix proof |
Statement discipline
[Model] fix the data model, query class, and cost/complexity measure before any theorem
[Quantifiers] say exactly what is universal and what is existential; data vs. combined complexity
[Tightness] pair each upper bound with a lower bound or state the gap as an open problem
[Assumptions] name every conjecture a bound rests on (e.g. OMv, ETH); never present conditional
hardness as unconditional
-> a reader should be able to restate your main theorem exactly from the abstract alone
Vignette: compressing a two-bound paper
A draft with an upper-bound algorithm, a lower-bound reduction, three corollaries, and a long
preliminaries section: keep both main theorems and their proof ideas in the body, move the full
reduction gadget and the corollary proofs to the appendix with forward references, and cut
preliminaries to exactly the definitions the theorems use. The test of a good cut: a reviewer should
be able to state what was proved and why it is tight from the body alone, and find every full proof in
the appendix.
Output format
[Writing diagnosis] clear / under-specified model / loose theorems / gap unstated / over-scoped
[First-page fix] <new framing leading with the model and the exact result>
[Theorem audit] <theorem -> hypotheses stated? complexity exact? proof located? tight?>
[Tightness fix] <where a matching lower bound or an honest open-case statement must be added>
[Anonymity edits] <named systems / self-citations / acknowledgements to rewrite>
1---2name: pods-writing-style3description: Use when revising an ACM PODS paper for a precise model and result on the first page, exact theorem statements with matching bounds, complete and self-contained proofs (body plus at-submission appendix), honest assumptions and open cases, double-anonymous wording, and disciplined use of the acmsmall 15-page budget.4---56# PODS Writing Style78Use this when revising the main paper. PODS papers are read by database theoreticians, so they need a9**precise model and a precise result stated on the first page** and **proofs a reviewer can verify**.10The failure this skill prevents is a paper whose interesting idea is buried under systems language or11whose theorems are stated loosely enough that no one can tell what was proved.1213## Revision rules1415- **Lead with the model and the result:** the data-management problem, the exact model (data/query16 model, complexity measure, cost model), the result (a bound, a dichotomy, a semantics, an optimal17 algorithm), why it is tight or complete, and what it settles — all on the first page.18- **State theorems precisely.** Every theorem names its hypotheses, its model, and its exact19 quantities (data vs. combined complexity, worst-case vs. parameterized, exact vs. approximate). A20 vague "our problem is hard" is not a PODS theorem.21- **Match upper and lower bounds.** The strongest PODS papers close the gap; where you cannot, say so22 and state the open case rather than hiding it behind "we leave this to future work" without a23 precise statement.24- **Every stated result has a complete proof.** In the body if it fits, otherwise in the appendix25 incorporated with the submission — PODS forbids online/external appendices, so a proof "omitted" or26 "in the full version" with nothing in the appendix is a reject.27- **Respect the acmsmall budget as a design constraint.** 15 pages excluding references, plus28 unlimited references, plus the appendix; the body must be a self-contained mathematical narrative,29 with routine or long proofs pushed to the appendix behind clear forward references.30- **Maintain lightweight double-anonymity** in self-citations, named systems, acknowledgements, and31 funding — phrase your own prior work in the third person.3233## Theory-paper skeleton3435| Section | Job it must do | Common failure |36|---|---|---|37| Intro | Problem, model, result, tightness, what it settles — first page | Leads with a system or a trend, not a model and a theorem |38| Preliminaries | Fix the data/query model, notation, and the exact problem | Definitions too informal for the theorem to be unambiguous |39| Main results | State each theorem precisely; give the key proof ideas | Theorems stated so loosely the contribution is unclear |40| Upper bound | The algorithm/construction + its correctness and complexity proof | Complexity asserted, not proved; hidden dependence on parameters |41| Lower bound | The hardness reduction or impossibility, with its assumptions | No matching lower bound, so optimality is unproven |42| Related work | Delta-first positioning against PODS/ICDT/logic literature | A citation catalog with no contrast of results |4344## Sentence-level rewrites4546| Draft pattern | PODS-safe rewrite |47|---|---|48| "Our algorithm is very efficient." | "runs in `O(n log n)` data complexity (Thm 3), matching the `Ω(n log n)` lower bound of §5" |49| "The problem is hard." | "consistent query answering for this class is `coNP`-complete in data complexity (Thm 2)" |50| "We handle a broad class of queries." | "we prove the dichotomy for all self-join-free conjunctive queries; self-joins remain open (§7)" |51| "Experiments confirm our approach." | "we give a matching lower bound; a small empirical check (§6) illustrates the constants" |52| "It is easy to see that..." | Replace with the actual argument or a pointer to the appendix proof |5354## Statement discipline5556```text57[Model] fix the data model, query class, and cost/complexity measure before any theorem58[Quantifiers] say exactly what is universal and what is existential; data vs. combined complexity59[Tightness] pair each upper bound with a lower bound or state the gap as an open problem60[Assumptions] name every conjecture a bound rests on (e.g. OMv, ETH); never present conditional61 hardness as unconditional62-> a reader should be able to restate your main theorem exactly from the abstract alone63```6465## Vignette: compressing a two-bound paper6667A draft with an upper-bound algorithm, a lower-bound reduction, three corollaries, and a long68preliminaries section: keep both main theorems and their proof ideas in the body, move the full69reduction gadget and the corollary proofs to the appendix with forward references, and cut70preliminaries to exactly the definitions the theorems use. The test of a good cut: a reviewer should71be able to state what was proved and why it is tight from the body alone, and find every full proof in72the appendix.7374## Output format7576```text77[Writing diagnosis] clear / under-specified model / loose theorems / gap unstated / over-scoped78[First-page fix] <new framing leading with the model and the exact result>79[Theorem audit] <theorem -> hypotheses stated? complexity exact? proof located? tight?>80[Tightness fix] <where a matching lower bound or an honest open-case statement must be added>81[Anonymity edits] <named systems / self-citations / acknowledgements to rewrite>82```
brycewang-stanford