Multi-index models provide a popular framework to investigate the learnability of functions with low-dimensional structure and, also due to their connections with neural networks, they have been object of recent intensive study. In this paper, we focus on recovering the subspace spanned by the signals via spectral estimators – a family of methods routinely used in practice, often as a warm-start for iterative algorithms. Our main technical contribution is a precise asymptotic characterization of the performance of spectral methods, when sample size and input dimension grow proportionally and the dimension $p$ of the space to recover is fixed. Specifically, we locate the top-$p$ eigenvalues of the spectral matrix and establish the overlaps between the corresponding eigenvectors (which give the spectral estimators) and a basis of the signal subspace. Our analysis unveils a phase transition phenomenon in which, as the sample complexity grows, eigenvalues escape from the bulk of the spectrum and, when that happens, eigenvectors recover directions of the desired subspace. The precise characterization we put forward enables the optimization of the data preprocessing, thus allowing to identify the spectral estimator that requires the minimal sample size for weak recovery.

In this work, we consider the list-decodability and list-recoverability of codes in the zero-rate regime. Briefly, a code $\mathcal{C} \subseteq [q]^n$ is $(p,\ell,L)$-list-recoverable if for all tuples of input lists $(Y_1,\dots,Y_n)$ with each $Y_i \subseteq [q]$ and $|Y_i|=\ell$ the number of codewords $c \in \mathcal{C}$ such that $c_i \notin Y_i$ for at most $pn$ choices of $i \in [n]$ is less than $L$; list-decoding is the special case of $\ell=1$. In recent work by Resch, Yuan and Zhang~(ICALP~2023) the zero-rate threshold for list-recovery was determined for all parameters: that is, the work explicitly computes $p_*:=p_*(q,\ell,L)$ with the property that for all $ε>0$ (a) there exist infinite families positive-rate $(p_*-ε,\ell,L)$-list-recoverable codes, and (b) any $(p_*+ε,\ell,L)$-list-recoverable code has rate $0$. In fact, in the latter case the code has constant size, independent on $n$. However, the constant size in their work is quite large in $1/ε$, at least $|\mathcal{C}|\geq (\frac{1}ε)^{O(q^L)}$. Our contribution in this work is to show that for all choices of $q,\ell$ and $L$ with $q \geq 3$, any $(p_*+ε,\ell,L)$-list-recoverable code must have size $O_{q,\ell,L}(1/ε)$, and furthermore this upper bound is complemented by a matching lower bound $Ω_{q,\ell,L}(1/ε)$. This greatly generalizes work by Alon, Bukh and Polyanskiy~(IEEE Trans.\ Inf.\ Theory~2018) which focused only on the case of binary alphabet (and thus necessarily only list-decoding). We remark that we can in fact recover the same result for $q=2$ and even $L$, as obtained by Alon, Bukh and Polyanskiy: we thus strictly generalize their work.

In an arbitrarily varying channel (AVC), the channel has a state which is under the control of an adversarial jammer and the corresponding capacities are often functions of the “power” constraints on the transmitter and jammer. In this paper we propose a model in which the constraints must hold almost surely over contiguous subsequences of the codeword and state, which we call a sliding window constraint. We study oblivious jammers and codes with stochastic encoding under maximum probability of error. We show that this extra limitation on the jammer is beneficial for the transmitter: in some cases, the capacity for unique decoding with a sliding window constraint is equal to the capacity for list decoding in the standard model without sliding windows, roughly implying that the addition of window constraints reduces list decoding to unique decoding. The list decoding capacity in the standard model can be strictly larger than the unique decoding capacity.

This work provides a framework for the design of codes for zero-error information theory problems via superposition coding and suitable expurgation processes. For the Hamming metric, the proposed code construction meets the Gilbert-Varshamov bound via a different construction/analysis than the folklore uniformly random ensemble usually considered in the literature.

