We give the first construction of explicit constantdegree lossless vertex expanders. Specifically, for any $\varepsilon\gt 0$ and sufficiently large d, we give an explicit construction of an infinite family of d-regular graphs where every small set S of vertices has $(1-\varepsilon) d|S|$ neighbors (which implies $(1-2 \varepsilon) d|S|$ unique-neighbors). Our results also extend naturally to construct biregular bipartite graphs of any constant imbalance, where small sets on each side have strong expansion guarantees. The graphs we construct admit a free group action, and hence realize new families of quantum LDPC codes of Lin and M. Hsieh [1] with a linear time decoding algorithm. Our construction is based on taking an appropriate product of a constant-sized lossless expander with a base graph constructed from Ramanujan Cayley cubical complexes.

We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work. Derandomized direct product testing, also known as agreement testing, is the following problem. Let$X$be a family of k-element subsets of$[N]$and let$\{f_{s}:s\rightarrow\Sigma\vert s\in X\}$be an ensemble of local functions, each defined over a subset$s\subset\lceil N$. Suppose that we run the following so-called agreement test: choose a random pair of sets$s_{1}, s_{2}\in X$that intersect on$\sqrt{k}$elements, and accept if$f_{s_{1}}, f_{s_{2}}$agree on the elements in$s_{1}\cap s_{2}$. We denote the success probability of this test by Agree$\{f_{s}\})$Given that Agree$(\{f_{s}\})=\varepsilon > 0$is there a global function$G:[N]\rightarrow\Sigma$such that$f_{s}=G\vert _{s}$for a non-negligible fraction of$s\in X\ ?$We construct a family$X$of k-subsets of$[N]$such that$\vert X\vert =O(N)$, and such that it satisfies the low acceptance agreement theorem. Namely,$\text{Agree}\left(\left\{f_s\right\}\right)>\varepsilon \Longrightarrow \exists G:[N] \rightarrow \Sigma, \quad \underset{s}{\mathbb{P}}\left[\left.f_s \stackrel{0.99}{\approx} G\right\vert_s\right] \geqslant \text{poly}(\varepsilon)$. A key idea is to replace the well-studied LSV complexes by symplectic high dimensional expanders (HDXs). The family$X$is just the k-faces of the new symplectic HDXs. The latter serve our needs better since their fundamental group satisfies the congruence subgroup property, which implies that they lack small covers. We also give a polynomial-time algorithm to construct this family of sym-plectic HDXs.

A locally testable code (LTC) is an error correcting code that has a property-tester. The tester reads q bits that are randomly chosen, and rejects words with probability proportional to their distance from the code. The parameter q is called the locality of the tester.

We initiate the study of property testing problems concerning relations between permutations. In such problems, the input is a tuple (σ1, …, σd) of permutations on \{1, \ldots, n\}, and one wishes to determine whether this tuple satisfies a certain system of relations E, or is far from every tuple that satisfies E. If this computational problem can be solved by querying only a small number of entries of the given permutations, we say that E is testable. For example, when d=2 and E consists of the single relation \mathrm{XY}= \mathrm{YX}, this corresponds to testing whether σ1σ2=σ2σ1, where σ1σ2and σ2σ1denote composition of permutations. We define a collection of graphs, naturally associated with the system E, that encodes all the information relevant to the testability of E. We then prove two theorems that provide criteria for testability and non-testability in terms of expansion properties of these graphs. By virtue of a deep connection with group theory, both theorems are applicable to wide classes of systems of relations. In addition, we formulate the well-studied group-theoretic notion of stability in permutations as a special case of the testa-bility notion above, interpret all previous works on stability as testability results, survey previous results on stability from a computational perspective, and describe many directions for future research on stability and testability. This is an extended abstract. The full version is available at https://arxiv.org/abs/2011.05234. All references beyond Sections I and II refer to the full version.

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}.

We consider the standard semi-direct product A/spl times/B of finite groups A, B. We show that with certain choices of generators for these three groups, the Cayley graph of A/spl times/B is (essentially) the zigzag product of the Cayley graphs of A and B. Thus, using the results of O. Reingold et al. (2000), the new Cayley graph is an expander if and only if its two components are. We develop some general ways of using this construction to obtain large constant-degree expanding Cayley graphs from small ones. A. Lubotzky and B. Weiss (1993) asked whether expansion is a group property; namely, is being an expander for (a Cayley graph of) a group G depend solely on G and not on the choice of generators. We use the above construction to answer the question in the negative, by showing an infinite family of groups A/sub i//spl times/B/sub i/ which are expanders with one choice of a (constant-size) set of generators and are not with another such choice. It is interesting to note that this problem is still open, though for "natural" families of groups like the symmetric groups S/sub n/ or the simple groups PSL(2, p).

The diameter of a group G with respect to a set S of generators is the maximum over g in G of the length of the shortest word in S union S/sup -1/ representing g. This concept arises in the contexts of efficient communication networks and Rubik's-cube-type puzzles. 'Best' generators are pertinent to networks, whereas 'worst' and 'average' generators seem more adequate models for puzzles. A substantial body of recent work on these subjects by the authors is surveyed. Regarding the 'best' case, it is shown that, although the structure of the group is essentially irrelevant if mod S mod is allowed to exceed (log mod G mod )/sup 1+c/(c>0), it plays a strong role when mod S mod =O(1).>

Kupitz and Perles showed that for $g = 3$ or 4 and fixed $k\geqq 3$, every connected, k-regular locally symmetric graph is finite and there are only finitely many such graphs. It is shown that the situation is completely different for every even $g\geqq 6$. The proof uses Coxeter groups and some suitable quotients.

Background.The aim of this note is to give an explicit construction of a rich family of k-regular (except for k ° =k) of the adjacency matrix satisfy Ikjl < 2 k~-l.graphs for which all the eigenvalues kj This bound is optimal (see Proposition 2.1).We call such graphs Ramanujan graphs.These graphs have many applications in the construction of explicit algorithms.~ny of these applications come from the fact that Ramanujan graphs make good expanders.Expanders in ~irn serve as basic building blocks for the construction of nonblocking networks [Pin, Bas-Pin, PI1], s~perconcentrators [G-G], sorting and selecting algorithms [AKS, PI3] etc.More precisely let X = (V,E) be a graph with vertices V and edges E .For A c: V we define the boundary of A, denoted ~A, by 8A = [yc V[d(y,A) = i} .