Search

Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords using lower degree polynomials (when codewords are viewed as evaluation vectors of degree r polynomials in m variables). It then overviews some of the algorithms for decoding RM codes. It covers both algorithms with provable performance guarantees for every block length, as well as algorithms with state-of-the-art performances in practical regimes, which do not perform as well for large block length. Finally, the paper concludes with a few open problems. [ABSTRACT FROM AUTHOR]

Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime $k = n^{\theta }$ (with $\theta \in (0,1)$), with $n$ individuals among which $k$ are infected. However, the required number of tests may increase substantially under real-world practical constraints, notably including bounds on the maximum number $\Delta $ of tests an individual can be placed in, or the maximum number $\Gamma $ of individuals in a given test. While previous works have given recovery guarantees for these settings, significant gaps remain between the achievability and converse bounds. In this paper, we substantially or completely close several of the most prominent gaps. In the case of $\Delta $ -divisible items, we show that the definite defectives (DD) algorithm coupled with a random regular design is asymptotically optimal in dense scaling regimes, and optimal to within a factor of e more generally; we establish this by strengthening both the best known achievability and converse bounds. In the case of $\Gamma $ -sized tests, we provide a comprehensive analysis of the regime $\Gamma = \Theta (1)$ , and again establish a precise threshold proving the asymptotic optimality of SCOMP (a slight refinement of DD) equipped with a tailored pooling scheme. Finally, for each of these two settings, we provide near-optimal adaptive algorithms based on sequential splitting, and provably demonstrate gaps between the performance of optimal adaptive and non-adaptive algorithms. [ABSTRACT FROM AUTHOR]

Motivated by the error behavior in the DNA storage channel, in this paper, we extend the previously studied sequence reconstruction problem by Levenshtein. The reconstruction problem studies the model in which the information is read through multiple noisy channels, and the decoder, which receives all channel estimations, is required to decode the information. For the combinatorial setup, the assumption is that all the channels cause at most some t errors. Levenshtein considered the case in which all the channels have the same behavior, and we generalize this model and assume that the channels are not identical. Thus, different channels may cause different maximum numbers of errors. For example, we assume that there are N channels, which cause at most t1 or t2 errors, where t1 < t2, and the number of channels with at most t1 errors is at least [pN], for some fixed 0 < p < 1. If the information codeword belongs to a code with minimum distance d, the problem is then to find the minimum number of channels that guarantees successful decoding in the worst case. A different problem we study in this paper is where the number of channels is fixed, and the question is finding the minimum distance d that provides exact reconstruction. We study these problems and show how to apply them for the cases of substitutions and transpositions. [ABSTRACT FROM AUTHOR]

The paper proposes an improved difference-of-syndromes decoding algorithm for decoding quadratic residue codes up to half the minimum distance. Therein, soft-decision information is not essential, but it can be used to speed up the computations. The improvement over the prior art is demonstrated by simulations. Moreover, the proposed algorithm is also compared with the classic Berlekamp-Massey algorithm by taking two BCH codes as examples. [ABSTRACT FROM AUTHOR]

The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes like Reed–Solomon or Reed–Muller codes. Fix a finite field \mathbb F . The Reed–Muller code \text RM {\mathbb {F}}(n,d) is defined by n -variate degree- d polynomials over \mathbb F . In this paper, we study the list decoding radius of Reed–Muller codes over a constant prime field \mathbb F= \mathbb Fp , constant degree d , and large n . We show that the list decoding radius is equal to the minimal distance of the code. That is, if we denote by {\delta }(d) the normalized minimal distance of \text RM {\mathbb {F}}(n,d) , then the number of codewords in any ball of radius {\delta }(d)- {\varepsilon } is bounded by c=c(p,d, \varepsilon ) independent of n . This resolves a conjecture of Gopalan et al., who among other results proved it in the special case of \mathbb F= \mathbb F2 ; and extends the work of Gopalan who proved the conjecture in the case of d=2 . We also analyse the number of codewords in balls of radius exceeding the minimal distance of the code. For e \leq d , we show that the number of codewords of \text RM \mathbb F(n,d) in a ball of radius \delta (e) - \varepsilon is bounded by \exp (c \cdot n^d-e) , where c=c(p,d, \varepsilon ) is independent of $n$ . The dependence on n$ is tight. This extends the work of Kaufman et al. who proved similar bounds over {\mathbb {F}}_{2} . The proof relies on several new ingredients: an extension of the Frieze–Kannan weak regularity to general function spaces, higher order Fourier analysis, and an extension of the Schwartz–Zippel lemma to the compositions of polynomials. [ABSTRACT FROM PUBLISHER]

Reed–Muller (RM) codes encode an m -variate polynomial of degree at most r by evaluating it on all points in \0,1\^m . We denote this code by RM(r,m) . The minimum distance of RM(r,m) is 2^{m-r} and so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result. In this paper we give an efficient algorithm (in the block length n=2^{m} ) for decoding random errors in RM codes far beyond the minimum distance. Specifically, for low-rate codes (of degree r=o(\sqrt m) ), we can correct a random set of (1/2-o(1))n errors with high probability. For high rate codes (of degree m-r for r=o(\sqrt {m/\log m}) ), we can correct roughly m^{r/2}$ errors. More generally, for any integer $r$ , our algorithm can correct any error pattern in $RM(m-(2r+2),m)$ , for which the same erasure pattern can be corrected in $RM(m-(r+1),m)$ . The results above are obtained by applying recent results of Abbe, Shpilka, and Wigderson (STOC, 2015) and Kudekar et al. (STOC, 2016) regarding the ability of RM codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding RM codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the error-locating pair method of Pellikaan, Duursma, and Kötter that generalizes the Berlekamp–Welch algorithm for decoding Reed–Solomon codes. [ABSTRACT FROM PUBLISHER]

Non-malleable codes, introduced by Dziembowski et al., encode messages s in a manner, so that tampering the codeword causes the decoder to either output s or a message that is independent of s . While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly non-malleable coding becomes possible against every fixed family of tampering functions that is not too large (for instance, when | \mathcal {F}| \leqslant 2^{2^{\vphantom {R^{a}}\alpha n}} for some \alpha <1 , where n is the number of bits in a codeword). In this paper, we study the capacity of non-malleable codes, and establish optimal bounds on the achievable rate as a function of the family size, answering an open problem from Dziembowski et al. Specifically, We prove that for every family \mathcal {F} with | \mathcal {F}| \leqslant 2^{2^{\vphantom {R^{}}\alpha n}} , there exist non-malleable codes against \mathcal F with rate arbitrarily close to 1-\alpha [this is achieved with high probability (w.h.p.) by a randomized construction]. We show the existence of families of size \exp (n^O(1) 2^\alpha n) against which there is no non-malleable code of rate $1-\alpha $ (in fact this is the case w.h.p for a random family of this size). We also show that 1-\alpha $ is the best achievable rate for the family of functions, which are only allowed to tamper the first \alpha n$ bits of the codeword, which is of special interest. As a corollary, this implies that the capacity of non-malleable coding in the split-state model (where the tampering function acts independently but arbitrarily on the two halves of the codeword, a model which has received some attention recently) equals 1/2. We also give an efficient Monte Carlo construction of codes of rate close to 1 with polynomial time encoding and decoding that is non-malleable against any fixed c > 0 of size 2^{n^{c}} , in particular tampering functions with, say, cubic size circuits. [ABSTRACT FROM PUBLISHER]