ﻻ يوجد ملخص باللغة العربية
In this work we show that high dimensional expansion implies locally testable code. Specifically, we define a notion that we call high-dimensional-expanding-system (HDE-system). This is a set system defined by incidence relations with certain high dimensional expansion relations between its sets. We say that a linear code is modelled over HDE-system, if the collection of linear constraints that the code satisfies could by described via the HDE-system. We show that a code that can be modelled over HDE-system is locally testable. This implies that high dimensional expansion phenomenon solely implies local testability of codes. Prior work had to rely to local notions of local testability to get some global forms of testability (e.g. co-systolic expansion from local one, global agreement from local one), while our work infers global testability directly from high dimensional expansion without relying on some local form of testability. The local testability result that we obtain from HDE-systems is, in fact, stronger than standard one, and we term it amplified local testability. We further show that most of the well studied locally testable codes as Reed-Muller codes and more generally affine invariant codes with single-orbit property fall into our framework. Namely, it is possible to show that they are modelled over an HDE-system, and hence the family of all p-ary affine invariant codes is amplified locally testable. This yields the strongest known testing results for affine invariant codes with single orbit, strengthening the work of Kaufman and Sudan.
We initiate the study of property testing problems concerning relations between permutations. In such problems, the input is a tuple $(sigma_1,dotsc,sigma_d)$ of permutations on ${1,dotsc,n}$, and one wishes to determine whether this tuple satisfies
A circulant-based spatially-coupled (SC) code is constructed by partitioning the circulants of an underlying block code into a number of components, and then coupling copies of these components together. By connecting (coupling) several SC codes, mul
Consider the problem of learning the drift coefficient of a $p$-dimensional stochastic differential equation from a sample path of length $T$. We assume that the drift is parametrized by a high-dimensional vector, and study the support recovery probl
This paper offers a characterization of fundamental limits on the classification and reconstruction of high-dimensional signals from low-dimensional features, in the presence of side information. We consider a scenario where a decoder has access both
In simplicial complexes it is well known that many of the global properties of the complex, can be deduced from expansion properties of its links. This phenomenon was first discovered by Garland [G]. In this work we develop a local to global machiner