We show that the entire class of polar codes (up to a natural necessary condition) converge to capacity at block lengths polynomial in the gap to capacity, while simultaneously achieving failure probabilities that are exponentially small in the block length (i.e., decoding fails with probability exp(N^{Omega(1)}) for codes of length N). Previously this combination was known only for one specific family within the class of polar codes, whereas we establish this whenever the polar code exhibits a condition necessary for any polarization. Our results adapt and strengthen a local analysis of polar codes due to the authors with Nakkiran and Rudra [Proc. STOC 2018]. Their analysis related the timelocal behavior of a martingale to its global convergence, and this allowed them to prove that the broad class of polar codes converge to capacity at polynomial block lengths. Their analysis easily adapts to show exponentially small failure probabilities, provided the associated martingale, the "Arikan martingale", exhibits a corresponding strong local effect. The main contribution of this work is a much stronger local analysis of the Arikan martingale. This leads to the general result claimed above. In addition to our general result, we also show, for the first time, polar codes thatmore »
General strong polarization
Arikan's exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constantsized) invertible matrix M, a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the polarization of an associated [0,1]bounded martingale, namely its convergence in the limit to either 0 or 1 with probability 1. Arikan showed appropriate polarization of the martingale associated with the matrix G2=(1011) to get capacity achieving codes. His analysis was later extended to all matrices M which satisfy an obvious necessary condition for polarization.
While Arikan's theorem does not guarantee that the codes achieve capacity at small blocklengths, it turns out that a "strong" analysis of the polarization of the underlying martingale would lead to such constructions. Indeed for the martingale associated with G2 such a strong polarization was shown in two independent works ([Guruswami and Xia, IEEE IT '15] and [Hassani et al., IEEE IT '14]), thereby resolving a major theoretical challenge associated with the efficient attainment of Shannon capacity.
In this work we extend the result above to cover martingales associated with all matrices that satisfy the necessary condition for (weak) polarization. In addition to being vastly more »
 Publication Date:
 NSFPAR ID:
 10062094
 Journal Name:
 Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing,
 Page Range or eLocationID:
 485 to 492
 Sponsoring Org:
 National Science Foundation
More Like this


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.

Generative neural networks have been empirically found very promising in providing effective structural priors for compressed sensing, since they can be trained to span lowdimensional data manifolds in highdimensional signal spaces. Despite the nonconvexity of the resulting optimization problem, it has also been shown theoretically that, for neural networks with random Gaussian weights, a signal in the range of the network can be efficiently, approximately recovered from a few noisy measurements. However, a major bottleneck of these theoretical guarantees is a network expansivity condition: that each layer of the neural network must be larger than the previous by a logarithmic factor. Our main contribution is to break this strong expansivity assumption, showing that constant expansivity suffices to get efficient recovery algorithms, besides it also being informationtheoretically necessary. To overcome the theoretical bottleneck in existing approaches we prove a novel uniform concentration theorem for random functions that might not be Lipschitz but satisfy a relaxed notion which we call "pseudoLipschitzness." Using this theorem we can show that a matrix concentration inequality known as the Weight Distribution Condition (WDC), which was previously only known to hold for Gaussian matrices with logarithmic aspect ratio, in fact holds for constant aspect ratios too. Sincemore »

Conventional lithiumion batteries are unable to meet the increasing demands for highenergy storage systems, because of their limited theoretical capacity. 1 In recent years, intensive attention has been paid to enhancing battery energy storage capability to satisfy the increasing energy demand in modern society and reduce the average energy capacity cost. Among the candidates for next generation high energy storage systems, the lithium sulfur battery is especially attractive because of its high theoretical specific energy (around 2600 W h kg1) and potential cost reduction. In addition, sulfur is a cost effective and environmentally friendly material due to its abundance and lowtoxicity. 2 Despite all of these advantages, the practical application of lithium sulfur batteries to date has been hindered by a series of obstacles, including low active material loading, poor cycle life, and sluggish sulfur conversion kinetics. 3 Achieving high mass loading cathode in the traditional 2D planar thick electrode has been challenged. The high distorsion of the traditional planar thick electrodes for ion/electron transfer leads to the limited utilization of active materials and high resistance, which eventually results in restricted energy density and accelerated electrode failure. 4 Furthermore, of the electrolyte to pores in the cathode and utilization ratiomore »

With the rapid growth of Internet of Things (IoT) applications in recent years, there is a strong need for wireless uplink scheduling algorithms that determine when and which subset of a large number of users should transmit to the central controller. Different from the downlink case, the central controller in the uplink scenario typically has very limited information about the users. On the other hand, collecting all such information from a large number of users typically incurs a prohibitively high communication overhead. This motivates us to investigate the development of an efficient and lowoverhead uplink scheduling algorithm that is suitable for largescale IoT applications with limited amount of coordination from the central controller. Specifically, we first characterize a capacity outer bound subject to the sampling constraint where only a small subset of users are allowed to use control channels for system state reporting and wireless channel probing. Next, we relax the sampling constraint and propose a joint sampling and transmission algorithm, which utilizes full knowledge of channel state distributions and instantaneous queue lengths to achieve the capacity outer bound. The insights obtained from this capacityachieving algorithm allow us to develop an efficient and lowoverhead scheduling algorithm that can strictly satisfymore »