Abstract. The problem of testing low-degree polynomials has received significant attention over the years due to its importance in theoretical computer science. The problem is specified by three parameters, the field size [Formula: see text], the degree [Formula: see text], and the proximity parameter [Formula: see text], and the goal is to design a test that makes as few queries as possible to a given function and distinguishes between the case the function has degree at most [Formula: see text] and the case it is [Formula: see text]-far from any degree [Formula: see text] function. We say that a test is optimal if it makes [Formula: see text] queries and rejects any function which is [Formula: see text]-far from degree [Formula: see text] with probability [Formula: see text]. The most natural tester to consider is the [Formula: see text]-flat test, wherein one picks an affine subspace [Formula: see text] of dimension [Formula: see text] (chosen appropriately) uniformly at random, and checks that [Formula: see text]. The [Formula: see text]-flat test was shown to be optimal by Bhattacharyya et al. [ Proceedings of FOCS, 2010, pp. 488–497] for [Formula: see text], and later by Haramaty, Shpilka, and Sudan [ SIAM J. Comput., 42 (2013), pp. 536–562] for all prime powers [Formula: see text]. Their analyses, however, has a tower type dependency on the field size [Formula: see text] (i.e., in the hidden constant in the big [Formula: see text] notation). We improve the result of Haramaty, Shpilka, and Sudan, showing that the dependency on the field size is polynomial in [Formula: see text]. Our technique also applies in the more general setting of lifted affine invariant codes and gives the same polynomial dependency on the field size. This answers a problem raised by Haramaty, Ron-Zewi, and Sudan [ Theory Comput., 11 (2015), pp. 299–338]. Our approach significantly deviates from the strategy taken in earlier works and is based on studying the structure of the collection of erroneous subspaces, i.e., subspaces [Formula: see text] such that [Formula: see text] has degree greater than [Formula: see text]. Toward this end, we observe that these sets are poorly expanding in the affine Grassmann graph and use that to establish structural results on them via global hypercontractivity. We then use this structure to perform local correction on [Formula: see text].

Recent constructions of the first asymptotically good quantum LDPC (qLDPC) codes led to two breakthroughs in complexity theory: the NLTS (No Low-Energy Trivial States) theorem (Anshu, Breuckmann, and Nirkhe, STOC'23), and explicit lower bounds against a linear number of levels of the Sum-of-Squares (SoS) hierarchy (Hopkins and Lin, FOCS'22). In this work, we obtain improvements to both of these results using qLDPC codes of low rate: - Whereas Anshu et al. only obtained NLTS Hamiltonians from qLDPC codes of linear dimension, we show the stronger result that qLDPC codes of arbitrarily small positive dimension yield NLTS Hamiltonians. - The SoS lower bounds of Hopkins and Lin are only weakly explicit because they require running Gaussian elimination to find a nontrivial codeword, which takes polynomial time. We resolve this shortcoming by introducing a new method of planting a strongly explicit nontrivial codeword in linear-distance qLDPC codes, which in turn yields strongly explicit SoS lower bounds. Our "planted" qLDPC codes may be of independent interest, as they provide a new way of ensuring a qLDPC code has positive dimension without resorting to parity check counting, and therefore provide more flexibility in the code construction.

We show that cosystolic expansion of sheaves on posets can be derived from local expansion conditions of the sheaf and the poset. When the poset at hand is a cell complex — typically a high dimensional expander — a sheaf 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. Our main technical contribution is providing a criterion that is more general in two ways: it applies to posets and sheaves, respectively.

Constructing quantum low-density parity-check (LDPC) codes with a minimum distance that grows faster than a square root of the length has been a major challenge of the field. With this challenge in mind, we investigate constructions that come from high-dimensional expanders, in particular Ramanujan complexes. These naturally give rise to very unbalanced quantum error correcting codes that have a large $X$-distance but a much smaller $Z$-distance. However, together with a classical expander LDPC code and a tensoring method that generalizes a construction of Hastings and also the Tillich–Zémor construction of quantum codes, we obtain quantum LDPC codes whose minimum distance exceeds the square root of the code length and whose dimension comes close to a square root of the code length. When the ingredient is a 2-dimensional Ramanujan complex, or the 2-skeleton of a 3-dimensional Ramanujan complex, we obtain a quantum LDPC code of minimum distance $n^{1/2}\log^{1/2}n$. We then exploit the expansion properties of the complex to devise the first polynomial-time algorithm that decodes above the square root barrier for quantum LDPC codes. Using a 3-dimensional Ramanujan complex, we also obtain an overall quantum code of minimum distance $n^{1/2}\log n$, which sets a new record for quantum LDPC codes.

One of the most important properties of high dimensional expanders is that high dimensional random walks converge rapidly. This property has proven to be extremely useful in variety of fields in the theory of computer science from agreement testing to sampling, coding theory and more. In this paper we present a state of the art result in a line of works analyzing the convergence of high dimensional random walks~\cite{DBLP:conf/innovations/KaufmanM17,DBLP:conf/focs/DinurK17, DBLP:conf/approx/KaufmanO18,DBLP:journals/corr/abs-2001-02827}, by presenting a \emph{structured} version of the result of~\cite{DBLP:journals/corr/abs-2001-02827}. While previous works examined the expansion in the viewpoint of the worst possible eigenvalue, in this work we relate the expansion of a function to the entire spectrum of the random walk operator using the structure of the function; We call such a theorem a Fine Grained High Order Random Walk Theorem. In sufficiently structured cases the fine grained result that we present here can be much better than the worst case while in the worst case our result is equivalent to~\cite{DBLP:journals/corr/abs-2001-02827}. In order to prove the Fine Grained High Order Random Walk Theorem we introduce a way to bootstrap the expansion of random walks on the vertices of a complex into a fine grained understanding of higher order random walks, provided that the expansion is good enough. In addition, our \emph{single} bootstrapping theorem can simultaneously yield our Fine Grained High Order Random Walk Theorem as well as the well known Trickling down Theorem. Prior to this work, High order Random walks theorems and Tricking down Theorem have been obtained from different proof methods.

One of the key components in PCP constructions are agreement tests. In agreement test the tester is given access to subsets of fixed size of some set, each equipped with an assignment. The tester is then tasked with testing whether these local assignments agree with some global assignment over the entire set. One natural generalization of this concept is the case where, instead of a single assignment to each local view, the tester is given access to $l$ different assignments for every subset. The tester is then tasked with testing whether there exist $l$ global functions that agree with all of the assignments of all of the local views. In this work we present sufficient condition for a set system to exhibit this generalized definition of list agreement expansion. This is, to our knowledge, the first work to consider this natural generalization of agreement testing. Despite initially appearing very similar to agreement expansion, list agreement expansion seem to require a different set of techniques. This is due to the fact that the natural extension of agreement testing does not suffice when testing for list agreement, as list agreement crucially relies on a global structure. It follows that if a local assignments satisfy list agreement they must not only agree locally but also exhibit some additional structure. In order to test for the existence of this additional structure we use a connection between covering spaces of a high dimensional complex and its coboundaries. We use this connection as a form of ``decoupling''. Moreover, we show that any set system that exhibits list agreement expansion also supports direct sum testing. This is the first scheme for direct sum testing that works regardless of the parity of the sizes of the local sets. Prior to our work the schemes for direct sum testing were based on the parity of the sizes of the local tests.

