Let $\mathsf{TH}_k$ denote the $k$-out-of-$n$ threshold function: given $n$ input Boolean variables, the output is $1$ if and only if at least $k$ of the inputs are $1$. We consider the problem of computing the $\mathsf{TH}_k$ function using noisy readings of the Boolean variables, where each reading is incorrect with some fixed and known probability $p \in (0,1/2)$. As our main result, we show that it is sufficient to use $(1+o(1)) \frac{n\log \frac{m}{\delta}}{D_{\mathsf{KL}}(p \| 1-p)}$ queries in expectation to compute the $\mathsf{TH}_k$ function with a vanishing error probability $\delta = o(1)$, where $m\triangleq \min\{k,n-k+1\}$ and $D_{\mathsf{KL}}(p \| 1-p)$ denotes the Kullback-Leibler divergence between $\mathsf{Bern}(p)$ and $\mathsf{Bern}(1-p)$ distributions. Conversely, we show that any algorithm achieving an error probability of $\delta = o(1)$ necessitates at least $(1-o(1))\frac{(n-m)\log\frac{m}{\delta}}{D_{\mathsf{KL}}(p \| 1-p)}$ queries in expectation. The upper and lower bounds are tight when $m=o(n)$, and are within a multiplicative factor of $\frac{n}{n-m}$ when $m=\Theta(n)$. In particular, when $k=n/2$, the $\mathsf{TH}_k$ function corresponds to the $\mathsf{MAJORITY}$ function, in which case the upper and lower bounds are tight up to a multiplicative factor of two. Compared to previous work, our result tightens the dependence on $p$ in both the upper and lower bounds.

In this paper, we address the problem of human trajectory forecasting, which aims to predict the inherently multi-modal future movements of humans based on their past trajectories and other contextual cues. We propose a novel motion prediction conditional flow matching model, termed MoFlow, to predict K-shot future trajectories for all agents in a given scene. We design a novel flow matching loss function that not only ensures at least one of the K sets of future trajectories is accurate but also encourages all K sets of future trajectories to be diverse and plausible. Furthermore, by leveraging the implicit maximum likelihood estimation (IMLE), we propose a novel distillation method for flow models that only requires samples from the teacher model. Extensive experiments on the real-world datasets, including SportVU NBA games, ETH-UCY, and SDD, demonstrate that both our teacher flow model and the IMLE-distilled student model achieve state-of-the-art performance. These models can generate diverse trajectories that are physically and socially plausible. Moreover, our one-step student model is 100 times faster than the teacher flow model during sampling. The code, model, and data are available at our project page: https://moflow-imle.github.io/.

This paper presents a novel technique to design receive beamformers for on-grid angle-of-arrival (AoA) estimation in large-scale multiple-input multiple-output systems using channel codes. Specifically, the receive beamformers are designed so that the measurement model is effectively transformed to a Gaussian channel whose inputs are codewords in a channel code, with each codeword corresponding to a different AoA on the grid. Assuming that the number of antennas is larger than the desired angle resolution in the grid, the AoAs can be recovered by leveraging a suitable decoder on the resulting equivalent channel. The performance of the proposed method is derived in terms of the performance of the underlying channel code. Simulations results demonstrate the advantage of the proposed approach compared to existing beamforming strategies.

Reed-Muller (RM) codes are known to achieve capacity on binary symmetric channels (BSC) under the Maximum a Posteriori (MAP) decoder. However, it remains an open problem to design a capacity achieving polynomial-time RM decoder. Due to a lemma by Liu, Cuff, and Verdú, it can be shown that decoding by sampling from the posterior distribution is also capacity-achieving for RM codes over BSC. The Gibbs decoder is one such Markov Chain Monte Carlo (MCMC) based method, which samples from the posterior distribution by flipping message bits according to the posterior, and can be modified to give other MCMC decoding methods. In this paper, we analyze the mixing time of the Gibbs decoder for RM codes. Our analysis reveals that the Gibbs decoder can exhibit slow mixing for certain carefully constructed sequences. This slow mixing implies that, in the worst-case scenario, the decoder requires super-polynomial time to converge to the desired posterior distribution.

