Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
From MaRDI portal
Publication:3990791
DOI10.1109/18.119713zbMath0744.94023OpenAlexW2122270497MaRDI QIDQ3990791
Ron M. Roth, Jehoshua Bruck, Noga Alon, Joseph (Seffi) Naor, Moni Naor
Publication date: 28 June 1992
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Full work available at URL: https://resolver.caltech.edu/CaltechAUTHORS:ALOieeetit92
Related Items (41)
A new formula for the minimum distance of an expander code ⋮ Shift lifts preserving Ramanujan property ⋮ MODp-tests, almost independence and small probability spaces ⋮ The cell probe complexity of succinct data structures ⋮ Expanding Generating Sets for Solvable Permutation Groups ⋮ The complexity of error-correcting codes ⋮ Deterministic constructions of high-dimensional sets with small dispersion ⋮ Polynomial Data Structure Lower Bounds in the Group Model ⋮ Random Cayley graphs and expanders ⋮ Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions ⋮ Defaults and relevance in model-based reasoning ⋮ Low-degree test with polynomially small error ⋮ Linear Time Constructions of Some $$d$$-Restriction Problems ⋮ Reasoning with models ⋮ Hardness amplification within NP against deterministic algorithms ⋮ Constructions of permutation arrays for certain scheduling cost measures ⋮ Finding a hidden code by asking questions ⋮ Revisiting time-space tradeoffs for function inversion ⋮ Unnamed Item ⋮ On rigid matrices and \(U\)-polynomials ⋮ Expander graphs and their applications ⋮ Generalized hashing and parent-identifying codes. ⋮ Unnamed Item ⋮ Nonmalleable Extractors and Codes, with Their Many Tampered Extensions ⋮ Spectral expansion of random sum complexes ⋮ Improved Extractors for Recognizable and Algebraic Sources ⋮ On quasilinear-time complexity theory ⋮ Improved parallel approximation of a class of integer programming problems ⋮ Unnamed Item ⋮ A coding scheme that increases the code rate ⋮ Distributed Corruption Detection in Networks ⋮ A Sample of Samplers: A Computational Perspective on Sampling ⋮ Basic Facts about Expander Graphs ⋮ Attribute-efficient learning in query and mistake-bound models ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ Improved algorithms via approximations of probability distributions ⋮ A combination of testability and decodability by tensor products ⋮ List-Decoding with Double Samplers ⋮ On hitting-set generators for polynomials that vanish rarely ⋮ On the decisional complexity of problems over the reals ⋮ Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics
This page was built for publication: Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