Local to global machinery plays an important role in the study of simplicial complexes, since the seminal work of Garland [G] to our days. In this work we develop a local to global machinery for general posets. We show that the high dimensional expansion notions and many recent expansion results have a generalization to posets. Examples are fast convergence of high dimensional random walks generalizing [KO,AL], an equivalence with a global random walk definition, generalizing [DDFH] and a trickling down theorem, generalizing [O]. In particular, we show that some posets, such as the Grassmannian poset, exhibit qualitatively stronger trickling down effect than simplicial complexes. Using these methods, and the novel idea of Posetification, to Ramanujan complexes [LSV1,LSV2], we construct a constant degree expanding Grassmannian poset, and analyze its expansion. This it the first construction of such object, whose existence was conjectured in [DDFH].

Fast mixing of random walks on hypergraphs (simplicial complexes) has recently led to myriad breakthroughs throughout theoretical computer science. Many important applications, however, (e.g. to LTCs, 2-2 games) rely on a more general class of underlying structures called posets, and crucially take advantage of non-simplicial structure. These works make it clear that the global expansion properties of posets depend strongly on their underlying architecture (e.g. simplicial, cubical, linear algebraic), but the overall phenomenon remains poorly understood. In this work, we quantify the advantage of different poset architectures in both a spectral and combinatorial sense, highlighting how regularity controls the spectral decay and edge-expansion of corresponding random walks. We show that the spectra of walks on expanding posets (Dikstein, Dinur, Filmus, Harsha APPROX-RANDOM 2018) concentrate in strips around a small number of approximate eigenvalues controlled by the regularity of the underlying poset. This gives a simple condition to identify poset architectures (e.g. the Grassmann) that exhibit strong (even exponential) decay of eigenvalues, versus architectures like hypergraphs whose eigenvalues decay linearly - a crucial distinction in applications to hardness of approximation and agreement testing such as the recent proof of the 2-2 Games Conjecture (Khot, Minzer, Safra FOCS 2018). We show these results lead to a tight characterization of edge-expansion on expanding posets in the 𝓁₂-regime (generalizing recent work of Bafna, Hopkins, Kaufman, and Lovett (SODA 2022)), and pay special attention to the case of the Grassmann where we show our results are tight for a natural set of sparsifications of the Grassmann graphs. We note for clarity that our results do not recover the characterization of expansion used in the proof of the 2-2 Games Conjecture which relies on 𝓁_∞ rather than 𝓁₂-structure.

Recent works have shown that expansion of pseudorandom sets is of great importance. However, all current works on pseudorandom sets are limited only to product (or approximate product) spaces, where Fourier Analysis methods could be applied. In this work we ask the natural question whether pseudorandom sets are relevant in domains where Fourier Analysis methods cannot be applied, e.g., one-sided local spectral expanders. We take the first step in the path of answering this question. We put forward a new definition for pseudorandom sets, which we call "double balanced sets". We demonstrate the strength of our new definition by showing that small double balanced sets in one-sided local spectral expanders have very strong expansion properties, such as unique-neighbor-like expansion. We further show that cohomologies in cosystolic expanders are double balanced, and use the newly derived strong expansion properties of double balanced sets in order to obtain an exponential improvement over the current state of the art lower bound on their minimal distance.

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.

The problem of testing low-degree polynomials has received significant attention over the years due to its importance in theoretical computer science, and in particular in complexity theory. The problem is specified by three parameters: field size q, degree d and proximity parameter δ, and the goal is to design a tester making as few as possible queries to a given function, which is able to distinguish between the case the given function has degree at most d, and the case the given function is δ-far from any degree d function. With respect to these parameters, we say that a tester is optimal if it makes $O(q^{t}+1/\delta)$ queries, where $t=t(d,q)$ is the testing dimension of d, q (defined as the minimum integer so that for all $g:\mathbb{F}_{q}^{n}\rightarrow\mathbb{F}_{q}$ of degree more than d, there is a subspace of dimension t on which their restriction has degree exceeding d). For the field of size q, such tester was first given by Bhattacharyya et al. for q = 2, and later by Haramaty et al. [7] for all prime powers q. In fact, they showed that the natural t-flat tester is an optimal tester for the Reed-Muller code, for an appropriate t. Here, the t-flat tester is the tester that picks a uniformly random affine subspace A of dimension t, and checks that $\operatorname{deg}(f|_{A})\leqslant d$. Their analysis proves that the dependency of the t-flat tester on δ and d is optimal, however the dependency on the field size, i.e. the hidden constant in the O, is a tower-type function in q. We improve the result of Haramaty et al., showing that the dependency on the field size is polynomial. Our technique also applies in the more general setting of lifted affine invariant codes, and gives the same polynomial dependency on the field size. This answers a problem raised in [6]. Our approach significantly deviates from the strategy taken in earlier works [2], [7], [6], and is based on studying the structure of the collection of erroneous subspaces, i.e. subspaces A such that f|A has degree greater than d. Towards this end, we observe that these sets are poorly expanding in the affine version of the Grassmann graph and use that to establish structural results on them via global hypercontractivity. We then use this structure to perform local correction on f.

Higher order random walks (HD-walks) on high dimensional expanders (HDX) have seen an incredible amount of study and application since their introduction by Kaufman and Mass (ITCS 2016), yet their broader combinatorial and spectral properties remain poorly understood. We develop a combinatorial characterization of the spectral structure of HD-walks on two-sided local-spectral expanders (Dinur and Kaufman FOCS 2017), which offer a broad generalization of the well-studied Johnson and Grassmann graphs. Our characterization, which shows that the spectra of HD-walks lie tightly concentrated in a few combinatorially structured strips, leads to novel structural theorems such as a tight ℓ2-characterization of edge-expansion, as well as to a new understanding of local-to-global graph algorithms on HDX. Towards the latter, we introduce a novel spectral complexity measure called Stripped Threshold Rank, and show how it can replace the (much larger) threshold rank as a parameter controlling the performance of algorithms on structured objects. Combined with a sum-of-squares proof for the former ℓ2-characterization, we give a concrete application of this framework to algorithms for unique games on HD-walks, where in many cases we improve the state of the art (Barak, Raghavendra, and Steurer FOCS 2011, and Arora, Barak, and Steurer JACM 2015) from nearly-exponential to polynomial time (e.g. for sparsifications of Johnson graphs or of slices of the q-ary hypercube). Our characterization of expansion also holds an interesting connection to hardness of approximation, where an ℓ∞-variant for the Grassmann graphs was recently used to resolve the 2-2 Games Conjecture (Khot, Minzer, and Safra FOCS 2018). We give a reduction from a related ℓ∞-variant to our ℓ2-characterization, but it loses factors in the regime of interest for hardness where the gap between ℓ2 and ℓ∞ structure is large. Nevertheless, our results open the door for further work on the use of HDX in hardness of approximation and their general relation to unique games.

