Fast computation of a matrix product $W^\top X$ is a workhorse of modern LLMs. To make their deployment more efficient, a popular approach is that of using a low-precision approximation $\widehat W$ in place of true $W$ (“weight-only quantization”). Information theory demonstrates that an optimal algorithm for reducing precision of $W$ depends on the (second order) statistics of $X$ and requires a careful alignment of vector quantization codebook with PCA directions of $X$ (a process known as “waterfilling allocation”). Dependence of the codebook on statistics of $X$, however, is highly impractical. This paper proves that there exist a universal codebook that is simultaneously near-optimal for all possible statistics of $X$, in the sense of being at least as good as an $X$-adapted waterfilling codebook with rate reduced by 0.11 bit per dimension in the case when $W$ is Gaussian. Such universal codebook would be an ideal candidate for the low-precision storage format, a topic of active modern research, but alas the existence proof is non-constructive. Equivalently, our result shows existence of a net in $\mathbb{R}^n$ that is a nearly-optimal covering of a sphere simultaneously with respect to all Hilbert norms.

For a lattice/linear code, we define the Voronoi spherical cumulative density function (CDF) as the CDF of the ℓ2-norm/Hamming weight of a random vector uniformly distributed over the Voronoi cell. Using the first moment method together with a simple application of Jensen’s inequality, we develop lower bounds on the expected Voronoi spherical CDF of a random lattice/linear code. Our bounds are valid for any finite dimension and are quite close to a ball-based lower bound. They immediately translate to new non-asymptotic upper bounds on the normalized second moment and the error probability of a random lattice over the additive white Gaussian noise channel, as well as new non-asymptotic upper bounds on the Hamming distortion and the error probability of a random linear code over the binary symmetric channel. In particular, we show that for most lattices in Rnthe second moment is greater than that of a Euclidean ball with the same covolume only by a (1 +O(1/n)) multiplicative factor. Similarly, for most linear codes in Fn2the expected Hamming distortion is greater than that of a corresponding Hamming ball only by an additive universal constant.

Recent work in machine learning community proposed multiple methods for performing lossy compression (quantization) of large matrices. This quantization is important for accelerating matrix multiplication (main component of large language models), which is often bottlenecked by the speed of loading these matrices from memory. Unlike classical vector quantization and rate-distortion theory, the goal of these new compression algorithms is to be able to approximate not the matrices themselves, but their matrix product. Specifically, given a pair of real matricesA,Ban encoder (compressor) is applied to each of them independently producing descriptions withRbits per entry. These representations subsequently are used by the decoder to estimate matrix productA⊤B. In this work, we provide a non-asymptotic lower bound on the mean squared error of this approximation (as a function of rateR) for the case of matricesA,Bwith iid Gaussian entries. Algorithmically, we construct a universal quantizer based on nested lattices with an explicit guarantee of approximation error for any (non-random) pair of matricesA,Bin terms of only Frobenius norms ∥Ā∥F, ∥B∥Fand ∥Ā⊤B∥F, where Ā,Bare versions ofA,Bwith zero-centered columns, respectively. For iid Gaussian matrices our quantizer achieves the lower bound and is, thus, asymptotically optimal. A practical low-complexity version of our quantizer achieves performance quite close to optimal. In addition, we derive rate-distortion function for matrix multiplication of iid Gaussian matrices, which exhibits an interesting phase-transition atR≈ 0.906 bit/entry, showing necessity of Johnson-Lindestrauss dimensionality reduction (sketching) in the low-rate regime.

Post-training quantization (PTQ) has emerged as a critical technique for efficient deployment of large language models (LLMs). This work proposes NestQuant, a novel PTQ scheme for weights and activations that is based on self-similar nested lattices. Recent works have mathematically shown such quantizers to be information-theoretically optimal for low-precision matrix multiplication. We implement a practical low-complexity version of NestQuant based on Gosset lattice, making it a drop-in quantizer for any matrix multiplication step (e.g., in self-attention, MLP etc). For example, NestQuant quantizes weights, KV-cache, and activations of Llama-3-8B to 4 bits, achieving perplexity of 6.6 on wikitext2. This represents more than 55% reduction in perplexity gap with respect to unquantized model (perplexity of 6.14) compared to state-of-the-art Meta’s SpinQuant (perplexity 7.3), OstQuant (7.3) and QuaRot (8.2). Comparisons on bigger models (up to 70B) and on various LLM evaluation benchmarks confirm uniform superiority of NestQuant.

In online betting, the bookmaker can update the payoffs it offers on a particular event many times before the event takes place, and the updated payoffs may depend on the bets accumulated thus far. We study the problem of bookmaking with the goal of maximizing the return in the worst-case, with respect to the gamblers' behavior and the event's outcome. We formalize this problem as the Optimal Online Bookmaking game, and provide the exact solution for the binary case. To this end, we develop the optimal bookmaking strategy, which relies on a new technique called bi-balancing trees, that assures that the house loss is the same for all decisive betting sequences, where the gambler bets all its money on a single outcome in each round.

Recent work have shown that the quantization for matrix multiplication problem can be optimally solved by quantizing each column in each matrix using a nested lattice code, and then multiplying the de-quantized matrices. It was further demonstrated that when product codes of sub-dimension$d$and rate$R$are used, the de-quantization and inner product operations can be implemented with querying a lookup table (LUT) of size$2^{2 d R}$, but this is only useful when$d R$is sufficiently small. This in turn limits LUT-based inner product decoding to low-rate quantizers. In this work, we develop a rate$R$hierarchical nested lattice quantization framework, which quantizes each vector to$M$layers, and admits LUT-based inner product decoding using an LUT of size$2^{2 d \frac{R}{M}}$, allowing for high-rate quantization. We provide analytic bounds on the loss of the developed scheme compared to standard nested lattice quantizers, and also numerically illustrate that this loss is negligible. Thus, our scheme enables to use small LUTs without compromising the overall distortion. Python code is available in https://github.com/iriskaplan/LatticeQuant.

