Define the codewords of the Tensor Reed-Muller code $\mathsf{TRM}(r_1,m_1;r_2,m_2;\dots;r_t,m_t)$ to be the evaluation vectors of all multivariate polynomials in the variables $\left\{x_{ij}\right\}_{i=1,\dots,t}^{j=1,\dots m_i}$ with degree at most $r_i$ in the variables $x_{i1},x_{i2},\dots,x_{im_i}$. The generator matrix of $\mathsf{TRM}(r_1,m_1;\dots;r_t,m_t)$ is thus the tensor product of the generator matrices of the Reed-Muller codes $\mathsf{RM}(r_1,m_1),\dots, \mathsf{RM}(r_t,m_t)$. We show that for any constant rate $R$ below capacity, one can construct a Tensor Reed-Muller code $\mathsf{TRM}(r_1,m_1;\dotsc;r_t,m_t)$ of rate $R$ that is decodable in quasilinear time. For any blocklength $n$, we provide two constructions of such codes: 1) Our first construction (with $t=3$) has error probability $n^{-ω(\log n)}$ and decoding time $O(n\log\log n)$. 2) Our second construction, for any $t\geq 4$, has error probability $2^{-n^{\frac{1}{2}-\frac{1}{2(t-2)}-o(1)}}$ and decoding time $O(n\log n)$. One of our main tools is a polynomial-time algorithm for decoding an arbitrary tensor code $C=C_1\otimes\dotsc\otimes C_t$ from $\frac{d_{\min}(C)}{2\max\{d_{\min}(C_1),\dotsc,d_{\min}(C_t) \}}-1$ adversarial errors. Crucially, this algorithm does not require the codes $C_1,\dotsc,C_t$ to themselves be decodable in polynomial time.

Abstract Improving risk stratification for coronary artery disease, the leading cause of death worldwide, continues to present a daily challenge in clinical practice, highlighting the urgent need for innovative approaches to early prediction of future cardiovascular events. In this work, we propose AngioGraphCAD, a deep learning based framework that employs graph neural networks to leverage geometry features and a masked attention to fuse geometry features from multiple coronary stenoses for future events prediction at both lesion and patient level from invasive coronary angiography. AngioGraphCAD is evaluated across two clinical cohorts at the lesion level and one datatset at the patient level, achieving superior performance compared to clinical measures. This is the first study that highlights the importance of geometry information in advancing future events prediction from invasive coronary angiography. Given the significance of the clinical question and the innovative nature of the proposed methodology, this work could pave the way for the development of an AI framework fueled by patient-specific data in cardiology, potentially revolutionizing personalized decision-making in managing coronary artery diseases for individual patients.

Parities have become a standard benchmark for evaluating learning algorithms. Recent works show that regular neural networks trained by gradient descent can efficiently learn degree $k$ parities on uniform inputs for constant $k$, but fail to do so when $k$ and $d-k$ grow with $d$ (here $d$ is the ambient dimension). However, the case where $k=d-O_d(1)$, including the degree $d$ parity (the full parity), has remained unsettled. This paper shows that for gradient descent on regular neural networks, learnability depends on the initial weight distribution. On one hand, the discrete Rademacher initialization enables efficient learning of almost-full parities, while on the other hand, its Gaussian perturbation with large enough constant standard deviation $\sigma$ prevents it. The positive result for almost-full parities is shown to hold up to $\sigma=O(d^{-1})$, pointing to questions about a sharper threshold phenomenon. Unlike statistical query (SQ) learning, where a singleton function class like the full parity is trivially learnable, our negative result applies to a fixed function and relies on an initial gradient alignment}measure of potential broader relevance to neural networks learning.

Reed-Muller (RM) codes have undergone significant analytical advancements over the past decade, particularly for binary memoryless symmetric (BMS) channels. We extend the scope of RM codes development and analysis to multiple-access channels (MACs) and quantum Pauli channels, leveraging a unified approach. Specifically, we first derive the achievable rate region for RM codes on so-called Q-MACs, a class of MACs with additive correlated noise. This is achieved via a generalization of the bending and boosting arguments defined in [1]. We then put forward a connection between the rate region of these QMACs and quantum RM codes designed for Pauli noise channels. This connection highlights a universality property of quantum RM codes, demonstrating their rate-optimal performance across a range of channel parameters, rather than for a single Pauli channel.

Simulation-based inference (SBI) of latent parameters in physical systems is often hindered by model misspecification--the mismatch between simulated and real-world observations caused by inherent modeling simplifications. RoPE, a recent SBI approach, addresses this challenge through a two-stage domain transfer process that combines semi-supervised calibration with optimal transport (OT)-based distribution alignment. However, RoPE operates in a fully transductive setting, requiring access to a batch of test samples at inference time, which limits scalability and generalization. We propose a fully inductive and amortized SBI framework that integrates calibration and distributional alignment into a single, end-to-end trainable model. Our method leverages mini-batch OT with a closed-form coupling to align real and simulated observations that correspond to the same latent parameters, using both paired calibration data and unpaired samples. A conditional normalizing flow is then trained to approximate the OT-induced posterior, enabling efficient inference without simulation access at test time. Across a range of synthetic and real-world benchmarks--including complex medical biomarker estimation--our approach matches or exceeds the performance of RoPE, while offering improved scalability and applicability in challenging, misspecified environments.

We investigate the capabilities of transformer models on relational reasoning tasks. In these tasks, models are trained on a set of strings encoding abstract relations, and are then tested out-of-distribution on data that contains symbols that did not appear in the training dataset. We prove that for any relational reasoning task in a large family of tasks, transformers learn the abstract relations and generalize to the test set when trained by gradient descent on sufficiently large quantities of training data. This is in contrast to classical fully-connected networks, which we prove fail to learn to reason. Our results inspire modifications of the transformer architecture that add only two trainable parameters per head, and that we empirically demonstrate improve data efficiency for learning to reason.

We investigate the out-of-domain generalization of random feature (RF) models and Transformers. We first prove that in the ‘generalization on the unseen (GOTU)’ setting, where training data is fully seen in some part of the domain but testing is made on another part, and for RF models in the small feature regime, the convergence takes place to interpolators of minimal degree as in the Boolean case (Abbe et al., 2023). We then consider the sparse target regime and explain how this regime relates to the small feature regime, but with a different regularization term that can alter the picture in the non-Boolean case. We show two different outcomes for the sparse regime with q-ary data tokens: (1) if the data is embedded with roots of unities, then a min-degree interpolator is learned like in the Boolean case for RF models, (2) if the data is not embedded as such, e.g., simply as integers, then RF models and Transformers may not learn minimal degree interpolators. This shows that the Boolean setting and its roots of unities generalization are special cases where the minimal degree interpolator offers a rare characterization of how learning takes place. For more general integer and real-valued settings, a more nuanced picture remains to be fully characterized.

Can Transformers predict new syllogisms by composing established ones? More generally, what type of targets can be learned by such models from scratch? Recent works show that Transformers can be Turing-complete in terms of expressivity, but this does not address the learnability objective. This paper puts forward the notion of 'globality degree' of a target distribution to capture when weak learning is efficiently achievable by regular Transformers. This measure shows a contrast with the expressivity results of Transformers captured by $TC^0/TC^1$ classes (further studied here), since the globality relates to correlations with the more limited $NC^0$ class. We show here experimentally and theoretically under additional assumptions that distributions with high globality cannot be learned efficiently. In particular, syllogisms cannot be composed on long chains. Further, we develop scratchpad techniques and show that: (i) agnostic scratchpads cannot break the globality barrier, (ii) educated scratchpads can break the globality with intermediate steps, although not all such scratchpads can generalize out-of-distribution (OOD), (iii) a notion of 'inductive scratchpad', that composes the prior information more efficiently, can both break the globality barrier and improve the OOD generalization. In particular, some of our inductive scratchpads can achieve length generalizations of up to $6\times$ for some arithmetic tasks depending on the input formatting.

