Current browse context:
math.CO
Change to browse by:
References & Citations
Mathematics > Combinatorics
Title: Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
(Submitted on 28 Mar 2024 (v1), last revised 29 Mar 2024 (this version, v2))
Abstract: We study sheaves on posets, showing that cosystolic expansion of such sheaves can be derived from local expansion conditions of the sheaf and the poset (typically a high dimensional expander). When the poset at hand is a cell complex, a sheaf on it may be thought of as generalizing coefficient groups used for defining homology and cohomology, by letting the coefficient group vary along the cell complex. Previous works established local criteria for cosystolic expansion only for simplicial complexes and with respect to constant coefficients. Cosystolic expansion of sheaves is related to property testing. We use this relation and our local criterion for cosystolic expansion to give two applications to locally testable codes (LTCs).
First, we show the existence of good $2$-query LTCs. These codes are related to the recent good $q$-query LTCs of Dinur et. al and Panteleev-Kalachev, being the formers' so-called line codes, but we get them from a new, more illuminating perspective, namely, by realizing them as cocycle codes of sheaves over posets. We then derive their good properties directly from our criterion for cosystolic expansion.
Second, we give a local criterion for a a lifted code (with some auxiliary structure) to be locally testable. This improves on a previous work of Dikstein et. al, where it was shown that one can obtain local testability of lifted codes from a mixture of local and global conditions.
Submission history
From: Uriya First [view email][v1] Thu, 28 Mar 2024 12:56:53 GMT (100kb)
[v2] Fri, 29 Mar 2024 08:20:15 GMT (100kb)
Link back to: arXiv, form interface, contact.