An official website of the United States government
In this paper, we present a linear-time decoding algorithm for expander codes based on irregular graphs of any positive vertex expansion factor [Formula: see text] and inner codes with a minimum distance of at least [Formula: see text], where [Formula: see text] is the maximum right degree. The algorithm corrects a constant fraction of errors. It builds on two thrusts. The first is a series of works starting with that of Sipser and Spielman [Expander codes, IEEE Trans. Inf. Theory 42(6) (1996) 1710–1722] demonstrating that an asymptotically good family of error-correcting codes that can be decoded in linear time even from a constant fraction of errors in a received word provided [Formula: see text] is at least [Formula: see text] and continuing to the results of Gao and Dowling [Fast decoding of expander codes, IEEE Trans. Inf. Theory 64(2) (2018) 972–978], which only require [Formula: see text] provided the inner code minimum distance is sufficiently large. The second is the improved performance of LDPC codes based on irregular graphs demonstrated by Luby et al. [Improved low- density parity-check codes using irregular graphs, IEEE Trans. Inf. Theory 47(2) (2001) 585–598] and Richardson et al. [Design of capacity- approaching irregular low-density parity-check codes, IEEE Trans. Inf. Theory 47(2) (2001) 619–637]. The algorithm presented in this paper allows for irregular or regular graph-based constructions and uses inner codes of appropriate lengths as checks rather than simple parity-checks.
more »
« less
Expanders and right-angled Artin groups
The purpose of this paper is to give a characterization of families of expander graphs via right-angled Artin groups. We prove that a sequence of simplicial graphs [Formula: see text] forms a family of expander graphs if and only if a certain natural mini-max invariant arising from the cup product in the cohomology rings of the groups [Formula: see text] agrees with the Cheeger constant of the sequence of graphs, thus allowing us to characterize expander graphs via cohomology. This result is proved in the more general framework of vector space expanders, a novel structure consisting of sequences of vector spaces equipped with vector-space-valued bilinear pairings which satisfy a certain mini-max condition. These objects can be considered to be analogues of expander graphs in the realm of linear algebra, with a dictionary being given by the cup product in cohomology, and in this context represent a different approach to expanders that those developed by Lubotzky–Zelmanov and Bourgain–Yehudayoff.
more »
« less
- Award ID(s):
- 2002596
- PAR ID:
- 10545257
- Publisher / Repository:
- World Scientific
- Date Published:
- Journal Name:
- Journal of Topology and Analysis
- Volume:
- 16
- Issue:
- 02
- ISSN:
- 1793-5253
- Page Range / eLocation ID:
- 155 to 179
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Locally trivial bundles of [Formula: see text]-algebras with fiber [Formula: see text] for a strongly self-absorbing [Formula: see text]-algebra [Formula: see text] over a finite CW-complex [Formula: see text] form a group [Formula: see text] that is the first group of a cohomology theory [Formula: see text]. In this paper, we compute these groups by expressing them in terms of ordinary cohomology and connective [Formula: see text]-theory. To compare the [Formula: see text]-algebraic version of [Formula: see text] with its classical counterpart we also develop a uniqueness result for the unit spectrum of complex periodic topological [Formula: see text]-theory.more » « less
-
Expander graphs play a central role in graph theory and algorithms. With a number of powerful algorithmic tools developed around them, such as the Cut-Matching game, expander pruning, expander decomposition, and algorithms for decremental All-Pairs Shortest Paths (APSP) in expanders, to name just a few, the use of expanders in the design of graph algorithms has become ubiquitous. Specific applications of interest to us are fast deterministic algorithms for cut problems in static graphs, and algorithms for dynamic distance-based graph problems, such as APSP. Unfortunately, the use of expanders in these settings incurs a number of drawbacks. For example, the best currently known algorithm for decremental APSP in constant-degree expanders can only achieve a (log n) O(1/ 2 ) -approximation with n 1+O( ) total update time for any . All currently known algorithms for the Cut Player in the Cut-Matching game are either randomized, or provide rather weak guarantees: expansion 1/(log n) 1/ with running time n 1+O( ) . This, in turn, leads to somewhat weak algorithmic guarantees for several central cut problems: the best current almost linear time deterministic algorithms for Sparsest Cut, Lowest Conductance Cut, and Balanced Cut can only achieve approximation factor (log n) ω(1). Lastly, when relying on expanders in distancebased problems, such as dynamic APSP, via current methods, it seems inevitable that one has to settle for approximation factors that are at least Ω(log n). In contrast, we do not have any negative results that rule out a factor-5 approximation with near-linear total update time. In this paper we propose the use of well-connected graphs, and introduce a new algorithmic toolkit for such graphs that, in a sense, mirrors the above mentioned algorithmic tools for expanders. One of these new tools is the Distanced Matching game, an analogue of the Cut-Matching game for well-connected graphs. We demonstrate the power of these new tools by obtaining better results for several of the problems mentioned above. First, we design an algorithm for decremental APSP in expanders with significantly better guarantees: in a constant-degree expander, the algorithm achieves (log n) 1+o(1)-approximation, with total update time n 1+o(1). We also obtain a deterministic algorithm for the Cut Player in the Cut-Matching game that achieves expansion 1 (log n) 5+o(1) in time n 1+o(1), deterministic almost linear-time algorithms for Sparsest Cut, Lowest-Conductance Cut, and Minimum Balanced Cut with approximation factors O(poly log n), as well as improved deterministic algorithm for Expander Decomposition. We believe that the use of well-connected graphs instead of expanders in various dynamic distance-based problems (such as APSP in general graphs) has the potential of providing much stronger guarantees, since we are no longer necessarily restricted to superlogarithmic approximation factors.more » « less
-
We provide a characterization of when a coarse equivalence between coarse disjoint unions of expander graphs is close to a bijective coarse equivalence. We use this to show that if the uniform Roe algebras over metric spaces that are coarse unions of expanders graphs are isomorphic, then the metric spaces must be bijectively coarsely equivalent.more » « less
-
This paper concerns cup product pairings in \'etale cohomology related to work of M. Kim and of W. McCallum and R. Sharifi. We will show that by considering Ext groups rather than cohomology groups, one arrives at a pairing which combines invariants defined by Kim with a pairing defined by McCallum and Sharifi. We also prove a formula for Kim's invariant in terms of Artin maps in the case of cyclic unramified Kummer extensions. One consequence is that for all integers $n>1$, there are infinitely many number fields over which there are both trivial and non-trivial Kim invariants associated to cyclic groups of order $$n$$.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1142/S179352532150059X
