Validation of Modern JSON Schema: Formalization and Complexity
summary
Paper formalizes Modern JSON Schema syntax and proves data validation is PSPACE-complete, pinpointing the blowup to dynamic references (Draft 2020‑12) while showing annotation-dependent validation stays in P. Complexity is PSPACE-complete in schema size even on a fixed instance but becomes polynomial when the schema is fixed. Formalization matches major tool behavior, includes a memoized evaluation rule, and experiments exhibit schema families where dynamic vs static references produce visibly divergent runtimes.
AI-written summary · about
chapters (7)
- 0:00JSON Schema validation intro
- 1:17Classical JSON Schema basics
- 3:14Modern JSON Schema features
- 5:09Dynamic references in Modern JSON Schema
- 10:18Dynamic references semantics
- 12:52Complexity of validation
- 16:32Implications and future
related talks
59mThe Power Of Compile-Time Resources
18mOn the Expressive Power of Languages for Static Variability
15mTowards Proof Stability in SMT-based Program Verification
22mOptimizing Optimizations: Case Study on Detecting Specific Types of Mathematical(…)
19mSo You Want To Analyze Scheme Programs With Datalog?
19mVerbatim++: Verified, Optimized, and Semantically Rich Lexing with Derivatives
54mSnarky: Algebraic effects in the Coda cryptocurrency
25mLegoSNARK: Modular Design and Composition of Succinct Zero Knowledge Proofs