We consider the problem of parameter estimation in a high-dimensional generalized linear model. Spectral methods obtained via the principal eigenvector of a suitable data-dependent matrix provide a simple yet surprisingly effective solution. However, despite their wide use, a rigorous performance characterization, as well as a principled way to preprocess the data, are available only for unstructured (i.i.d. Gaussian and Haar orthogonal) designs. In contrast, real-world data matrices are highly structured and exhibit non-trivial correlations. To address the problem, we consider correlated Gaussian designs capturing the anisotropic nature of the features via a covariance matrix $\Sigma$. Our main result is a precise asymptotic characterization of the performance of spectral estimators. This allows us to identify the optimal preprocessing that minimizes the number of samples needed for parameter estimation. Surprisingly, such preprocessing is universal across a broad set of statistical models, which partly addresses a conjecture on optimal spectral estimators for rotationally invariant designs. Our principled approach vastly improves upon previous heuristic methods, including for designs common in computational imaging and genetics. The proposed methodology, based on approximate message passing, is broadly applicable and opens the way to the precise characterization of spiked matrices and of the corresponding spectral methods in a variety of settings.

We study the matrix denoising problem of estimating the singular vectors of a rank-$1$ signal corrupted by noise with both column and row correlations. Existing works are either unable to pinpoint the exact asymptotic estimation error or, when they do so, the resulting approaches (e.g., based on whitening or singular value shrinkage) remain vastly suboptimal. On top of this, most of the literature has focused on the special case of estimating the left singular vector of the signal when the noise only possesses row correlation (one-sided heteroscedasticity). In contrast, our work establishes the information-theoretic and algorithmic limits of matrix denoising with doubly heteroscedastic noise. We characterize the exact asymptotic minimum mean square error, and design a novel spectral estimator with rigorous optimality guarantees: under a technical condition, it attains positive correlation with the signals whenever information-theoretically possible and, for one-sided heteroscedasticity, it also achieves the Bayes-optimal error. Numerical experiments demonstrate the significant advantage of our theoretically principled method with the state of the art. The proofs draw connections with statistical physics and approximate message passing, departing drastically from standard random matrix theory techniques.

In this work we consider the list-decodability and list-recoverability of arbitrary q-ary codes, for all integer values of$q\geq 2$. A code is called$(p,L)_{q}$-list-decodable if every radius pn Hamming ball contains less than L codewords;$(p,\ell ,L)_{q}$-list-recoverability is a generalization where we place radius pn Hamming balls on every point of a combinatorial rectangle with side length$\ell $and again stipulate that there be less than L codewords. Our main contribution is to precisely calculate the maximum value of p for which there exist infinite families of positive rate$(p,\ell ,L)_{q}$-list-recoverable codes, the quantity we call the zero-rate threshold. Denoting this value by$p_{*}$, we in fact show that codes correcting a$p_{*}+\varepsilon $fraction of errors must have size$O_{\varepsilon }(1)$, i.e., independent of n. Such a result is typically referred to as a “Plotkin bound.” To complement this, a standard random code with expurgation construction shows that there exist positive rate codes correcting a$p_{*}-\varepsilon $fraction of errors. We also follow a classical proof template (typically attributed to Elias and Bassalygo) to derive from the zero-rate threshold other tradeoffs between rate and decoding radius for list-decoding and list-recovery. Technically, proving the Plotkin bound boils down to demonstrating the Schur convexity of a certain function defined on the q-simplex as well as the convexity of a univariate function derived from it. We remark that an earlier argument claimed similar results for q-ary list-decoding; however, we point out that this earlier proof is flawed.

We derive lower bounds on the maximal rates for multiple packings in high-dimensional Euclidean spaces. For any$ N > 0 $and$ L\in \mathbb {Z}_{\ge 2} $, a multiple packing is a set$\mathcal {C}$of points in$ \mathbb {R}^{n} $such that any point in$ \mathbb {R}^{n} $lies in the intersection of at most$ L-1 $balls of radius$ \sqrt {nN} $around points in$ \mathcal {C} $. This is a natural generalization of the sphere packing problem. We study the multiple packing problem for both bounded point sets whose points have norm at most$\sqrt {nP}$for some constant$P > 0$, and unbounded point sets whose points are allowed to be anywhere in$ \mathbb {R}^{n} $. Given a well-known connection with coding theory, multiple packings can be viewed as the Euclidean analog of list-decodable codes, which are well-studied over finite fields. We derive the best known lower bounds on the optimal multiple packing density. This is accomplished by establishing an inequality which relates the list-decoding error exponent for additive white Gaussian noise channels, a quantity of average-case nature, to the list-decoding radius, a quantity of worst-case nature. We also derive novel bounds on the list-decoding error exponent for infinite constellations and closed-form expressions for the list-decoding error exponents for the power-constrained AWGN channel, which may be of independent interest beyond multiple packing.

