Lemma 2.1 — accepted profiles of a fixed board form a product, and a row and board fix the decoded component
ProvedMatchIndiff.PublicSM.lemma_2_1communication-complexityp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1
Fix a verification protocol at a fixed public input, with report holders , allowed report sets , board alphabet , decoders and checks , and fix a board . Put . Then the profiles on which all checks accept form exactly the product
and a fixed row and board give the same decoded component: if then .
This rectangle property is what makes the fooling-set lower bound of Theorem 6.2 work: rows copied from two accepted profiles form a mixed profile on which the same board is still accepted.
Formalization Note. Stated for the generic VerifProtocol R X C with an arbitrary holder type V, report types R v, domains T v : Set (R v) and any board type C.
Differences from the source:
- generalization: a protocol of one of the paper's models: finite report sets T_v, finite holder set V, finite nonempty board alphabet C → any holder type V, any report types R v with domains T v, any board type C, any output types; reason: the statement and its proof use no finiteness; it specializes to the paper's protocols
Preamble
import Mathlib import Definitions.Def_MatchIndiff_PublicSM_Protocol
Formal statement
namespace MatchIndiff.PublicSM
/-- Lemma 2.1 (p. 7): for a fixed board `c`, the profiles of the product domain `∏ T_v` on which
all checks accept `c` form exactly `∏_v S_v(c)`, `S_v(c) = {x ∈ T_v : V_v(x, c) = 1}`; and a fixed
row and board give the same decoded component. -/
theorem lemma_2_1 {V : Type*} {R X : V → Type*} {C : Type*} (p : VerifProtocol R X C)
(T : (v : V) → Set (R v)) (c : C) :
{P : (v : V) → R v | (∀ v, P v ∈ T v) ∧ ∀ v, p.chk v (P v) c = true} =
Set.pi Set.univ (fun v => {x : R v | x ∈ T v ∧ p.chk v x c = true}) ∧
∀ (P P' : (v : V) → R v) (v : V), P v = P' v → p.dec v (P v) c = p.dec v (P' v) c := by sorry
end MatchIndiff.PublicSM
Source
Zhang, Zhao, Xu, Xi, Zhao, Structural Complexity of Matching with Indifferences, STOC 2027 submission (manuscript sha256 22dfb437…), p. 7, Lemma 2.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.