@unpublished{6748,
abstract = {Fitting a function by using linear combinations of a large number N of `simple' components is one of the most fruitful ideas in statistical learning. This idea lies at the core of a variety of methods, from two-layer neural networks to kernel regression, to boosting. In general, the resulting risk minimization problem is non-convex and is solved by gradient descent or its variants. Unfortunately, little is known about global convergence properties of these approaches.
Here we consider the problem of learning a concave function f on a compact convex domain Ω⊆ℝd, using linear combinations of `bump-like' components (neurons). The parameters to be fitted are the centers of N bumps, and the resulting empirical risk minimization problem is highly non-convex. We prove that, in the limit in which the number of neurons diverges, the evolution of gradient descent converges to a Wasserstein gradient flow in the space of probability distributions over Ω. Further, when the bump width δ tends to 0, this gradient flow has a limit which is a viscous porous medium equation. Remarkably, the cost function optimized by this gradient flow exhibits a special property known as displacement convexity, which implies exponential convergence rates for N→∞, δ→0. Surprisingly, this asymptotic theory appears to capture well the behavior for moderate values of δ,N. Explaining this phenomenon, and understanding the dependence on δ,N in a quantitative manner remains an outstanding challenge.},
author = {Javanmard, Adel and Mondelli, Marco and Montanari, Andrea},
booktitle = {arXiv:1901.01375},
title = {{Analysis of a two-layer neural network via displacement convexity}},
year = {2019},
}
@article{6750,
abstract = {Polar codes have gained extensive attention during the past few years and recently they have been selected for the next generation of wireless communications standards (5G). Successive-cancellation-based (SC-based) decoders, such as SC list (SCL) and SC flip (SCF), provide a reasonable error performance for polar codes at the cost of low decoding speed. Fast SC-based decoders, such as Fast-SSC, Fast-SSCL, and Fast-SSCF, identify the special constituent codes in a polar code graph off-line, produce a list of operations, store the list in memory, and feed the list to the decoder to decode the constituent codes in order efficiently, thus increasing the decoding speed. However, the list of operations is dependent on the code rate and as the rate changes, a new list is produced, making fast SC-based decoders not rate-flexible. In this paper, we propose a completely rate-flexible fast SC-based decoder by creating the list of operations directly in hardware, with low implementation complexity. We further propose a hardware architecture implementing the proposed method and show that the area occupation of the rate-flexible fast SC-based decoder in this paper is only 38% of the total area of the memory-based base-line decoder when 5G code rates are supported. },
author = {Hashemi, Seyyed Ali and Condo, Carlo and Mondelli, Marco and Gross, Warren J},
issn = {1053587X},
journal = {IEEE Transactions on Signal Processing},
number = {22},
publisher = {IEEE},
title = {{Rate-flexible fast polar decoders}},
doi = {10.1109/TSP.2019.2944738},
volume = {67},
year = {2019},
}
@article{6662,
abstract = {In phase retrieval, we want to recover an unknown signal 𝑥∈ℂ𝑑 from n quadratic measurements of the form 𝑦𝑖=|⟨𝑎𝑖,𝑥⟩|2+𝑤𝑖, where 𝑎𝑖∈ℂ𝑑 are known sensing vectors and 𝑤𝑖 is measurement noise. We ask the following weak recovery question: What is the minimum number of measurements n needed to produce an estimator 𝑥^(𝑦) that is positively correlated with the signal 𝑥? We consider the case of Gaussian vectors 𝑎𝑎𝑖. We prove that—in the high-dimensional limit—a sharp phase transition takes place, and we locate the threshold in the regime of vanishingly small noise. For 𝑛≤𝑑−𝑜(𝑑), no estimator can do significantly better than random and achieve a strictly positive correlation. For 𝑛≥𝑑+𝑜(𝑑), a simple spectral estimator achieves a positive correlation. Surprisingly, numerical simulations with the same spectral estimator demonstrate promising performance with realistic sensing matrices. Spectral methods are used to initialize non-convex optimization algorithms in phase retrieval, and our approach can boost the performance in this setting as well. Our impossibility result is based on classical information-theoretic arguments. The spectral algorithm computes the leading eigenvector of a weighted empirical covariance matrix. We obtain a sharp characterization of the spectral properties of this random matrix using tools from free probability and generalizing a recent result by Lu and Li. Both the upper bound and lower bound generalize beyond phase retrieval to measurements 𝑦𝑖 produced according to a generalized linear model. As a by-product of our analysis, we compare the threshold of the proposed spectral method with that of a message passing algorithm.},
author = {Mondelli, Marco and Montanari, Andrea},
issn = {1615-3383},
journal = {Foundations of Computational Mathematics},
number = {3},
pages = {703--773},
publisher = {Springer},
title = {{Fundamental limits of weak recovery with applications to phase retrieval}},
doi = {10.1007/s10208-018-9395-y},
volume = {19},
year = {2019},
}
@article{7007,
abstract = {We consider the primitive relay channel, where the source sends a message to the relay and to the destination, and the relay helps the communication by transmitting an additional message to the destination via a separate channel. Two well-known coding techniques have been introduced for this setting: decode-and-forward and compress-and-forward. In decode-and-forward, the relay completely decodes the message and sends some information to the destination; in compress-and-forward, the relay does not decode, and it sends a compressed version of the received signal to the destination using Wyner–Ziv coding. In this paper, we present a novel coding paradigm that provides an improved achievable rate for the primitive relay channel. The idea is to combine compress-and-forward and decode-and-forward via a chaining construction. We transmit over pairs of blocks: in the first block, we use compress-and-forward; and, in the second block, we use decode-and-forward. More specifically, in the first block, the relay does not decode, it compresses the received signal via Wyner–Ziv, and it sends only part of the compression to the destination. In the second block, the relay completely decodes the message, it sends some information to the destination, and it also sends the remaining part of the compression coming from the first block. By doing so, we are able to strictly outperform both compress-and-forward and decode-and-forward. Note that the proposed coding scheme can be implemented with polar codes. As such, it has the typical attractive properties of polar coding schemes, namely, quasi-linear encoding and decoding complexity, and error probability that decays at super-polynomial speed. As a running example, we take into account the special case of the erasure relay channel, and we provide a comparison between the rates achievable by our proposed scheme and the existing upper and lower bounds.},
author = {Mondelli, Marco and Hassani, S. Hamed and Urbanke, Rüdiger},
issn = {1999-4893},
journal = {Algorithms},
number = {10},
publisher = {MDPI},
title = {{A new coding paradigm for the primitive relay channel}},
doi = {10.3390/a12100218},
volume = {12},
year = {2019},
}
@article{6663,
abstract = {Consider the problem of constructing a polar code of block length N for a given transmission channel W. Previous approaches require one to compute the reliability of the N synthetic channels and then use only those that are sufficiently reliable. However, we know from two independent works by Schürch and by Bardet et al. that the synthetic channels are partially ordered with respect to degradation. Hence, it is natural to ask whether the partial order can be exploited to reduce the computational burden of the construction problem. We show that, if we take advantage of the partial order, we can construct a polar code by computing the reliability of roughly a fraction 1/ log 3/2 N of the synthetic channels. In particular, we prove that N/ log 3/2 N is a lower bound on the number of synthetic channels to be considered and such a bound is tight up to a multiplicative factor log log N. This set of roughly N/ log 3/2 N synthetic channels is universal, in the sense that it allows one to construct polar codes for any W, and it can be identified by solving a maximum matching problem on a bipartite graph. Our proof technique consists of reducing the construction problem to the problem of computing the maximum cardinality of an antichain for a suitable partially ordered set. As such, this method is general, and it can be used to further improve the complexity of the construction problem, in case a refined partial order on the synthetic channels of polar codes is discovered.},
author = {Mondelli, Marco and Hassani, Hamed and Urbanke, Rudiger},
journal = {IEEE},
number = {5},
pages = {2782--2791},
publisher = {IEEE},
title = {{Construction of polar codes with sublinear complexity}},
doi = {10.1109/tit.2018.2889667},
volume = {65},
year = {2019},
}
@article{6678,
abstract = {We survey coding techniques that enable reliable transmission at rates that approach the capacity of an arbitrary discrete memoryless channel. In particular, we take the point of view of modern coding theory and discuss how recent advances in coding for symmetric channels help provide more efficient solutions for the asymmetric case. We consider, in more detail, three basic coding paradigms. The first one is Gallager's scheme that consists of concatenating a linear code with a non-linear mapping so that the input distribution can be appropriately shaped. We explicitly show that both polar codes and spatially coupled codes can be employed in this scenario. Furthermore, we derive a scaling law between the gap to capacity, the cardinality of the input and output alphabets, and the required size of the mapper. The second one is an integrated scheme in which the code is used both for source coding, in order to create codewords distributed according to the capacity-achieving input distribution, and for channel coding, in order to provide error protection. Such a technique has been recently introduced by Honda and Yamamoto in the context of polar codes, and we show how to apply it also to the design of sparse graph codes. The third paradigm is based on an idea of Böcherer and Mathar, and separates the two tasks of source coding and channel coding by a chaining construction that binds together several codewords. We present conditions for the source code and the channel code, and we describe how to combine any source code with any channel code that fulfill those conditions, in order to provide capacity-achieving schemes for asymmetric channels. In particular, we show that polar codes, spatially coupled codes, and homophonic codes are suitable as basic building blocks of the proposed coding strategy. Rather than focusing on the exact details of the schemes, the purpose of this tutorial is to present different coding techniques that can then be implemented with many variants. There is no absolute winner and, in order to understand the most suitable technique for a specific application scenario, we provide a detailed comparison that takes into account several performance metrics.},
author = {Mondelli, Marco and Hassani, Hamed and Urbanke, Rudiger },
issn = {0018-9448},
journal = {IEEE Transactions on Information Theory},
number = {5},
pages = {3371--3393},
publisher = {IEEE},
title = {{How to achieve the capacity of asymmetric channels}},
doi = {10.1109/tit.2018.2789885},
volume = {64},
year = {2018},
}
@article{6674,
abstract = {Polar codes represent one of the major recent breakthroughs in coding theory and, because of their attractive features, they have been selected for the incoming 5G standard. As such, a lot of attention has been devoted to the development of decoding algorithms with good error performance and efficient hardware implementation. One of the leading candidates in this regard is represented by successive-cancellation list (SCL) decoding. However, its hardware implementation requires a large amount of memory. Recently, a partitioned SCL (PSCL) decoder has been proposed to significantly reduce the memory consumption. In this paper, we consider the paradigm of PSCL decoding from a practical standpoint, and we provide several improvements. First, by changing the target signal-to-noise ratio and consequently modifying the construction of the code, we are able to improve the performance at no additional computational, latency, or memory cost. Second, we bridge the performance gap between SCL and PSCL decoding by introducing a generalized PSCL decoder and a layered PSCL decoder. In this way, we obtain almost the same performance of the SCL decoder with a significantly lower memory requirement, as testified by hardware implementation results. Third, we present an optimal scheme to allocate cyclic redundancy checks. Finally, we provide a lower bound on the list size that guarantees optimal maximum a posteriori performance for the binary erasure channel.},
author = {Hashemi, Seyyed Ali and Mondelli, Marco and Hassani, S. Hamed and Condo, Carlo and Urbanke, Rudiger L. and Gross, Warren J.},
issn = {1558-0857},
journal = {IEEE Transactions on Communications},
number = {9},
pages = {3749--3759},
publisher = {IEEE},
title = {{Decoder partitioning: Towards practical list decoding of polar codes}},
doi = {10.1109/tcomm.2018.2832207},
volume = {66},
year = {2018},
}
@inproceedings{6675,
abstract = {We present a coding paradigm that provides a new achievable rate for the primitive relay channel by combining compress-and-forward and decode-and-forward with a chaining construction. In the primitive relay channel model, the source broadcasts a message to the relay and to the destination; and the relay facilitates this communication by sending an additional message to the destination through a separate channel. Two well-known coding approaches for this setting are decode-and-forward and compress-and-forward: in the former, the relay decodes the message and sends some of the information to the destination; in the latter, the relay does not attempt to decode, but it sends a compressed description of the received sequence to the destination via Wyner-Ziv coding. In our scheme, we transmit over pairs of blocks and we use compress-and-forward for the first block and decode-and-forward for the second. In particular, in the first block, the relay does not attempt to decode and it sends only a part of the compressed description of the received sequence; in the second block, the relay decodes the message and sends this information plus the remaining part of the compressed sequence relative to the first block. As a result, we strictly outperform both compress-and- forward and decode-and-forward. Furthermore, this paradigm can be implemented with a low-complexity polar coding scheme that has the typical attractive features of polar codes, i.e., quasi-linear encoding/decoding complexity and super-polynomial decay of the error probability. Throughout the paper we consider as a running example the special case of the erasure relay channel and we compare the rates achievable by our proposed scheme with the existing upper and lower bounds.},
author = {Mondelli, Marco and Hassani, Hamed and Urbanke, Rudiger},
booktitle = {2018 IEEE International Symposium on Information Theory},
issn = {2157-8117},
location = {Vail, CO, United States},
pages = {351--355},
publisher = {IEEE},
title = {{A new coding paradigm for the primitive relay channel}},
doi = {10.1109/isit.2018.8437479},
year = {2018},
}
@inproceedings{6664,
abstract = {Reed-Muller (RM) and polar codes are a class of capacity-achieving channel coding schemes with the same factor graph representation. Low-complexity decoding algorithms fall short in providing a good error-correction performance for RM and polar codes. Using the symmetric group of RM and polar codes, the specific decoding algorithm can be carried out on multiple permutations of the factor graph to boost the error-correction performance. However, this approach results in high decoding complexity. In this paper, we first derive the total number of factor graph permutations on which the decoding can be performed. We further propose a successive permutation (SP) scheme which finds the permutations on the fly, thus the decoding always progresses on a single factor graph permutation. We show that SP can be used to improve the error-correction performance of RM and polar codes under successive-cancellation (SC) and SC list (SCL) decoding, while keeping the memory requirements of the decoders unaltered. Our results for RM and polar codes of length 128 and rate 0.5 show that when SP is used and at a target frame error rate of 10 -4 , up to 0.5 dB and 0.1 dB improvement can be achieved for RM and polar codes respectively.},
author = {Hashemi, Seyyed Ali and Doan, Nghia and Mondelli, Marco and Gross, Warren },
booktitle = {2018 IEEE 10th International Symposium on Turbo Codes & Iterative Information Processing},
location = {Hong Kong, China},
pages = {1--5},
publisher = {IEEE},
title = {{Decoding Reed-Muller and polar codes by successive factor graph permutations}},
doi = {10.1109/istc.2018.8625281},
year = {2018},
}
@inproceedings{6665,
abstract = {We prove that, at least for the binary erasure channel, the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but, in fact, do so under the best possible scaling of their block length as a function of the gap to capacity. This result exhibits the first known family of binary codes that attain both optimal scaling and quasi-linear complexity of encoding and decoding. Specifically, for any fixed δ > 0, we exhibit binary linear codes that ensure reliable communication at rates within ε > 0 of capacity with block length n = O(1/ε 2+δ ), construction complexity Θ(n), and encoding/decoding complexity Θ(n log n).},
author = {Fazeli, Arman and Hassani, Hamed and Mondelli, Marco and Vardy, Alexander},
booktitle = {2018 IEEE Information Theory Workshop},
location = {Guangzhou, China},
pages = {1--5},
publisher = {IEEE},
title = {{Binary linear codes with optimal scaling: Polar codes with large kernels}},
doi = {10.1109/itw.2018.8613428},
year = {2018},
}
@inproceedings{6728,
abstract = {Polar codes are a channel coding scheme for the next generation of wireless communications standard (5G). The belief propagation (BP) decoder allows for parallel decoding of polar codes, making it suitable for high throughput applications. However, the error-correction performance of polar codes under BP decoding is far from the requirements of 5G. It has been shown that the error-correction performance of BP can be improved if the decoding is performed on multiple permuted factor graphs of polar codes. However, a different BP decoding scheduling is required for each factor graph permutation which results in the design of a different decoder for each permutation. Moreover, the selection of the different factor graph permutations is at random, which prevents the decoder to achieve a desirable error correction performance with a small number of permutations. In this paper, we first show that the permutations on the factor graph can be mapped into suitable permutations on the codeword positions. As a result, we can make use of a single decoder for all the permutations. In addition, we introduce a method to construct a set of predetermined permutations which can provide the correct codeword if the decoding fails on the original permutation. We show that for the 5G polar code of length 1024, the error-correction performance of the proposed decoder is more than 0.25 dB better than that of the BP decoder with the same number of random permutations at the frame error rate of 10 -4 .},
author = {Doan, Nghia and Hashemi, Seyyed Ali and Mondelli, Marco and Gross, Warren J.},
booktitle = {2018 IEEE Global Communications Conference },
isbn = {9781538647271},
location = {Abu Dhabi, United Arab Emirates},
publisher = {IEEE},
title = {{On the decoding of polar codes on permuted factor graphs}},
doi = {10.1109/glocom.2018.8647308},
year = {2018},
}
@unpublished{6747,
abstract = {We establish connections between the problem of learning a two-layer neural network and tensor decomposition. We consider a model with feature vectors x∈ℝd, r hidden units with weights {wi}1≤i≤r and output y∈ℝ, i.e., y=∑ri=1σ(w𝖳ix), with activation functions given by low-degree polynomials. In particular, if σ(x)=a0+a1x+a3x3, we prove that no polynomial-time learning algorithm can outperform the trivial predictor that assigns to each example the response variable 𝔼(y), when d3/2≪r≪d2. Our conclusion holds for a `natural data distribution', namely standard Gaussian feature vectors x, and output distributed according to a two-layer neural network with random isotropic weights, and under a certain complexity-theoretic assumption on tensor decomposition. Roughly speaking, we assume that no polynomial-time algorithm can substantially outperform current methods for tensor decomposition based on the sum-of-squares hierarchy. We also prove generalizations of this statement for higher degree polynomial activations, and non-random weight vectors. Remarkably, several existing algorithms for learning two-layer networks with rigorous guarantees are based on tensor decomposition. Our results support the idea that this is indeed the core computational difficulty in learning such networks, under the stated generative model for the data. As a side result, we show that under this model learning the network requires accurate learning of its weights, a property that does not hold in a more general setting. },
author = {Mondelli, Marco and Montanari, Andrea},
booktitle = {arXiv:1802.07301},
pages = {41},
title = {{On the connection between learning two-layers neural networks and tensor decomposition}},
year = {2018},
}
@inproceedings{6729,
abstract = {Consider the problem of constructing a polar code of block length N for the transmission over a given channel W. Typically this requires to compute the reliability of all the N synthetic channels and then to include those that are sufficiently reliable. However, we know from [1], [2] that there is a partial order among the synthetic channels. Hence, it is natural to ask whether we can exploit it to reduce the computational burden of the construction problem. We show that, if we take advantage of the partial order [1], [2], we can construct a polar code by computing the reliability of roughly N/ log 3/2 N synthetic channels. Such a set of synthetic channels is universal, in the sense that it allows one to construct polar codes for any W, and it can be identified by solving a maximum matching problem on a bipartite graph. Our proof technique consists in reducing the construction problem to the problem of computing the maximum cardinality of an antichain for a suitable partially ordered set. As such, this method is general and it can be used to further improve the complexity of the construction problem in case a new partial order on the synthetic channels of polar codes is discovered.},
author = {Mondelli, Marco and Hassani, S. Hamed and Urbanke, Rudiger},
booktitle = {2017 IEEE International Symposium on Information Theory },
isbn = {9781509040964},
issn = {2157-8117},
location = {Aachen, Germany},
pages = {1853--1857},
publisher = {IEEE},
title = {{Construction of polar codes with sublinear complexity}},
doi = {10.1109/isit.2017.8006850},
year = {2017},
}
@inproceedings{6731,
abstract = {We present a rate-compatible polar coding scheme that achieves the capacity of any family of channels. Our solution generalizes the previous results [1], [2] that provide capacity-achieving rate-compatible polar codes for a degraded family of channels. The motivation for our extension comes from the fact that in many practical scenarios, e.g., MIMO systems and non-Gaussian interference, the channels cannot be ordered by degradation. The main technical contribution of this paper consists in removing the degradation condition. To do so, we exploit the ideas coming from the construction of universal polar codes. Our scheme possesses the usual attractive features of polar codes: low complexity code construction, encoding, and decoding; super-polynomial scaling of the error probability with the block length; and absence of error floors. On the negative side, the scaling of the gap to capacity with the block length is slower than in standard polar codes, and we prove an upper bound on the scaling exponent.},
author = {Mondelli, Marco and Hassani, Hamed and Maric, Ivana and Hui, Dennis and Hong, Song-Nam},
booktitle = {2017 IEEE Wireless Communications and Networking Conference Workshops },
isbn = {9781509059089},
location = {San Francisco, CA, USA},
publisher = {IEEE},
title = {{Capacity-achieving rate-compatible polar codes for general channels}},
doi = {10.1109/wcncw.2017.7919107},
year = {2017},
}
@inproceedings{6679,
abstract = {Polar codes represent one of the major recent breakthroughs in coding theory and, because of their attractive features, they have been selected for the incoming 5G standard. As such, a lot of attention has been devoted to the development of decoding algorithms with good error performance and efficient hardware implementation. One of the leading candidates in this regard is represented by successive-cancellation list (SCL) decoding. However, its hardware implementation requires a large amount of memory. Recently, a partitioned SCL (PSCL) decoder has been proposed to significantly reduce the memory consumption [1]. In this paper, we examine the paradigm of PSCL decoding from both theoretical and practical standpoints: (i) by changing the construction of the code, we are able to improve the performance at no additional computational, latency or memory cost, (ii) we present an optimal scheme to allocate cyclic redundancy checks (CRCs), and (iii) we provide an upper bound on the list size that allows MAP performance.},
author = {Hashemi, Seyyed Ali and Mondelli, Marco and Hassani, Hamed and Urbanke, Ruediger and Gross, Warren},
booktitle = {2017 IEEE Global Communications Conference},
location = {Singapore, Singapore},
pages = {1--7},
publisher = {IEEE},
title = {{Partitioned list decoding of polar codes: Analysis and improvement of finite length performance}},
doi = {10.1109/glocom.2017.8254940},
year = {2017},
}
@article{6730,
abstract = {We introduce a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes, our method exploits code symmetry. In particular, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge, and the permutation group of each code is doubly transitive. In other words, we show that symmetry alone implies near-optimal performance. An important consequence of this result is that a sequence of Reed-Muller codes with increasing block length and converging rate achieves capacity. This possibility has been suggested previously in the literature but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to all affine-invariant codes and, thus, to extended primitive narrow-sense BCH codes. This also resolves, in the affirmative, the existence question for capacity-achieving sequences of binary cyclic codes. The primary tools used in the proof are the sharp threshold property for symmetric monotone Boolean functions and the area theorem for extrinsic information transfer functions.},
author = {Kudekar, Shrinivas and Kumar, Santhosh and Mondelli, Marco and Pfister, Henry D. and Sasoglu, Eren and Urbanke, Ridiger L.},
issn = {1557-9654},
journal = {IEEE Transactions on Information Theory},
number = {7},
pages = {4298--4316},
publisher = {IEEE},
title = {{Reed–Muller codes achieve capacity on erasure channels}},
doi = {10.1109/tit.2017.2673829},
volume = {63},
year = {2017},
}
@article{6732,
abstract = {Consider the transmission of a polar code of block length N and rate R over a binary memoryless symmetric channel W and let P e be the block error probability under successive cancellation decoding. In this paper, we develop new bounds that characterize the relationship of the parameters R, N, P e , and the quality of the channel W quantified by its capacity I(W) and its Bhattacharyya parameter Z(W). In previous work, two main regimes were studied. In the error exponent regime, the channel W and the rate R <; I(W) are fixed, and it was proved that the error probability Pe scales roughly as 2 -√N . In the scaling exponent approach, the channel W and the error probability Pe are fixed and it was proved that the gap to capacity I(W) - R scales as N -1/μ . Here, μ is called scaling exponent and this scaling exponent depends on the channel W. A heuristic computation for the binary erasure channel (BEC) gives μ = 3.627 and it was shown that, for any channel W, 3.579 ≤ μ ≤ 5.702. Our contributions are as follows. First, we provide the tighter upper bound μ <;≤ 4.714 valid for any W. With the same technique, we obtain the upper bound μ ≤ 3.639 for the case of the BEC; this upper bound approaches very closely the heuristically derived value for the scaling exponent of the erasure channel. Second, we develop a trade-off between the gap to capacity I(W)- R and the error probability Pe as the functions of the block length N. In other words, we neither fix the gap to capacity (error exponent regime) nor the error probability (scaling exponent regime), but we do consider a moderate deviations regime in which we study how fast both quantities, as the functions of the block length N, simultaneously go to 0. Third, we prove that polar codes are not affected by error floors. To do so, we fix a polar code of block length N and rate R. Then, we vary the channel W and study the impact of this variation on the error probability. We show that the error probability Pe scales as the Bhattacharyya parameter Z(W) raised to a power that scales roughly like VN. This agrees with the scaling in the error exponent regime.},
author = {Mondelli, Marco and Hassani, S. Hamed and Urbanke, Rudiger L.},
issn = {1557-9654},
journal = {IEEE Transactions on Information Theory},
number = {12},
pages = {6698--6712},
publisher = {IEEE},
title = {{Unified scaling of polar codes: Error exponent, scaling exponent, moderate deviations, and error floors}},
doi = {10.1109/tit.2016.2616117},
volume = {62},
year = {2016},
}
@inproceedings{6770,
abstract = {We describe a new method to compare the bit-MAP and block-MAP decoding thresholds of Reed-Muller (RM) codes for transmission over a binary memoryless symmetric channel. The question whether RM codes are capacity-achieving is a long-standing open problem in coding theory and it has recently been answered in the affirmative for transmission over
erasure channels. Remarkably, the proof does not rely on specific properties of RM codes, apart from their symmetry. Indeed, the main technical result consists in showing that any sequence of linear codes, with doubly-transitive permutation groups, achieves capacity on the memoryless erasure channel under bit-MAP decoding. A natural question is what happens under block-MAP decoding. If the minimum distance of the code family is close to linear (e.g., of order N/ log(N)), then one can combine an upper bound on the bit-MAP error probability with a lower bound on the minimum distance to show that the code family is also capacity-achieving under block-MAP decoding. This strategy is successful for BCH codes. Unfortunately, the minimum distance of RM codes scales only as √N, which does not suffice to obtain the desired result. Then, one can exploit further symmetries of RM codes to show that the bit-MAP threshold is sharp enough so that the block erasure probability also tends to 0. However, this technique relies heavily on the fact that the transmission is over an erasure channel.
We present an alternative approach to strengthen results regarding the bit-MAP threshold to block-MAP thresholds. This approach is based on a careful analysis of the weight distribution of RM codes. In particular, the flavor of the main result is the following: assume that the bit-MAP error probability decays as N−δ, for some δ > 0. Then, the block-MAP
error probability also converges to 0. This technique applies to the transmission over any binary memoryless symmetric channel. Thus, it can be thought of as a first step in extending the proof that RM codes are capacity-achieving to the general case.},
author = {Mondelli, Marco and Kudekar, Shrinivas and Kumar, Santosh and Pfister, Henry D. and Şaşoğlu, Eren and Urbanke, Rüdiger},
booktitle = {24th International Zurich Seminar on Communications},
location = {Zurich, Switzerland},
pages = {50},
publisher = {ETH Zürich},
title = {{Reed-Muller codes: Thresholds and weight distribution}},
doi = {10.3929/ETHZ-A-010646484},
year = {2016},
}
@inproceedings{6733,
abstract = {The question whether RM codes are capacity-achieving is a long-standing open problem in coding theory that was recently answered in the affirmative for transmission over erasure channels [1], [2]. Remarkably, the proof does not rely on specific properties of RM codes, apart from their symmetry. Indeed, the main technical result consists in showing that any sequence of linear codes, with doubly-transitive permutation groups, achieves capacity on the memoryless erasure channel under bit-MAP decoding. Thus, a natural question is what happens under block-MAP decoding. In [1], [2], by exploiting further symmetries of the code, the bit-MAP threshold was shown to be sharp enough so that the block erasure probability also converges to 0. However, this technique relies heavily on the fact that the transmission is over an erasure channel. We present an alternative approach to strengthen results regarding the bit-MAP threshold to block-MAP thresholds. This approach is based on a careful analysis of the weight distribution of RM codes. In particular, the flavor of the main result is the following: assume that the bit-MAP error probability decays as N -δ , for some δ > 0. Then, the block-MAP error probability also converges to 0. This technique applies to transmission over any binary memoryless symmetric channel. Thus, it can be thought of as a first step in extending the proof that RM codes are capacity-achieving to the general case.},
author = {Kudekar, Shrinivas and Kumar, Santhosh and Mondelli, Marco and Pfister, Henry D. and Urbankez, Rudiger},
booktitle = {2016 IEEE International Symposium on Information Theory },
location = {Barcelona, Spain},
pages = {1755--1759},
publisher = {IEEE},
title = {{Comparing the bit-MAP and block-MAP decoding thresholds of Reed-Muller codes on BMS channels}},
doi = {10.1109/isit.2016.7541600},
year = {2016},
}
@article{6736,
abstract = {Motivated by the significant performance gains which polar codes experience under successive cancellation list decoding, their scaling exponent is studied as a function of the list size. In particular, the error probability is fixed, and the tradeoff between the block length and back-off from capacity is analyzed. A lower bound is provided on the error probability under MAP decoding with list size L for any binary-input memoryless output-symmetric channel and for any class of linear codes such that their minimum distance is unbounded as the block length grows large. Then, it is shown that under MAP decoding, although the introduction of a list can significantly improve the involved constants, the scaling exponent itself, i.e., the speed at which capacity is approached, stays unaffected for any finite list size. In particular, this result applies to polar codes, since their minimum distance tends to infinity as the block length increases. A similar result is proved for genie-aided successive cancellation decoding when transmission takes place over the binary erasure channel, namely, the scaling exponent remains constant for any fixed number of helps from the genie. Note that since genie-aided successive cancellation decoding might be strictly worse than successive cancellation list decoding, the problem of establishing the scaling exponent of the latter remains open.},
author = {Mondelli, Marco and Hassani, Hamed and Urbanke, Rudiger},
journal = {IEEE Transactions on Information Theory},
number = {9},
pages = {4838--4851},
publisher = {IEEE},
title = {{Scaling exponent of list decoders with applications to polar codes}},
doi = {10.1109/tit.2015.2453315},
volume = {61},
year = {2015},
}