In this work we consider the list-decodability and list-recoverability of arbitrary q-ary codes, for all integer values of q ≥ 2. A code is called (p,L)_q-list-decodable if every radius pn Hamming ball contains less than L codewords; (p,,L)_q-list-recoverability is a generalization where we place radius pn Hamming balls on every point of a combinatorial rectangle with side length and again stipulate that there be less than L codewords. Our main contribution is to precisely calculate the maximum value of p for which there exist infinite families of positive rate (p,,L)_q-list-recoverable codes, the quantity we call the zero-rate threshold. Denoting this value by p_*, we in fact show that codes correcting a p_*+ε fraction of errors must have size O_ε(1), i.e., independent of n. Such a result is typically referred to as a "Plotkin bound." To complement this, a standard random code with expurgation construction shows that there exist positive rate codes correcting a p_*-ε fraction of errors. We also follow a classical proof template (typically attributed to Elias and Bassalygo) to derive from the zero-rate threshold other tradeoffs between rate and decoding radius for list-decoding and list-recovery. Technically, proving the Plotkin bound boils down to demonstrating the Schur convexity of a certain function defined on the q-simplex as well as the convexity of a univariate function derived from it. We remark that an earlier argument claimed similar results for q-ary list-decoding; however, we point out that this earlier proof is flawed.

This paper is a collection of results on combinatorial properties of codes for the Z-channel. A Z-channel with error fraction$\tau $takes as input a length-$n$binary codeword and injects in an adversarial manner up to$n\tau $asymmetric errors, i.e., errors that only zero out bits but do not flip 0’s to 1’s. It is known that the largest$(L-1)$-list-decodable code for the Z-channel with error fraction$\tau $has exponential size (in$n$) if$\tau $is less than a critical value that we call the$(L-1)$-list-decoding Plotkin point and has constant size if$\tau $is larger than the threshold. The$(L-1)$-list-decoding Plotkin point is known to be$L^{-({1}/{L-1})} - L^{-({L}/{L-1})} $, which equals 1/4 for unique-decoding with$L-1=1 $. In this paper, we derive various results for the size of the largest codes above and below the list-decoding Plotkin point. In particular, we show that the largest$(L-1)$-list-decodable code$\varepsilon $-above the Plotkin point, for any given sufficiently small positive constant$\varepsilon >0 $, has size$\Theta _{L}(\varepsilon ^{-3/2})$for any$L-1\ge 1$. We also devise upper and lower bounds on the exponential size of codes below the list-decoding Plotkin point.

We consider zero-error communication over a two-transmitter deterministic adversarial multiple access channel (MAC) governed by an adversary who has access to the transmissions of both senders (hence calledomniscient) and aims to maliciously corrupt the communication. None of the encoders, jammer and decoder is allowed to randomize using private or public randomness. This enforces a combinatorial nature of the problem. Our model covers a large family of channels studied in the literature, including all deterministic discrete memoryless noisy or noiseless MACs. In this work, given an arbitrary two-transmitter deterministic omniscient adversarial MAC, we characterize when the capacity region: 1) has nonempty interior (in particular, is two-dimensional); 2) consists of two line segments (in particular, has empty interior); 3) consists of one line segment (in particular, is one-dimensional); 4) or only contains (0,0) (in particular, is zero-dimensional). This extends a recent result by Wang et al. (201 9) from the point-to-point setting to the multiple access setting. Indeed, our converse arguments build upon their generalized Plotkin bound and involve delicate case analysis. One of the technical challenges is to take care of both “joint confusability” and “marginal confusability”. In particular, the treatment of marginal confusability doesnotfollow from the point-to-point results by Wang et al. Our achievability results follow from random coding with expurgation.