Recent work in machine learning community proposed multiple methods for performing lossy compression (quantization) of large matrices. This quantization is important for accelerating matrix multiplication (main component of large language models), which is often bottlenecked by the speed of loading these matrices from memory. Unlike classical vector quantization and rate-distortion theory, the goal of these new compression algorithms is to be able to approximate not the matrices themselves, but their matrix product. Specifically, given a pair of real matrices$A, B$an encoder (compressor) is applied to each of them independently producing descriptions with$R$bits per entry. These representations subsequently are used by the decoder to estimate matrix product$A^{\top} B$. In this work, we provide a non-asymptotic lower bound on the mean squared error of this approximation (as a function of rate$R$) for the case of matrices$A, B$with iid Gaussian entries. Algorithmically, we construct a universal quantizer based on nested lattices with an explicit guarantee of approximation error for any (non-random) pair of matrices$A$,$B$in terms of only Frobenius norms$\vert\bar{A}\vert_{F},\vert\bar{B}\vert_{F}$and$\left\vert\bar{A}^{\top} \bar{B}\right\vert_{F}$, where$\bar{A}, \bar{B}$are versions of$A, B$with zerocentered columns, respectively. For iid Gaussian matrices our quantizer achieves the lower bound and is, thus, asymptotically optimal. In particular, we derive the rate-distortion function for matrix multiplication of iid Gaussian matrices, which exhibits an interesting phase-transition at$R \approx 0.906$bit/entry. An extended version of this paper is available in [1].

We observe an infinite sequence of independent identically distributed random variables$X_{1},X_{2},\ldots $drawn from an unknown distributionpover$[n]$, and our goal is to estimate the entropy$H(p)=-\mathop {\mathrm {\mathbb {E}}}\nolimits [\log p(X)]$within an$\varepsilon $-additive error. To that end, at each time point we are allowed to update a finite-state machine withSstates, using a possibly randomized but time-invariant rule, where each state of the machine is assigned an entropy estimate. Our goal is to characterize the minimax memory complexity$S^{*}$of this problem, which is the minimal number of states for which the estimation task is feasible with probability at least$1-\delta $asymptotically, uniformly inp. Specifically, we show that there exist universal constants$C_{1}$and$C_{2}$such that$ S^{*} \leq C_{1}\cdot \frac {n (\log n)^{4}}{\varepsilon ^{2}\delta }$for$\varepsilon $not too small, and$S^{*} \geq C_{2} \cdot \max \left \{{{n, \frac {\log n}{\varepsilon }}}\right \}$for$\varepsilon $not too large. The upper bound is proved using approximate counting to estimate the logarithm ofp, and a finite memory bias estimation machine to estimate the expectation operation. The lower bound is proved via a reduction of entropy estimation to uniformity testing. We also apply these results to derive bounds on the memory complexity of mutual information estimation.

Let$\nu $and$\mu $be probability distributions on$\mathbb {R}^{n}$, and$\nu _{s},\mu _{s}$be their evolution under the heat flow, that is, the probability distributions resulting from convolving their density with the density of an isotropic Gaussian random vector with variancesin each entry. This paper studies the rate of decay of$s\mapsto D(\nu _{s}\|\mu _{s})$for various divergences, including the$\chi ^{2}$and Kullback-Leibler (KL) divergences. We prove upper and lower bounds on the strong data-processing inequality (SDPI) coefficients corresponding to the source$\mu $and the Gaussian channel. We also prove generalizations of de Bruijn’s identity, and Costa’s result on the concavity insof the differential entropy of$\nu _{s}$. As a byproduct of our analysis, we obtain new lower bounds on the mutual information betweenXand$Y=X+\sqrt {s} Z$, whereZis a standard Gaussian vector in$\mathbb {R}^{n}$, independent ofX, and on the minimum mean-square error (MMSE) in estimatingXfromY, in terms of the Poincaré constant ofX.

It has been known for a long time that the mutual information between the input sequence and output sequence of a binary symmetric channel (BSC) is upper bounded by the mutual information between the same input sequence and the output sequence of a binary erasure channel (BEC) with the same capacity. Recently, Samorodnitsky discovered that one may also lower bound the BSC mutual information in terms of the mutual information between the same input sequence and a more capable BEC. In this paper, we strengthen Samorodnitsky's bound for the special case where the input to the channel is distributed uniformly over a linear code. Furthermore, for a general (not necessarily binary) input distribution$P_{X}$and channel$W_{Y\vert X}$, we derive a new lower bound on the mutual information$I(X;Y^{n})$for$n$transmissions of$X\sim P_{X}$through the channel$W_{Y\vert X}$.

This paper develops a unified framework for upper bounding the minimax risk in high-dimensional parameter estimation problems. To this end, we study a quantized maximum likelihood estimator, where the estimator computes the likelihood for all points within a discrete cover, and outputs the candidate with the maximal likelihood. While this concept is straightforward, our analysis is quite delicate. It splits the competing candidates in the cover to small shells, and controls the number of candidates in each shell, as well as the probability that a candidate in the shell outscores a candidate which is close to the true parameter. We demonstrate the utility of our bounds by applying them to different Gaussian problems, and showing that they recover the optimal minimax rate for the Gaussian location model and the spiked Wigner Model. For the multi-reference alignment problem we obtain a novel minimax upper bound, which essentially places no assumptions on the signal of interest.

