Theorem A.4 — simultaneous deterministic sampled-boundary recovery
OpenHypRecov.Supplement.theorem_A_4hypergraphslinear-sketchingp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-recoverystreaming-algorithms
Fix a finite family of vertex subsets and write . For every simple unweighted terminal hypergraph, deterministic per-vertex linear measurements at order
recover
with complete original memberships for every and satisfying .
The guarantee is simultaneous, including adaptively chosen queries. State and decoder workspace use bits; per-fragment updates and per-query decoding are polynomial in . Only the terminal projection vector is promised.
Differences from the source:
- reading: “vertex subsets ” followed by → a finite family
Finset (Finset (Fin n)); reason: this is the unique type-correct reading of the displayed sum and the later quantification over - encoding: deterministic per-vertex linear measurements, simultaneous adaptive queries and resources → a state concatenating one block per vertex occurrence, depending only on the terminal vector, with uniform additive/subtraction/query TM2 machines and explicit all-stack budgets; reason: determinism makes the all-query guarantee adaptive, and the machine interface preserves every stated resource
Preamble
import Mathlib import Definitions.Def_HypRecov_Supplement_QuerySketchGuarantee set_option autoImplicit false
Formal statement
namespace HypRecov.Supplement
/-- **Theorem A.4 (Deterministic sparse boundary recovery).** Zhang, Chen, Shen, *Hypergraph Recovery
from Anonymous Projection Streams*, STOC 2027 submission (manuscript sha256 719dcfff…), Theorem A.4,
p.32 (PDF p.33).
For a finite family `family` of sampled vertex sets, one deterministic per-vertex additive state at
order `min{r,floor(log₂ K)+3}` recovers `D_{R,S}` with every original membership whenever
`R` belongs to the family, `S ⊆ R`, and the sampled boundary has at most `K` edges. The same state
answers every such query, including adaptive queries. State and decoder workspace are
`O-tilde(N_family K r + K r)`, and updates and queries are uniformly polynomial.
**Formalization Note.** The source's printed `R ⊆ [n]` followed by a sum over `R in R` is read as
the unique type-correct object: a finite family of vertex subsets. The state depends only on the
terminal projection vector, so no prefix promise is introduced. -/
theorem theorem_A_4 :
∃ (A : QuerySketch) (C c : ℕ),
∀ (n r K : ℕ) (family : Finset (Finset (Fin n))),
r ≤ n → 1 ≤ r → 1 ≤ K →
let q := min r (Nat.log 2 K + 3)
QuerySketchGuarantee A C c n r K q (familySize family * K * r + K * r) family
(fun E R S => R ∈ family ∧ S ⊆ R ∧ (sampledBoundary E R S).card ≤ K)
(fun E R S out => FullEdgeOutput (sampledBoundary E R S) out)
:= by sorry
end HypRecov.Supplement
Source
Zhang, Chen, Shen, Hypergraph Recovery from Anonymous Projection Streams, STOC 2027 submission (manuscript sha256 719dcfff4dc2eba2d8c5a3c51679a08cfb11f076546dea963c6376a2b9da2c82), Theorem A.4, p.32 (PDF p.33)