We study the problem of high-dimensional multiple packing in Euclidean space. Multiple packing is a natural generalization of sphere packing and is defined as follows. Let$N>0 $and$L\in \mathbb {Z}_{\ge 2} $. A multiple packing is a set$\mathcal {C}$of points in$\mathbb {R}^{n} $such that any point in$\mathbb {R}^{n} $lies in the intersection of at most$L-1 $balls of radius$\sqrt {nN} $around points in$\mathcal {C} $. Given a well-known connection with coding theory, multiple packings can be viewed as the Euclidean analog of list-decodable codes, which are well-studied for finite fields. In this paper, we derive the best known lower bounds on the optimal density of list-decodable infinite constellations for constant$L$under a stronger notion called average-radius multiple packing. To this end, we apply tools from high-dimensional geometry and large deviation theory.

We consider the problem of communication over adversarial channels with feedback. Two parties comprising sender Alice and receiver Bob seek to communicate reliably. An adversary James observes Alice's channel transmission entirely and chooses, maliciously, its additive channel input or jamming state thereby corrupting Bob's observation. Bob can communicate over a one-way reverse link with Alice; we assume that transmissions over this feedback link cannot be corrupted by James. Our goal in this work is to study the optimum throughput or capacity over such channels with feedback. We first present results for the quadratically-constrained additive channel where communication is known to be impossible when the noise-to-signal (power) ratio (NSR) is at least 1. We present a novel achievability scheme to establish that positive rate communication is possible even when the NSR is as high as 8/9. We also present new converse upper bounds on the capacity of this channel under potentially stochastic encoders and decoders. We also study feedback communication over the more widely studied q-ary alphabet channel under additive noise. For the q -ary channel, where q > 2, it is well known that capacity is positive under full feedback if and only if the adversary can corrupt strictly less than half the transmitted symbols. We generalize this result and show that the same threshold holds for positive rate communication when the noiseless feedback may only be partial; our scheme employs a stochastic decoder. We extend this characterization, albeit partially, to fully deterministic schemes under partial noiseless feedback. We also present new converse upper bounds for q-ary channels under full feedback, where the encoder and/or decoder may privately randomize. Our converse results bring to the fore an interesting alternate expression for the well known converse bound for the q—ary channel under full feedback which, when specialized to the binary channel, also equals its known capacity.

This paper studies combinatorial properties of codes for the Z-channel. A Z-channel with error fraction τ takes as input a length-n binary codeword and injects in an adversarial manner up to nτ asymmetric errors, i.e., errors that only zero out bits but do not flip 0’s to 1’s. It is known that the largest (L − 1)-list-decodable code for the Z-channel with error fraction τ has exponential (in n) size if τ is less than a critical value that we call the Plotkin point and has constant size if τ is larger than the threshold. The (L−1)-list-decoding Plotkin point is known to be ${L^{ - \frac{1}{{L - 1}}}} - {L^{ - \frac{L}{{L - 1}}}}$. In this paper, we show that the largest (L−1)-list-decodable code ε-above the Plotkin point has size ΘL(ε−3/2) for any L − 1 ≥ 1.

In the classic adversarial communication problem, two parties communicate over a noisy channel in the presence of a malicious jamming adversary. The arbitrarily varying channels (AVCs) offer an elegant framework to study a wide range of interesting adversary models. The optimal throughput or capacity over such AVCs is intimately tied to the underlying adversary model; in some cases, capacity is unknown and the problem is known to be notoriously hard. The omniscient adversary, one which knows the sender’s entire channel transmission a priori, is one of such classic models of interest; the capacity under such an adversary remains an exciting open problem. The myopic adversary is a generalization of that model where the adversary’s observation may be corrupted over a noisy discrete memoryless channel. Through the adversary’s myopicity, one can unify the slew of different adversary models, ranging from the omniscient adversary to one that is completely blind to the transmission (the latter is the well known oblivious model where the capacity is fully characterized).In this work, we present new results on the capacity under both the omniscient and myopic adversary models. We completely characterize the positive capacity threshold over general AVCs with omniscient adversaries. The characterization is in terms of two key combinatorial objects: the set of completely positive distributions and the CP-confusability set. For omniscient AVCs with positive capacity, we present non-trivial lower and upper bounds on the capacity; unlike some of the previous bounds, our bounds hold under fairly general input and jamming constraints. Our lower bound improves upon the generalized Gilbert-Varshamov bound for general AVCs while the upper bound generalizes the well known Elias-Bassalygo bound (known for binary and q-ary alphabets). For the myopic AVCs, we build on prior results known for the so-called sufficiently myopic model, and present new results on the positive rate communication threshold over the so-called insufficiently myopic regime (a completely insufficient myopic adversary specializes to an omniscient adversary). We present interesting examples for the widely studied models of adversarial bit-flip and bit-erasure channels. In fact, for the bit-flip AVC with additive adversarial noise as well as random noise, we completely characterize the omniscient model capacity when the random noise is sufficiently large vis-a-vis the adversary’s budget.