Learning with identical train and test distributions has been extensively investigated both practically and theoretically. Much remains to be understood, however, in statistical learning under distribution shifts. This paper focuses on a distribution shift setting where train and test distributions can be related by classes of (data) transformation maps. We initiate a theoretical study for this framework, investigating learning scenarios where the target class of transformations is either known or unknown. We establish learning rules and algorithmic reductions to Empirical Risk Minimization (ERM), accompanied with learning guarantees. We obtain upper bounds on the sample complexity in terms of the VC dimension of the class composing predictors with transformations, which we show in many cases is not much larger than the VC dimension of the class of predictors. We highlight that the learning rules we derive offer a game-theoretic viewpoint on distribution shift: a learner searching for predictors and an adversary searching for transformation maps to respectively minimize and maximize the worst-case loss.

This paper considers the learning of logical (Boolean) functions with a focus on the generalization on the unseen (GOTU) setting, a strong case of out-of-distribution generalization. This is motivated by the fact that the rich combinatorial nature of data in certain reasoning tasks (e.g., arithmetic/logic) makes representative data sampling challenging, and learning successfully under GOTU gives a first vignette of an 'extrapolating' or 'reasoning' learner. We study how different network architectures trained by (S)GD perform under GOTU and provide both theoretical and experimental evidence that for sparse functions and a class of network models including instances of Transformers, random features models, and linear networks, a min-degree-interpolator is learned on the unseen. More specifically, this means an interpolator of the training data that has minimal Fourier mass on the higher degree basis elements. These findings lead to two implications: (1) we provide an explanation to the length generalization problem for Boolean functions (e.g., Anil et al. 2022); (2) we introduce a curriculum learning algorithm called Degree-Curriculum that learns monomials more efficiently by incrementing supports. Finally, we discuss extensions to other models or non-sparse regimes where the min-degree bias may still occur or fade, as well as how it can be potentially corrected when undesirable.

We investigate the time complexity of SGD learning on fully-connected neural networks with isotropic data. We put forward a complexity measure,{\it the leap}, which measures how “hierarchical” target functions are. For $d$-dimensional uniform Boolean or isotropic Gaussian data, our main conjecture states that the time complexity to learn a function $f$ with low-dimensional support is $$\Tilde \Theta (d^{\max(\mathrm{Leap}(f),2)}) \,\,.$$ We prove a version of this conjecture for a class of functions on Gaussian isotropic data and 2-layer neural networks, under additional technical assumptions on how SGD is run. We show that the training sequentially learns the function support with a saddle-to-saddle dynamic. Our result departs from Abbe et al.’22 by going beyond leap 1 (merged-staircase functions), and by going beyond the mean-field and gradient flow approximations that prohibit the full complexity control obtained here.Finally, we note that this gives an SGD complexity for the full training trajectory that matches that of Correlational Statistical Query (CSQ) lower-bounds.

In 1948, Shannon used a probabilistic argument to show that there exist codes achieving a maximal rate defined by the channel capacity. In 1954, Muller and Reed introduced a simple deterministic code construction, conjectured shortly after to achieve channel capacity. Major progress was made towards establishing this conjecture over the last decades, with various branches of discrete mathematics involved such as combinatorial bounds, sharp thresholds, hypercontractivity, additive combinatorics and polarization theory. In particular, the special case of the erasure channel was settled by Kudekar at al., relying on Bourgain-Kalai’s sharp threshold theorem for symmetric monotone properties. The main case of error channels remained however unsettled, due in particular to the property being non-monotone and the lack of techniques to obtain fast local error decay up to capacity, despite the notable vanishing bound on the local error from Reeves-Pfister. This paper closes the conjecture’s proof. The main ingredient is a new recursive boosting framework for coding, where codewords are decoded by aggregating restrictions on a ‘subspace-sunflower’ structure, analogous to the structure from Erdős-Rado 1960. The dependencies between the sunflower petals are handled with an $L_{2}$ and $L_{4}$ Boolean Fourier analysis, and a list-decoding argument with a weight enumerator bound from Sberlo-Shpilka is used to control the global error from the local one. For the local error, while monotonicity does not apply, we show that a ‘weak threshold’ result still holds using solely symmetries. This gives in particular a shortened and tightened argument for the vanishing local error result, and with prior works, it also implies the strong wire-tap secrecy of RM codes on pure-state classical-quantum channels.

This paper considers the learning of logical (Boolean) functions with focus on the generalization on the unseen (GOTU) setting, a strong case of out-of-distribution generalization. This is motivated by the fact that the rich combinatorial nature of data in certain reasoning tasks (e.g., arithmetic/logic) makes representative data sampling challenging, and learning successfully under GOTU gives a first vignette of an ’extrapolating’ or ’reasoning’ learner. We then study how different network architectures trained by (S)GD perform under GOTU and provide both theoretical and experimental evidence that for a class of network models including instances of Transformers, random features models, and diagonal linear networks, a min-degree-interpolator is learned on the unseen. We also provide evidence that other instances with larger learning rates or mean-field networks reach leaky min-degree solutions. These findings lead to two implications: (1) we provide an explanation to the length generalization problem (e.g., Anil et al. 2022); (2) we introduce a curriculum learning algorithm called Degree-Curriculum that learns monomials more efficiently by incrementing supports.

We identify incremental learning dynamics in transformers, where the difference between trained and initial weights progressively increases in rank. We rigorously prove this occurs under the simplifying assumptions of diagonal weight matrices and small initialization. Our experiments support the theory and also show that phenomenon can occur in practice without the simplifying assumptions.

Experimental results have shown that curriculum learning, i.e., presenting simpler examples before more complex ones, can improve the efficiency of learning. Some recent theoretical results also showed that changing the sampling distribution can help neural networks learn parities, with formal results only for large learning rates and one-step arguments. Here we show a separation result in the number of training steps with standard (bounded) learning rates on a common sample distribution: if the data distribution is a mixture of sparse and dense inputs, there exists a regime in which a 2-layer ReLU neural network trained by a curriculum noisy-GD (or SGD) algorithm that uses sparse examples first, can learn parities of sufficiently large degree, while any fully connected neural network of possibly larger width or depth trained by noisy-GD on the unordered samples cannot learn without additional steps. We also provide experimental results supporting the qualitative separation beyond the specific regime of the theoretical results.

It is currently known how to characterize functions that neural networks can learn with SGD for two extremal parametrizations: neural networks in the linear regime, and neural networks with no structural constraints. However, for the main parametrization of interest —non-linear but regular networks— no tight characterization has yet been achieved, despite significant developments. We take a step in this direction by considering depth-2 neural networks trained by SGD in the mean-field regime. We consider functions on binary inputs that depend on a latent low-dimensional subspace (i.e., small number of coordinates). This regime is of interest since it is poorly understood how neural networks routinely tackle high-dimensional datasets and adapt to latent low-dimensional structure without suffering from the curse of dimensionality. Accordingly, we study SGD-learnability with $O(d)$ sample complexity in a large ambient dimension $d$. Our main results characterize a hierarchical property —the merged-staircase property— that is both \emph{necessary and nearly sufficient} for learning in this setting. We further show that non-linear training is necessary: for this class of functions, linear methods on any feature map (e.g., the NTK) are not capable of learning efficiently. The key tools are a new “dimension-free” dynamics approximation result that applies to functions defined on a latent space of low-dimension, a proof of global convergence based on polynomial identity testing, and an improvement of lower bounds against linear methods for non-almost orthogonal functions.