We study the Out-of-Distribution (OOD) generalization in machine learning and propose a general framework that establishes information-theoretic generalization bounds. Our framework interpolates freely between Integral Probability Metric (IPM) andf-divergence, which naturally recovers some known results (including Wasserstein- and KL-bounds), as well as yields new generalization bounds. Additionally, we show that our framework admits an optimal transport interpretation. When evaluated in two concrete examples, the proposed bounds either strictly improve upon existing bounds in some cases or match the best existing OOD generalization bounds. Moreover, by focusing onf-divergence and combining it with the Conditional Mutual Information (CMI) methods, we derive a family of CMI-based generalization bounds, which include the state-of-the-art ICIMI bound as a special instance. Finally, leveraging these findings, we analyze the generalization of the Stochastic Gradient Langevin Dynamics (SGLD) algorithm, showing that our derived generalization bounds outperform existing information-theoretic generalization bounds in certain scenarios.

Graph alignment refers to the task of finding the vertex correspondence between two correlated graphs ofnvertices. Extensive study has been done on polynomial-time algorithms for the graph alignment problem under the Erdős–Rényi graph pair model, where the two graphs are Erdős–Rényi graphs with edge probability$q_{\mathrm {u}}$, correlated under certain vertex correspondence. To achieve exact recovery of the correspondence, all existing algorithms at least require the edge correlation coefficient$\rho _{\mathrm {u}}$between the two graphs to benon-vanishingas$n\rightarrow \infty $. Moreover, it is conjectured that no polynomial-time algorithm can achieve exact recovery under vanishing edge correlation${\rho _{\mathrm {u}}}\lt 1/\mathrm {polylog}(n)$. In this paper, we show that with a vanishing amount of additionalattribute information, exact recovery is polynomial-time feasible undervanishingedge correlation${\rho _{\mathrm {u}}}\ge n^{-\Theta (1)}$. We identify alocaltree structure, which incorporates one layer of user information and one layer of attribute information, and apply the subgraph counting technique to such structures. A polynomial-time algorithm is proposed that recovers the vertex correspondence for most of the vertices, and then refines the output to achieve exact recovery. The consideration of attribute information is motivated by real-world applications like LinkedIn and Twitter, where user attributes like birthplace and education background can aid alignment.

Graph alignment refers to the task of finding the vertex correspondence between two correlated graphs of $n$ vertices. Extensive study has been done on polynomial-time algorithms for the graph alignment problem under the Erdős–Rényi graph pair model, where the two graphs are Erdős–Rényi graphs with edge probability $q_\mathrm{u}$, correlated under certain vertex correspondence. To achieve exact recovery of the correspondence, all existing algorithms at least require the edge correlation coefficient $\rho_\mathrm{u}$ between the two graphs to be \emph{non-vanishing} as $n\rightarrow\infty$. Moreover, it is conjectured that no polynomial-time algorithm can achieve exact recovery under vanishing edge correlation $\rho_\mathrm{u}<1/\mathrm{polylog}(n)$. In this paper, we show that with a vanishing amount of additional \emph{attribute information}, exact recovery is polynomial-time feasible under \emph{vanishing} edge correlation $\rho_\mathrm{u} \ge n^{-\Theta(1)}$. We identify a \emph{local} tree structure, which incorporates one layer of user information and one layer of attribute information, and apply the subgraph counting technique to such structures. A polynomial-time algorithm is proposed that recovers the vertex correspondence for most of the vertices, and then refines the output to achieve exact recovery. The consideration of attribute information is motivated by real-world applications like LinkedIn and Twitter, where user attributes like birthplace and education background can aid alignment.

Gradient coding is a distributed computing technique aiming to provide robustness against slow or non-responsive computing nodes, known as stragglers, while balancing the computational load for responsive computing nodes. Among existing gradient codes, a construction based on combinatorial designs, called BIBD gradient code, achieves the best trade-off between robustness and computational load in the worst-case adversarial straggler setting. However, the range of system parameters for which BIBD gradient codes exist is limited. In this paper, we overcome this limitation and propose a new probabilistic gradient code, termed Sparse Gaussian (SG) gradient code. The encoding matrix of the proposed SG gradient code is generated from a carefully chosen correlated multivariate Gaussian distribution, masked by Bernoulli random variables to reduce computational load. With high probability, the proposed gradient code achieves a similar worst-case error performance compared to the BIBD gradient code (when such a code of the same parameters exists) and outperforms several other existing gradient codes, including Fractional Repetition gradient codes and Bernoulli gradient codes. Moreover, it further extends the range of system parameters over existing BIBD and soft BIBD gradient codes, making it a promising solution for distributed computing tasks.