We present new scalar and matrix Chernoff-style concentration bounds for a broad class of probability distributions over the binary hypercube {0, 1}n. Motivated by recent tools developed for the study of mixing times of Markov chains on discrete distributions, we say that a distribution is ℓ∞-independent when the infinity norm of its influence matrix is bounded by a constant. We show that any distribution which is ℓ∞-infinity independent satisfies a matrix Chernoff bound that matches the matrix Chernoff bound for independent random variables due to Tropp. Our matrix Chernoff bound is a broad generalization and strengthening of the matrix Chernoff bound of Kyng and Song (FOCS'18). Using our bound, we can conclude as a corollary that a union of O(log |V|) random spanning trees gives a spectral graph sparsifier of a graph with |V| vertices with high probability matching results for independent edge sampling, and matching lower bounds from Kyng and Song.

Hypercontractivity is one of the most powerful tools in Boolean function analysis. Originally studied over the discrete hypercube, recent years have seen increasing interest in extensions to settings like the p-biased cube, slice, or Grassmannian, where variants of hypercontractivity have found a number of breakthrough applications including the resolution of Khot’s 2-2 Games Conjecture (Khot, Minzer, Safra FOCS 2018). In this work, we develop a new theory of hypercontractivity on high dimensional expanders (HDX), an important class of expanding complexes that has recently seen similarly impressive applications in both coding theory and approximate sampling. Our results lead to a new understanding of the structure of Boolean functions on HDX, including a tight analog of the KKL Theorem and a new characterization of non-expanding sets.

The question of finding expander graphs with strong vertex expansion properties such as unique neighbor expansion and lossless expansion is central to computer science. A barrier to constructing these is that strong notions of expansion could not be proven via the spectral expansion paradigm.

Coboundary and cosystolic expansion are notions of expansion that generalize the Cheeger constant or edge expansion of a graph to higher dimensions. The classical Cheeger inequality implies that for graphs edge expansion is equivalent to spectral expansion. In higher dimensions this is not the case: a simplicial complex can be spectrally expanding but not have high dimensional edge-expansion. The phenomenon of high dimensional edge expansion in higher dimensions is much more involved than spectral expansion, and is far from being understood. In particular, prior to this work, the only known bounded degree cosystolic expanders were derived from the theory of buildings that is far from being elementary. In this work we study high dimensional complexes which are strongly symmetric. Namely, there is a group that acts transitively on top dimensional cells of the simplicial complex [e.g., for graphs it corresponds to a group that acts transitively on the edges]. Using the strong symmetry, we develop a new machinery to prove coboundary and cosystolic expansion. It was an open question whether the recent elementary construction of bounded degree spectral high dimensional expanders based on coset complexes give rise to bounded degree cosystolic expanders. In this work we answer this question affirmatively. We show that these complexes give rise to bounded degree cosystolic expanders in dimension two, and that their links are (two-dimensional) coboundary expanders. We do so by exploiting the strong symmetry properties of the links of these complexes using a new machinery developed in this work. Previous works have shown a way to bound the co-boundary expansion using strong symmetry in the special situation of "building like" complexes. Our new machinery shows how to get coboundary expansion for general strongly symmetric coset complexes, which are not necessarily "building like", via studying the (Dehn function of the) presentation of the symmetry group of these complexes.

In this work we introduce a new notion of expansion in higher dimensions that is stronger than the well studied cosystolic expansion notion, and is termed Collective-cosystolic expansion.

We strengthen the notion of double samplers, first introduced by Dinur and Kaufman [``High dimensional expanders imply agreement expanders,” in Proc. 58th IEEE Symp. on Foundations of Comp. Science, IEEE, 2017, pp. 974--985], which are samplers with additional combinatorial properties, and whose existence we prove using high-dimensional expanders. The ABNNR code construction [N. Alon et al., IEEE Trans. Inform. Theory, 38 (1992), pp. 509--516] achieves large distance by starting with a base code $C$ with moderate distance, and then amplifying the distance using a sampler. We show that if the sampler is part of a larger double sampler, then the construction has an efficient list-decoding algorithm. Our algorithm works even if the ABNNR construction is not applied to a base code $C$ but rather to any string. In this case the resulting code is approximate-list-decodable, i.e., the output list contains an approximation to the original input. Our list-decoding algorithm works as follows: It uses a local voting scheme from which it constructs a unique games constraint graph. The constraint graph is an expander, so we can solve unique games efficiently. These solutions are the output of the list-decoder. This is a novel use of a unique games algorithm as a subroutine in a decoding procedure, as opposed to the more common situation in which unique games are used for demonstrating hardness results. Double samplers and high-dimensional expanders are akin to pseudorandom objects in their utility, but they greatly exceed random objects in their combinatorial properties. We believe that these objects hold significant potential for coding theoretic constructions and view this work as demonstrating the power of double samplers in this context.

We generalize the expander Chernoff bound to high-dimensional expanders. The expander Chernoff bound is an essential property of expanders, first proved by Gillman [Gillman, 1993]. Given a graph G and a function f on the vertices, it states that the probability of f’s mean sampled via a random walk on G to deviate from its actual mean, has a bound that depends on the spectral gap of the walk and decreases exponentially as the walk’s length increases. We are interested in obtaining an analog Chernoff bound for high order walks on high-dimensional expanders. A naive generalization of the expander Chernoff bound from expander graphs to high-dimensional expanders gives a very poor bound due to obstructions that occur in high-dimensional expanders and are not present in (one-dimensional) expander graphs. Because of these obstructions, the spectral gap of high-order random walks is inherently small. A natural question that arises is how to get a meaningful Chernoff bound for high-dimensional expanders. In this paper, we manage to get a strong Chernoff bound for high-dimensional expanders by looking beyond the spectral gap. First, we prove an expander Chernoff bound that depends on a notion that we call the "shrinkage of a function" instead of the spectral gap. In one-dimensional expanders, the shrinkage of any function with zero-mean is bounded by λ(M). Therefore, the spectral gap is just the one-dimensional manifestation of the shrinkage. Next, we show that in good high-dimensional expanders, the shrinkage of functions that "do not come from below" is good. A function does not come from below if from any local point of view (called "link") its mean is zero. Finally, we prove a high-dimensional Chernoff bound that captures the expansion of the complex. When the function on the faces has a small variance and does not "come from below", our bound is better than the naive high-dimensional expander Chernoff bound.

Constructing quantum LDPC codes with a minimum distance that grows faster than a square root of the length has been a major challenge of the field. With this challenge in mind, we investigate constructions that come from high-dimensional expanders, in particular Ramanujan complexes. These naturally give rise to very unbalanced quantum error correcting codes that have a large X-distance but a much smaller Z-distance. However, together with a classical expander LDPC code and a tensoring method that generalises a construction of Hastings and also the Tillich-Zemor construction of quantum codes, we obtain quantum LDPC codes whose minimum distance exceeds the square root of the code length and whose dimension comes close to a square root of the code length. When the ingredient is a 3-dimensional Ramanujan complex, we show that its 2-systole behaves like a square of the log of the complex size, which results in an overall quantum code of minimum distance n1/2logn, and sets a new record for quantum LDPC codes. When we use a 2-dimensional Ramanujan complex, or the 2-skeleton of a 3-dimensional Ramanujan complex, we obtain a quantum LDPC code of minimum distance n1/2log1/2n. We then exploit the expansion properties of the complex to devise the first polynomial time algorithm that decodes above the square root barrier for quantum LDPC codes.

Agreement expansion is concerned with set systems for which local assignments to the sets with almost perfect pairwise consistency (i.e., most overlapping pairs of sets agree on their intersections) implies the existence of a global assignment to the ground set (from which the sets are defined) that agrees with most of the local assignments. It is currently known that if a set system forms a two-sided or a partite high dimensional expander then agreement expansion is implied. However, it was not known whether agreement expansion can be implied for one-sided high dimensional expanders. In this work we show that agreement expansion can be deduced for one-sided high dimensional expanders assuming that all the vertices' links (i.e., the neighborhoods of the vertices) are agreement expanders. Thus, for one-sided high dimensional expander, an agreement expansion of the large complicated complex can be deduced from agreement expansion of its small simple links. Using our result, we settle the open question whether the well studied Ramanujan complexes are agreement expanders. These complexes are neither partite nor two-sided high dimensional expanders. However, they are one-sided high dimensional expanders for which their links are partite and hence are agreement expanders. Thus, our result implies that Ramanujan complexes are agreement expanders, answering affirmatively the aforementioned open question. The local-to-global agreement expansion that we prove is based on the variance method that we develop. We show that for a high dimensional expander, if we define a function on its top faces and consider its local averages over the links then the variance of these local averages is much smaller than the global variance of the original function. This decreasing in the variance enables us to construct one global agreement function that ties together all local agreement functions.

In this work, using methods from high dimensional expansion, we show that the property of k-direct-sum is testable for odd values of k . Previous work of [Kaufman and Lubotzky, 2014] could inherently deal only with the case that k is even, using a reduction to linearity testing. Interestingly, our work is the first to combine the topological notion of high dimensional expansion (called co-systolic expansion) with the combinatorial/spectral notion of high dimensional expansion (called colorful expansion) to obtain the result. The classical k-direct-sum problem applies to the complete complex; Namely it considers a function defined over all k-subsets of some n sized universe. Our result here applies to any collection of k-subsets of an n-universe, assuming this collection of subsets forms a high dimensional expander.

A local tester for an error-correcting code is a probabilistic procedure that queries a small subset of coordinates, accepts codewords with probability one, and rejects non-codewords with probability proportional to their distance from the code. The local tester is robust if for non-codewords it satisfies the stronger property that the average distance of local views from accepting views is proportional to the distance from the code. Robust testing is an important component in constructions of locally testable codes and probabilistically checkable proofs as it allows for composition of local tests. In this work we show that for certain codes, any (natural) local tester can be converted to a roubst tester with roughly the same number of queries. Our result holds for the class of affine-invariant lifted codes which is a broad class of codes that includes Reed-Muller codes, as well as recent constructions of high-rate locally testable codes (Guo, Kopparty, and Sudan, ITCS 2013). Instantiating this with known local testing results for lifted codes gives a more direct proof that improves some of the parameters of the main result of Guo, Haramaty, and Sudan (FOCS 2015), showing robustness of lifted codes. To obtain the above transformation we relate the notions of local testing and robust testing to the notion of agreement testing that attempts to find out whether valid partial assignments can be stitched together to a global codeword. We first show that agreement testing implies robust testing, and then show that local testing implies agreement testing. Our proof is combinatorial, and is based on expansion / sampling properties of the collection of local views of local testers. Thus, it immediately applies to local testers of lifted codes that query random affine subspaces in F_q^m, and moreover seems amenable to extension to other families of locally testable codes with expanding families of local views.

We develop the notion of double samplers, first introduced by Dinur and Kaufman [DK17], which are samplers with additional combinatorial properties, and whose existence we prove using high dimensional expanders. We show how double samplers give a generic way of amplifying distance in a way that enables efficient list-decoding. There are many error correcting code constructions that achieve large distance by starting with a base code C with moderate distance, and then amplifying the distance using a sampler, e.g., the ABNNR code construction [ABN+ 92] is such. We show that if the sampler is part of a larger double sampler then the construction has an efficient list-decoding algorithm and the list decoding algorithm is oblivious to the base code C (i.e., it runs the unique decoder for C in a black box way). Our list-decoding algorithm works as follows: it uses a local voting scheme from which it constructs a unique games constraint graph. The constraint graph is an expander, so we can solve unique games efficiently. These solutions are the output of the list decoder. This is a novel use of a unique games algorithm as a subroutine in a decoding procedure, as opposed to the more common situation in which unique games are used for demonstrating hardness results. Double samplers and high dimensional expanders are akin to pseudorandom objects in their utility, but they greatly exceed random objects in their combinatorial properties. We believe that these objects hold significant potential for coding theoretic constructions and view this work as demonstrating the power of double samplers in this context.

High dimensional expanders is a vibrant emerging field of study. Nevertheless, the only known construction of bounded degree high dimensional expanders is based on Ramanujan complexes, whereas one dimensional bounded degree expanders are abundant.

We show that high dimensional expanders imply derandomized direct product tests, with a number of subsets that is linear in the size of the universe. Direct product tests belong to a family of tests called agreement tests that are important components in PCP constructions and include, for example, low degree tests such as line vs. line and plane vs. plane. For a generic hypergraph, we introduce the notion of agreement expansion, which captures the usefulness of the hypergraph for an agreement test. We show that explicit bounded degree agreement expanders exist, based on Ramanujan complexes.

Random walks on bounded degree expander graphs have numerous applications, both in theoretical and practical computational problems. A key property of these walks is that they converge rapidly to their stationary distribution. In this work we define high order random walks: These are generalizations of random walks on graphs to high dimensional simplicial complexes, which are the high dimensional analogues of graphs. A simplicial complex of dimension d has vertices, edges, triangles, pyramids, up to d-dimensional cells. For any 0 \leq i < d, a high order random walk on dimension i moves between neighboring i-faces (e.g., edges) of the complex, where two i-faces are considered neighbors if they share a common (i+1)-face (e.g., a triangle). The case of i=0 recovers the well studied random walk on graphs. We provide a local-to-global criterion on a complex which implies rapid convergence of all high order random walks on it. Specifically, we prove that if the 1-dimensional skeletons of all the links of a complex are spectral expanders, then for all 0 \le i < d the high order random walk on dimension i converges rapidly to its stationary distribution. We derive our result through a new notion of high dimensional combinatorial expansion of complexes which we term colorful expansion. This notion is a natural generalization of combinatorial expansion of graphs and is strongly related to the convergence rate of the high order random walks. We further show an explicit family of bounded degree complexes which satisfy this criterion. Specifically, we show that Ramanujan complexes meet this criterion, and thus form an explicit family of bounded degree high dimensional simplicial complexes in which all of the high order random walks converge rapidly to their stationary distribution.

In recent years a high dimensional theory of expanders has emerged. The notion of combinatorial expansion of graphs (i.e. the Cheeger constant of a graph) has seen two generalizations to high dimensional simplicial complexes. One generalization, known as coboundary expansion, is due to Linial and Meshulem; the other, which we term here cosystolic expansion, is due to Gromov, who showed that cosystolic expanders have the topological overlapping property. No construction (either random or explicit) of bounded degree combinational expanders (according to either definition) were known until a recent work of Kaufman, Kazhdan and Lubotzky, which provided the first bounded degree cosystolic expanders of dimension two. No bounded degree combinatorial expanders are known in higher dimensions. In this work we present explicit bounded degree cosystolic expanders of every dimension. This solves affirmatively an open question raised by Gromov, who asked whether there exist bounded degree complexes with the topological overlapping property in every dimension. Moreover, we provide a local to global criterion on a complex that implies cosystolic expansion: Namely, for a d-dimensional complex, X, if its underlying graph is a good expander, and all its links are both coboundary expanders and good expander graphs, then the (d-1)-dimensional skeleton of the complex is a cosystolic expander.

Expander graphs have been a focus of attention in computer science in the last four decades. In recent years a high dimensional theory of expanders is emerging. There are several possible generalizations of the theory of expansion to simplicial complexes, among them stand out coboundary expansion and topological expanders. It is known that for every d there are unbounded degree simplicial complexes of dimension d with these properties. However, a major open problem, formulated by Gromov, is whether bounded degree high dimensional expanders, according to these definitions, exist for d ≥ 2. We present an explicit construction of bounded degree complexes of dimension d = 2 which are high dimensional expanders. More precisely, our main result says that the 2-skeletons of the 3-dimensional Ramanujan complexes are topological expanders. Assuming a conjecture of Serre on the congruence subgroup property, infinitely many of them are also coboundary expanders.

We show that the high dimensional expansion property as defined by Gromov, Linial and Meshulam, for simplicial complexes is a form of testability. Namely, a simplicial complex is a high dimensional expander iff a suitable property is testable. Using this connection, we derive several testability results.

We present the first explicit construction of a binary symmetric code with constant rate and constant distance (i.e., good code). Moreover, the code is LDPC and its constraint space is generated by the orbit of one constant weight constraint under the group action. Our construction provides the first symmetric LDPC good codes. In particular, it solves the main open problem raised by Kaufman and Wigderson {8}.

Motivated by questions in property testing, we search for linear error-correcting codes that have the “single local orbit” property, i.e., they are specified by a single local constraint and its translations under the symmetry group of the code. We show that the dual of every “sparse” binary code whose coordinates are indexed by elements of $\mathbb{F}_{2^n}$ for prime $n$ and whose symmetry group includes the group of nonsingular affine transformations of $\mathbb{F}_{2^n}$ has the single local orbit property. (A code is said to be sparse if it contains polynomially many codewords in its block length.) In particular this class includes the dual-BCH codes for whose duals (i.e., for BCH codes) simple bases were not known. Our result gives the first short ($O(n)$-bit, as opposed to the natural $\exp(n)$-bit) description of a low-weight basis for BCH codes. The interest in the single local orbit property comes from the recent result of Kaufman and Sudan (STOC 2008) that shows that the duals of codes that have the single local orbit property under the affine symmetry group are locally testable. When combined with our main result, this shows that all sparse affine-invariant codes over the coordinates $\mathbb{F}_{2^n}$ for prime $n$ are locally testable. If, in addition to $n$ being prime, $2^n-1$ does not have large divisors, then we get that every sparse cyclic-invariant code also has the single local orbit. In particular this implies that BCH codes of such length are generated by a single low-weight codeword and its cyclic shifts.

We exhibit explicit bases for BCH codes of designed distance 5. While BCH codes are some of the most studied families of codes, only recently Kaufman and Litsyn (FOCS, 2005) showed that they admit bases of small weight codewords. Fur thermore, Grigorescu, Kaufman, and Sudan (RANDOM, 2009) and Kaufman and Lovett (FOCS, 2011) proved that, in fact, BCH codes can admit very structured bases of small weight codewords (i.e., bases that can be fully specified by a single codeword and its orbit under the affine group). The existence of such structured bases has applications in property testing, and motivates our search for a fully explicit description of low weight codewords and, in particular, of codewords that generate a basis for BCH codes. In this paper, we describe the support of basis-generating codewords under affine transformations of the domain for the very specific case of binary (extended) BCH(2, n). We believe that extending these findings to general BCH codes merits further investigation.

The weight distribution and list-decoding size of Reed-Muller codes are studied in this work. Given a weight parameter, we are interested in bounding the number of Reed-Muller codewords with weight up to the given parameter; and given a received word and a distance parameter, we are interested in bounding the size of the list of Reed-Muller codewords that are within that distance from the received word. Obtaining tight bounds for the weight distribution of Reed-Muller codes has been a long standing open problem in coding theory, dating back to 1976. In this work, we make a new connection between computer science techniques used to study low-degree polynomials and these coding theory questions. This allows us to resolve the weight distribution and list-decoding size of Reed-Muller codes for all distances. Previous results could only handle bounded distances: Azumi, Kasami, and Tokura gave bounds on the weight distribution which hold up to 2.5 times the minimal distance of the code; and Gopalan, Klivans, and Zuckerman gave bounds on the list-decoding size which hold up to the Johnson bound.

The Weil bound for character sums is a deep result in Algebraic Geometry with many applications both in mathematics and in the theoretical computer science. The Weil bound states that for any polynomial f(x) over a finite field F and any additive character χ : F → ℂ, either χ(f(x)) is a constant function or it is distributed close to uniform. The Weil bound is quite effective as long as deg (f) ≪ √|F|, but it breaks down when the degree of f exceeds √|F|. As the Weil bound plays a central role in many areas, finding extensions for polynomials of larger degree is an important problem with many possible applications. In this work we develop such an extension over finite fields Fpn of small characteristic: we prove that if f(x) = g(x) + h(x) where deg(g) ≪ √|F| and h(x) is a sparse polynomial of arbitrary degree but bounded weight degree, then the same conclusion of the classical Weil bound still holds: either χ(f(x)) is constant or its distribution is close to uniform. In particular, this shows that the subcode of Reed-Muller codes of degree ω(1) generated by traces of sparse polynomials is a code with near optimal distance, while Reed-Muller of such a degree has no distance (i.e. o(1) distance) ; this is one of the few examples where one can prove that sparse polynomials behave differently from non-sparse polynomials of the same degree. As an application we prove new general results for affine invariant codes. We prove that any affine-invariant subspace of quasi-polynomial size is (1) indeed a code (i.e. has good distance) and (2) is locally testable. Previous results for general affine invariant codes were known only for codes of polynomial size, and of length 2nwhere n needed to be a prime. Thus, our techniques are the first to extend to general families of such codes of super- polynomial size, where we also remove the requirement from n to be a prime. The proof is based on two main ingredients: the extension of the Weil bound for character sums, and a new Fourier-analytic approach for estimating the weight distribution of general codes with large dual distance, which may be of independent interest.

A locally testable code allows one to store vast amounts of data, where estimating the fraction of errors in the data takes roughly as much time as takes to read one bit of the data! If the fraction of errors is below a certain threshold, a locally decodeable code would allow one to recover every bit of the original message, again, in time which is roughly the time to read one bit of the data. Are such locally testable/decodeable codes of constant rate possible? So far we don't know, but surprisingly-good codes are known. Following, we survey some of the literature and discuss a connection between these notions to symmetric LDPC codes.

Locally testable codes (LTCs) are error-correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of LTCs are linear codes and give error-correcting codes whose duals have (superlinearly) many small weight codewords. Examining this feature appears to be one of the promising approaches to proving limitation results for (i.e., upper bounds on the rate of) LTCs. Unfortunately, until now it has not even been known whether LTCs need to be nontrivially redundant, i.e., need to have one linear dependency among the low-weight codewords in their dual. In this paper we give the first lower bound of this form, by showing that every positive rate constant query strong LTC must have linearly many redundant low-weight codewords in its dual. We actually prove the stronger claim that the actual test itself must use a linear number of redundant dual codewords (beyond the minimum number of basis elements required to characterize the code); in other words, nonredundant (in fact, low redundancy) local testing is impossible. Our main theorem is a special case of a more general theorem that applies to any tester for an arbitrary linear LTC $\mathcal{C}$. The general theorem can be used, for instance, to provide an arguably simpler proof of the main result of Ben-Sasson, Harsha, and Raskhodnikova [SIAM J. Comput., 35 (2005), pp. 1–21], which says that testing random low density parity check (LDPC) codes requires linear query complexity. Informally, our more general theorem says the following. Take any basis B for the dual code of $\mathcal{C}$ that is composed of words of small support; i.e., every element of B has very few nonzero entries. Then the dual code of $\mathcal{C}$ must contain many words that (i) are not in B, (ii) have small support, and, most importantly, (iii) are a linear combination of a constant fraction of B.

For Boolean functions that are $\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted by $\textsc{rej}(\epsilon)$) of the linearity test suggested by Blum, Luby, and Rubinfeld [J. Comput. System Sci., 47 (1993), pp. 549–595]. This problem is arguably the most fundamental and extensively studied problem in property testing of Boolean functions. The previously best bounds for $\textsc{rej}(\epsilon)$ were obtained by Bellare et al. [IEEE Trans. Inform. Theory, 42 (1996), pp. 1781–1795]. They used Fourier analysis to show that $\textsc{rej}(\epsilon)\geq\epsilon$ for every $0\leq\epsilon\leq1/2$. They also conjectured that this bound might not be tight for $\epsilon$'s which are close to $1/2$. In this paper we show that this indeed is the case. Specifically, we improve the lower bound of $\textsc{rej}(\epsilon)\geq\epsilon$ by an additive constant that depends only on $\epsilon$: $\textsc{rej}(\epsilon)\geq\epsilon+\min\{1376\epsilon^{3}(1-2\epsilon)^{12},\frac{1}{4}\epsilon(1-2\epsilon)^{4}\}$, for every $0\leq\epsilon\leq1/2$. Our analysis is based on a relationship between $\textsc{rej}(\epsilon)$ and the weight distribution of a coset code of the Hadamard code. We use both Fourier analysis and coding theory tools to estimate this weight distribution.