This paper introduces the notion of “Initial Alignment” (INAL) between a neural network at initialization and a target function. It is proved that if a network and a Boolean target function do not have a noticeable INAL, then noisy gradient descent with normalized i.i.d. initialization will not learn in polynomial time. Thus a certain amount of knowledge about the target (measured by the INAL) is needed in the architecture design. This also provides an answer to an open problem posed in (AS-NeurIPS’20). The results are based on deriving lower-bounds for descent algorithms on symmetric neural networks without explicit knowledge of the target function beyond its INAL.

We prove limitations on what neural networks trained by noisy gradient descent (GD) can efficiently learn. Our results apply whenever GD training is equivariant, which holds for many standard architectures and initializations. As applications, (i) we characterize the functions that fully-connected networks can weak-learn on the binary hypercube and unit sphere, demonstrating that depth-2 is as powerful as any other depth for this task; (ii) we extend the merged-staircase necessity result for learning with latent low-dimensional structure [ABM22] to beyond the mean-field regime. Under cryptographic assumptions, we also show hardness results for learning with fully-connected networks trained by stochastic gradient descent (SGD).

This paper considers the Pointer Value Retrieval (PVR) benchmark introduced in [ZRKB21], where a `reasoning' function acts on a string of digits to produce the label. More generally, the paper considers the learning of logical functions with gradient descent (GD) on neural networks. It is first shown that in order to learn logical functions with gradient descent on symmetric neural networks, the generalization error can be lower-bounded in terms of the noise-stability of the target function, supporting a conjecture made in [ZRKB21]. It is then shown that in the distribution shift setting, when the data withholding corresponds to freezing a single feature (referred to as canonical holdout), the generalization error of gradient descent admits a tight characterization in terms of the Boolean influence for several relevant architectures. This is shown on linear models and supported experimentally on other models such as MLPs and Transformers. In particular, this puts forward the hypothesis that for such architectures and for learning logical functions such as PVR functions, GD tends to have an implicit bias towards low-degree representations, which in turn gives the Boolean influence for the generalization error under quadratic loss.

It was recently shown that almost all solutions in the symmetric binary perceptron are isolated, even at low constraint densities, suggesting that finding typical solutions is hard. In contrast, some algorithms have been shown empirically to succeed in finding solutions at low density. This phenomenon has been justified numerically by the existence of subdominant and dense connected regions of solutions, which are accessible by simple learning algorithms. In this paper, we establish formally such a phenomenon for both the symmetric and asymmetric binary perceptrons. We show that at low constraint density (equivalently for overparametrized perceptrons), there exists indeed a subdominant connected cluster of solutions with almost maximal diameter, and that an efficient multiscale majority algorithm can find solutions in such a cluster with high probability, settling in particular an open problem posed by Perkins-Xu in STOC'21. In addition, even close to the critical threshold, we show that there exist clusters of linear diameter for the symmetric perceptron, as well as for the asymmetric perceptron under additional assumptions.

The limit of the entropy in the stochastic block model (SBM) has been characterized in the sparse regime for the special case of disassortative communities [Coja-Oghlan et al. (2017)] and for the classical case of assortative communities but in the dense regime [Deshpande et al. (2016)]. The problem has not been closed in the classical sparse and assortative case. This paper establishes the result in this case for any SNR besides for the interval (1, 3.513). It further gives an approximation to the limit in this window. The result is obtained by expressing the global SBM entropy as an integral of local tree entropies in a broadcasting on tree model with erasure side-information. The main technical advancement then relies on showing the irrelevance of the boundary in such a model, also studied with variants in [Kanade et al. (2016)], [Mossel et al. (2016)] and [Mossel and Xu (2015)]. In particular, we establish the uniqueness of the BP fixed point in the survey model for any SNR above 3.513 or below 1. This only leaves a narrow region in the plane between SNR and survey strength where the uniqueness of BP conjectured in these papers remains unproved.

We consider the symmetric binary perceptron model, a simple model of neural networks that has gathered significant attention in the statistical physics, information theory and probability theory communities, with recent connections made to the performance of learning algorithms in Baldassi et al. '15. We establish that the partition function of this model, normalized by its expected value, converges to a log-normal distribution. As a consequence, this allows us to establish several conjectures for this model: (i) it proves the contiguity conjecture of Aubin et al. '19 between the planted and unplanted models in the satisfiable regime; (ii) it establishes the sharp threshold conjecture; (iii) it proves the frozen 1-RSB conjecture in the symmetric case, conjectured first by Krauth-Mézard '89 in the asymmetric case. In a recent work of Perkins-Xu '21, the last two conjectures were also established by proving that the partition function concentrates on an exponential scale, under an analytical assumption on a real-valued function. This left open the contiguity conjecture and the lognor-mal limit characterization, which are established here unconditionally, with the analytical assumption verified. In particular, our proof technique relies on a dense counter-part of the small graph conditioning method, which was developed for sparse models in the celebrated work of Robinson and Wormald.

We study the relative power of learning with gradient descent on differentiable models, such as neural networks, versus using the corresponding tangent kernels. We show that under certain conditions, gradient descent achieves small error only if a related tangent kernel method achieves a non-trivial advantage over random guessing (a.k.a. weak learning), though this advantage might be very small even when gradient descent can achieve arbitrarily high accuracy. Complementing this, we show that without these conditions, gradient descent can in fact learn with small error even when no kernel method, in particular using the tangent kernel, can achieve a non-trivial advantage over random guessing.

This paper identifies a structural property of data distributions that enables deep neural networks to learn hierarchically. We define the ``staircase'' property for functions over the Boolean hypercube, which posits that high-order Fourier coefficients are reachable from lower-order Fourier coefficients along increasing chains. We prove that functions satisfying this property can be learned in polynomial time using layerwise stochastic coordinate descent on regular neural networks -- a class of network architectures and initializations that have homogeneity properties. Our analysis shows that for such staircase functions and neural networks, the gradient-based algorithm learns high-level features by greedily combining lower-level features along the depth of the network. We further back our theoretical results with experiments showing that staircase functions are learnable by more standard ResNet architectures with stochastic gradient descent. Both the theoretical and experimental results support the fact that the staircase property has a role to play in understanding the capabilities of gradient-based learning on regular networks, in contrast to general polynomial-size networks that can emulate any Statistical Query or PAC algorithm, as recently shown.

We study the power of learning via mini-batch stochastic gradient descent (SGD) on the loss of a differentiable model or neural network, and ask what learning problems can be learnt using this paradigm. We show that SGD can always simulate learning with statistical queries (SQ), but its ability to go beyond that depends on the precision $\rho$ of the gradients and the minibatch size $b$. With fine enough precision relative to minibatch size, namely when $b \rho$ is small enough, SGD can go beyond SQ learning and simulate any sample-based learning algorithm and thus its learning power is equivalent to that of PAC learning; this extends prior work that achieved this result for $b=1$. Moreover, with polynomially many bits of precision (i.e. when $\rho$ is exponentially small), SGD can simulate PAC learning regardless of the batch size. On the other hand, when $b \rho^2$ is large enough, the power of SGD is equivalent to that of SQ learning.

This paper considers “$\delta $-almost Reed–Muller codes”, i.e., linear codes spanned by evaluations of all but a$\delta $fraction of monomials of degree at most$d$. It is shown that for any$\delta > 0$and any$\varepsilon >0$, there exists a family of$\delta $-almost Reed–Muller codes of constant rate that correct$1/2- \varepsilon $fraction of random errors with high probability. For exact Reed–Muller codes, the analogous result is not known and represents a weaker version of the longstanding conjecture that Reed–Muller codes achieve capacity for random errors (Abbe-Shpilka-Wigderson STOC ’15). Our proof is based on the recent polarization result for Reed–Muller codes, combined with a combinatorial approach to establishing inequalities between the Reed–Muller code entropies.

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.

This paper introduces a model for opinion dynamics, where at each time step, randomly selected agents see their opinions - modeled as scalars in [0,1] - evolve depending on a local interaction function. In the classical Bounded Confidence Model, agents opinions get attracted when they are close enough. The proposed model extends this by adding a repulsion component, which models the effect of opinions getting further pushed away when dissimilar enough. With this repulsion component added, and under a repulsion-attraction cleavage assumption, it is shown that a new stable configuration emerges beyond the classical consensus configuration, namely the polarization configuration. More specifically, it is shown that total consensus and total polarization are the only two possible limiting configurations. The paper further provides an analysis of the infinite population regime in dimension 1 and higher, with a phase transition phenomenon conjectured and backed heuristically.

This paper shows that deep learning, i.e., neural networks trained by SGD, can learn in polytime any function class that can be learned in polytime by some algorithm, including parities. This universal result is further shown to be robust, i.e., it holds under possibly poly-noise on the gradients, which gives a separation between deep learning and statistical query algorithms, as the latter are not comparably universal due to cases like parities. This also shows that SGD-based deep learning does not suffer from the limitations of the perceptron discussed by Minsky-Papert '69. The paper further complement this result with a lower-bound on the generalization error of descent algorithms, which implies in particular that the robust universality breaks down if the gradients are averaged over large enough batches of samples as in full-GD, rather than fewer samples as in SGD.

This paper develops deterministic upper and lower bounds on the influence measure in a network, more precisely, the expected number of nodes that a seed set can influence in the independent cascade model. In particular, our bounds exploit r-nonbacktracking walks and Fortuin-Kasteleyn-Ginibre (FKG) type inequalities, and are computed by message passing algorithms. Further, we provide parameterized versions of the bounds that control the trade-off between efficiency and accuracy. Finally, the tightness of the bounds is illustrated on various network models.

We derive generalization and excess risk bounds for neural networks using a family of complexity measures based on a multilevel relative entropy. The bounds are obtained by introducing the notion of generated hierarchical coverings of neural networks and by using the technique of chaining mutual information introduced by Asadi et al. '18. The resulting bounds are algorithm-dependent and multiscale: they exploit the multilevel structure of neural networks. This, in turn, leads to an empirical risk minimization problem with a multilevel entropic regularization. The minimization problem is resolved by introducing a multiscale extension of the celebrated Gibbs posterior distribution, proving that the derived distribution achieves the unique minimum. This leads to a new training procedure for neural networks with performance guarantees, which exploits the chain rule of relative entropy rather than the chain rule of derivatives (as in backpropagation), and which takes into account the interactions between different scales of the hypothesis sets of neural networks corresponding to different depths of the hidden layers. To obtain an efficient implementation of the latter, we further develop a multilevel Metropolis algorithm simulating the multiscale Gibbs distribution, with an experiment for a two-layer neural network on the MNIST data set.

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms using list-decoding. We run our algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) regime for a wide range of code rates. Simulation results show that in both low code rate and high code rate regimes, the new algorithm outperforms the widely used decoder for polar codes (SCL+CRC) with the same parameters. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.

Reed-Muller (RM) codes were introduced in 1954 and have long been conjectured to achieve Shannon's capacity on symmetric channels. The activity on this conjecture has recently been revived with the emergence of polar codes. RM codes and polar codes are generated by the same matrix Gm= [1110]⊗mbut using different subset of rows. RM codes 1 1 select simply rows having largest weights. Polar codes select instead rows having the largest conditional mutual information proceeding top to down in Gm; while this is a more elaborate and channel-dependent rule, the top-to-down ordering allows Arıkan to show that the conditional mutual information polarizes, and this gives directly a capacity-achieving code on any symmetric channel. RM codes are yet to be proved to have such a property, despite the recent success for the erasure channel. In this article, we connect RM codes to polarization theory. We show that proceeding in the RM code ordering, i.e., not top-to-down but from the lightest to the heaviest rows inGm, the conditional mutual information again polarizes. Here “polarization” means that almost all the conditional mutual information becomes either very close to 0 or very close to 1. Polarization itself is a necessary condition for RM codes to achieve capacity on symmetric channels while polarization together with a strong order on the conditional mutual information gives a sufficient condition, where strong order means that rows with larger weight always correspond to larger conditional mutual information. Although we are not able to prove the strong order, we establish a partial order on the conditional mutual information, which is a subset of the strong order. While the main results of this article-polarization together with the partial order-provide some advances on the capacity-achieving conjecture of RM codes, we emphasize that our results do not allow us to prove the conjecture.

Reed-Muller (RM) codes were introduced in 1954 and have long been conjectured to achieve Shannon's capacity on symmetric channels. The activity on this conjecture has recently been revived with the emergence of polar codes. RM codes and polar codes are generated by the same matrix G_m= [1/1 0/1] ^⊗m but using different subset of rows. RM codes select simply rows having largest weights. Polar codes select instead rows having the largest conditional mutual information proceeding top to down in G_m; while this is a more elaborate and channel-dependent rule, the top-to-down ordering allows Arikan to show that the conditional mutual information polarizes, and this gives directly a capacity-achieving code on any symmetric channel. RM codes are yet to be proved to have such a property, despite the recent success for the erasure channel. In this paper, we connect RM codes to polarization theory. We show that proceeding in the RM code ordering, i.e., not top-to-down but from the lightest to the heaviest rows in G_m, the conditional mutual information again polarizes. We further demonstrate that it does so faster than for polar codes. This implies that G_m contains another code, different than the polar code and called here the twin-RM code, that is provably capacity-achieving on any symmetric channel. This gives in particular a necessary condition for RM codes to achieve capacity on symmetric channels. It further gives a sufficient condition if the rows with largest conditional mutual information correspond to the heaviest rows, i.e., if the twin-RM code is the RM code. We demonstrate here that the two codes are at least similar and give further evidence that they are indeed the same.

Evans et al. [1] proved the subadditivity of the mutual information in the broadcasting on tree model with binary vertex labels and symmetric edge channels. They raised the question of whether such subadditivity extends to loopy graphs in some appropriate way. We propose here such a generalization for general graphs and binary vertex labels. With enough channel symmetry, the generalization applies to arbitrary graphs, and with partial symmetry, it applies to series-parallel graphs. The results are obtained using the Chi-squared mutual information rather than the classical KL-mutual information (for which some of our bounds do not hold). Various properties of the Chi-squared mutual information are discussed.

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms based on list-decoding algorithms and code concatenation. We run our main algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) and low code rate (≤ 0.5) regime. Simulation results show that the new algorithm not only outperforms the previous decoding algorithms for RM codes, it also outperforms the optimal decoder for polar codes (SCL+CRC) with the same parameters by a wide margin. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.

In the multireference alignment model, a signal is observed by the action of a random circular translation and the addition of Gaussian noise. The goal is to recover the signal’s orbit by accessing multiple independent observations. Of particular interest is the sample complexity, i.e., the number of observations/samples needed in terms of the signal-to-noise ratio (SNR) (the signal energy divided by the noise variance) in order to drive the mean-square error to zero. Previous work showed that if the translations are drawn from the uniform distribution, then, in the low SNR regime, the sample complexity of the problem scales as$\omega (1/ \mathrm {SNR}^{3})$. In this paper, using a generalization of the Chapman–Robbins bound for orbits and expansions of the$\chi ^{2}$divergence at low SNR, we show that in the same regime the sample complexity for any aperiodic translation distribution scales as$\omega (1/ \mathrm {SNR}^{2})$. This rate is achieved by a simple spectral algorithm. We propose two additional algorithms based on non-convex optimization and expectation–maximization. We also draw a connection between the multireference alignment problem and the spiked covariance model.

This paper develops coding techniques to reduce the running time of distributed learning tasks. It characterizes the fundamental tradeoff to compute gradients in terms of three parameters: computation load, straggler tolerance and communication cost. It further gives an explicit coding scheme that achieves the optimal tradeoff based on recursive polynomial constructions, coding both across data subsets and vector components. As a result, the proposed scheme allows to minimize the running time for gradient computations. Implementations are made on Amazon EC2 clusters using Python with mpi4py package. Results show that the proposed scheme maintains the same generalization error while reducing the running time by $32%$ compared to uncoded schemes and $23%$ compared to prior coded schemes focusing only on stragglers (Tandon et al., ICML 2017).

We analyze the problem of estimating a signal from multiple measurements on a group action channel that linearly transforms a signal by a random group action followed by a fixed projection and additive Gaussian noise. This channel is motivated by applications such as multi-reference alignment and cryo-electron microscopy. We focus on the large noise regime prevalent in these applications. We give a lower bound on the mean square error (MSE) of any asymptotically unbiased estimator of the orbit in terms of the signal's moment tensors, which implies that the MSE is bounded away from 0 when N/σ2dis bounded from above, where N is the number of observations, σ is the noise standard deviation, and d is the so-called moment order cutoff. In contrast, the maximum likelihood estimator is shown to be consistent if N/σ2ddiverges.

Bounding the generalization error of learning algorithms has a long history, which yet falls short in explaining various generalization successes including those of deep learning. Two important difficulties are (i) exploiting the dependencies between the hypotheses, (ii) exploiting the dependence between the algorithm’s input and output. Progress on the first point was made with the chaining method, originating from the work of Kolmogorov, and used in the VC-dimension bound. More recently, progress on the second point was made with the mutual information method by Russo and Zou ’15. Yet, these two methods are currently disjoint. In this paper, we introduce a technique to combine chaining and mutual information methods, to obtain a generalization bound that is both algorithm-dependent and that exploits the dependencies between the hypotheses. We provide an example in which our bound significantly outperforms both the chaining and the mutual information bounds. As a corollary, we tighten Dudley’s inequality when the learning algorithm chooses its output from a small subset of hypotheses with high probability.

The Boolean multireference alignment problem consists in recovering a Boolean signal from multiple shifted and noisy observations. In this paper we obtain an expression for the error exponent of the maximum A posteriori decoder. This expression is used to characterize the number of measurements needed for signal recovery in the low SNR regime, in terms of higher order autocorrelations of the signal. The characterization is explicit for various signal dimensions, such as prime and even dimensions.

This paper investigates the fundamental limits for compressing data on graphs, exploiting dependencies due to community structures in the graph. The source model, referred to as the data block model (DBM), is a mixture of discrete memoryless sources determined by the community structure of a stochastic block model (SBM). The main result gives the optimal expected length of a lossless compressor when the community signal is strong enough, a condition on the edge probabilities and the data distributions, which can take place below the exact recovery threshold of the SBM. This is derived in part by obtaining the threshold for exact recovery in SBMs with strong side information, a result of independent interest, which extends the CH-divergence threshold. Finally we discuss compressing data with almost exact recovery algorithms.

This paper develops upper and lower bounds on the influence measure in a network, more precisely, the expected number of nodes that a seed set can influence in the independent cascade model. In particular, our bounds exploit nonbacktracking walks, Fortuin-Kasteleyn-Ginibre type inequalities, and are computed by message passing algorithms. Nonbacktracking walks have recently allowed for headways in community detection, and this paper shows that their use can also impact the influence computation. Further, we provide parameterized versions of the bounds that control the trade-off between the efficiency and the accuracy. Finally, the tightness of the bounds is illustrated with simulations on various network models.

In this paper, we show that the Hadamard matrix acts as an extractor over the reals of the Rényi Information Dimension (RID), in an analogous way to how it acts as an extractor of the discrete entropy over finite fields. More precisely, we prove that the RID of an i.i.d. sequence of mixture random variables polarizes to the extremal values of 0 and 1 (corresponding to discrete and continuous distributions) when transformed by a Hadamard matrix. Furthermore, we prove that the polarization pattern of the RID admits a closed form expression and follows exactly the Binary Erasure Channel (BEC) polarization pattern in the discrete setting. We discuss the applications of the RID polarization to Compressed Sensing of i.i.d. sources. In particular, we use the RID polarization to construct a family of deterministic ±1-valued sensing matrices for Compressed Sensing. We run numerical simulations to compare the performance of the resulting matrices with that of the random Gaussian and the random Hadamard matrices. The results indicate that the proposed matrices afford competitive performances, while being explicitly constructed.

Decelle et al. conjectured that community detection in the symmetric stochastic block model has a computational threshold given by the so-called Kesten-Stigum (KS) threshold, and that information-theoretic methods can cross this threshold for a large enough number of communities (4 or 5 depending on the regime of the parameters). This paper shows that at k = 5, it is possible to cross the KS threshold in the disassortative regime with a non-efficient algorithm that samples a clustering having typical cluster volumes. Further, the gap between the KS and information-theoretic threshold is shown to be large in some cases. In the case where edges are drawn only across clusters with an average degree of b, and denoting by k the number of communities, the KS threshold reads b ≳ k2whereas our information-theoretic bound reads b ≳ k ln(k).

We develop an information-theoretic view of the stochastic block model, a popular statistical model for the large-scale structure of complex networks. A graph G from such a model is generated by first assigning vertex labels at random from a finite alphabet, and then connecting vertices with edge probabilities depending on the labels of the endpoints. In the case of the symmetric two-group model, we establish an explicit `single-letter' characterization of the per-vertex mutual information between the vertex labels and the graph, when the graph average degree diverges. The explicit expression of the mutual information is intimately related to estimation-theoretic quantities, and -in particular- reveals a phase transition at the critical point for community detection. Below the critical point the per-vertex mutual information is asymptotically the same as if edges were independent of the vertex labels. Correspondingly, no algorithm can estimate the partition better than random guessing. Conversely, above the threshold, the per-vertex mutual information is strictly smaller than the independent-edges upper bound. In this regime there exists a procedure that estimates the vertex labels better than random guessing.

