A New Look at Gallager's Bounds
summary
Random LDPC codes are constructed from a parity-check matrix with J ones/column and K ones/row built by J random permutations of block identity matrices, J ≥ 3. A simple first-moment bound <1 estimates the expected number of codewords of weight ≤ Δn and yields a lower bound on distance; the J=3 case reduces to maximizing a multinomial count via u0 u2 u4 Lagrange multiplier calculation. Open questions: bunching two layers, Eulerian subgraphs of K‑regular graphs, and whether this can beat Gilbert–Varshamov.
AI-written summary · about
chapters (4)
related talks
01h 01mCoding for Modern Distributed Storage Systems I
01h 00mAverage-case Complexity for Polynomials, and All That
24mBlock Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing
50mRandom Combinatorial Matrices
59mDawn in the age of quantum fault tolerance
01h 17mInapproximability of Constraint Satisfaction Problems III
01h 04mInformation Theory in Computational Complexity I
01h 10mDistribution Estimation and Applications I