Consider the rank-1 spiked model: $\bf{X}=\sqrt{\nu}\xi \bf{u}+ \bf{Z}$, where $\nu$ is the spike intensity, $\bf{u}\in\mathbb{S}^{k-1}$ is an unknown direction and $\xi\sim \mathcal{N}(0,1),\bf{Z}\sim \mathcal{N}(\bf{0},\bf{I})$. Motivated by recent advances in analog-to-digital conversion, we study the problem of recovering $\bf{u}\in \mathbb{S}^{k-1}$ from $n$ i.i.d. modulo-reduced measurements $\bf{Y}=[\bf{X}]\mod \Delta$, focusing on the high-dimensional regime ($k\gg 1$). We develop and analyze an algorithm that, for most directions $\bf{u}$ and $\nu=\mathrm{poly}(k)$, estimates $\bf{u}$ to high accuracy using $n=\mathrm{poly}(k)$ measurements, provided that $\Delta\gtrsim \sqrt{\log k}$. Up to constants, our algorithm accurately estimates $\bf{u}$ at the smallest possible $\Delta$ that allows (in an information-theoretic sense) to recover $\bf{X}$ from $\bf{Y}$. A key step in our analysis involves estimating the probability that a line segment of length $\approx\sqrt{\nu}$ in a random direction $\bf{u}$ passes near a point in the lattice $\Delta \mathbb{Z}^k$. Numerical experiments show that the developed algorithm performs well even in a non-asymptotic setting.

In this paper we consider the problem of uniformity testing with limited memory. We observe a sequence of independent identically distributed random variables drawn from a distribution $p$ over $[n]$, which is either uniform or is $\eps$-far from uniform under the total variation distance, and our goal is to determine the correct hypothesis. At each time point we are allowed to update the state of a finite-memory machine with $S$ states, where each state of the machine is assigned one of the hypotheses, and we are interested in obtaining an asymptotic probability of error at most $0<\delta<1/2$ uniformly under both hypotheses. The main contribution of this paper is deriving upper and lower bounds on the number of states $S$ needed in order to achieve a constant error probability $\delta$, as a function of $n$ and $\eps$, where our upper bound is $O(\frac{n\log n}{\eps})$ and our lower bound is $\Omega (n+\frac{1}{\eps})$. Prior works in the field have almost exclusively used collision counting for upper bounds, and the Paninski mixture for lower bounds. Somewhat surprisingly, in the limited memory with unlimited samples setup, the optimal solution does not involve counting collisions, and the Paninski prior is not hard, thus different proof techniques are needed in order to attain our bounds.

This paper studies the sample complexity of learning the $k$ unknown centers of a balanced Gaussian mixture model (GMM) in $\mathbb{R}^d$ with spherical covariance matrix $\sigma^2\bm{I}$. In particular, we are interested in the following question: what is the maximal noise level $\sigma^2$, for which the sample complexity is essentially the same as when estimating the centers from labeled measurements? To that end, we restrict attention to a Bayesian formulation of the problem, where the centers are uniformly distributed on the sphere $\sqrt{d}\mathcal{S}^{d-1}$. Our main results characterize the \emph{exact noise threshold} $\sigma^2$ below which the GMM learning problem, in the large system limit $d,k\to\infty$, is as easy as learning from labeled observations, and above which it is substantially harder. The threshold occurs at $\frac{\log k}{d} = \frac12\log\left( 1+\frac{1}{\sigma^2} \right)$, which is the capacity of the additive white Gaussian noise (AWGN) channel. Thinking of the set of $k$ centers as a code, this noise threshold can be interpreted as the largest noise level for which the error probability of the code over the AWGN channel is small. Previous works on the GMM learning problem have identified the \emph{minimum distance} between the centers as a key parameter in determining the statistical difficulty of learning the corresponding GMM. While our results are only proved for GMMs whose centers are uniformly distributed over the sphere, they hint that perhaps it is the decoding error probability associated with the center constellation as a channel code that determines the statistical difficulty of learning the corresponding GMM, rather than just the minimum distance.

In a growing number of applications, there is a need to digitize a (possibly high) number of correlated signals whose spectral characteristics are challenging for traditional analog-to-digital converters (ADCs). Examples, among others, include multiple-input multiple-output systems where the ADCs must acquire at once several signals at a very wide but sparsely and dynamically occupied bandwidth supporting diverse services. In such scenarios, the resolution requirements can be prohibitively high. As an alternative, the recently proposed modulo-ADC architecture can in principle require dramatically fewer bits in the conversion to obtain the target fidelity, but requires that spatiotemporal information be known and explicitly taken into account by the analog and digital processing in the converter, which is frequently impractical. Building on our recent work, we address this limitation and develop a blind version of the architecture that requires no such knowledge in the converter. In particular, it features an automatic modulo-level adjustment and a fully adaptive modulo-decoding mechanism, allowing it to asymptotically match the characteristics of the unknown input signal. Simulation results demonstrate the successful operation of the proposed algorithm.

For any channel$P_{Y|X}$the strong data processing constant is defined as the smallest number$\eta _{KL}\in [{0,1}]$such that$I(U;Y)\le \eta _{KL} I(U;X)$holds for any Markov chain$U-X-Y$. It is shown that the value of$\eta _{KL}$is given by that of the best binary-input subchannel of$P_{Y|X}$. The same result holds for any$f$-divergence, verifying a conjecture of Cohen, Kemperman and Zbaganu (1998).