The stochastic block model (SBM) has long been studied in machine learning and network science as a canonical model for clustering and community detection. In the recent years, new developments have demonstrated the presence of threshold phenomena for this model, which have set new challenges for algorithms. For the {\it detection} problem in symmetric SBMs, Decelle et al.\ conjectured that the so-called Kesten-Stigum (KS) threshold can be achieved efficiently. This was proved for two communities, but remained open from three communities. We prove this conjecture here, obtaining a more general result that applies to arbitrary SBMs with linear size communities. The developed algorithm is a linearized acyclic belief propagation (ABP) algorithm, which mitigates the effects of cycles while provably achieving the KS threshold in $O(n \ln n)$ time. This extends prior methods by achieving universally the KS threshold while reducing or preserving the computational complexity. ABP is also connected to a power iteration method on a generalized nonbacktracking operator, formalizing the spectral-message passing interplay described in Krzakala et al., and extending results from Bordenave et al.

This paper considers the problem of linear Boolean classification, where the goal is to determine in which set, among two given sets of Boolean vectors, an unknown vector belongs to by making linear queries. Finding the least number of queries is equivalent to determining the minimal rank of a matrix over GF(2), whose kernel does not intersect a given set S. In the case where S is a Hamming ball, this reduces to finding linear codes of largest dimension. For a general set S, this is an instance of the critical problem posed by Crapo and Rota in 1970, open in general. This paper focuses on the case where S is an annulus. As opposed to balls, it is shown that an optimal kernel is composed not only of dense but also of sparse vectors, and the optimal mixture is identified in various cases. These findings corroborate a proposed conjecture that for an annulus of inner and outer radius nq and np respectively, the optimal relative rank is given by the normalized entropy (1 - q)H(p/(1 - q)), an extension of the Gilbert-Varshamov bound.

