 Award ID(s):
 1717842
 NSFPAR ID:
 10063529
 Date Published:
 Journal Name:
 2018 IEEE Int. Symp. Inf. Theory (ISIT)
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Consider a binary linear code of length N, minimum distance dmin, transmission over the binary erasure channel with parameter 0 < < 1 or the binary symmetric channel with parameter 0 < < 1 2 , and blockMAP decoding. It was shown by Tillich and Zemor that in this case the error probability of the blockMAP decoder transitions “quickly” from δ to 1−δ for any δ > 0 if the minimum distance is large. In particular the width of the transition is of order O(1/ √ dmin). We strengthen this result by showing that under suitable conditions on the weight distribution of the code, the transition width can be as small as Θ(1/N 1 2 −κ ), for any κ > 0, even if the minimum distance of the code is not linear. This condition applies e.g., to ReedMueller codes. Since Θ(1/N 1 2 ) is the smallest transition possible for any code, we speak of “almost” optimal scaling. We emphasize that the width of the transition says nothing about the location of the transition. Therefore this result has no bearing on whether a code is capacityachieving or not. As a second contribution, we present a new estimate on the derivative of the EXIT function, the proof of which is based on the BlowingUp Lemma.more » « less


null (Ed.)A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are δclose to the property in relative Hamming distance or (ii) only a tiny fraction of members are δclose to the property. In particular, no set in the collection has roughly half of its members δclose to the property and the others δfar from it. We show that the collection of affine spaces displays a proximity gap with respect to ReedSolomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to any δ smaller than the Johnson/GuruswamiSudan listdecoding bound of the RS code. We also show nearoptimal gap results, over fields of (at least) linear size in the RS code dimension, for δ smaller than the unique decoding radius. Concretely, if δ is smaller than half the minimal distance of an RS code V ⊂ Fq n , every affine space is either entirely δclose to the code, or alternatively at most an ( n/q)fraction of it is δclose to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multiparty cryptographic protocols, and concretely efficient proof systems. We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for ReedSolomon codes (due to BerlekampWelch and GuruswamiSudan) on a formal element of an affine space. This involves working with ReedSolomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing lowdegree tests.more » « less

A collection of sets displays a
proximity gap with respect to some property if for every set in the collection, either (i) all members areδ close to the property in relative Hamming distance or (ii) only a tiny fraction of members areδ close to the property. In particular, no set in the collection has roughly half of its membersδ close to the property and the othersδ far from it.We show that the collection of affine spaces displays a proximity gap with respect to Reed–Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to any
δ smaller than the Johnson/Guruswami–Sudan listdecoding bound of the RS code. We also show nearoptimal gap results, over fields of (at least)linear size in the RS code dimension, forδ smaller than the unique decoding radius. Concretely, ifδ is smaller than half the minimal distance of an RS code , every affine space is either entirely\(V\subset {\mathbb {F}}_q^n \) δ close to the code, or alternatively at most an (n /q )fraction of it isδ close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multiparty cryptographic protocols, and concretely efficient proof systems.We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed–Solomon codes (due to Berlekamp–Welch and Guruswami–Sudan) on a
formal element of an affine space. This involves working with Reed–Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing lowdegree tests. 
In this paper we study codes with sparse generator matrices. More specifically, codes with a certain constraint on the weight of all the columns in the generator matrix are considered. The end result is the following. For any binaryinput memoryless symmetric (BMS) channel and any e>0.085, we show an explicit sequence of capacityachieving codes with all the column wights of the generator matrix upper bounded by (log N) to the power (1+e), where N is the code block length. The constructions are based on polar codes. Applications to crowdsourcing are also shown.more » « less