We study the Out-of-Distribution (OOD) generalization in machine learning and propose a general framework that provides information-theoretic generalization bounds. Our framework interpolates freely between Integral Probability Metric (IPM) and$f$-divergence, which naturally recovers some known results (including Wasserstein- and KL-bounds), as well as yields new generalization bounds. Moreover, we show that our framework admits an optimal transport interpretation. When evaluated in two concrete examples, the proposed bounds either strictly improve upon existing bounds in some cases or recover the best among existing OOD generalization bounds.

Motivated by the prevalent data science applications of processing large-scale graph data such as social networks and biological networks, this paper investigates lossless compression of data in the form of a labeled graph. Particularly, we consider a widely used random graph model, stochastic block model (SBM), which captures the clustering effects in social networks. An information-theoretic universal compression framework is applied, in which one aims to design a single compressor that achieves the asymptotically optimal compression rate, for every SBM distribution, without knowing the parameters of the SBM. Such a graph compressor is proposed in this paper, which universally achieves the optimal compression rate with polynomial time complexity for a wide class of SBMs. Existing universal compression techniques are developed mostly for stationary ergodic one-dimensional sequences. However, the adjacency matrix of SBM has complex two-dimensional correlations. The challenge is alleviated through a carefully designed transform that converts two-dimensional correlated data into almost i.i.d. submatrices. The sequence of submatrices is then compressed by a Krichevsky-Trofimov compressor, whose length analysis is generalized to identically distributed but arbitrarily correlated sequences. In four benchmark graph datasets, the compressed files from competing algorithms take 2.4 to 27 times the space needed by the proposed scheme.

Coding schemes for several problems in network information theory are constructed starting from point-to-point channel codes that are designed for symmetric channels. Given that the point-to-point codes satisfy certain properties pertaining to the rate, the error probability, and the distribution of decoded sequences, bounds on the performance of the coding schemes are derived and shown to hold irrespective of other properties of the codes. In particular, we consider the problems of lossless and lossy source coding, Slepian–Wolf coding, Wyner–Ziv coding, Berger–Tung coding, multiple description coding, asymmetric channel coding, Gelfand–Pinsker coding, coding for multiple access channels, Marton coding for broadcast channels, and coding for cloud radio access networks (C-RAN’s). We show that the coding schemes can achieve the best known inner bounds for these problems, provided that the constituent point-to-point channel codes are rate-optimal. This would allow one to leverage commercial off-the-shelf codes for point-to-point symmetric channels in the practical implementation of codes over networks. Simulation results demonstrate the gain of the proposed coding schemes compared to existing practical solutions to these problems.

Graph alignment aims at finding the vertex correspondence between two correlated graphs, a task that frequently occurs in graph mining applications such as social network analysis. Attributed graph alignment is a variant of graph alignment, in which publicly available side information or attributes are exploited to assist graph alignment. Existing studies on attributed graph alignment focus on either theoretical performance without computational constraints or empirical performance of efficient algorithms. This motivates us to investigate efficient algorithms with theoretical performance guarantee. In this paper, we propose two polynomial-time algorithms that exactly recover the vertex correspondence with high probability. The feasible region of the proposed algorithms is near optimal compared to the information-theoretic limits. When specialized to the seeded graph alignment problem under the seeded Erdős-Rényi graph pair model, the proposed algorithms extends the best known feasible region for exact alignment by polynomial-time algorithms.

Motivated by various data science applications including de-anonymizing user identities in social networks, we consider the graph alignment problem, where the goal is to identify the vertex/user correspondence between two correlated graphs. Existing work mostly recovers the correspondence by exploiting the user-user connections. However, in many real-world applications, additional information about the users, such as user profiles, might be publicly available. In this paper, we introduce the attributed graph alignment problem, where additional user information, referred to as attributes, is incorporated to assist graph alignment. We establish both the achievability and converse results on recovering vertex correspondence exactly, where the conditions match for certain parameter regimes. Our results span the full spectrum between models that only consider user-user connections and models where only attribute information is available.