In this paper we consider the problem of estimating a Bernoulli parameter using finite memory. Let $X_1,X_2,\ldots$ be a sequence of independent identically distributed Bernoulli random variables with expectation $\theta$, where $\theta \in [0,1]$. Consider a finite-memory deterministic machine with $S$ states, that updates its state $M_n \in \{1,2,\ldots,S\}$ at each time according to the rule $M_n = f(M_{n-1},X_n)$, where $f$ is a deterministic time-invariant function. Assume that the machine outputs an estimate at each time point according to some fixed mapping from the state space to the unit interval. The quality of the estimation procedure is measured by the asymptotic risk, which is the long-term average of the instantaneous quadratic risk. The main contribution of this paper is an upper bound on the smallest worst-case asymptotic risk any such machine can attain. This bound coincides with a lower bound derived by Leighton and Rivest, to imply that $\Theta(1/S)$ is the minimax asymptotic risk for deterministic $S$-state machines. In particular, our result disproves a longstanding $\Theta(\log S/S)$ conjecture for this quantity, also posed by Leighton and Rivest.

In rate-distortion (RD) problems one seeks reduced representations of a source that meet a target distortion constraint. Such optimal representations undergo topological transitions at some critical rate values, when their cardinality or dimensionality change. We study the convergence time of the Arimoto-Blahut alternating projection algorithms, used to solve such problems, near those critical points, both for the ratedistortion and information bottleneck settings. We argue that they suffer from critical slowing down - a diverging number of iterations for convergence - near the critical points. This phenomenon can have theoretical and practical implications for both machine learning and data compression problems.

The construction of multiclass classifiers from binary classifiers is studied in this paper, and performance is quantified by the regret, defined with respect to the Bayes optimal log-loss. We start by proving that the regret of the well known One vs. All (OVA) method is upper bounded by the sum of the regrets of its constituent binary classifiers. We then present a new method called Conditional OVA (COVA), and prove that its regret is given by the weighted sum of the regrets corresponding to the constituent binary classifiers. Lastly, we present a method termed Leveraged COVA (LCOVA), designated to reduce the regret of a multiclass classifier by breaking it down to independently optimized binary classifiers.

We consider a two-terminal variant (double-sided) of the information bottleneck problem, which is related to biclus-tering. In our setup,$x$and Y are dependent random variables and the problem is to find two independent channels$\mathrm{P}_{\cup 1\times}$and$\mathrm{p}_{\vee 1!}$(setting the Markovian structure$\cup\rightarrow\times\rightarrow \mathrm{Y}\rightarrow$V) that maximize$I(\cup;\mathrm{V})$subject to constraints on the relevant mutual information expressions:$I(\cup;\mathrm{X})$and$I(\mathrm{V};\mathrm{Y})$. For jointly Gaussian X and Y, we show that Gaussian channels are optimal in the low-SNR regime, but not for general SNR. Similarly, it is shown that for a doubly symmetric binary source, binary symmetric channels are optimal when the correlation is low, and are suboptimal for high correlation. We conjecture that Z and S channels are optimal when the correlation is 1 (i.e.,$\mathrm{X}=\mathrm{Y})$, and provide supporting numerical evidence.

The essential interactive capacity of a discrete memoryless channel is defined in this paper as the maximal rate at which the transcript of any interactive protocol can be reliably simulated over the channel, using a deterministic coding scheme. In contrast to other interactive capacity definitions in the literature, this definition makes no assumptions on the order of speakers (which can be adaptive) and does not allow any use of private/public randomness; hence, the essential interactive capacity is a function of the channel model only. It is shown that the essential interactive capacity of any binary memoryless symmetric (BMS) channel is at least 0.0302 its Shannon capacity. To that end, we present a simple coding scheme, based on extended-Hamming codes combined with error detection, that achieves the lower bound in the special case of the binary symmetric channel (BSC). We then adapt the scheme to the entire family of BMS channels, and show that it achieves the same lower bound using extremes of the Bhattacharyya parameter.

Let X and Y be dependent random variables. This paper considers the problem of designing a scalar quantizer for Y to maximize the mutual information between the quantizer's output and X, and develops fundamental properties and bounds for this form of quantization, which is connected to the log-loss distortion criterion. The main focus is the regime of low I(X;Y), where it is shown that, if X is binary, a constant fraction of the mutual information can always be preserved usingO(log(1/I(X;Y))) quantization levels, and there exist distributions for which this many quantization levels are necessary. Furthermore, for larger finite alphabets 2X|X| /I(X;Y)))η·(|X| - 1)quantization levels.

Consider a channel$W$along with a given input distribution$P_{X}$. In certain settings, such as in the construction of polar codes, the output alphabet of$W$is ‘too large’, and hence we replace$W$by a channel$Q$having a smaller output alphabet. We say that$Q$is upgraded with respect to$W$if$W$is obtained from$Q$by processing its output. In this case, the mutual information$I(P_{X},W)$between the input and output of$W$is upper-bounded by the mutual information$I(P_{X},Q)$between the input and output of$Q$. In this paper, we present an algorithm that produces an upgraded channel$Q$from$W$, as a function of$P_{X}$and the required output alphabet size of$Q$, denoted$L$. We show that the difference in mutual informations is ‘small’. Namely, it is$O(L^{-2/(| \mathcal {X}|-1)})$, where$| \mathcal {X}|$is the size of the input alphabet. This power law of$L$is optimal. We complement our analysis with numerical experiments which show that the developed algorithm improves upon the existing state-of-the-art algorithms also in non-asymptotic setups.