The stochastic block model with two communities, or equivalently the planted bisection model, is a popular model of random graph exhibiting a cluster behavior. In the symmetric case, the graph has two equally sized clusters and vertices connect with probability p within clusters and q across clusters. In the past two decades, a large body of literature in statistics and computer science has focused on providing lower bounds on the scaling of | p - q| to ensure exact recovery. In this paper, we identify a sharp threshold phenomenon for exact recovery: if α = pn/log(n) and β = qn/ log(n) are constant (with α > β), recovering the communities with high probability is possible if (α + β/2) - √(αβ) > 1 and is impossible if (α + β/2) - √(αβ) <; 1. In particular, this improves the existing bounds. This also sets a new line of sight for efficient clustering algorithms. While maximum likelihood (ML) achieves the optimal threshold (by definition), it is in the worst case NP-hard. This paper proposes an efficient algorithm based on a semidefinite programming relaxation of ML, which is proved to succeed in recovering the communities close to the threshold, while numerical experiments suggest that it may achieve the threshold. An efficient algorithm that succeeds all the way down to the threshold is also obtained using a partial recovery algorithm combined with a local improvement procedure.

New phase transition phenomena have recently been discovered for the stochastic block model, for the special case of two non-overlapping symmetric communities. This gives raise in particular to new algorithmic challenges driven by the thresholds. This paper investigates whether a general phenomenon takes place for multiple communities, without imposing symmetry. In the general stochastic block model SBM(n,p,W), n vertices are split into k communities of relative size {pi}i∈[k], and vertices in community i and j connect independently with probability {Wij}i,j∈[k]. This paper investigates the partial and exact recovery of communities in the general SBM (in the constant and logarithmic degree regimes), and uses the generality of the results to tackle overlapping communities. The contributions of the paper are: (i) an explicit characterization of the recovery threshold in the general SBM in terms of a new f-divergence function D+, which generalizes the Hellinger and Chernoff divergences, and which provides an operational meaning to a divergence function analog to the KL-divergence in the channel coding theorem, (ii) the development of an algorithm that recovers the communities all the way down to the optimal threshold and runs in quasi-linear time, showing that exact recovery has no information-theoretic to computational gap for multiple communities, (iii) the development of an efficient algorithm that detects communities in the constant degree regime with an explicit accuracy bound that can be made arbitrarily close to 1 when a prescribed signal-to-noise ratio [defined in terms of the spectrum of diag(p)W] tends to infinity.