PCR testing is an invaluable diagnostic tool that has most recently seen widespread use during the COVID-19 pandemic. A recent work by Wang, Gabrys and Vardy proposed tropical codes as a model for group PCR testing. For a known but arbitrary number of infected persons, a sufficient condition on the underlying block design of a zero-error tropical code, called double disjunction, is proposed. Despite this, the parameters for which the construction of doubly disjunct block designs is known to exist are very limited. In this paper, we define probabilistic tropical codes and consider random block designs that are doubly disjunct with high probability. We also provide a deterministic construction for a doubly disjunct block design given a disjunct block design. We show that for certain choices of parameters, our probabilistic construction has vanishing error. Our constructions, combined with existing methods, give us three different ways to construct tropical codes. We compare the number of tests required by each, and bounds on the error.

In this work, we study the problem of sorting n elements with pairwise comparisons under the presence of observation noise. We consider variable-length algorithms with a random number of queries M, and attempt to characterize the noisy sorting capacity defined as the maximal ratio $\frac{{n\log n}}{{{\text{E}}[M]}}$ such that the ordering can be correctly estimated with a vanishing error probability. This can be viewed as a generalization of the framework introduced in [1] to allow variable-length algorithms. We provide upper and lower bounds for the noisy sorting capacity. The proposed algorithm attaining the lower bound is based on the insertion sort algorithm for the sorting problem in the noiseless case and the variable-length version of the Burnashev–Zigangirov algorithm for coding over channels with feedback. Moreover, we also derive an upper bound on the maximal ratio that can be achieved by noisy sorting algorithms that are based on insertion sort.

We revisit the problem of computing with noisy information considered in Feige et al. [1], which includes computing the OR function from noisy queries, and computing the MAX, SEARCH, and SORT functions from noisy pairwise comparisons. For K given elements, the goal is to correctly recover the desired function with probability at least 1 – δ when the outcome of each query is flipped with probability p. We consider both the adaptive sampling setting where each query can be adaptively designed based on past outcomes, and the non-adaptive sampling setting where the query cannot depend on past outcomes. The prior work provides tight bounds on the worst-case query complexity in terms of the dependence on K. However, the upper and lower bounds do not match in terms of the dependence on δ and p. We improve the lower bounds for all the four functions under both adaptive and non-adaptive query models. Most of our lower bounds match the upper bounds up to constant factors when either p or δ is bounded away from 0, while the ratio between the best prior upper and lower bounds go to infinity when p → 0 or p → 1/2. On the other hand, we also provide matching upper and lower bounds for the number of queries in expectation, improving both the upper and lower bounds for variable-length query model.

Edge Computing (EC) offers a superior user experience by positioning cloud resources in close proximity to end users. The challenge of allocating edge resources efficiently while maximizing profit for the EC platform remains a sophisticated problem, especially with the added complexity of the online arrival of resource requests. To address this challenge, we propose to cast the problem as a multi-armed bandit problem and develop two novel online pricing mechanisms, the Kullback-Leibler Upper Confidence Bound (KL-UCB) algorithm and the Min-Max Optimal algorithm, for heterogeneous edge resource allocation. These mechanisms operate in real-time and do not require prior knowledge of demand distribution, which can be difficult to obtain in practice. The proposed posted pricing schemes allow users to select and pay for their preferred resources, with the platform dynamically adjusting resource prices based on observed historical data. Numerical results show the advantages of the proposed mechanisms compared to several benchmark schemes derived from traditional bandit algorithms, including the Epsilon-Greedy, basic UCB, and Thompson Sampling algorithms.

Sorting is the task of ordering n elements using pairwise comparisons. It is well known that$m=\Theta (n\log n)$comparisons are both necessary and sufficient when the outcomes of the comparisons are observed with no noise. In this paper, we study the sorting problem when each comparison is incorrect with some fixed yet unknown probability p. Unlike the common approach in the literature which aims to minimize the number of pairwise comparisons m to achieve a given desired error probability, we consider randomized algorithms with expected number of queries$\textsf {E}[M]$and aim at characterizing the maximal sorting rate$\frac {n\log n}{\mathop {\mathrm {\textsf {E}}}\nolimits [M]}$such that the ordering of the elements can be estimated with a vanishing error probability asymptotically. The maximal rate is referred to as the noisy sorting capacity. In this work, we derive upper and lower bounds on the noisy sorting capacity. The two lower bounds — one for fixed-length algorithms and one for variable-length algorithms — are established by combining the insertion sort algorithm with the well-known Burnashev-Zigangirov algorithm for channel coding with feedback. Compared with existing methods, the proposed algorithms are universal in the sense that they do not require the knowledge of p, while maintaining a strictly positive sorting rate. Moreover, we derive a general upper bound on the noisy sorting capacity, along with an upper bound on the maximal rate that can be achieved by sorting algorithms that are based on insertion sort.

