Construction Of Asymptotically Good Low-rate Error-correcting Codes Through Pseudo-random Graphs

A novel technique, based on the pseudo-random properties of certain graphs known as expanders, is used to obtain novel simple explicit constructions of asymptotically good codes. In one of the constructions, the expanders are used to enhance Justesen codes by replicating, shuffling, and then regrouping the code coordinates. For any fixed (small) rate, and for a sufficiently large alphabet, the codes thus obtained lie above the Zyablov bound. Using these codes as outer codes in a concatenated scheme, a second asymptotic good construction is obtained which applies to small alphabets (say, GF(2)) as well. Although these concatenated codes lie below the Zyablov bound, they are still superior to previously known explicit constructions in the zero-rate neighborhood. >

• Publication year

  1991

• Venue

  Proceedings. 1991 IEEE International Symposium on Information Theory

• Publication date

  1991-06-24

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/ISIT.1991.695195
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the second eigenvalue of a graph

  1991cited by this paper
• Small-bias probability spaces: efficient constructions and applications

  1990influential reference
• Dispersers, deterministic amplification, and weak random sources

  1989cited by this paper
• How to recycle random bits

  1989cited by this paper
• Vector sets for exhaustive testing of logic circuits

  1988cited by this paper
• Deterministic simulation in LOGSPACE

  1987cited by this paper
• Explicit expanders and the Ramanujan conjectures

  1986cited by this paper
• Explicit construction of exponential sized families of k-independent sets

  1986cited by this paper
• Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory

  1986cited by this paper
• A note on lower bounds

  1986cited by this paper
• Eigenvalues and expanders

  1986cited by this paper
• On Computational Complexity of Some Algebraic Curves Over Finite Fields

  1985cited by this paper
• Modular curves and codes with a polynomial construction

  1984cited by this paper
• Modular curves, Shimura curves, and Goppa codes, better than Varshamov‐Gilbert bound

  1982cited by this paper
• Superimposed concatenated codes (Corresp.)

  1980cited by this paper
• A new class of asymptotically good codes beyond the Zyablov bound

  1978cited by this paper
• The Theory of Error-Correcting Codes

  1977cited by this paper
• Some results on the problem of constructing asymptotically good error-correcting codes

  1975cited by this paper
• A Modification of the Constructive Asymptotically Good Codes of Justesen for Low Rates

  1974influential reference
• Justesen's construction-The low-rate case (Corresp.)

  1973cited by this paper
• Families of k-independent sets

  1973cited by this paper
• Class of constructive asymptotically good algebraic codes

  1972influential reference
• Multiplicative Number Theory

  1967cited by this paper
• Ramanujan Graphs

  1965cited by this paper
• Sur les courbes algébriques et les variétés qui s'en déduisent

  1948cited by this paper

• Optimal PRGs for Low-Degree Polynomials over Polynomial-Size Fields

  2026cites this paper
• Trellis codes with a good distance profile constructed from expander graphs

  2026cites this paper
• List Decoding Expander-Based Codes via Fast Approximation of Expanding CSPs: I

  2025cites this paper
• Decoding Balanced Linear Codes With Preprocessing

  2025cites this paper
• List Decoding Expander-Based Codes up to Capacity in Near-Linear Time*

  2025cites this paper
• Explicit Codes Approaching Generalized Singleton Bound using Expanders

  2025influential citation
• Uniform Universal Sets, Splitters, and Bisectors

  2025cites this paper
• Almost-Ramanujan Expanders From Arbitrary Expanders via Operator Amplification

  2025cites this paper
• Fooling Near-Maximal Decision Trees

  2025cites this paper
• Random coding for long-range continuous-variable QKD

  2025cites this paper
• Explicit Time and Space Efficient Encoders Exist Only With Random Access

  2024cites this paper
• SIGACT News Complexity Theory Column

  2024cites this paper
• Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL

  2024cites this paper
• Improved Explicit Near-Optimal Codes in the High-Noise Regimes

  2024cites this paper
• Binary Codes with Distance Close to Half

  2024cites this paper
• Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate

  2024cites this paper
• When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?

  2024cites this paper
• A High Dimensional Goldreich-Levin Theorem

  2023cites this paper
• List Decoding of Tanner and Expander Amplified Codes from Distance Certificates

  2023cites this paper
• Pseudorandom Linear Codes are List Decodable to Capacity

  2023cites this paper
• Derandomization with Minimal Memory Footprint

  2023cites this paper
• Strong blocking sets and minimal codes from expander graphs

  2023cites this paper
• Gilbert and Varshamov Meet Johnson: List-Decoding Explicit Nearly-Optimal Binary Codes

  2023cites this paper
• Polynomial Formulations as a Barrier for Reduction-Based Hardness Proofs

  2022cites this paper
• Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification

  2022cites this paper
• List-Decoding XOR Codes Near the Johnson Bound

  2022cites this paper
• CS294-226: Advances in Error-Correcting Codes

  2022cites this paper
• New near-linear time decodable codes closer to the GV bound

  2022cites this paper
• Analyzing Ta-Shma’s Code via the Expander Mixing Lemma

  2022cites this paper
• List-Decoding Random Walk XOR Codes Near the Johnson Bound

  2022cites this paper
• Revisiting Time-Space Tradeoffs for Function Inversion

  2022cites this paper