The girth of a matrix is the least number of linearly dependent columns, in contrast to the rank which is the largest number of linearly independent columns. This paper considers the construction of high-girth matrices, whose probabilistic girth is close to their rank. Random matrices can be used to show the existence of high-girth matrices. This paper uses a recursive construction based on conditional ranks (inspired by polar codes) to obtain a deterministic and efficient construction of high-girth matrices for arbitrary relative ranks. Interestingly, the construction is agnostic to the underlying field and applies to both finite and continuous fields with the same binary matrix. The construction gives in particular the following: (i) over the binary field, high-girth matrices are equivalent to capacity-achieving codes, and our construction turns out to match exactly the BEC polar codes (even at finite block length). It hence gives a different interpretation of BEC polar codes, using the parity-check matrix instead of the generator matrix, and basic linear algebra instead of the mutual information, and generalizes to larger fields; (ii) for the BSC, our construction gives an operational meaning to the Bhattacharyya upper-bound process used in polar codes; (iii) for the reals, it gives an explicit candidate matrix for sparse recovery.

The stochastic block model (SBM) has recently gathered significant attention due to new threshold phenomena. However, most developments rely on the knowledge of the model parameters, or at least on the number of communities. This paper introduces efficient algorithms that do not require such knowledge and yet achieve the optimal information-theoretic tradeoffs identified in Abbe-Sandon FOCS15. In the constant degree regime, an algorithm is developed that requires only a lower-bound on the relative sizes of the communities and achieves the optimal accuracy scaling for large degrees. This lower-bound requirement is removed for the regime of arbitrarily slowly diverging degrees, and the model parameters are learned efficiently. For the logarithmic degree regime, this is further enhanced into a fully agnostic algorithm that achieves the CH-limit for exact recovery in quasi-linear time. These provide the first algorithms affording efficiency, universality and information-theoretic optimality for strong and weak consistency in the SBM.

This paper studies the parameters for which binary Reed-Muller (RM) codes can be decoded successfully on the BEC and BSC, and in particular when can they achieve capacity for these two classical channels. Necessarily, the paper also studies properties of evaluations of multi-variate GF(2) polynomials on random sets of inputs. For erasures, we prove that RM codes achieve capacity both for very high rate and very low rate regimes. For errors, we prove that RM codes achieve capacity for very low rate regimes, and for very high rates, we show that they can uniquely decode at about square root of the number of errors at capacity.

The polarization phenomenon for a single source is extended to a framework with multiple correlated sources. It is shown in addition to extracting the randomness of the source, the polar transforms take the original arbitrary dependencies to extremal dependencies. Polar coding schemes for the Slepian-Wolf (SW) coding problem and for secret key generations are then proposed based on this phenomenon. In particular, secret keys achieving the secrecy capacity and compression schemes achieving the SW capacity region are obtained with a complexity of O(n log (n)) .