We characterize the capacity for the discrete-time arbitrarily varying channel with discrete inputs, outputs, and states when (a) the encoder and decoder do not share common randomness, (b) the input and state are subject to cost constraints, (c) the transition matrix of the channel is deterministic given the state, and (d) at each time step the adversary can only observe the current and past channel inputs when choosing the state at that time. The achievable strategy involves stochastic encoding together with list decoding and a disambiguation step. The converse uses a two-phase "babble-and-push" strategy where the adversary chooses the state randomly in the first phase, list decodes the output, and then chooses state inputs to symmetrize the channel in the second phase. These results generalize prior work on specific channels models (additive, erasure) to general discrete alphabets and models.

We study the problem of characterizing the maximal rates of list decoding in Euclidean spaces for finite list sizes. For any positive integer L ≥ 2 and real N > 0, we say that a subset $\mathcal{C} \subset {\mathbb{R}^n}$ is an (N,L – 1)-multiple packing or an (N,L– 1)-list decodable code if every Euclidean ball of radius $\sqrt {nN} $ in ℝncontains no more than L − 1 points of C. We study this problem with and without ℓ2norm constraints on $\mathcal{C}$, and derive the best-known lower bounds on the maximal rate for (N,L−1) multiple packing. Our bounds are obtained via error exponents for list decoding over Additive White Gaussian Noise (AWGN) channels. We establish a curious inequality which relates the error exponent, a quantity of average-case nature, to the list-decoding radius, a quantity of worst-case nature. We derive various bounds on the error exponent for list decoding in both bounded and unbounded settings which could be of independent interest beyond multiple packing.

We study the problem of high-dimensional multiple packing in Euclidean space. Multiple packing is a natural generalization of sphere packing and is defined as follows. Let N > 0 and $L \in {\mathbb{Z}} \geq 2$. A multiple packing is a set ${\mathcal{C}}$ of points in ${{\mathbb{R}}^n}$ such that any point in ${{\mathbb{R}}^n}$ lies in the intersection of at most L – 1 balls of radius $\sqrt {nN} $ around points in ${\mathcal{C}}$. Given a well-known connection with coding theory, multiple packings can be viewed as the Euclidean analog of list-decodable codes, which are well-studied for finite fields. In this paper, we exactly pin down the asymptotic density of (expurgated) Poisson Point Processes under a stronger notion called average-radius multiple packing. To this end, we apply tools from high-dimensional geometry and large deviation theory. This gives rise to the best known lower bound on the largest multiple packing density. Our result corrects a mistake in a previous paper by Blinovsky [Bli05].

We study the problem of high-dimensional multiple packing in Euclidean space. Multiple packing is a natural generalization of sphere packing and is defined as follows. Let P, N > 0 and $L \in {{\mathbb{Z}}_{ \geq 2}}$. A multiple packing is a set ${\mathcal{C}}$ of points in ${{\mathcal{B}}^n}(\underline{0} ,\sqrt {nP} )$ such that any point in ℝnlies in the intersection of at most L – 1 balls of radius $\sqrt {nN} $ around points in ${\mathcal{C}}$.1In this paper, we derive two lower bounds on the largest possible density of a multiple packing. These bounds are obtained through a stronger notion called average-radius multiple packing. Specifically, we exactly pin down the asymptotics of (expurgated) Gaussian codes and (expurgated) spherical codes under average-radius multiple packing. To this end, we apply tools from high-dimensional geometry and large deviation theory. The bound for spherical codes matches the previous best known bound which was obtained for the standard (weaker) notion of multiple packing through a curious connection with error exponents [Bli99], [ZV21]. The bound for Gaussian codes suggests that they are strictly inferior to spherical codes.