Locally testable codes (LTCs) are error- correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes whose duals have (superlinearly) many small weight codewords. Examining this feature appears to be one of the promising approaches to proving limitation results for (i.e., upper bounds on the rate of) LTCs. Unfortunately till now it was not even known if LTCs need to be non-trivially redundant, i.e., need to have one linear dependency among the low-weight codewords in its dual. In this paper we give the first lower bound of this form, by showing that every positive rate constant query strong LTC must have linearly many redundant low-weight codewords in its dual. We actually prove the stronger claim that the actual test itself must use a linear number of redundant dual codewords (beyond the minimum number of basis elements required to characterize the code); in other words, non-redundant (in fact, low redundancy) local testing is impossible.

A basic goal in property testing is to identify a minimal set of features that make a property testable. For the case when the property to be tested is membership in a binary linear error-correcting code, Alon et al. [N. Alon et al., 2003] had conjectured that the presence of a single low weight code in the dual, and "2-transitivity" of the code (i.e., the code is invariant under a 2-transitive group of permutations on the coordinates of the code) suffice to get local testability. We refute this conjecture by giving a family of error correcting codes where the coordinates of the codewords form a large field of characteristic two, and the code is invariant under affine transformations of the domain. This class of properties was introduced by Kaufman and Sudan [2008] as a setting where many results in algebraic property testing generalize. Our result shows a complementary virtue: this family also can be useful in producing counterexamples to natural conjectures.