This paper studies the parameters for which binary Reed-Muller (RM) codes can be decoded successfully on the binary erasure channel and binary symmetry channel, and, in particular, when can they achieve capacity for these two classical channels. Necessarily, this paper also studies the properties of evaluations of multivariate GF(2) polynomials on the random sets of inputs. For erasures, we prove that RM codes achieve capacity both for very high rate and very low rate regimes. For errors, we prove that RM codes achieve capacity for very low rate regimes, and for very high rates, we show that they can uniquely decode at about the square root of the number of errors at capacity. The proofs of these four results are based on different techniques, which we find interesting in their own right. In particular, we study the following questions about E(m, r), the matrix whose rows are the truth tables of all the monomials of degree ≤ r in m variables. What is the most (resp. least) number of random columns in E(m, r) that define a submatrix having full column rank (resp. full row rank) with high probability? We obtain tight bounds for very small (resp. very large) degrees r, which we use to show that RM codes achieve capacity for erasures in these regimes. Our decoding from random errors follows from the following novel reduction. For every linear code C of sufficiently high rate, we construct a new code C' obtained by tensorizing C, such that for every subset S of coordinates, if C can recover from erasures in S, then C' can recover from errors in S. Specializing this to the RM codes and using our results for erasures imply our result on the unique decoding of the RM codes at high rate. Finally, two of our capacity achieving results require tight bounds on the weight distribution of RM codes. We obtain such bounds extending the recent bounds from constant degree to linear degree polynomials.

Polar codes are introduced for discrete memoryless broadcast channels. For m-user deterministic broadcast channels, polarization is applied to map uniformly random message bits from m-independent messages to one codeword while satisfying broadcast constraints. The polarization-based codes achieve rates on the boundary of the private-message capacity region. For two-user noisy broadcast channels, polar implementations are presented for two information-theoretic schemes: 1) Cover's superposition codes and 2) Marton's codes. Due to the structure of polarization, constraints on the auxiliary and channel-input distributions are identified to ensure proper alignment of polarization indices in the multiuser setting. The codes achieve rates on the capacity boundary of a few classes of broadcast channels (e.g., binary-input stochastically degraded). The complexity of encoding and decoding is O(n log n), where n is the block length. In addition, polar code sequences obtain a stretched-exponential decay of O(2-nβ) of the average block error probability where 0 <; β <; 1/2. Reproducible experiments for finite block lengths n = 512, 1024, 2048 corroborate the theory.

This paper considers the problem of linear Boolean classification, where the goal is to determine in which set, among two given sets of Boolean vectors, an unknown vector belongs to by making linear queries. Finding the least number of queries is formulated as determining the minimal rank of a matrix over GF(2) whose kernel does not intersect a given set S. In the case where S is a Hamming ball, this reduces to finding linear codes of largest dimension. For a general set S, this is an instance of “the critical problem” posed by Crapo and Rota in 1970, open in general. This work focuses on the case where S is an annulus. As opposed to balls, it is shown that an optimal kernel is composed not only of dense but also of sparse vectors, and the optimal mixture is identified in various cases. These findings corroborate a proposed conjecture that for an annulus of inner and outer radius nq and np respectively, the optimal relative rank is given by the normalized entropy (1 - q)H(p=(1 - q)), an extension of the Gilbert-Varshamov bound.

This paper considers the inverse problem with observed variables Y = BGX ⊕ Z, where BGis the incidence matrix of a graph G, X is the vector of unknown vertex variables with a uniform prior, and Z is a noise vector with Bernoulli(ε) i.i.d. entries. All variables and operations are Boolean. This model is motivated by coding, synchronization, and community detection problems. In particular, it corresponds to a stochastic block model or a correlation clustering problem with two communities and censored edges. Without noise, exact recovery of X is possible if and only the graph G is connected, with a sharp threshold at the edge probability log(n)=n for Erdös-Rényi random graphs. The first goal of this paper is to determine how the edge probability p needs to scale to allow exact recovery in the presence of noise. Defining the degree (oversampling) rate of the graph by α = np= log(n), it is shown that exact recovery is possible if and only if α > 2/(1-2ε)2+o(1/(1-2ε)2). In other words, 2/(1-2ε)2is the information theoretic threshold for exact recovery at low-SNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. Full version available in [1].