Graph alignment aims at finding the vertex correspondence between two correlated graphs, a task that frequently occurs in graph mining applications such as social network analysis. Attributed graph alignment is a variant of graph alignment, in which publicly available side information or attributes are exploited to assist graph alignment. Existing studies on attributed graph alignment focus on either theoretical performance without computational constraints or empirical performance of efficient algorithms. This motivates us to investigate efficient algorithms with theoretical performance guarantee. In this paper, we propose two polynomial-time algorithms that exactly recover the vertex correspondence with high probability. The feasible region of the proposed algorithms is near optimal compared to the information-theoretic limits. When specialized to the seeded graph alignment problem, the proposed algorithms strictly improve the best known feasible region for exact alignment by polynomial-time algorithms.

Motivated by the prevalent data science applications of processing large-scale graph data such as social networks, web graphs, and biological networks, as well as the high I/O and communication costs of storing and transmitting such data, this paper investigates universal compression of data appearing in the form of a labeled graph. In particular, we consider a widely used random graph model, stochastic block model (SBM), which captures the clustering effects in social networks. A universal graph compressor is proposed, which achieves the optimal compression rate for a wide family of SBMs with edge probabilities from$O$(1) to Ω(1/$n$2-∊) for any 0 < ∊ < 1. Existing universal compression techniques are developed mostly for stationary ergodic one-dimensional sequences with entropy linear in the number of variables. However, the adjacency matrix of SBM has complex two-dimensional correlations and sublinear entropy in the sparse regime. These challenges are alleviated through a carefully designed transform that converts two-dimensional correlated data into almost i.i.d. blocks. The blocks are then compressed by a Krichevsky-Trofimov compressor, whose length analysis is generalized to arbitrarily correlated processes with identical marginals.

Coding schemes for asymmetric channels and channels with state are developed starting from a pair of linear codes designed for symmetric channels. Guarantees on the block error rate performance of the coding schemes are derived in terms of the parameters of the constituent codes. Assuming the constituent codes satisfy some properties on the rate, the error probability, and the distribution of the Hamming distance to decoded sequences, the performance guarantees hold irrespective of other properties of the codes. This would allow one to leverage commercial off-the-shelf codes for point-to-point symmetric channels to design codes for asymmetric channels and channels with state known noncausally at the encoder.

Motivated by various data science applications including de-anonymizing user identities in social networks, we consider the graph alignment problem, where the goal is to identify the vertex/user correspondence between two correlated graphs. Existing work mostly recovers the correspondence by exploiting the user-user connections. However, in many real-world applications, additional information about the users, such as user profiles, might be publicly available. In this paper, we introduce the attributed graph alignment problem, where additional user information, referred to as attributes, is incorporated to assist graph alignment. We establish sufficient and necessary conditions for recovering vertex correspondence exactly, where the conditions match for a wide range of practical regimes. Our results recover existing tight information-theoretic limits for models where only the user-user connections are available, and further span the full spectrum between these models and models where only attribute information is available.

We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences$U^{n}$and$V^{n}$respectively, drawn from a joint distribution$p_{UV}^ {\otimes n}$, and wish to locally generate sequences$X^{n}$and$Y^{n}$respectively with a joint distribution that is close (in KL divergence) to$p_{XY}^ {\otimes n}$. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between$U$and$V$is nonzero, and we conjecture that only scalar Markov chains$X-U-V-Y$can be simulated otherwise. Motivated by this conjecture, we further examine the case where both$p_{UV}$and$p_{XY}$are doubly symmetric binary sources with parameters$p,q\leq 1/2$respectively. While it is trivial that in this case$p\leq q$is both necessary and sufficient, we use Fourier analytic tools to show that when$p$is close to$q$then any successful simulation is close to being scalar in the total variation sense.

Codes are developed for two-user multiple access and broadcast channels starting from Gelfand-Pinsker codes with known block lengths, rates, and error performances. Guarantees are provided on the block error rates of the MAC and BC codes in terms of the parameters of the constituent Gelfand- Pinsker codes. These guarantees hold as long as the constituent codes satisfy the assumed properties on rate, codeword weights, and performances, irrespective of the basic structure and other properties.