We consider a high-dimensional mean estimation problem over a binary hidden Markov model, which illuminates the interplay between memory in data, sample size, dimension, and signal strength in statistical inference. In this model, an estimator observes $n$ samples of a $d$-dimensional parameter vector $\theta_{*}\in\mathbb{R}^{d}$, multiplied by a random sign $ S_i $ ($1\le i\le n$), and corrupted by isotropic standard Gaussian noise. The sequence of signs $\{S_{i}\}_{i\in[n]}\in\{-1,1\}^{n}$ is drawn from a stationary homogeneous Markov chain with flip probability $\delta\in[0,1/2]$. As $\delta$ varies, this model smoothly interpolates two well-studied models: the Gaussian Location Model for which $\delta=0$ and the Gaussian Mixture Model for which $\delta=1/2$. Assuming that the estimator knows $\delta$, we establish a nearly minimax optimal (up to logarithmic factors) estimation error rate, as a function of $\|\theta_{*}\|,\delta,d,n$. We then provide an upper bound to the case of estimating $\delta$, assuming a (possibly inaccurate) knowledge of $\theta_{*}$. The bound is proved to be tight when $\theta_{*}$ is an accurately known constant. These results are then combined to an algorithm which estimates $\theta_{*}$ with $\delta$ unknown a priori, and theoretical guarantees on its error are stated.

We study the list decodability of different ensembles of codes over the real alphabet under the assumption of an omniscient adversary. It is a well-known result that when the source and the adversary have power constraints$P $and$N $respectively, the list decoding capacity is equal to$\frac {1}{2}\log \frac {P}{N}$. Random spherical codes achieve constant list sizes, and the goal of the present paper is to obtain a better understanding of the smallest achievable list size as a function of the gap to capacity. We show a reduction from arbitrary codes to spherical codes, and derive a lower bound on the list size of typical random spherical codes. We also give an upper bound on the list size achievable using nested Construction-A lattices and infinite Construction-A lattices. We then define and study a class of infinite constellations that generalize Construction-A lattices and prove upper and lower bounds for the same. Other goodness properties such as packing goodness and AWGN goodness of infinite constellations are proved along the way. Finally, we consider random lattices sampled from the Haar distribution and show that if a certain conjecture that originates in analytic number theory is true, then the list size grows as a polynomial function of the gap-to-capacity.

We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is allowed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding or stochastic encoding, i.e., with no common randomness between the encoder/decoder pair. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most$2\log (n)$bits in one sub-regime, and at most$\Omega ({n})$bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques involve a novel myopic list-decoding result for achievability, and a Plotkin-type push attack for the converse in a subregion of the NSRs, both of which may be of independent interest. We also give bounds on the strong secrecy capacity of this channel assuming that the jammer is simultaneously eavesdropping.

We consider the problem of reliable communication over a network containing a hidden myopic adversary who can eavesdrop on some Zrolinks, jam some Zwolinks, and do both on some Zrwlinks. We provide the first information-theoretically tight characterization of the optimal rate of reliable communication possible under all possible settings of the tuple (Zro, Zwo, Zrw) by providing a novel coding scheme/analysis for a subset of parameter regimes. In particular, by leveraging the adversary's uncertainty on unobserved links our vanishing-error schemes bypass the Network Singleton Bound (which requires a zero-error recovery criteria) in a certain parameter regime where the capacity had been heretofore open. As a direct corollary we also obtain the capacity of the corresponding problem where information-theoretic secrecy against eavesdropping is required in addition to reliable communication.