A degree-d polynomial p in n variables over a field F is equidistributed if it takes on each of its |F| values close to equally often, and biased otherwise. We say that p has low rank if it can be expressed as a function of a small number of lower degree polynomials. Green and Tao [GT07] have shown that over large fields (i.e when d <|F|) a biased polynomial must have low rank. They have also conjectured that bias implies low rank over general fields, but their proof technique fails to show that. In this work we affirmatively answer their conjecture. Using this result we obtain a general worst case to average case reductions for polynomials. That is, we show that a polynomial that can be approximated by a few polynomials of bounded degree (i.e. a polynomial with non negligible correlation with a function of few bounded degree polynomials), can be computed by a few polynomials of bounded degree. We derive some relations between our results to the construction of pseudorandom generators. Our work provides another evidence to the structure vs. randomness dichotomy.

Program checking, program self-correcting and program self-testing were pioneered by [Blum and Kannan] and [Blum, Luby and Rubinfeld] in the mid eighties as a new way to gain confidence in software, by considering program correctness on an input by input basis rather than full program verification. Work in the field of program checking focused on designing, for specific functions, checkers, testers and correctors which are more efficient than the best program known for the function. These were designed utilizing specific algebraic, combinatorial or completeness properties of the function at hand. In this work we introduce a novel composition methodology for improving the efficiency of program checkers. We use this approach to design a variety of program checkers that are provably more efficient, in terms of circuit depth, than the optimal program for computing the function being checked. Extensions of this methodology for the cases of program testers and correctors are also presented. In particular, we show: For all i ≥ 1, every language in RNCi (that is NCO-hard under NCZ-reductions) has a program checker in RNCi-1. In addition, for all i ≥ 1, every language in RNCi (that is NCO-hard under ACZ-reductions) has a program corrector, tester and checker in RACi-1. This is the first time checkers are designed for a wide class of functions characterized only by its complexity, rather than by algebraic or combinatorial properties. This characterization immediately yields new and efficient checkers for languages such as graph connectivity, perfect matching and bounded-degree graph isomorphism. Constant-depth checkers, testers and correctors for matrix multiplication, inversion, determinant and rank. All previous program checkers, testers and correctors for these problems run in nearly logarithmic depth. Moreover, except for matrix multiplication, they all require the use of the library notion of [Blum-Luby-Rubinfeld], in which checkers have access to a library of programs for various matrix functions, rather than only having access to a program for the function being checked. Furthermore, we provide conditions under which program libraries can be eliminated. Important ingredients in these results are new and very efficient checkers for complete languages in low complexity classes (e.g. NCO). These constructions are based on techniques that were developed in the field of cryptography.

