期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 68, 期 2, 页码 905-922出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2021.3123497
关键词
Coding theory; random codes; list-decoding and recovery; threshold rates
资金
- NSF [CCF-1563742, CCF-1814603]
- Simons Investigator Award
- European Research Council (ERC) H2020 (ALGSTRONGCRYPTO) [74079]
- NSF-CAREER [CCF-1844628]
- NSF-U.S.-Israel Binational Science Foundation (BSF) [CCF1814629]
- Sloan Research Fellowship
- Google Graduate Fellowship in Computer Science
- NSF-BSF [CCF-1814629]
The article discusses the threshold rate for random codes satisfying specific properties, by studying properties defined by symmetric sets of codewords, the conclusion is reached that the threshold rate is equal to the lower bound obtained by a first-moment calculation.
Suppose that P is a property that may be satisfied by a random code C subset of Sigma(n). For example, for some p is an element of (0, 1), P might be the property that there exist three elements of C that lie in some Hamming ball of radius pn. We say that R* is the threshold rate for P if a random code of rate R* + epsilon is very likely to satisfy P, while a random code of rate R* - epsilon is very unlikely to satisfy P. While random codes are well-studied in coding theory, even the threshold rates for relatively simple properties like the one above are not well understood. We characterize threshold rates for a rich class of properties. These properties, like the example above, are defined by the inclusion of specific sets of codewords which are also suitably symmetric. For properties in this class, we show that the threshold rate is in fact equal to the lower bound that a simple first-moment calculation obtains. Our techniques not only pin down the threshold rate for the property P above, they give sharp bounds on the threshold rate for list-recovery in several parameter regimes, as well as an efficient algorithm for estimating the threshold rates for list-recovery in general.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据