We consider the problem of recovering n i.i.d. samples from a zero mean multivariate Gaussian distribution with an unknown covariance matrix, from their modulo wrapped measurements, i.e., measurements where each coordinate is reduced modulo Δ, for some Δ > 0. For this setup, which is motivated by quantization and analog-to-digital conversion, we develop a low-complexity iterative decoding algorithm. We show that if a benchmark informed decoder that knows the covariance matrix can recover each sample with small error probability, and n is large enough, the performance of the proposed blind recovery algorithm closely follows that of the informed one. We complement the analysis with numerical results that show that the algorithm performs well even in non-asymptotic conditions.

In this paper we consider the problem of binary hypothesis testing with finite memory systems. Let X1, X2, .. . be a sequence of independent identically distributed Bernoulli random variables, with expectation p under H0and q under H1. Consider a finite-memory deterministic machine with S states that updates its state Mn∈ {1, 2, ... , S} at each time according to the rule Mn= f(Mn-1, Xn), where f is a deterministic time-invariant function. Assume that we let the process run for a very long time (n → ∞), and then make our decision according to some mapping from the state space to the hypothesis space. The main contribution of this paper is a lower bound on the Bayes error probability Peof any such machine. In particular, our findings show that the ratio between the maximal exponential decay rate of Pewith S for a deterministic machine and for a randomized one, can become unbounded, complementing a result by Hellman.

Motivated by a fundamental paradigm in cryptography, we consider a recent variant of the classic problem of bounding the distinguishing advantage between a random function and a random permutation. Specifically, we consider the problem of deciding whether a sequence of q values was sampled uniformly with or without replacement from [N], where the decision is made by a streaming algorithm restricted to using at most s bits of internal memory. In this work, the distinguishing advantage of such an algorithm is measured by the KL divergence between the distributions of its output as induced under the two cases. We show that for any s = Ω(logN) the distinguishing advantage is upper bounded by O(q · s/N), and even by O(q·s/N logN) when q ≤ N1-εfor any constant ε > 0 where it is nearly tight with respect to the KL divergence.

Consider two sequences of n independent and identically distributed fair coin tosses, X = (X1, . . . , Xn) and Y = (Y1, . . . , Yn), which are ρ-correlated for each j, i.e. P[Xj= Yj] = 1+ρ/2 .We study the question of how large (small) the probability P[X ∈ A, Y ∈ B] can be among all sets A, B ⊂ {0, 1}nof a given cardinality. For sets |A|, |B| = Θ(2n) it is well known that the largest (smallest) probability is approximately attained by concentric (anti-concentric) Hamming balls, and this can be proved via the hypercontractive inequality (reverse hypercontractivity). Here we consider the case of |A|, |B| = 2Θ(n). By applying a recent extension of the hypercontractive inequality of Polyanskiy-Samorodnitsky (J. Functional Analysis, 2019), we show that Hamming balls of the same size approximately maximize P[X ∈ A, Y ∈ B] in the regime of p → 1. We also prove a similar tight lower bound, i.e. show that for p → 0 the pair of opposite Hamming balls approximately minimizes the probability P[X ∈ A, Y ∈ B].

We define the interactive capacity of the binary symmetric channel (BSC) as the maximal rate for which any interactive protocol can be fully and reliably simulated over a pair of BSC's. We show that this quantity is at least 1/40 of the BSC Shannon capacity, uniformly for all channel crossover probabilities. Our result is based on a public-coin rewind-if-error coding scheme in the spirit of Kol & Raz 2013 [1].

We consider the classic joint source-channel coding problem of transmitting a memoryless source over a memoryless channel. The focus of this work is on the rate of convergence of the smallest attainable expected distortion to its asymptotic value, as a function of blocklength n. Our main result is that in general the convergence rate is not faster than n-1/2. In particular, we show that for the problem of transmitting i.i.d uniform bits over a binary symmetric channels with Hamming distortion, the smallest attainable distortion (bit error rate) is at least Ω(n-1/2) above the asymptotic value, if the "bandwidth expansion ratio" is above 1.

We consider the problem of recovering n i.i.d samples from a zero mean multivariate Gaussian distribution with an unknown covariance matrix, from their modulo wrapped measurements, i.e., measurement where each coordinate is reduced modulo Δ, for some Δ > 0. For this setup, which is motivated by quantization and analog-to-digital conversion, we develop a low-complexity iterative decoding algorithm. We show that if an informed decoder that knows the covariance matrix can recover each sample with small error probability, and n is large enough, the performance of the proposed blind recovery algorithm closely follows that of the informed one. We complement the analysis with numeric results that show that the algorithm performs well even in non-asymptotic conditions.

We consider the problem of recovering a continuoustime bandlimited signal from the discrete-time signal, obtained from sampling it every Tsseconds and reducing the result modulo Δ, for some Δ > 0. For Δ = ∞, the celebrated Shannon-Nyquist sampling theorem guarantees that perfect recovery is possible, provided that the sampling rate 1/Tsexceeds the so-called Nyquist rate. Recent work by Bhandari et al. has shown that for any Δ > 0 perfect reconstruction is still possible, if the sampling rate exceeds the Nyquist rate by a factor of ire. In this letter, we improve upon this result and show that for finite energy signals, perfect recovery is possible for any Δ > 0 and any sampling rate above the Nyquist rate. Thus, modulo folding does not degrade the signal, provided that the sampling rate exceeds the Nyquist rate. This claim is proved by establishing a connection between the recovery problem of a discrete-time signal from its modulo reduced version and the problem of predicting the next sample of a discrete-time signal from its past, and leveraging the fact that for a bandlimited signal the prediction error can be made arbitrarily small.