A low-complexity coding scheme, termed as sliding-window Gelfand–Pinsker coding, is proposed. It is shown that in a general K-user broadcast channel, every rate point in the Marton’s inner bound can be achieved using single-user encoders and decoders. The scheme provides us with a low-complexity alternative to implement the conceptual K dimensional multi-coding, which is an irreplaceable component in many important network communication schemes, such as Marton coding in Gaussian MIMO broadcast channels and distributed decode–forward in cloud radio access networks, but has not been adopted in practical systems due to high computational complexity. Key features in the proposed scheme include staggered message scheduling, successive Gelfand–Pinsker coding, and sliding-window decoding.

A low-complexity coding scheme is developed to achieve the rate region of maximum likelihood decoding for interference channels. As in the classical rate-splitting multiple access scheme by Grant, Urbanke, and Whiting, the proposed coding scheme uses superposition of multiple codewords with successive cancellation decoding, which can be implemented using standard point-to-point encoders and decoders. Unlike rate-splitting multiple access, which is not rate-optimal for multiple receivers, the proposed coding scheme transmits codewords over multiple blocks in a staggered manner and recovers them successively over sliding decoding windows, achieving the single-stream optimal rate region as well as the more general Han–Kobayashi inner bound for the two-user interference channel. The feasibility of this scheme in practice is verified by implementing it using commercial channel codes over the two-user Gaussian interference channel.

A phase detection sequence is a length-n cyclic sequence such that the location of any length-k contiguous subsequence can be determined from a noisy observation of that subsequence. In this paper, we consider the problem of designing phase detection sequences that allow adaptive phase detection for different noise levels at the detector. We discuss two detection scenarios: depending on the noise level, the detector adaptively chooses the length k of the observation period, or adaptively chooses the detection resolution. We establish the optimal rate regions in both settings.

We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences Unand Vnrespectively, drawn from a joint distribution $p_{UV}^{\otimes n}$, and wish to locally generate sequences Xnand Ynrespectively with a joint distribution that is close (in KL divergence) to $p_{XY}^{\otimes n}$. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between U and V is nonzero, and we conjecture that only scalar Markov chains $X-U-V-Y$ can be simulated otherwise. Motivated by this conjecture, we further examine the case where both pUVand pXYare doubly symmetric binary sources with parameters $p, q\leq 1/2$ respectively. While it is trivial that in this case $p\leq q$ is both necessary and sufficient, we show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.

We introduce the notion of information ratio Ir(H/G) between two (simple, undirected) graphs G and H, which characterizes the maximal number of source symbols per channel use that can be reliably sent over a channel with confusion graph H, where reliability is measured w.r.t. a source confusion graph G. Many different results are provided, including in particular lower and upper bounds on Ir(H/G) in terms of various graph properties, inequalities and identities for behavior under strong product and disjoint union, relations to graph cores, and notions of graph criticality. Informally speaking, Ir(H/G) can be interpreted as a measure of similarity between G and H. We make this notion precise by introducing the concept of information equivalence between graphs, a more quantitative version of homomorphic equivalence. We then describe a natural partial ordering over the space of information equivalence classes, and endow it with a suitable metric structure that is contractive under the strong product. Various examples and intuitions are discussed.

We introduce the notion of information ratio Ir$(H/G)$ between two (simple, undirected) graphs $G$ and $H$, defined as the supremum of ratios $k/n$ such that there exists a mapping between the strong products $G^k$ to $H^n$ that preserves nonadjacency. Operationally speaking, the information ratio is the maximal number of source symbols per channel use that can be reliably sent over a channel with a confusion graph $H$, where reliability is measured w.r.t. a source confusion graph $G$. Various results are provided, including, in particular, lower and upper bounds on Ir$(H/G)$ in terms of different graph properties, inequalities, and identities for behavior under strong product and disjoint union, relations to graph cores, and notions of graph criticality. Informally speaking, Ir$(H/G)$ can be interpreted as a measure of similarity between $G$ and $H$. We make this notion precise by introducing the concept of information equivalence between graphs, a more quantitative version of homomorphic equivalence. We then describe a natural partial ordering over the space of information equivalence classes, and endow it with a suitable metric structure that is contractive under the strong product. Various examples and open problems are discussed.

