Agreement Theorems for High Dimensional Expanders in the Low Acceptance Regime: The Role of Covers

Let X be a family of k-element subsets of [n] and let fs : s → Σ | s ∈ X be an ensemble of local functions, each defined over a subset s ⊂ [n]. Is there a global function G : [n] → Σ such that fs = G|s for all s ∈ X ? An agreement test is a randomized property tester for this question. One such test is the V-test, that chooses a random pair of sets s 1 , s 2 ∈ X with prescribed intersection size and accepts if fs 1 , fs 2 agree on the elements in s 1 ∩ s 2 .

The low acceptance (or 1%) regime is concerned with the situation that the test succeeds with low but non-negligible probability Agree(fs) ⩾ ε > 0. A "classical" low acceptance agreement theorem says Agree(fs) > ε =⇒ ∃G : [n] → Σ, P