Sampling above the Nyquist rate is at the heart of sigma-delta modulation, where the increase in sampling rate is translated to a reduction in the overall (mean-squared-error) reconstruction distortion. This is attained by using a feedback filter at the encoder, in conjunction with a low-pass filter at the decoder. The goal of this paper is to characterize the optimal trade-off between the per-sample quantization rate and the resulting mean-squared-error distortion under various restrictions on the feedback filter. To this end, we establish a duality relation between the performance of sigma-delta modulation and the performance of differential pulse-code modulation when applied to (discrete-time) band-limited inputs. As the optimal trade-off for the latter scheme is fully understood, the full characterization for sigma-delta modulation, as well as the optimal feedback filters, immediately follows.

Consider a binary linear code of length N, minimum distance dmin, transmission over the binary erasure channel with parameter 00 if the minimum distance is large. In particular the width of the transition is of order O(1/√dmin). We strengthen this result by showing that under suitable conditions on the weight distribution of the code, the transition width can be as small as O(1/N1/2-κ), for any κ > 0, even if the minimum distance of the code is not linear. This condition applies e.g., to Reed-Mueller codes. Since O(1/N1/2) is the smallest transition possible for any code, we speak of “almost” optimal scaling. We emphasize that the width of the transition says nothing about the location of the transition. Therefore this result has no bearing on whether a code is capacity-achieving or not. As a second contribution, we present a new estimate on the derivative of the EXIT function, the proof of which is based on the Blowing-Up Lemma.

Two problems, namely multiple-description source coding and joint source-channel broadcasting of a common source, are addressed. For the multiple-description problem, we revisit Ozarow's technique for establishing impossibility results, and extend it to general sources and distortion measures. For the problem of sending a source over a broadcast channel, we revisit the bounding technique of Reznik, Feder and Zamir, and extend it to general sources, distortion measures and broadcast channels. Although the obtained bounds do not improve over existing results in the literature, they are relatively easy to evaluate, and their derivation reveals the similarities between the two bounding techniques.

Let Znbe iid Bernoulli (δ) and Unbe uniform on the set of all binary vectors of weight δn (Hamming sphere). As is well known, the entropies of Znand Unare within O(logn). However, if Xnis another binary random variable independent of Znand Un, we show that H(Xn+Un) and H(Xn+Zn) are within O(√n) and this estimate is tight. The bound is shown via coupling method. Tightness follows from the observation that the channels xn→ xn+Unand xn→ xn+Znhave similar capacities, but the former has zero dispersion. Finally, we show that despite the √n slack in general, the Mrs. Gerber Lemma for H(Xn+Un) holds with only an O(logn) correction compared to its brethren for H(Xn+Zn).

Suppose that Ynis obtained by observing a uniform Bernoulli random vector Xnthrough a binary symmetric channel with crossover probability α. The “most informative Boolean function” conjecture postulates that the maximal mutual information between Ynand any Boolean function b(Xn) is attained by a dictator function. In this paper, we consider the “complementary” case in which the Boolean function is replaced by f : {0, 1}n→ {0, 1}n-1, namely, an n - 1 bit quantizer, and show that I(f(Xn); Yn) ≤ (n - 1)·(1 - h(α)) for any such f. Thus, in this case, the optimal function is of the form f (xn) = (x1,..., xn-1).