A phase detection sequence is a length-n cyclic sequence, such that the location of any length-k contiguous subsequence can be determined from a noisy observation of that subsequence. In this paper, we derive bounds on the minimal possible k in the limit of n → ∞, and describe some sequence constructions. We further consider multiple phase detection sequences, where the location of any length-k contiguous subsequence of each sequence can be determined simultaneously from a noisy mixture of those subsequences. We study the optimal trade-offs between the lengths of the sequences, and describe some sequence constructions. We compare these phase detection problems to their natural channel coding counterparts, and show a strict separation between the fundamental limits in the multiple sequence case. Both adversarial and probabilistic noise models are addressed.

This paper studies the noncausal relay channel, also known as the relay channel with unlimited look ahead, introduced by by El Gamal, Hassanpour, and Mammen. Unlike the standard relay channel model, where the relay encodes its signal based on the previous received output symbols, the relay in the noncausal relay channel encodes its signal as a function of the entire received sequence. In the existing coding schemes, the relay uses this noncausal information solely to recover the transmitted message or part of it and then cooperates with the sender to communicate this message to the receiver. However, it is shown in this paper that by applying the Gelfand-Pinsker coding scheme, the relay can take further advantage of the noncausally available information and achieve rates strictly higher than those of the existing coding schemes. This paper also provides a new upper bound on the capacity of the noncausal relay channel that strictly improves upon the existing cutset bound. These new lower and upper bounds on the capacity coincide for the class of degraded noncausal relay channels and establish the capacity for this class.

We consider the problem of designing a length-n binary sequence, such that the location of any length-k contiguous subsequence can be determined from a noisy observation of that subsequence. We derive bounds on the minimal possible k in the limit of n → ∞, and describe some sequence constructions. Both adversarial and probabilistic noise models are addressed. Two applications of the problem include fast positioning and card tricks.

A method to polarize channels universally is introduced. The method is based on combining channels of unequal capacities in each polarization step, as opposed to the standard method of combining identical channels. The locations of the good and bad channels that emerge upon polarization are only a function of the polar transform chosen, and are otherwise independent of the channel being polarized. This yields a simple method to design universal polar codes for discrete memoryless channels. It is also shown that the less noisy ordering of channels is preserved under polarization, and thus, a good polar code for a given channel will perform well over a less noisy one.

The sliding-window superposition coding scheme aims to mitigate intercell interference at the physical layer by achieving the simultaneous decoding performance with point-to-point channel codes, low- complexity decoding, and minimal coordination overhead. The associated sliding-window coded modulation (SWCM) scheme can be readily implemented using standard off-the-shelf codes, such as the standard LTE turbo code, and tracks the information-theoretical performance guarantee of sliding-window superposition coding. This paper investigates how the basic SWCM scheme performs for the Ped-B fading interference channel model and proposes several improvements in transceiver design, such as soft decoding, input bit-mapping and layer optimization, and power control. Our enhanced SWCM scheme achieves the rates higher than those of the basic SWCM scheme by 10% to 20%, which already shows a significant gain over existing schemes that ignore modulation or coding information of interfering signals. This result confirms the potential of SWCM as a basic building block for physical-layer interference management in 5G and subsequent generations of cellular networks.

Polar coding schemes are developed for the decode-forward relaying (digital-to-digital interface) and the compress-forward relaying (analog-to-digital interface) in the three-node relay channel. For decode-forward, a technique based on the recent universal polarization method is applied to create the desired nested structure. For compress-forward, existing methods are generalized to allow arbitrary input distributions and channel statistics. Both schemes achieve full theoretical rates in general relay channels.

A method to polarize channels universally is introduced. The method is based on combining two distinct channels in each polarization step as opposed to Arikan's original method of combining identical channels. This creates an equal number of only two types of channels, one of which becomes progressively better as the other becomes worse. The locations of the good channels are independent of the underlying channel, guaranteeing universality at rate 1/2. The method is generalized to construct codes of arbitrary rates.

A polar coding scheme for interference networks is introduced. The scheme builds on Arikan's monotone chain rules for multiple access channels and a method by Hassani and Urbanke to “align” two incompatible polarization processes. It achieves the Han-Kobayashi inner bound for two-user interference channels and generalizes to interference networks.

