Are there explicit or random construction of linear codes that achieve the $GV$ bound with polynomial time decodable property with alphabet size $q=2$?
Tsfasman, Manin, Vladut beat the bound at alphabet size $q\geq49$ and so is there any evidence the bound can be beaten at $q=2$ (I see possibility mentioned in Sudan's and Guruswami's notes however they provide no evidence)?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
This is the closest reference I know of (available at Guruswami's homepage)
Guruswami and Indyk, Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates, SODA '04 Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 756-757
Abstract
We demonstrate a probabilistic construction of binary linear codes meeting the Gilbert-Varshamov bound (with overwhelming probability) for rates up to about $10^{-4}$ together with polynomial time algorithms to perform encoding and decoding up to half the distance. This is the first such result (for some positive rate) with polynomial decoding complexity; previously a similar result (up to rate about 0.02) was known with sub-exponential time decoding (Zyablov and Pinsker, 1981, my note: apparently $O(2^{\sqrt{n}})$)
From page 2:
We remark that though we do not know how to certify that the distance of the overall code will meet the GV bound (but we do know it will do so with high probability), we can certify the decoding property deterministically in the following sense: the decoding algorithm is guaranteed to (list) decode the code up to a fraction 1/4 of errors, regardless of whether the distance of the code meets the GV bound or not. This certification property gives us the desirable feature that a failure of the algorithm to uniquely decode the closest codeword from the received word (due to there being multiple close-by codewords) is in fact a “proof” that the distance fell short of the GV bound, and till we detect this failure, all decodings produced by the algorithm are indeed the correct closest codewords.
A quick look at papers citing this did not unearth any improvements.
-
$\begingroup$ I am not aware of anything further. But you can ask him by email, he is very approachable and will respond, I am sure. $\endgroup$– kodluCommented Jun 3, 2019 at 5:43
-
$\begingroup$ Yeah I saw that paper too and that is why I asked. His and his advisor's notes speculate the same about beatability of binary $GV$ bound. Do you know if they talk of $GV$ bound for random linear codes or just random codes? I am guessing it is the former. $\endgroup$– TurboCommented Jun 3, 2019 at 5:43
-
$\begingroup$ Section $2$ says rates get to $1/2-O(eps)$ while gv bound is $1-O(eps^2)$. Factor of half makes it look like if gets the random code bound not random linear code but construction is linear and so I wonder how it passed review without this clarification. $\endgroup$– TurboCommented Jun 3, 2019 at 6:01