The entropy power inequality (EPI) yields lower bounds on the differential entropy of the sum of two independent real-valued random variables in terms of the individual entropies. Versions of the EPI for discrete random variables have been obtained for special families of distributions with the differential entropy replaced by the discrete entropy, but no universal inequality is known (beyond trivial ones). More recently, the sumset theory for the entropy function yields a sharp inequality H(X + X') - H(X) ≥ 1/2 - o(1) when X, X' are independent identically distributed (i.i.d.) with high entropy. This paper provides the inequality H(X + X') - H(X)≥ g(H(X)), where X, X' are arbitrary i.i.d. integer-valued random variables and where g is a universal strictly positive function on R+satisfying g(0) = 0. Extensions to nonidentically distributed random variables and to conditional entropies are also obtained.

Building on polar code constructions proposed by the authors for deterministic broadcast channels, two theorems are introduced in the present paper for noisy two-user broadcast channels. The theorems establish polar code constructions for two important information-theoretic broadcast strategies: (1) Cover's superposition strategy; (2) Marton's construction. One aspect of the polar code constructions is the alignment of polarization indices via constraints placed on the auxiliary and channel-input distributions. The codes achieve capacity-optimal rates for several classes of broadcast channels (e.g., binary-input stochastically degraded channels). Applying Arıkan's original matrix kernel for polarization, it is shown that the average probability of error in decoding two private messages at the broadcast receivers decays as O(2(-nβ)) where 0 <; β <; 1/2 and n is the code length. The encoding and decoding complexities remain O(n log n). The error analysis is made possible by defining new polar code ensembles for broadcast channels.

This paper shows that the Rényi information dimension (RID) of an i.i.d. sequence of mixture random variables polarizes to the extremal values of 0 and 1 (fully discrete and continuous distributions) when transformed by an Hadamard matrix. This provides a natural counter-part over the reals of the entropy polarization phenomenon over finite fields. It is further shown that the polarization pattern of the RID is equivalent to the BEC polarization pattern, which admits a closed form expression. These results are used to construct universal and deterministic partial Hadamard matrices for analog to analog (A2A) compression of memoryless sources. In addition, a framework for the A2A compression of multi-terminal correlated sources is developed, providing a first counter-part of the Slepian-Wolf coding problem in the A2A setting.

The entropy power inequality (EPI) provides lower bounds on the differential entropy of the sum of two independent real-valued random variables in terms of the individual entropies. Versions of the EPI for discrete random variables have been obtained for special families of distributions with the differential entropy replaced by the discrete entropy, but no universal inequality is known (beyond trivial ones). More recently, the sumset theory for the entropy function yields a sharp inequality H(X + X') - H(X) ≥ 1/2 - o(l) when X,X' are i.i.d. with high entropy. This paper provides the inequality H(X + X') - H(X) ≥ g(H(X)), where X, X' are arbitrary i.i.d. integer-valued random variables and where g is a universal strictly positive function on R+satisfying g(0) = 0. Extensions to non identically distributed random variables and to conditional entropies are also obtained.

Practical implementations of secret-key generation are often based on sequential strategies, which handle reliability and secrecy in two successive steps, called reconciliation and privacy amplification. In this paper, we propose an alternative approach based on polar codes that jointly deals with reliability and secrecy. Specifically, we propose secret-key capacity-achieving polar coding schemes for the following models: (i) the degraded binary memoryless source (DBMS) model with rate-unlimited public communication, (ii) the DBMS model with one-way rate-limited public communication, (iii) the 1-to-m broadcast model and (iv) the Markov tree model with uniform marginals. For models (i) and (ii) our coding schemes remain valid for non-degraded sources, although they may not achieve the secret-key capacity. For models (i), (ii) and (iii), our schemes rely on pre-shared secret seed of negligible rate; however, we provide special cases of these models for which no seed is required. Finally, we show an application of our results to secrecy and privacy for biometric systems. We thus provide the first examples of low-complexity secret-key capacity-achieving schemes that are able to handle vector quantization for model (ii), or multiterminal communication for models (iii) and (iv).

It is conjectured that the covariance matrices minimizing the outage probability under a power constraint for multiple-input multiple-output channels with Gaussian fading are diagonal with either zeros or constant values on the diagonal. In the multiple-input single-output (MISO) setting, this is equivalent to conjecture that the Gaussian quadratic forms having largest tail probability correspond to such diagonal matrices. This paper provides a proof of the conjecture in this MISO setting.

This paper investigates the construction of deterministic measurement matrices preserving the entropy of a random vector with a given probability distribution. In particular, it is shown that for a random vector with i.i.d. discrete components, this is achieved by selecting a subset of rows of a Hadamard matrix such that (i) the selection is deterministic (ii) the fraction of selected rows is vanishing. In contrast, it is shown that for a random vector with i.i.d. continuous components, no entropy preserving measurement matrix allows dimensionality reduction. These results are in agreement with the results of Wu-Verdu on almost lossless analog compression and provide a low-complexity measurement matrix. The proof technique is based on a polar code martingale argument and on a new entropy power inequality for integer-valued random variables.

It is conjectured in [6] that the covariance matrices minimizing the outage probability under a power constraint for MIMO channels with Gaussian fading are diagonal with either zeros or constant values on the diagonal. In the MISO setting, this is equivalent to conjecture that the Gaussian quadratic forms having largest tail probability correspond to such diagonal matrices. This paper provides a proof of the conjecture in this MISO setting.

In this paper, polar codes for the m-user multiple access channel (MAC) with binary inputs are constructed. It is shown that Arikan's polarization technique applied individually to each user transforms independent uses of an m-user binary input MAC into successive uses of extremal MACs. This transformation has a number of desirable properties: 1) the “uniform sum-rate” of the original MAC is preserved, 2) the extremal MACs have uniform rate regions that are not only polymatroids but matroids, and thus, 3) their uniform sum-rate can be reached by each user transmitting either uncoded or fixed bits; in this sense, they are easy to communicate over. A polar code can then be constructed with an encoding and decoding complexity of O(n log n) (where n is the block length), a block error probability of o(exp (- n1/2 - ε)), and capable of achieving the uniform sum-rate of any binary input MAC with arbitrary many users. Applications of this polar code construction to channels with a finite field input alphabet and to the additive white Gaussian noise channel are also discussed.

This paper investigates network information theory problems where the external noise is Gaussian distributed. In particular, the Gaussian broadcast channel with coherent fading and the Gaussian interference channel are considered. It is shown that in these problems, non-Gaussian code ensembles can achieve higher rates than the Gaussian ones. It is also shown that the strong Shamai-Laroia conjecture on the Gaussian ISI channel does not hold. In order to analyze non-Gaussian code ensembles over Gaussian networks, a geometrical tool using the Hermite polynomials is proposed. This tool provides a coordinate system to analyze a class of non-Gaussian input distributions that are invariant over Gaussian networks.

This paper explores a connection between randomness extraction and channel (source) coding problems. It is explained how efficient extractors can be used to define efficient coding schemes and reciprocally, a new deterministic extractor based on a polar coding scheme is proposed. Since the source model used in extractors for computer science (cryptography) do not assume i.i.d. or known distributions, a generalized polarization phenomenon for sources with block memory and unknown distributions is developed. It is shown that in this setting, the min-entropy (as usual in extractors) rather than Shannon entropy can be efficiently extracted. The derived polar coding results also apply to compound channels with memory.

This paper investigates polar coding schemes achieving capacity for the AWGN channel. The approaches using a multiple access channel with a large number of binary-input users and a single-user channel with a large prime-cardinality input are compared with respect to complexity attributes. The problem of finding discrete approximations to the Gaussian input is then investigated, and it is shown that a quantile quantizer achieves a gap to capacity which decreases like 1/q (where q is the number of constellation points), improving on the 1/log(q) decay achieved with a binomial (central limit theorem) quantizer.

Polar codes allow to perform lossless compression of i.i.d. sources at the lowest rate with low encoding and decoding complexity. In this paper, it is shown that for binary sources, there exist “universal polar codes” which can compress any source of low enough entropy, without requiring knowledge of the source distribution. While this result does not extend to q-ary sources, it is shown how it extends to q-ary sources which belong to a restricted family. An analogy between this family and BECs in channel polarization is discussed. Finally, an application of the universal source polarization results to sparse data recovery is proposed.

Over binary input channels, the uniform distribution is a universal prior, in the sense that it maximizes the worst case mutual information of all binary input channels and achieves at least 94.2% of the capacity. In this paper, we address a similar question. We look for the best collection of finitely many a posteriori metrics, to maximize the worst case mismatched mutual information achieved by decoding with these metrics (instead of an optimal decoder such as the Maximum Likelihood (ML) tuned to the true channel). It is shown that for binary input and output channels, two metrics suffice to actually achieve the same performance as an optimal decoder. In particular, this implies that there exist a decoder which is generalized linear and achieves at least 94.2% of the compound capacity on any compound set, without knowledge of the underlying set.

Over discrete memoryless channels (DMC), linear decoders (maximizing additive metrics) afford several nice properties. In particular, if suitable encoders are employed, the use of decoding algorithms with manageable complexities is permitted. For a compound DMC, decoders that perform well without the channel's knowledge are required in order to achieve capacity. Several such decoders have been studied in the literature, however, there is no such known decoder which is linear. Hence, the problem of finding linear decoders achieving capacity for compound DMC is addressed, and it is shown that under minor concessions, such decoders exist and can be constructed. A geometric method based on the very noisy transformation is developed and used to solve this problem.

This paper shows that the capacity achieving input distribution for a fading Gaussian broadcast channel is not Gaussian in general. The construction of non-Gaussian distributions that strictly outperform Gaussian ones, for certain characterized fading distributions, is provided. The ability of analyzing non-Gaussian input distributions with closed form expressions is made possible in a local setting. It is shown that there exists a specific coordinate system, based on Hermite polynomials, which parametrizes Gaussian neighborhoods and which is particularly suitable to study the entropic operators encountered with Gaussian noise.

On a discrete memoryless channel (DMC), the maximum likelihood (ML) decoding rule is not only optimal (for equiprobable messages and average error probability), but it is also linear (the metric that it maximizes is additive over the block length), which in particular, makes ML practically conceivable. On a compound DMC, the use of ML is ruled out by the channelpsilas law ignorance. In order to account for this, the universal decoders proposed in (Feder et al., 1998) can be employed. However, none of these decoders is linear. Hence, we consider the problem of finding good linear decoders for compound DMCpsilas. We show that on most compound sets, when universality requires to be capacity achieving, there exists a universal decoding rule which is generalized linear, in the sense that it maximizes only a finite number of additive metrics. A local to global geometric method is developed to solve this problem. By considering very noisy channels, the global problem is reduced, in the limit, to an inner product space problem, for which insightful solutions can be found. We describe a heuristic method used, in this problem, to ldquoliftrdquo local results to global results.