We consider zero-error communication over a two-transmitter deterministic adversarial multiple access channel (MAC) governed by an adversary who has access to the transmissions of both senders (hence called omniscient) and aims to maliciously corrupt the communication. None of the encoders, jammer and decoder is allowed to randomize using private or public randomness. This enforces a combinatorial nature of the problem. Our model covers a large family of channels studied in the literature, including all deterministic discrete memoryless noisy or noiseless MACs. In this work, given an arbitrary two-transmitter deterministic omniscient adversarial MAC, we characterize when the capacity region 1)has nonempty interior (in particular, is two-dimensional); 2)consists of two line segments (in particular, has empty interior); 3)consists of one line segment (in particular, is one-dimensional); 4)or only contains (0, 0) (in particular, is zero-dimensional). This extends a recent result by Wang, Budkuley, Bogdanov and Jaggi (2019) from the point-to-point setting to the multiple access setting. Indeed, our converse arguments build upon their generalized Plotkin bound and involve delicate case analysis. One of the technical challenges is to take care of both “joint confusability” and “marginal confusability”. In particular, the treatment of marginal confusability does not follow from the point-to-point results by Wang et al. Our achievability results follow from random coding with expurgation.

We study list-decoding over adversarial channels governed by oblivious adversaries (a.k.a. oblivious Arbitrarily Varying Channels (AVCs)). This type of adversaries aims to maliciously corrupt the communication without knowing the actual transmission from the sender. For any oblivious AVCs potentially with constraints on the sender's transmitted sequence and the adversary's noise sequence, we determine the exact value of the minimum list-size that can support a reliable communication at positive rate. This generalizes a classical result by Hughes (IEEE Transactions on Information Theory, 1997) and answers an open question posed by Sarwate and Gastpar (IEEE Transactions on Information Theory, 2012). A lower bound on the list-decoding capacity (whenever positive) is presented. Under a certain combinatorial conjecture, we also prove a matching upper bound. En route to a tight characterization of the list-decoding capacity, we propose a method for subcode construction towards the resolution of the combinatorial conjecture.

This paper concerns itself with the question of list decoding for general adversarial channels, e.g., bit-flip ($\textsf{XOR}$) channels, erasure channels, $\textsf{AND}$ ($Z$-) channels, $\textsf{OR}$ channels, real adder channels, noisy typewriter channels, etc. We precisely characterize when exponential-sized (or positive rate) $(L-1)$-list decodable codes (where the list size $L$ is a universal constant) exist for such channels. Our criterion asserts that: "For any given general adversarial channel, it is possible to construct positive rate $(L-1)$-list decodable codes if and only if the set of completely positive tensors of order-$L$ with admissible marginals is not entirely contained in the order-$L$ confusability set associated to the channel." The sufficiency is shown via random code construction (combined with expurgation or time-sharing). The necessity is shown by 1. extracting equicoupled subcodes (generalization of equidistant code) from any large code sequence using hypergraph Ramsey's theorem, and 2. significantly extending the classic Plotkin bound in coding theory to list decoding for general channels using duality between the completely positive tensor cone and the copositive tensor cone. In the proof, we also obtain a new fact regarding asymmetry of joint distributions, which be may of independent interest. Other results include 1. List decoding capacity with asymptotically large $L$ for general adversarial channels; 2. A tight list size bound for most constant composition codes (generalization of constant weight codes); 3. Rederivation and demystification of Blinovsky's [Bli86] characterization of the list decoding Plotkin points (threshold at which large codes are impossible); 4. Evaluation of general bounds ([WBBJ]) for unique decoding in the error correction code setting.

In this article, we revisit the classical problem of channel coding and obtain novel results on properties of capacity- achieving codes. Specifically, we give a linear algebraic characterization of the set of capacity-achieving input distributions for discrete memoryless channels. This allows us to characterize the dimension of the manifold on which the capacity-achieving distributions lie. We then proceed by examining empirical properties of capacity-achieving codebooks by showing that the joint-type of k-tuples of codewords in a good code must be close to the k- fold product of the capacity-achieving input distribution. While this conforms with the intuition that all capacity-achieving codes must behave like random capacity-achieving codes, we also show that some properties of random coding ensembles do not hold for all codes. We prove this by showing that there exist pairs of communication problems such that random code ensembles simultaneously attain capacities of both problems, but certain (superposition ensembles) do not.Due to lack of space, several proofs have been omitted but can be found at https://sites.google.com/view/yihan/ [1]