Superposition coding with successive cancellation decoding for interference channels is investigated as a low-complexity alternative to the rate-optimal simultaneous decoding. It is shown that regardless of the number of superposition layers and the code distribution of each layer, the standard rate-splitting scheme by Grant, Rimoldi, Urbanke, and Whiting for multiple access channels fails to achieve the simultaneous decoding inner bound on the capacity region for interference channels. A new coding scheme is proposed that uses coding over multiple blocks and sliding-window decoding. With at most two superposition layers, this scheme achieves the simultaneous decoding inner bound for any two-user-pair interference channels without using high-complexity simultaneous multiuser sequence detection. The proposed coding scheme can be also extended to achieve the performance of simultaneous decoding for general interference networks, including the Han-Kobayashi inner bound.

A new inner bound on the capacity region of the general index coding problem is established. Unlike most existing bounds that are based on graph theoretic or algebraic tools, the bound relies on a random coding scheme and optimal decoding, and has a simple polymatroidal single-letter expression. The utility of the inner bound is demonstrated by examples that include the capacity region for all index coding problems with up to five messages (there are 9846 nonisomorphic ones).

There are two variants of superposition coding schemes. Cover's original superposition coding scheme has code clouds of identical shape, while Bergmans's superposition coding scheme has code clouds of independently generated shapes. These two schemes yield identical achievable rate regions in several scenarios, such as the capacity region for degraded broadcast channels. This paper shows that under optimal decoding, these two superposition coding schemes can result in different rate regions. In particular, it is shown that for the two-receiver broadcast channel, Cover's scheme achieves a larger rate region than Bergmans's scheme in general.

Write-once memory (WOM) is a binary storage medium in which each memory cell is initially in state 0 and can be irreversibly programmed to state 1. This paper studies the problem of writing multiple messages into a WOM. Instead of writing a new message (and obliterating old ones) as in the traditional setup, the user wishes to retain access to some of the previously written messages. The capacity region is studied and code constructions are proposed for three canonical cases.

Motivated by the emerging interests in non-volatile solid-state computer memories such as flash memories, this paper studies the problem of repeatedly storing information on memory cells with noise and state. The goal is to reliably convey t messages by writing Xjjon an n-cell noisy memory p(yj|xj, yj−1), which stores Yjnat the j-th write. We model this problem as a channel with state and introduce the multiple-write noisy memory model, which includes the write-once memory and flash memory models as special cases. The t-write sum-capacity for the multiple-write noisy memory is established as equation where the maximum is over all pmfs p(x1) Пjt=2 p(uj|yj−1) and functions xj(uj, yj−1), j = 2, …, t. We derive three outer bounds on the capacity region and discuss their extension to other classes of memory models. These results extend Wolf, Wyner, Ziv, and Körner's work on the binary write-once memory and Fu and Vinck's work on the generalized write-once memory to noisy memories.

This paper studies the noncausal relay channel, also known as the relay channel with unlimited lookahead, introduced by El Gamal, Hassanpour, and Mammen. Unlike the standard relay channel model, where the relay encodes its signal based on the previous received output symbols, the relay in the noncausal relay channel encodes its signal as a function of the entire received sequence. In the existing coding schemes, the relay uses this noncausal information solely to recover the transmitted message and then cooperates with the sender to communicate this message to the receiver. However, it is shown in this paper that by applying the Gelfand-Pinsker coding scheme, the relay can take further advantage of the noncausally available information, which can achieve strictly higher rates than existing coding schemes. This paper also provides a new upper bound on the capacity of the noncausal relay that strictly improves upon the cutset bound. These new lower and upper bounds on the capacity coincide for the class of degraded noncausal relay channels and establish the capacity for this class.

H.264/AVC scalable video coding (SVC) is an upto-date video compression standard. This paper deals with the issue of transmitting H.264 scalable video bitstreams over wireless fading channels. The contribution is twofold: Firstly, to exploit the importance of prioritized video packets in different temporal layer, quality layer and group of pictures (GOP), a simple and accurate performance metric, namely, layer-GOP-weighted expected zone of error propagation (LGW-EZEP) model is proposed. Secondly, a joint power control and forward error correction (FEC) unequal error protection (UEP) scheme is proposed to transmit the video streams over orthogonal frequency division multiplexing (OFDM) systems efficiently and robustly. Meanwhile, a new iterative algorithm is given to solve the joint optimization problem. Compared to other independent power control or FEC UEP schemes, the combined protecting scheme demonstrates stronger robustness and flexibility via various fading channels.