STOC2024

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

Yotam Dikstein, Irit Dinur

5 citations

Abstract

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.