We argue that the symmetries of a property being tested play a central role in property testing. We support this assertion in the context of algebraic functions, by examining properties of functions mapping a vector space Kn over a field K to a subfield F. We consider (F-)linear properties that are invariant under linear transformations of the domain and prove that an O(1)-local "characterization" is a necessary and sufficient condition for O(1)-local testability. when |K| = O(1). (A local characterization of a property is a definition of a property in terms of local constraints satisfied by functions exhibiting a property.) For the subclass of properties that are invariant under affine transformations of the domain, we prove that the existence of a single O(1)-local constraint implies O(1)-local testability. These results generalize and extend the class of algebraic properties, most notably linearity and low-degree-ness, that were previously known to be testable. In particular, the extensions include properties satisfied by functions of degree linear in n that turn out to be O(1)-locally testable. Our results are proved by introducing a new notion that we term "formal characterizations". Roughly this corresponds to characterizations that are given by a single local constraint and its permutations under linear transformations of the domain. Our main testing result shows that local formal characterizations essentially imply local testability. We then investigate properties that are linear-invariant and attempt to understand their local formal characterizability. Our results here give coarse upper and lower bounds on the locality of constraints and characterizations for linear-invariant properties in terms of some structural parameters of the property we introduce. The lower bounds rule out any characterization, while the upper bounds give formal characterizations. Combining the two gives a test for all linear-invariant properties with local characterizations. We believe that invariance of properties is a very interesting notion to study in the context of property testing in general and merits a systematic study. In particular, the class of linear-invariant and affine-invariant properties exhibits a rich variety among algebraic properties and offer better intuition about algebraic properties than the more limited class of low-degree functions.

