On expander codes

By G. Zémor. IEEE Transactions on Information Theory, 2001

433 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/ba539d025259257b4ace2390bcc74519c279c4e8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

Batch codes and their applications (2004, background): “A standard union bound analysis gives the following: 1) , the neighborhood of every sets S ⊂ A such that | S | ≤ k contains at least | S | vertices in B .”
Low-density parity-check codes based on finite geometries: A rediscovery and new results (2001, background): “Low density parity check (LDPC) codes were first discovered by Gallager [1] [2] in the early 1960's and have recently been rediscovered and generalized [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14].”
The PCP theorem by gap amplification (2006, neutral): “, expander codes [33]).”
Efficient and reliable low-power backscatter networks (2012, background): “is devised to effectively decode such a rateless code on a complex constellation graph representing multiple sources, unlike bit flipping decoding in the modulo-2 domain often employed by the coding theory community [33, 44].”
Spectral Graph Theory (2012, background): “In addition to playing a prominent role in countless theorems, they are used in the design of pseudorandom generators [41, 42, 43], error-correcting codes [44, 45, 46, 47, 48], fault-tolerant circuits [49] and routing networks [50].”
The capacity of low-density parity-check codes under message-passing decoding (2001, background): “I N the wake of the phenomenal success of turbo codes [2], another class of codes exhibiting similar characteristics and performance was rediscovered [3], [4].”
The art of error correcting coding (2002, methodology): “This graph is known as a Tanner graph (Sipser and Spielman 1996; Tanner 1981), named after its inventor.”
Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation (2001, neutral): “[3] and MacKay et al.”
Quantum error correction (2001, neutral): “The second step occurred much later when Sipser and Spielman noticed that applying this recipe to a special class of graphs known as expander graphs would yield good LDPC codes [SS96].”
Asymptotically good Quantum and locally testable classical LDPC codes (2021, methodology): “In some sense, it plays a role similar to the role of the minimal distance of the local codes in the classical proof of Sipser and Spielman from [32], where it is shown that expander codes have linear minimum distances.”
Polar Codes for Channel and Source Coding (2009, background): “Around the same time Sipser and Spielman [22] constructed expander codes and came up with a simple decoding algorithm that could correct a linear fraction of adversarial errors.”
Spatially coupled ensembles universally achieve capacity under belief propagation (2012, background): “Shannon limit performance under lowcomplexity iterative decoding. Their remarkable performance lead to a ﬂurry of research on the “turbo” principle. Around the same time, Spielman in his thesis [31], [32] and MacKay and Neal in [33]–[36], independently rediscovered low-density parity-check (LDPC) co”
On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit (2001, background): “This shows that LDPC codes—originally invented by Gallager [2], forgotten for decades, rediscovered by many [3], [4]—can now outperform powerful turbo codes [5] if designed properly.”
Multilevel expander codes (2005, background): “Codes on graphs are presently actively studied both from the standpoint of their parameters and the convergence properties of various decoding algorithms.”
Efficient encoding of low-density parity-check codes (2001, background): “) It was suggested in [13] and [9] to use cascaded rather than bipartite graphs.”
Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees (2013, background): “For example, the explicit constructions of error correcting codes of Sipser and Spielman [28] require non-bipartite expanders, while the improvements of their construction [29], [30], [31] require bipartite Ramanujan expanders.”
ENTROPY WAVES, THE ZIG-ZAG GRAPH PRODUCT, AND NEW CONSTANT-DEGREE (2004, neutral): “blems in computer science, on topics including network design (e.g. [Pip87], [PY82], [AKS83]), complexity theory ([Val77], [Sip88], [Urq87]), derandomization ([NN93], [INW94], [IW97]), coding theory ([SS96], [Spi96]), and cryptography ([GILVZ90]). Expander graphs have also found some applications in”