Exact agreement expansion achieved for complex mathematical structures
Exact Agreement Expansion up to the Top via Non-polarity
Computational ComplexityDiscrete Mathematics
Summary
This paper focuses on a math problem called agreement expansion, which asks if local pieces that mostly agree can be combined into one global solution. The authors develop a new proof method that works in more complicated settings, including certain geometric and combinatorial shapes where previous approaches failed. They show exact agreement between different layers of these structures using weaker assumptions than before. Their ideas rely on studying distributions of local pieces in a new way through random sampling.
What this means in practice
- •For matroid theorists: Test exact consistency properties of rank-k matroid bases when verified through smaller independent sets.
- •For coding theory developers: Design error-detection schemes with exact agreement guarantees based on hierarchical combinatorial structures under weaker spectral assumptions.
A theory result. No direct application yet.
Authors
Tali Kaufman, Huy Tuan Pham
Abstract
Agreement expansion asks whether local assignments to faces of a poset that usually agree on a sampled common face must agree with a single global function on most faces. Agreement expansion is exact (approximate) if local assignments need to exactly (approximately) agree with the global function. We suggest a new proof technique for agreement expansion that enables agreement expansion in settings which were previously beyond reach, such as: exact agreement expansion for Grassmannian posets (before only simplicial complexes support exact agreement expansion); agreement expansion based on assignments to top faces of the a complex (before agreement expansion is generally proven only for assignments to low dimensional faces); agreement expansion from one-sided spectral expansion (before, two sided spectral assumption was needed in general settings). Specifically, for down-closed simplicial and Grassmannian complexes, we prove an exact agreement theorem between any two layers assuming one-sided spectral expansion in links of singletons. As an application, we show that full bases of every rank-$k$ matroid admit exact agreement with soundness $O(k^2/[h(k-h)])$ when tested through $h$-element independent sets. We also obtain exact agreement on Grassmannian posets under one-sided spectral expansion, with stronger soundness under a local distance guarantee. Our key proof ideas center around non-polarity of the distributions of local assignments, probed via a random exposure of elements.