In this paper we consider the problem of testing whether a graph is triangle-free and, more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are triangle-free and reject graphs that are far from being triangle-free in the sense that a constant fraction of the edges should be removed in order to obtain a triangle-free graph. The algorithm is allowed a small probability of error. This problem has been studied quite extensively in the past, but the focus was on dense graphs, that is, when $d = \Theta(n)$, where d is the average degree in the graph and n is the number of vertices. Here we study the complexity of the problem in general graphs, that is, for varying d. In this model a testing algorithm is allowed to ask neighbor queries (i.e., “What is the ith neighbor of vertex v?”), vertex-pair queries (i.e., “Is there an edge between vertices v and u?”), and degree queries (i.e., “What is the degree of vertex v?”). Our main finding is a lower bound of $\Omega(n^{1/3})$ on the necessary number of queries that holds for every $d < n^{1-\nu(n)}$, where $\nu(n) = o(1)$. Since when $d = \Theta(n)$ the number of queries sufficient for testing has been known to be independent of n, we observe an abrupt, threshold-like behavior of the complexity of testing around n. This lower bound holds for testing H-freeness of every nonbipartite subgraph H. Additionally, we provide sublinear upper bounds for testing triangle-freeness that are at most quadratic in the stated lower bounds, and we describe a transformation from certain one-sided error lower bounds for testing subgraph-freeness to two-sided error lower bounds. Finally, in the course of our analysis we show that dense random Cayley graphs behave like quasi-random graphs in the sense that relatively large subsets of vertices have the “correct” edge density. The result for subsets of this size cannot be obtained from the known spectral techniques that only supply such estimates for much larger subsets.

We show that random sparse binary linear codes are locally testable and locally decodable (under any linear encoding) with constant queries (with probability tending to one). By sparse, we mean that the code should have only polynomially many codewords. Our results are the first to show that local decodability and testability can be found in random, unstructured, codes. Previously known locally decodable or testable codes were either classical algebraic codes, or new ones constructed very carefully. We obtain our results by extending the techniques of Kaufman and Litsyn [11] who used the MacWilliams Identities to show that "almost-orthogonal" binary codes are locally testable. Their definition of almost orthogonality expected codewords to disagree in n/2 plusmn O(radicn) coordinates in codes of block length n. The only families of codes known to have this property were the dual-BCH codes. We extend their techniques, and simplify them in the process, to include codes of distance at least n/2 - O(n1-gamma) for any gamma > 0, provided the number of codewords is O(nt) for some constant t. Thus our results derive the local testability of linear codes from the classical coding theory parameters, namely the rale and the distance of the codes. More significantly, we show that this technique can also be used to prove the "self-correctability" of sparse codes of sufficiently large distance. This allows us to show that random linear codes under linear encoding functions are locally decodable. This ought to be surprising in that the definition of a code doesn't specify the encoding function used! Our results effectively say that any linear function of the bits of the codeword can be locally decoded in this case.

In this work, we consider the problems of testing whether adistribution over (0,1n) is k-wise (resp. (ε,k)-wise) independentusing samples drawn from that distribution.

We develop a general approach for improving the efficiency of a computationally bounded receiver interacting with a powerful and possibly malicious sender. The key idea we use is that of delegating some of the receiver's computation to the (potentially malicious) sender. This idea was recently introduced by Goldwasser et al. [14] in the area of program checking. A classic example of such a sender-receiver setting is interactive proof systems. By taking the sender to be a (potentially malicious) prover and the receiver to be a verifier, we show that (p-prover) interactive proofs with k rounds of interaction are equivalent to (p-prover) interactive proofs with k+O(1) rounds, where the verifier is in NC0. That is, each round of the verifier's computation can be implemented in constant parallel time. As a corollary, we obtain interactive proof systems, with (optimally) constant soundness, for languages in AM and NEXP, where the verifier runs in constant parallel-time.