• Random Cayley graphs and expanders. (English)

  2022cites this paper
• On Hitting-Set Generators for Polynomials that Vanish Rarely

  2022cites this paper
• List-Decoding with Double Samplers

  2021cites this paper
• Differentially Private Correlation Clustering

  2021cites this paper
• Near-linear time decoding of Ta-Shma’s codes via splittable regularity

  2021influential citation
• Punctured Low-Bias Codes Behave Like Random Linear Codes

  2021cites this paper
• Hardness of KT characterizes parallel cryptography

  2021cites this paper
• Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity

  2021cites this paper
• A New Formula for the Minimum Distance of an Expander Code

  2021cites this paper
• Polynomial Data Structure Lower Bounds in the Group Model

  2020cites this paper
• Nearly Optimal Pseudorandomness From Hardness

  2020cites this paper
• Locally testable codes via high-dimensional expanders

  2020cites this paper
• List Decoding of Direct Sum Codes

  2020cites this paper
• Unique Decoding of Explicit ε-balanced Codes Near the Gilbert-Varshamov Bound

  2020cites this paper
• Unique Decoding of Explicit $\varepsilon$-balanced Codes Near the Gilbert-Varshamov Bound

  2020cites this paper
• High-Probability List-Recovery, and Applications to Heavy Hitters

  2020cites this paper
• Combinatorial Solution of the Syndrome Decoding Problem using Copula on Grassmann graph

  2020cites this paper
• Combinatorics with Copula for Code based Post-Quantum Cryptography

  2020cites this paper
• Average Bias and Polynomial Sources

  2019cites this paper
• Pseudorandom Constructions: Computing in Parallel and Applications to Edit Distance Codes

  2019cites this paper
• Graph-based Algorithms for Smart Mobility Planning and Large-scale Network Discovery

  2019cites this paper
• Bounded Independence Plus Noise

  2019cites this paper
• Improved Extractors for Recognizable and Algebraic Sources

  2019cites this paper
• Deterministic Constructions of High-Dimensional Sets with Small Dispersion

  2019cites this paper
• N ov 2 01 7 Quantified Derandomization of Linear Threshold Circuits

  2018cites this paper
• Pseudorandom generators for width-3 branching programs

  2018cites this paper
• Circuit Depth Reductions

  2018cites this paper
• List Decoding with Double Samplers

  2018cites this paper
• C C ] 1 2 N ov 2 01 8 Circuit Depth Reductions

  2018cites this paper
• Spectral expansion of random sum complexes

  2018cites this paper
• Expanding Generating Sets for Solvable Permutation Groups

  2018cites this paper
• Ja n 20 18 Spectral Expansion of Random Sum Complexes

  2018cites this paper
• Quantified derandomization of linear threshold circuits

  2017cites this paper
• Non-malleable codes and extractors for small-depth circuits, and affine functions

  2017cites this paper
• Shift lifts preserving Ramanujan property

  2017cites this paper
• Near-Optimal Secret Sharing and Error Correcting Codes in \mathsf AC^0 AC 0

  2017cites this paper
• On shortened and punctured cyclic codes

  2017cites this paper
• Small bias requires large formulas

  2017cites this paper
• High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity

  2017cites this paper
• Explicit, almost optimal, epsilon-balanced codes

  2017influential citation
• Boolean Tensor Decomposition for Conjunctive Queries with Negation

  2017cites this paper
• Some Limitations of the Sum of Small-Bias Distributions

  2017cites this paper
• Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics

  2017cites this paper
• Near-Optimal Secret Sharing and Error Correcting Codes in AC0

  2017cites this paper
• Erasure Codes with a Hierarchical Bundle Structure

  2017cites this paper
• Explicit two-source extractors and more

  2016cites this paper
• Low-degree test with polynomially small error

  2016cites this paper
• Derandomizing Chernoff Bound with Union Bound with an Application to k-wise Independent Sets

  2016cites this paper
• Bounded Indistinguishability and the Complexity of Recovering Secrets

  2016cites this paper
• Universal Sets and Cover-Free Families

  2016cites this paper
• Expander Graphs and Coding Theory

  2016cites this paper
• Robust Protocols for Securely Expanding Randomness and Distributing Keys Using Untrusted Quantum Devices

  2016cites this paper
• The Hardness of Approximation of Euclidean k-Means

  2015cites this paper
• High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity

  2015cites this paper
• An algebraic approach to graph codes

  2015cites this paper
• Towards Constructing Ramanujan Graphs Using Shift Lifts

  2015cites this paper
• Non-malleable extractors and codes, with their many tampered extensions

  2015cites this paper
• On the hardness of learning sparse parities

  2015cites this paper
• Corruption Detection on Networks

  2015cites this paper
• High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity

  2015cites this paper
• Constructing Ramanujan Graphs Using Shift Lifts

  2015cites this paper
• Distributed Corruption Detection in Networks

  2015cites this paper
• Linear Time Probabilistic Erasure Codes With Nearly Optimal Recovery

  2014cites this paper
• Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices

  2014cites this paper
• An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing

  2014cites this paper
• Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications

  2014cites this paper
• Linear Time Constructions of Some d -Restriction Problems

  2014cites this paper
• Testers and their applications

  2014cites this paper
• Small-Bias Sets for Nonabelian Groups: Derandomizing the Alon-Roichman Theorem

  2013cites this paper