A covering code is a subset C ⊆ {0, 1}nwith the property that any z E {0, 1}nis close to some c E C in Hamming distance. For every c, δ > 0, we show a construction of a family of codes with relative covering radius δ+ε and rate 1-H(δ) with block length at most exp(O((1/c) log(1/c))) for every c> 0. This improves upon a folklore construction which only guaranteed codes of block length exp(1/ε2). The main idea behind this proof is to find a distribution on codes with relatively small support such that most of these codes have good covering properties.

This paper provides inner and outer bounds on list sizes of list decoding for two-user oblivious arbitrarily varying multiple access channels (AVMACs). An oblivious AVMAC consists of two users who wish to transmit messages (without cooperation) to a remote receiver, a malicious jammer who only has access to the codebooks of both users (which are also known to every party), and a receiver who is required to decode the message pair sent by both users. The transmitters send codewords which encode messages subject to input constraints. The jammer, without knowing the transmitted codeword pair, injects adversarial noise subject to state constraints so as to actively corrupt the communication from both users to the receiver. It was left as an open question in [Cai16] to nail down the smallest list sizes for constrained AVMACs. Our inner and outer bounds are based on a judicious notion of symmetrizability for AVMACs introduced by [Cai16] with twists to incorporate input and state constraints. The analysis follows techniques by Csiszár and Narayan [CN88]. When no constraints are imposed,́ our bound collapse to prior results by Cai [Cai16] which characterized the list-decoding capacity region of unconstrained AVMACs. Techniques used in this paper can also be extended to the Gaussian case and we characterize the list-decoding capacity region of Gaussian AVMACs. The converse argument relies on a bounding technique recently used by Hosseinigoki and Kosut [HK19]. The full version of this paper is [Zha20].

We study achievable rates of reliable communication in a power-constrained two-way additive interference channel over the real alphabet where communication is disrupted by a power-constrained jammer. This models the wireless communication scenario where two users Alice and Bob, operating in the full duplex mode, wish to exchange messages with each other in the presence of a jammer, James. Alice and Bob simultaneously transmit their encodings xAand xBover n channel uses. It is assumed that James can choose his jamming signal s as a noncausal randomized function of xA+ xB, and the codebooks used by Alice and Bob. Alice and Bob observe xA+ xB+ s, and must recover each others' messages reliably. In this article, we provide upper and lower bounds on the capacity of this channel which match each other and equal 1/2 log (1/2 + SNR) in the high-SNR regime (where SNR, signal to noise ratios, is defined as the ratio of the power constraints of the users to the power constraint of the jammer). We give a code construction based on lattice codes, and derive achievable rates for large SNR. We also present upper bounds based on two specific attack strategies for James. Along the way, sumset property of lattices for the achievability and general properties of capacity-achieving codes for memoryless channels for the converse are proved, which might be of independent interest. The full version of this paper is [1].

We study the list decodability of different ensembles of codes over the real alphabet under the assumption of an omniscient adversary. It is a well-known result that when the source and the adversary have power constraints P and N respectively, the list decoding capacity is equal to z log Ñ. Random spherical codes achieve capacity with constant (as a function of the blocklength) list sizes, and the goal of the present paper is to obtain a better understanding of the smallest achievable list size as a function of the gap to capacity. We show a reduction from arbitrary codes to spherical codes, and derive a lower bound on the list size of typical random spherical codes. We also give an upper bound on the list size achievable using nested Construction-A lattices and infinite Construction-A lattices. We then define and study a class of infinite constellations that generalize Construction-A lattices and prove upper and lower bounds for the same. Other goodness properties such as packing goodness and AWGN goodness of infinite constellations are proved along the way. Finally, we consider random lattices sampled from the Haar distribution and show that if a certain number-theoretic conjecture is true, then the list size grows as a polynomial function of the gap-to-capacity.

We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is assumed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most O(log(n)) bits in one sub-regime, and at most O(n) bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques include a novel myopic list-decoding result for achievability and a Plotkin-type push attack for the converse in a subregion of the NSRs, which may be of independent interest.