We consider the guessing secrets problem defined by Chung et al. [2001]. This is a variant of the standard 20 questions game where the player has a set of k > 1 secrets from a universe of N possible secrets. The player is asked Boolean questions about the secret. For each question, the player picks one of the k secrets adversarially, and answers according to this secret. We present an explicit set of O (log N ) questions together with an efficient (i.e., poly(log N ) time) algorithm to solve the guessing secrets problem for the case of 2 secrets. This answers the main algorithmic question left unanswered by Chung et al. [2001]. The main techniques we use are small ϵ-biased spaces and the notion of list decoding . We also establish bounds on the number of questions needed to solve the k -secrets game for k > 2, and discuss how list decoding can be used to get partial information about the secrets, specifically to find a small core of secrets that must intersect the actual set of k secrets.

In this work we fill the knowledge gap concerning testing polynomials over finite fields. As previous works show, when the cardinality of the field, q, is sufficiently larger than the degree bound, d, then the number of queries sufficient for testing is polynomial or even linear in d. On the other hand, when $q=2$ then the number of queries, both sufficient and necessary, grows exponentially with d. Here we study the intermediate case where $2 < q = O(d)$ and show a smooth transition between the two extremes. Specifically, let p be the characteristic of the field (so that p is prime and $q = p^s$ for some integer $s \geq 1$). Then the number of queries performed by the test grows like $\ell\cdot q^{2\ell+1}$, where $\ell = \big\lceil \frac{d+1}{q-q/p}\big\rceil $. Furthermore, $q^{\Omega(\ell)}$ queries are necessary when $q = O(d)$. The test itself provides a unifying view of the tests for these two extremes: it considers random affine subspaces of dimension $\ell$ and verifies that the function restricted to the selected subspaces is a polynomial of degree at most d. Viewed in the context of coding theory, our result shows that Reed–Muller codes over general fields (usually referred to as generalized Reed–Muller (GRM) codes) are locally testable. In the course of our analysis we provide a characterization of small‐weight words that span the code. Such a characterization was previously known only when the field size is a prime or is sufficiently large, in which case the minimum‐weight words span the code.

A code is said to be locally testable if an algorithm can distinguish between a codeword and a vector being essentially far from the code using a number of queries that is independent of the code's length. The question of characterizing codes that are locally testable is highly complex. In this work we provide a sufficient condition for linear codes to be locally testable. Our condition is based on the weight distribution (spectrum) of the code and of its dual. Codes of (large) length n and minimum distance n/2 - /spl Theta/(/spl radic/n) have size which is at most polynomial in n. We call such codes almost-orthogonal. We use our condition to show that almost-orthogonal codes are locally testable, and, moreover, their dual codes can be spanned by words of constant weights (weight of a codeword refers to the number of its non-zero coordinates). Dual-BCH(n, t) codes are generalizations of the well studied Hadamard codes (t = 1 is Hadamard). Alon et al. (2003) raised the question whether Dual-BCH(n, t) codes are locally testable for constant t. As these codes are known to be almost-orthogonal, we solve this question. We further show that BCH(n, t) code is spanned by its almost shortest words, that is by codewords of weight at most 2t + 2, while the minimum weight is 2t + 1. Our results can be straightforwardly extended to Goppa codes and trace subcodes of algebraic-geometric codes.

A code is locally testable if there is a way to indicate with high probability that a vector is far enough from any codeword by accessing only a very small number of the vector's bits. We show that the Reed-Muller codes of constant order are locally testable. Specifically, we describe an efficient randomized algorithm to test if a given vector of length n=2/sup m/ is a word in the rth-order Reed-Muller code R(r,m) of length n=2/sup m/. For a given integer r/spl ges/1, and real /spl epsi/>0, the algorithm queries the input vector /spl upsi/ at O(1//spl epsi/+r2/sup 2r/) positions. On the one hand, if /spl upsi/ is at distance at least /spl epsi/n from the closest codeword, then the algorithm discovers it with probability at least 2/3. On the other hand, if /spl upsi/ is a codeword, then it always passes the test. Our result is almost tight: any algorithm for testing R(r,m) must perform /spl Omega/(1//spl epsi/+2/sup r/) queries.

We consider the generalized Reed-Muller code R/sub Fq/(/spl rho/,m) of order /spl rho/ and length q/sup m/,m>1, over the field F/sub q/, where q=p/sup t/ for prime p and t/spl ges/1. In particular, we are interested in the case that t>1 (so that q is not prime), and the order /spl rho/ is at least q. As shown by Ding and Key, under these conditions, unless /spl rho/ is very large (i.e., /spl rho/>(m-1)(q-1)+p/sup t-1/-2), the code is not spanned by its minimum-weight words. Furthermore, there was no known characterization of words with small weight that span the code. In this correspondence, we characterize a set of words that span the code, and show that their weight is upper-bounded by q/sup /spl lceil/m(q-1)-/spl rho//q-q/p/spl rceil//, which is at most quadratic in the weight of the minimum-weight words.

In this work we fill in the knowledge gap concerning testing polynomials over finite fields. As previous works show, when the cardinality of the field, q, is sufficiently larger than the degree bound, d, then the number of queries sufficient for testing is polynomial or even linear in d. On the other hand, when q = 2 then the number of queries, both sufficient and necessary, grows exponentially with d. Here we study the intermediate case where 21). Then the number of queries performed by the test grows like /spl lscr/ /spl middot/ q/sup 2/spl lscr/+1/, where /spl lscr/ = /spl lceil/(d+1)/((q-q)/p)/spl rceil/. Furthermore, q/sup /spl Omega/(/spl lscr/)/ queries are necessary when q /spl les/ O(d). The test itself provides a unifying view of the two extremes: it considers random affine subspaces of dimension /spl lscr/ and verifies that the function restricted to the selected subspaces is a degree d polynomial. Viewed in the context of coding theory, our result shows that Reed-Muller codes over general fields (usually referred to as generalized Reed-Muller (GRM) codes) are locally testable. In the course of our analysis we provide a characterization of small-weight words that span the code. Such a characterization was previously known only when the field size is a prime or is sufficiently large, in which case the minimum weight words span the code.

In this paper we consider the problem of testing bipartiteness of general graphs. The problem has previously been studied in two models, one most suitable for dense graphs and one most suitable for bounded-degree graphs. Roughly speaking, dense graphs can be tested for bipartiteness with constant complexity, while the complexity of testing bounded-degree graphs is $\tilde{\Theta}(\sqrt{n})$, where n is the number of vertices in the graph (and $\tilde{\Theta}(f(n))$ means $\Theta(f(n)\cdot{\rm polylog}(f(n)))$). Thus there is a large gap between the complexity of testing in the two cases. In this work we bridge the gap described above. In particular, we study the problem of testing bipartiteness in a model that is suitable for all densities. We present an algorithm whose complexity is $\tilde{O}(\min(\sqrt{n},n^2/m))$, where m is the number of edges in the graph, and we match it with an almost tight lower bound.