STOC2024
Agreement Theorems for High Dimensional Expanders in the Low Acceptance Regime: The Role of Covers
Yotam Dikstein, Irit Dinur
被引用 5 次
摘要
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.