Let X and Y be dependent random variables. We consider the problem of designing a scalar quantizer for Y to maximize the mutual information between its output and X, and study fundamental properties and bounds for this form of quantization. Our main focus is the regime of low I(X; Y), where we show that for a binary X, there always exists an M-level quantizer attaining mutual information of Ω(-M · I(X;Y)/log(I(X;Y)) and that there exist pairs of X, Y for which the mutual information attained by any M-level quantizer is O(-M · I (X;Y)/ log (I(X;Y))).

We consider an uncoordinated Gaussian multiple access channel with a relatively large number of active users within each block. A low complexity coding scheme is proposed, which is based on a combination of compute-and-forward and coding for a binary adder channel. For a wide regime of parameters of practical interest, the energy-per-bit required by each user in the proposed scheme is significantly smaller than that required by popular solutions such as slotted-ALOHA and treating interference as noise.

Recently, Samorodnitsky proved a strengthened version of Mrs. Gerber's Lemma, where the output entropy of a binary symmetric channel is bounded in terms of the average entropy of the input projected on a random subset of coordinates. Here, this result is applied for deriving novel lower bounds on the entropy rate of binary hidden Markov processes. For symmetric underlying Markov processes, our bound improves upon the best known bound in the very noisy regime. The nonsymmetric case is also considered, and explicit bounds are derived for Markov processes that satisfy the (1, ∞)-RLL constraint.

Suppose X is a uniformly distributed n-dimensional binary vector and Y is obtained by passing X through a binary symmetric channel with crossover probability α. A recent conjecture by Courtade and Kumar postulates that I(f(X); Y ) ≤ 1 - h(α) for any Boolean function f. So far, the best known upper bound was essentially I(f(X); Y ) ≤ (1 - 2α)2. In this paper, we derive a new upper bound that holds for all balanced functions, and improves upon the best known previous bound for α > 1 over 3.

Let $\mathcal{F}_1$ and $\mathcal{F}_2$ be two families of subsets of an $n$-element set. We say that $\mathcal{F}_1$ and $\mathcal{F}_2$ are multiset-union-free if for any $A,B\in \mathcal{F}_1$ and $C,D\in \mathcal{F}_2$ the multisets $A\uplus C$ and $B\uplus D$ are different, unless both $A = B$ and $C= D$. We derive a new upper bound on the maximal sizes of multiset-union-free pairs, improving a result of Urbanke and Li.

The mutual information between two jointly distributed random variables X and Y is a functional of the joint distribution PXY, which is sometimes difficult to handle or estimate. A coarser description of the statistical behavior of (X, Y) is given by the marginal distributions PX, PY and the adjacency relation induced by the joint distribution, where x and y are adjacent if P(x, y) > 0. We derive a lower bound on the mutual information in terms of these entities. The bound is obtained by viewing the channel from X to Y as a probability distribution on a set of possible actions, where an action determines the output for any possible input, and is independently drawn. We also provide an alternative proof based on convex optimization that yields a generally tighter bound. Finally, we derive an upper bound on the mutual information in terms of adjacency events between the action and the pair (X, Y), where in this case, an action a and a pair (x, y) are adjacent if y = a(x). As an example, we apply our bounds to the binary deletion channel and show that for the special case of an independent identically distributed input distribution and a range of deletion probabilities, our lower and upper bounds both outperform the best known bounds for the mutual information.

This paper provides a simplified proof for the existence of nested lattice codebooks allowing to achieve the capacity of the additive white Gaussian noise channel, as well as the optimal rate-distortion tradeoff for a Gaussian source. The proof is self-contained and relies only on basic probabilistic and geometrical arguments. An ensemble of nested lattices that is different, and more elementary, than the one used in the previous proofs is introduced. This ensemble is based on lifting different subcodes of a linear code to the Euclidean space using Construction A. In addition to being simpler, the analysis is less sensitive to the assumption that the additive noise is Gaussian. In particular, for additive ergodic noise channels, it is shown that the achievable rates of the nested lattice coding scheme depend on the noise distribution only via its power. Similarly, the nested lattice source coding scheme attains the same rate-distortion tradeoff for all ergodic sources with the same second moment.

Sampling above the Nyquist-rate is at the heart of sigma-delta modulation, where the increase in sampling rate is translated to a reduction in the overall (minimum mean-squared-error) reconstruction distortion. This is attained by using a feedback filter at the encoder, in conjunction with a low-pass filter at the decoder. The goal of this work is to characterize the optimal trade-off between the per-sample quantization rate and the resulting mean-squared-error distortion, under various restrictions on the feedback filter. To this end, we establish a duality relation between the performance of sigma-delta modulation, and that of differential pulse-code modulation when applied to (discrete-time) band-limited inputs. As the optimal trade-off for the latter scheme is fully understood, the full characterization for sigma-delta modulation, as well as the optimal feedback filters, immediately follow.

The binary adder is a two-user multiple access channel whose inputs are binary and whose output is the real sum of the inputs. While the Shannon capacity region of this channel is well known, little is known regarding its zero-error capacity region, and a large gap remains between the best inner and outer bounds. In this paper, we provide an improved outer bound for this problem. To that end, we introduce a soft variation of the Saur-Perles-Shelah Lemma, that is then used in conjunction with an outer bound for the Shannon capacity region with an additional common message.

We consider a Gaussian multiple-access channel where each user's message is identified with a vector of elements from a finite field, and the receiver's goal is to decode a linear combination of these finite field vectors. It is further assumed that each transmitter can causally observe the channel's output through a clean feedback link. We propose a novel coding scheme for this setup, which can be seen as an extension of the Cover-Leung scheme for the computation problem. This scheme is shown to achieve computation rates higher than the best known computation rates for the same scenario without feedback. In particular, for the symmetric two-user Gaussian multiple-access channel, the proposed scheme attains a symmetric computation rate greater than 1/2 log(3/4 + SNR).

A lossy source code C with rate R for a discrete memoryless source S is called subset-universal if for every 0nR'of its codewords achieves average distortion close to the source's distortion-rate function D(R'). In this paper we prove the asymptotic existence of such codes. Moreover, we show the asymptotic existence of a code that is subset-universal with respect to all sources with the same alphabet.

Mrs. Gerber's Lemma lower bounds the entropy at the output of a binary symmetric channel in terms of the entropy of the input process. In this paper, we lower bound the output entropy via a different measure of input uncertainty, pertaining to the minimum mean squared error prediction cost of the input process. We show that in many cases our bound is tighter than the one obtained from Mrs. Gerber's Lemma. As an application, we evaluate the bound for binary hidden Markov processes, and obtain new estimates for the entropy rate.

Integer-Forcing (IF) is a new framework, based on compute-and-forward, for decoding multiple integer linear combinations from the output of a Gaussian multiple-input multiple-output channel. This paper applies the IF approach to arrive at a new low-complexity scheme, IF source coding, for distributed lossy compression of correlated Gaussian sources under a minimum mean squared error distortion measure. All encoders use the same nested lattice codebook. Each encoder quantizes its observation using the fine lattice as a quantizer and reduces the result modulo the coarse lattice, which plays the role of binning. Rather than directly recovering the individual quantized signals, the decoder first recovers a full-rank set of judiciously chosen integer linear combinations of the quantized signals, and then inverts it. In general, the linear combinations have smaller average powers than the original signals. This allows to increase the density of the coarse lattice, which in turn translates to smaller compression rates. We also propose and analyze a one-shot version of IF source coding that is simple enough to potentially lead to a new design principle for analog-to-digital converters that can exploit spatial correlations between the sampled signals.

A channel can generally be defined by a probability distribution on a set of possible actions. These actions determine the output for any possible input, and are independently drawn. The intrinsic uncertainty of a channel is defined as the conditional entropy of the action given the input and output sequences. For many channels, such as the deletion channel, the insertion channel, and various permutation channels, e.g., the trapdoor channel, quantifying the intrinsic uncertainty is the main challenge in determining the capacity. In this paper, we derive an alternative expression for the intrinsic uncertainty via the Laplace variational principle, and utilize it to obtain a general lower bound for the capacity. As an example, we apply our bound to the binary deletion channel and show that for the special case of an i.i.d. input distribution and a range of deletion probabilities, it outperforms the best known lower bound for the mutual information.

Interference alignment has emerged as a powerful tool in the analysis of multiuser networks. Despite considerable recent progress, the capacity region of the Gaussian K-user interference channel is still unknown in general, in part due to the challenges associated with alignment on the signal scale using lattice codes. This paper develops a new framework for lattice interference alignment, based on the compute-and-forward approach. Within this framework, each receiver decodes by first recovering two or more linear combinations of the transmitted codewords with integer-valued coefficients and then solving these linear combinations for its desired codeword. For the special case of symmetric channel gains, this framework is used to derive the approximate sum capacity of the Gaussian interference channel, up to an explicitly defined outage set of the channel gains. The key contributions are the capacity lower bounds for the weak through strong interference regimes, where each receiver should jointly decode its own codeword along with part of the interfering codewords. As part of the analysis, it is shown that decoding K linear combinations of the codewords can approach the sum capacity of the K-user Gaussian multiple-access channel up to a gap of no more than K/2 log K bits.

An open-loop single-user multiple-input multiple-output communication scheme is considered where a transmitter, equipped with multiple antennas, encodes the data into independent streams all taken from the same linear code. The coded streams are then linearly precoded using the encoding matrix of a perfect linear dispersion space-time code. At the receiver side, integer-forcing equalization is applied, followed by standard single-stream decoding. It is shown that this communication architecture achieves the capacity of any Gaussian multiple-input multiple-output channel up to a gap that depends only on the number of transmit antennas.

A static (constant channel gains) realK-user interference channel is considered, where all interference (cross) channel gains are integers. For such channels, previous results demonstrate that the number of degrees of freedom is very sensitive to slight variations in the direct channel gains. In this paper, we derive an achievable rate region for such channels that is valid for finite SNR. At moderate values of SNR, the derived rate region is robust to slight variations in the direct channel gains. At asymptotic high SNR conditions, known results on the degrees of freedom are recovered. The new rate region is based on lattice interference alignment. The result is established via a new coding theorem for the two-user Gaussian multiple-access channel where both users use a single linear code.

We derive a new achievable sum rate for the symmetric Gaussian K-user interference channel. This sum rate is shown to be within a constant gap of the outer bound on the sum capacity of this channel for all values of interference level outside some outage set. The result is established through the use of lattice interference alignment. A new lattice-based extension to the Han-Kobayshi scheme is also introduced.

We derive an achievable rate region for the Gaussian K-user multiple-access channel (MAC) where all users transmit codewords from a chain of nested lattices. For any set of channel coefficients, this rate region contains points within a constant gap from the sum capacity boundary of the MAC. The main tool used is the recently proposed compute-and-forward framework. A new transformation of a MAC to a modulo-lattice multiple-input multiple-output (MIMO) channel is introduced based on this framework. Specifically, from one noisy linear combination of the transmitted signals the receiver attempts to decode K linearly independent equations with integer-valued coefficients. While the individual rates at which these equations can be decoded are highly sensitive to the exact channel gains, their sum is always within a constant gap from the sum capacity boundary of the MAC. The transformation is then utilized for establishing the desired rate region.

This work considers practical implementation of the decode-and-forward relaying protocol for the full-duplex Gaussian relay channel. Unlike previous works which developed coding techniques tailored to this protocol, it is shown that standard codes which are good for the Gaussian scalar channel of fixed signal-to-noise ratio suffice to approach the theoretical performance promised by this protocol. The proposed technique employs only linear operations and successive interference cancelation in conjunction with fixed signal-to-noise ratio base codes, and the achievable rate is solely dictated by the performance of these base codes. The same approach and results carry over to the multiple-antenna case as well.

A discrete-time intersymbol interference (ISI) channel with additive Gaussian noise is considered, where only the receiver has knowledge of the channel impulse response. An approach for combining decision-feedback equalization with channel coding is proposed, where decoding precedes the removal of ISI. The proposed approach involves equalizing the channel impulse response to a response with integer-valued coefficients in conjunction with utilizing cyclic block codes. Leveraging the property that a cyclic code is closed under cyclic integer-valued convolution allows us to perform decoding prior to applying decision feedback. Explicit bounds on the performance of the proposed scheme are derived.

The Compute-and-Forward approach has been proven to be very beneficial for communication over Gaussian networks. While the theoretical results are promising, it is still not completely understood how to best apply this scheme in practice. The objective of this work is to provide a low complexity scheme suitable for Compute-and-Forward. The scheme is based on utilizing linear codes over ℤqwhere q is not restricted to be prime and allows to achieve high transmission rates following Ungerboeck's set partitioning principle.

A time-invariant (constant channel gains) K-user interference channel is considered, where all interference (cross) channel gains are integers. For such channels, previous results demonstrate that the number of degrees of freedom is very sensitive to slight variations in the direct channel gains. In this paper we derive an achievable rate region for such channels which is valid for finite SNR. At moderate values of SNR the derived rate region is robust to slight variations in the direct channel gains. At asymptotic high SNR conditions, the known results on the degrees of freedom are recovered. The new rate region is based on lattice interference alignment. The result is established via a new coding theorem for the two-user Gaussian multiple-access channel where both users use a single linear code.