Reliability of sequential hypothesis testing can be greatly improved when the decision maker is given the freedom to adaptively take an action that determines the distribution of the current collected sample. Such advantage of sampling adaptivity has been realized since Chernoff’s seminal paper in 1959 [1]. While a large body of works have explored and investigated the gain of adaptivity, in the general multiple-hypothesis setting, the fundamental limits of individual error probabilities have not been fully understood. In particular, in the asymptotic regime as the expected stopping time tends to infinity, the error exponents are only characterized in specific cases, such as that of the total error probability. In this paper, we consider a general setup of active sequential multiple-hypothesis testing where at each time slot, a temporally varying subset of data sources (out of a known set) emerges from which the decision maker can select to collect samples, subject to a family of expected selection budget constraints. The selection of sources, understood as the “action” at each time slot, is constrained in a predefined action space. At the end of each time slot, the decision maker either decides to make the inference on theMhypotheses, or continues to observe the data sources for the next time slot. The optimal tradeoffs amongM(M– 1) types of error exponents are characterized. A companion asymptotically optimal test that strikes the balance between exploration and exploitation is proposed to achieve any target error exponents within the region. To the best of our knowledge, this is the first time in the literature to identify such tradeoffs among error exponents in active sequential hypothesis testing, and it uncovers the tension among different action taking policies even in the basic setting of Chernoff [1].

Fundamental limits on the error probabilities of a family of decentralized detection algorithms (e.g., the social learning rule proposed by Lalitha et al., 2018) over directed graphs are investigated. In decentralized detection, a network of nodes locally exchanging information about the samples they observe with their neighbors to collectively infer the underlying unknown hypothesis. Each node in the network weighs the messages received from its neighbors to form its private belief and only requires knowledge of the data generating distribution of its observation. In this work, it is first shown that while the original social learning rule of Lalitha et al., 2018 achieves asymptotically vanishing error probabilities as the number of samples tends to infinity, it suffers a gap in the achievable error exponent compared to the centralized case. The gap is due to the network imbalance caused by the local weights that each node chooses to weigh the messages received from its neighbors. To close this gap, a modified learning rule is proposed and shown to achieve error exponents as large as those in the centralized setup. This implies that there is essentially no first-order penalty caused by decentralization in the exponentially decaying rate of error probabilities. To elucidate the price of decentralization, further analysis on the higher-order asymptotics of the error probability is conducted. It turns out that the price is at most a constant multiplicative factor in the error probability, equivalent to an$o(1/t)$additive gap in the error exponent, wheretis the number of samples observed by each agent in the network and the number of rounds of information exchange. This constant depends on the network connectivity and captures the level of network imbalance. Results of simulation on the error probability supporting our learning rule are shown. Further discussions and extensions of results are also presented.

In the binary hypothesis testing problem, it is well known that sequentiality in taking samples eradicates the trade-off between two error exponents, yet implementing the optimal test requires the knowledge of the underlying distributions, sayP0andP1. In the scenario where the knowledge of distributions is replaced by empirically observed statistics from the respective distributions, the gain of sequentiality is less understood when subject to universality constraints over all possibleP0;P1. In this work, the gap is mended by a unified study on sequentiality in the universal binary classification problem, where the universality constraints are set on the expected stopping time as well as the type-I error exponent. The type-I error exponent is required to achieve a pre-set distribution-dependent constraint λ(P0,P1) for allP0;P1. Under the proposed framework, different sequential setups are investigated so that fair comparisons can be made with the fixed-length counterpart. By viewing these sequential classification problems as special cases of a general sequential composite hypothesis testing problem, the optimal type-II error exponents are characterized. Specifically, in the general sequential composite hypothesis testing problem subject to universality constraints, upper and lower bounds on the type-II error exponent are proved, and a sufficient condition for which the bounds coincide is given. The results for sequential classification problems are then obtained accordingly. With the characterization of the optimal error exponents, the benefit of sequentiality is shown both analytically and numerically by comparing the sequential and the fixed-length cases in representative examples of type-I exponent constraint λ.

Streaming codestake a string of source symbols as input and output a string of coded symbols in real time, which eliminate the queueing delay of traditionalblock codesand are thus especially appealing for delay sensitive applications. This work studies the asymptotics of random linear streaming codes (RLSCs) in the large finite-field-size regime under the i.i.d. symbol erasure channel models. Two important scenarios are analyzed: (i) tradeoff between decoding deadline Δ and probability of errorpeassuming infinite memory α = ∞; and (ii) tradeoff between α andpeassuming infinite Δ = ∞. For each scenario, this work derives the corresponding asymptotic constant ρ, power β and decay rate η that satisfype(x) ∼ ρxβe−ηx. The results of (i) and (ii) are then used to study an important code design problem: Under a given target deadline Δ, what is the memory length α needed for the error probabilitypeto be within a factor ofc> 1 of the best possiblep∗eover α. Further analysis also suggests that regardless thecvalue being considered, the necessary memory length is approximately 3–7% of the target deadline Δ when Δ is large, the actual percentage depending on the channel model and the coding rate. Such a prediction is consistent with existing brute-force-based evaluations.

Reliability of sequential hypothesis testing can be greatly improved when decision maker is given the freedom to adaptively take an action that determines the distribution of the current collected sample. Such advantage of sampling adaptivity has been realized since Chernoff's seminal paper in 1959 [1]. While a large body of works have explored and investigated the gain of adaptivity, in the general multiple-hypothesis setting, the fundamental limits of individual error probabilities have not been fully understood. In particular, in the asymptotic regime as the expected stopping time tends to infinity, the error exponents are only characterized in specific cases, such as that of the total error probability. In this paper, we consider a general setup of active sequential multiple-hypothesis testing where at each time slot, a temporally varying subset of data sources (out of a known set) emerges from which the decision maker can select to collect samples, subject to expected selection budget constraints. The selection of sources, understood as the “action” at each time slot, is constrained in a predefined action space. At the end of each time slot, the decision maker either decides to make the inference on the$\rfloor\psi$hypotheses, or continues to observe the data sources for the next time slot. The optimal tradeoffs among$M(M-1)$types of error exponents are characterized, and the achievable region is shown to be a convex polytope. A companion asymptotically optimal test that strikes the balance between exploration and exploitation is proposed to achieve any target error exponents within the region. To the best of our knowledge, this is the first time in the literature to identify such tradeoffs among error exponents, and it uncovers the tension among different action taking policies even in the basic setting of Chernoff [1].

In hypothesis testing problems, taking samples sequentially and stopping opportunistically to make the inference greatly enhances the reliability. The design of the stopping and inference policy, however, critically relies on the knowledge of the underlying distribution of each hypothesis. When the knowledge of distributions, say,$P_{0}$and$P_{1}$in the binary-hypothesis case, is replaced by empirically observed statistics from the respective distributions, the gain of sequentiality is less understood when subject to universality constraints. In this work, the gap is mended by a unified study on sequentiality in the universal binary classification problem. We propose a unified framework where the universality constraints are set on the expected stopping time as well as the type-I error exponent. The type-I error exponent is required to achieve a pre-set distribution-dependent constraint$\lambda(P_{0}, P_{1})$for all$P_{0}, P_{1}$. The framework is employed to investigate a semi-sequential and a fully-sequential setup, so that fair comparison can be made with the fixed-length setup. The optimal type-II error exponents in different setups are characterized when the function$\lambda$satisfies mild continuity conditions. The benefit of sequentiality is shown by comparing the semi-sequential, the fully-sequential, and the fixed-length cases in representative examples of$\lambda$. Conditions under which sequentiality eradicates the trade-off between error exponents are also derived.

In this work, fundamental limits and optimal mechanisms of privacy-preserving data release that aims to minimize the privacy leakage under utility constraints of a set of multiple tasks are investigated. While the private feature to be protected is typically determined and known by the sanitizer, the target task is usually unknown. To address the lack of information on the specific task, utility constraints laid on a set of multiple possible tasks are considered. The mechanism protects the specific privacy feature of the to-be-released data while satisfying utility constraints of all possible tasks in the set. First, the single-letter characterization of the rate-leakage-distortion region is derived, where the utility of each task is measured by a distortion function. It turns out that the minimum privacy leakage problem with log-loss distortion constraints and the unconstrained released rate is a non-convex optimization problem. Second, focusing on the case where the raw data consists of multiple independent components, we show that the above non-convex optimization problem can be decomposed into multiple parallel privacy funnel (PF) problems with different weightings. We explicitly derive the optimal solution to each PF problem when the private feature is a component-wise deterministic function of a data vector. The solution is characterized by a leakage-free threshold: when the utility constraint is below the threshold, the minimum leakage is zero; once the required utility level is above the threshold, the privacy leakage increases linearly. Finally, we show that the optimal weighting of each privacy funnel problem can be found by solving a linear program (LP). A sufficient released rate to achieve the minimum leakage is also derived. Numerical results are shown to illustrate the robustness of our approach against the task non-specificity.

The benefit of single-user state feedback for secret communication over the two-user broadcast packet erasure channel is investigated. Without feedback, Wyner's seminal result implied that only the stronger user has strictly positive secret communication rate. When both users can feedback receiver state information to the transmitter, Czap et al. characterized the capacity region for secret communication and showed that both users can achieve strictly positive rates. Such significant gain is due to the dual role of feedback: on one hand, it helps each receiver to agree a key with the transmitter while keeping it secret from the other user; on the other hand, it provides the opportunity for multicast network coding as in the non-secret case by Georgiadis and Tassiulas. When one of the two receivers does not feedback, however, it is unclear how the single-user feedback helps secret communication for the non-feedback user. In this work, it is shown that with single-user feedback, even if the non-feedback user has a weaker transmitter-receiver link, a strictly positive secret communication rate is achievable. Furthermore, when the non-feedback user has a stronger transmitter-receiver link, its achievable rate is strictly larger than the wiretap channel capacity. The result is based on a novel scheme that utilizes the single-user feedback for three purposes: to generate a secret key for the feedback user, to create a randomizer for wiretap-channel coset coding of the non-feedback user, and to facilitate opportunistic network coding for side information exploitation without further secrecy leakage.

Streaming codes eliminate the queueing delay and are an appealing candidate for low latency communications. This work studies the tradeoff between error probability peand decoding deadline ∆ of infinite-memory random linear streaming codes (RLSCs) over i.i.d. symbol erasure channels (SECs). The contributions include (i) Proving pe(∆) ∼ ρ∆−1.5e−η∆. The asymptotic power term ∆−1.5of RLSCs is a strict improvement over the ∆−0.5term of random linear block codes; (ii) Deriving a pair of upper and lower bounds on the asymptotic constant ρ, which are tight (i.e., identical) for one specific class of SECs; (iii) For any c > 1 and any decoding deadline ∆, the c-optimal memory length $\alpha _c^{\ast}(\Delta )$ is defined as the minimal memory length α needed for the resulting peto be within a factor of c of the best possible $p_e^{\ast}$ under any α, an important piece of information for practical implementation. This work studies and derives new properties of $\alpha _c^{\ast}(\Delta )$ based on the newly developed asymptotics.

Federated learning is a nascent framework for collaborative machine learning over networks of devices with local data and local model updates. Data heterogeneity across the devices is one of the challenges confronting this emerging field. Personalization is a natural approach to simultaneously utilize information from the other users’ data and take data heterogeneity into account. In this work, we study the linear regression problem where the data across users are generated from different regression vectors. We present an information-theoretic lower bound of the minimax expected excess risk of personalized linear models. We show an upper bound that matches the lower bound within constant factors. The results characterize the effect of data heterogeneity on learning performance and the trade-off between sample size, problem difficulty, and distribution discrepancy, suggesting that the discrepancy-to-difficulty ratio is the key factor governing the effectiveness of heterogeneous data.

Channel dispersion quantifies the convergence speed of coding rate to channel capacity under different latency constraints. Under the setting of packet erasure channels (PECs) with Bernoulli packet arrivals, this work characterizes the channel dispersions of random linear streaming codes (RLSCs) and MDS block codes, respectively. New techniques are developed to quantify the channel dispersion of sequential (non-block-based) coding, the first in the literature. The channel dispersion expressions are then used to compare the levels of error protection between RLSCs and MDS block codes. The results show that if and only if the target error probability peis smaller than a threshold (≈0.1774), RLSCs offer strictly stronger error protection than MDS block codes, which is on top of the already significant 50% latency savings of RLSCs that eliminate the queueing delay completely.

The focus of this paper is on binary classification of a sequentially observed stream of i.i.d. samples, based on sequentially observed empirical statistics. The decision maker (classifier) sequentially observes a sequence of testing data i.i.d. sampled from one of two unknown distributions P0and P1. In addition, it receives two sequences of training data which are also sequentially sampled from the two unknown distributions in an i.i.d. fashion, respectively. Since the distributions are unknown, it is natural to put a constraint either on the expected stopping times or on the error probabilities that has to be satisfied universally over all possible pairs of distributions (P0, P1). For both settings, we develop tests that are asymptotically optimal within the class of tests that satisfy the respective universality constraints. For expected-stopping-time universality, the optimal error exponents are shown to be the Rényi divergences of order $\frac{\alpha }{{1 + \alpha }}$, where α is the ratio of the length of a training data sequence to that of the testing data sequence. For error-probability universality, the optimal expected stopping times normalized by the logarithm of the error probability are the reciprocal of the α-weighted generalized Jensen-Shannon (GJS) divergences. The proposed sequential tests are both based on threshold tests of two statistics, each of which is the α-weighted GJS divergences of the type of the testing sequence from that of a training sequence. Interestingly, to achieve asymptotic optimality, the stopping and decision rules in the two different universality setups take a "matching" and a "discriminating" viewpoint respectively in designing the threshold tests.

Streaming codestake a string of source symbols as input and output a string of coded symbols in real time, which eliminate the queueing delay of traditionalblock codesand are thus especially appealing for delay sensitive applications. Existing works on streaming code performance either focused on the asymptotic error-exponent analyses, or on the optimal code construction underdeterministic adversarial channel models. In contrast, this work analyzes the exact error probability ofrandom linear streaming codes(RLSCs) in the large field size regime over the stochastic i.i.d. symbol erasure channel model. A closed-form expression of the error probability of large-field-size RLSCs is derived under, simultaneously, the finite memory length and decoding deadline constraints. The result is then used to examine the intricate tradeoff between memory length (complexity), decoding deadline (delay), code rate (throughput), and error probability (reliability). Numerical evaluation shows that under the same code rate and error probability requirements, the end-to-end delay of RLSCs is 40–48% of that of the optimal block codes (i.e., MDS codes). This implies that switching from block codes to streaming codes not only eliminates the queueing delay completely (which accounts for the initial 50% of the delay reduction) but also improves the reliability (which accounts for the additional 2–10% delay reduction).

The problem of computing the modulo-sum of independent messages over a finite-field erasure multiple access channel is investigated. The focus is on the role of delayed state feedback for function computation over state dependent multiple access channels. For the two-user case, a set of new outer bounds on the non-feedback computation capacity region are developed, which strictly improve the state of the art by Khistiet al., 2013. As a result, a previously unsettled question is answered in the affirmative: delayed state feedback strictly increases computation capacity for the two-user erasure multiple access channel universally. The proof leverages the subset entropy inequalities by Madiman and Tetali, 2010, Jianget al., 2014, and submodularity of conditional entropies. For the achievability part of the non-feedback case, an achievable computation rate region is derived by generalizing the proposed schemes in Khistiet al., 2013. Beyond the two-user case, the$K$-user case is also investigated, with emphasis on the large system regime, where$K$is the number of users. For the non-feedback case, we propose a grouping scheme which has higher computation rate than that of the conventional “compute-and-forward” (CF) scheme. Furthermore, with a growing number of users, the proposed grouping scheme strictly outperforms the conventional “decode-and-forward (DF)” scheme when the erasure probability is smaller than$1-e^{\frac {1}{e}}\approx 0.3078$. This is in contrast to the two-user case where the currently best known achievability (Khistiet al., 2013) coincides with the better one betweenDFandCF. For the case with delayed state feedback, a new hybrid-ARQ-type scheme is proposed, and in the large system regime, it achieves a computation rate scaling like$\Omega \left({\frac {1}{\log (K)}}\right)$, much higher than the scaling$\Theta \left({\frac {1}{K}}\right)$achieved by the grouping scheme without feedback.

In this paper, the joint clustering and ranking problem is studied. Assume that there are items that belong to several communities and are compared in a pairwise manner repeatedly. The task is to identify the community each item belongs to and to give a consistent preference ordering of the items in each community. A statistical model called “Cluster-BTL” is proposed to model the difference between inter-community and intra-community comparisons. Such a difference is called “heterogeneity” throughout this paper, and we are interested in how the heterogeneity level affects the joint clustering and ranking problem. In this work, we characterize the fundamental limit on the heterogeneity level and the number of comparisons for reliable joint clustering and ranking. The converse part is proved by a Fano-type argument. For the achievability part, a polynomial-time algorithm that combines the Borda counting algorithm and the SDP based method is developed.

Sequential binary hypothesis testing from temporally heterogeneously generated random samples with an active decision maker under budget constraints is considered. The problem is motivated from applications in crowdsourced classification and sequential detection from sensory data in IoT networks. In such applications, at each time slot, the source of data may vary from time to time, and the decision on the two possible hypotheses is to be made in a reliable, fast, and cost effective manner. In particular, the active decision maker either takes the current source and collects a sample, or skips the current source and waits for the next time slot. At the end of each time slot, the decision maker either decides to claim the decision on the two hypotheses, or continues to observe the data source for the next time slot. The goal is to design action taking and decision making policies so that the probability of error is minimized under two constraints: one on the total number of samples collected by the decision maker, and the other is on the total number of time slots. In this work, the available data source changes among$n$possible ones i.i.d. over time, and the two constraints are in expectation. We establish the optimal error exponents of the two types of error probabilities as the two constraints tend to infinity with a fixed proportion. For achievability, a scheme that combines a sequential probability ratio test and an adaptive randomized policy that dynamically switches between two sets of accepting probabilities of the current source, according to the observed samples collected so far, is proposed. Matching upper bounds on the error exponents are developed using data processing inequality and Doob's Optional Stopping Theorem.

Motivated by the applications for low-delay communication networks, the finite-length analysis, or channel dispersion identification, of the multi-user channel is very important. Recent studies also incorporate the effects of feedback in point-to-point and common-message broadcast channels (BCs). However, with private messages and feedback, finite-length results for BCs are much more scarce. Though it is known that feedback can strictly enlarge the capacity, the ultimate feedback capacity regions remain unknown for even some classical channels including Gaussian BCs. In this work, we study the two-user broadcast packet erasure channel (PEC) with causal feedback, which is one of the cleanest feedback capacity results and the capacity region can be achieved by elegant linear network coding (LNC). We first derive a new finite-length outer bound for any LNCs and then accompanying inner bound by analyzing a three-phase LNC. For the outer-bound, we adopt a linear-space-based framework, which can successfully find the LNC capacity. However, naively applying this method in finite-length regime will result in a loose outer bound. Thus a new bounding technique based on carefully labelling each time slot according to the type of LNC transmitted is proposed. Simulation results show that the sum-rate gap between our inner and outer bounds is within 0.02 bits/channel use. Asymptotic analysis also shows that our bounds bracket the channel dispersion of LNC feedback capacity for broadcast PEC to within a factor of Q-l (E/2)/Q-l (E).

Streaming codes take a string of source symbols as input and output a string of coded symbols in real time, which effectively eliminate the queueing delay and are regarded as a promising scheme for low latency communications. Aiming at quantifying the fundamental latency performance of random linear streaming codes (RLSCs) over i.i.d. symbol erasure channels, this work derives the exact error probability under, simultaneously, the finite memory length and finite decoding deadline constraints. The result is then used to examine the tradeoff among memory length (complexity), decoding deadline (delay), and error probability (reliability) of RLSCs for the first time in the literature. Two critical observations are made: (i) Too much memory can adversely impact the performance under a finite decoding deadline constraint, a surprising finding not captured by the traditional wisdom that large memory length monotonically improves the performance in the asymptotic regime; (ii) The end-to-end delay of the RLSC is roughly 50% of that of the MDS block code when under identical code rate and error probability requirements. This implies that switching from block codes to RLSCs not only eliminates the queueing delay (thus 50%) but also has little negative impact on the error probability.

With the recent emergence of many low-latency applications over wireless networks, the need for accurate finite-length analysis of channel coding over multi-user wireless channels is ever increasing. This paper focuses exclusively on the two-user broadcast packet erasure channel (PEC) with causal feedback, for which existing results show that various linear network coding (LNC) schemes can attain the broadcast capacity region when the block length approaches infinity. Instead of the asymptotic capacity-based analysis, this work derives the exact value of the LNC-based broadcast channel dispersion. Our approach is based on a new explicit characterization of the optimal LNC scheme under any arbitrarily given finite block length. The results show that among all existing asymptotically capacity-achieving LNC schemes, one (class) of them is provably finite-length optimal. By analyzing its second-order asymptotic, we have thus derived the exact (optimal) LNC broadcast channel dispersion, which closes the gap of the state-of-the-art inner and outer bounds previously derived in Lin et al. ISIT 2021

Achievable data rates in wireless systems rely heavily on the available channel state information (CSI) throughout the network. However, feedback links, which provide this information, are scarce, unreliable, and subject to security threats. In this work, we study the impact of having intermittent feedback links on the capacity region of the canonical two-user erasure broadcast channels. In our model, at any time instant, each receiver broadcasts its CSI, and at any other node, this information either becomes available with unit delay or gets erased. For this setting, we develop a new set of outer bounds to capture the intermittent nature of the feedback links. These outer bounds depend on the probability that the CSI from both receivers are erased at the transmitter. In particular, if at any time, the CSI from at least one of the two receivers is available at the other two nodes, then the outer-bounds match the capacity with global delayed CSI. We also provide capacity-achieving transmission strategies under certain scenarios, and we establish a connection between this problem and Blind Index Coding with feedback.

We characterize the capacity region of the two-user broadcast packet erasure channel (PEC) with single-user delayed channel state information (CSI). More precisely, we assume one receiver does not provide its channel state to the other two nodes (the other receiver and the transmitter), while the other receiver reveals its state globally with unit delay. This is a hybrid CSI at the transmitter (CSIT) setting where the transmitter has the delayed CSI of one user but not the other. Previous results developed opportunistic network coding schemes for this setting, which strictly enlarge the achievable rate region compared to the no-CSIT baseline. Characterization of the capacity region with single-user delayed CSI, however, remained open. In this work, we develop an improved achievability strategy and show that the capacity region, surprisingly, matches that of the broadcast PEC with global delayed CSI of both users. The key to such improvement over previous results is a new precoding strategy for the retransmission phase of the opportunistic network coding scheme. It harnesses the single-user delayed CSI in the retransmission phase, so that interference from the feedback receiver can be aligned at the other receiver. Besides the broadcast PEC with two private messages, an extension to a model with an additional common message is also provided and the corresponding capacity region with single-user CSI also matches that with global delayed CSI. Finally, further extensions to three-user cases are also provided.

5G downlink communications are expected to suffer more from the intermittent link connectivity, and studying the erasure broadcast channel (BC) provides the fundamental understanding of their performance. Recently, the capacity region of two-user erasure BC with single-user delayed channel state information (CSI) was characterized, where one receiver does not provide its channel state to the transmitter and the other receiver, while the other receiver feeds back its state globally with unit delay. Surprisingly, the capacity region with single-user delayed CSI matches that of the erasure BC with global delayed CSI of both users. When two links have same erasure probabilities, this result is valid even when a common message intended for both users is required besides two private messages. The capacity in this case is easily achieved by adding a phase multicasting the common message after the transmission of private messages. However, when erasure probabilities are unequal, this scheme is clearly not capacity-achieving since the rate of the last phase will be limited by the weaker user having larger erasure probability. We propose a scheme which transmits the common message with rate higher than the link capacity of the weaker user in the last phase but still can ensure the decodability. The key is to simultaneously create equations of the common message at the weaker receiver and re-transmit private bits before the last phase. The proposed scheme achieves the converse under unequal link erasure probabilities, and the capacity with common and private messages is fully characterized under single-user delayed CSI.

In this paper, we analyze the fundamental limit of statistical classification with mismatched empirically observed statistics. Unlike classical hypothesis testing where we have access to the distributions of data, now we only have two training sequences sampled i.i.d. from two unknown distributions P0and P1respectively. The goal is to classify a testing sequence sampled i.i.d. from one of the two candidate distributions, each of which is deviated slightly from P0and P1respectively. In other words, there is mismatch between how the training and testing sequences are generated. The amount of mismatch is measured by the norm of the deviation in the Euclidean space. Assuming the norm of deviation is not greater than δ, we derive an asymptotically optimal test in Chernoff's regime, and analyze its error exponents in both Stein's regime and Chernoff's regime. We also give both upper and lower bounds on the decrease of error exponents due to (i) unknown distributions (ii) mismatch in training and testing distributions. When δ is small, we show that the decrease in error exponents is linear in δ and characterize its first-order term.

Streaming codes encode a string of source packets and output a string of coded packets in real time, which eliminate the queueing delay of block coding and are thus especially suitable for delay-sensitive applications. This work studies random linear streaming codes (RLSCs) and i.i.d. packet erasure channels. While existing works focused on the asymptotic error-exponent analyses, this work characterizes the error rate in the finite memory length regime and the contributions include: (i) A new information-debt-based description of the error event; (ii) A matrix-based characterization of the error rate; (iii) A closed-form approximation of the error rate that is provably tight for large memory lengths; and (iv) A new Markov-chainbased analysis framework, which can be of independent research interest. Numerical results show that the approximation, i.e. (iii), closely matches the exact error rate even for small memory length (≈ 20). The results can be viewed as a sequential- coding counterpart of the finite length analysis of block coding [Polyanskiy et al. 10] under the specialized setting of RLSCs.

Fundamental limits on the error probability of the social learning rule proposed by Lalitha et al. [1] and its variants for decentralized detection over a directed graph is investigated. We show that while social learning algorithms enjoy the benefits that each node in the graph weights the messages received from its neighbors locally to form its private belief and only requires knowledge of the data generating distributions of its own observation, it suffers a gap in the achievable error exponent compared to the centralized case. We propose a generalization of the social learning rule achieving the error exponent in centralized detection with the aid of slight global knowledge. A further analysis reveals that the price of decentralization is at most a constant term in the higher-order asymptotics. To obtain the slight global knowledge needed at each node for achieving the centralized error exponent, we develop a decentralized estimation method for each node to come up with a local estimate of that piece of global knowledge.

In this work, combinatorial quantitative group testing (QGT) with noisy measurements is studied. The goal of QGT is to detect defective items from a data set of size n with counting measurements, each of which counts the number of defects in a selected pool of items. While most literatures consider either probabilistic QGT with random noise or combinatorial QGT with noiseless measurements, our focus is on the combinatorial QGT with noisy measurements that might be adversarially perturbed by additive bounded noises. Since perfect detection is impossible, a partial detection criterion is adopted. With the adversarial noise being bounded by dn= Θ(nδ) and the detection criterion being to ensure no more than kn= Θ(nκ) errors can be made, our goal is to characterize the fundamental limit on the number of measurement, termed pooling complexity, as well as provide explicit construction of measurement plans with optimal pooling complexity and efficient decoding algorithms. We first show that the fundamental limit is $\frac{1}{{1 - 2\delta }}\frac{n}{{\log n}}$ to within a constant factor not depending on (n, κ, δ) for the non-adaptive setting when 0 < 2δ ≤ κ < 1, sharpening the previous result by Chen and Wang [1]. We also provide deterministic constructions of an adaptive method with $\frac{1}{{1 - 2\delta }}\frac{n}{{{{\log }_2}n}}$ pooling complexity up to a constant factor and O(n) decoding complexity.

Privacy-preserving data release mechanisms aiming to minimize the privacy leakage under utility constraints of nonspecific tasks are studied through the lens of information theory. While the private feature to be protected is typically determined and known by the users who release their data, the specific task where the release data is utilized is usually unknown. To address the lack of information of the specific task, utility constraints laid on a set of multiple possible tasks are considered. The mechanism protects the privacy of a given feature of the to-be-released data while satisfying utility constraints of all possible tasks in the set. First, the single-letter characterization of the privacy-utility tradeoff region is derived. Characterization of the minimum privacy under log-loss utility constraints turns out to be a non-convex optimization problem involving mutual information in the objective function and the constraints. Second, focusing on the case where the raw data consists of multiple independent components, we show that the above optimization problem can be decomposed into multiple parallel privacy funnel (PF) problems [1] with different weightings. We explicitly derive the optimal solution to each PF problem when the private feature is a deterministic function of a data component. The solution is characterized by the leakage-free threshold, and the minimum leakage is zero while the utility constraint is below the threshold. Once the utility requirement is above the threshold, the privacy leakage increases linearly. Finally, we show that the optimal weighting of each privacy funnel problem can be found by solving a linear program (LP). Numerical results are shown to illustrate the robustness of our approach.

In this work, an efficient and robust learning-based JPEG2000 architecture is proposed. It uses machine learning techniques for predicting and encoding the decision bit in the embedded block coding with optimized truncation (EBCOT) process. First, we apply non-locally weighted ridge regression to predict the quantized wavelet coefficients in the LL subband. Then, during the EBCOT process, we perform inter/intra subband prediction and inter/intra bit plane symbol prediction to estimate the activity of the decision bit using the deep learning architecture. Then, the binary prediction result is treated as an additional context and the decision bit is eventually coded using an advanced context-based adaptive binary arithmetic coder. Simulations show that the proposed framework provides the same visual quality as conventional codecs with as much as 30% bitrate savings.

Parametric point estimation from anonymous and heterogeneous data is studied. For heterogeneity, we assume n samples are independently drawn, each following one of K possible distributions. For anonymity, we assume the estimator knows the number of samples drawn from each distribution, but which one each sample follows is hidden. In words, samples as a sequence are passed through an unknown permutation prior to being observed. The goal is to find an estimator that minimizes the worst-case statistical risk over all possible permutations. We prove that an optimal estimator depends only on the empirical distribution (type) of samples, and when the risk function is the mean squared error (MSE), it follows a non-trivial Cramer-Rao lower bound. We further characterize its asymptote as n → ∞, assuming the number of samples from each distribution is proportional to n. The lower bound is of the order of 1/n, and the reciprocal of its prefactor is the Fisher information of the mixture of the K distributions.

We characterize the capacity region of the two-user erasure broadcast channel (BC) with single-user delayed channel state information (CSI). More precisely, we assume one receiver does not provide its channel state to the other two nodes (the other receiver and the transmitter), while the other receiver reveals its state globally with unit delay. This is a "DN" hybrid CSI at the transmitter (CSIT) setting where the transmitter has the delayed CSI of one user but not the other. Previous results developed opportunistic network coding schemes for this DN setting, which strictly enlarge the achievable rate region compared to the no-CSIT baseline. Characterization of the capacity region for the DN setting, however, remained open. In this work, we develop an improved achievability strategy and show that the capacity region, surprisingly, matches that of the erasure BC with global delayed CSI of both users. The key to such improvement over previous results is a new precoding strategy for the retransmission phase of the opportunistic network coding scheme. It harnesses the single-user delayed CSI in the retransmission phase, so that interference from the "D" receiver can be aligned at the "N" receiver. Besides erasure BCs with two private messages, an extension to BCs with an additional common message is also provided.

Recently, we showed that, rather surprisingly, the capacity region of the two-user erasure broadcast channel with global delayed channel state information (CSI) can be achieved with single-user delayed CSI only. More precisely, we assumed one receiver does not provide its channel state to the other two nodes (the other receiver and the transmitter), while the other receiver reveals its state globally with unit delay. In this work, we consider a more general setting in which feedback links are intermittent. To be precise, at any time instant, each receiver broadcasts its CSI, and this information either becomes available to the other two nodes or gets erased. For this setting, we develop a new set of outer bounds to capture the intermittent nature of the feedback links. These outer bounds depend on the probability that both feedback links are erased rather than the individual erasure probability of each feedback link. This result matches our earlier findings for the single-user delayed CSI scenario. We also provide a capacity-achieving recursive communication protocol for the scenario in which feedback links are fully correlated.

We explore the fundamental limits of heterogeneous distributed detection in an anonymous sensor network with n sensors and a single fusion center. The fusion center collects the single observation from each of the n sensors to detect a binary parameter. The sensors are clustered into multiple groups, and different groups follow different distributions under a given hypothesis. The key challenge for the fusion center is the anonymity of sensors-although it knows the exact number of sensors and the distribution of observations in each group, it does not know which group each sensor belongs to. It is hence natural to consider it as a composite hypothesis testing problem. First, we propose an optimal test called mixture likelihood ratio test, which is a randomized threshold test based on the ratio of the uniform mixture of all the possible distributions under one hypothesis to that under the other hypothesis. Optimality is shown by first arguing that there exists an optimal test that is symmetric, that is, it does not depend on the order of observations across the sensors, and then proving that the mixture likelihood ratio test is optimal among all symmetric tests. Second, we focus on the Neyman-Pearson setting and characterize the error exponent of the worst-case type-II error probability as n tends to infinity, assuming the number of sensors in each group is proportional to n. Finally, we generalize our result to find the collection of all achievable type-I and type-II error exponents, showing that the boundary of the region can be obtained by solving an optimization problem. Our results elucidate the price of anonymity in heterogeneous distributed detection, and can be extended to M-ary hypothesis testing with heterogeneous observations generated according to hidden latent variables.

Community detection in hypergraphs is explored. Under a generative hypergraph model called “$d$-wise hypergraph stochastic block model” ($d$-$\mathtt {hSBM}$), which naturally extends the stochastic block model ($\mathtt {SBM}$) from graphs to$d$-uniform hypergraphs, the fundamental limit of the misclassification ratio (the loss function in the community detection problem) is studied. For the converse part, a lower bound of the minimax risk, that is, the minimax expected misclassification ratio, is derived. Asymptotically, it decays exponentially fast to zero as the number of nodes tends to infinity, and the rate function is a weighted combination of several divergence terms, each of which is the Rényi divergence of order 1/2 between two Bernoulli distributions. The Bernoulli distributions involved in the characterization of the rate function are those governing the random instantiation of hyperedges in$d$-$\mathtt {hSBM}$. For the achievability part, we propose a two-step polynomial-time algorithm which, with high probability, has a misclassification ratio with a decaying exponent that is asymptotically greater than or equal to that of our proposed lower bound. The first step of the algorithm is a hypergraph spectral clustering method, which achieves partial recovery to a certain precision level. The second step is a local refinement method, which leverages the underlying probabilistic model along with parameter estimation from the outcome of the first step. To characterize the asymptotic performance of the proposed algorithm, we first derive a sufficient condition for attaining weak consistency in the hypergraph spectral clustering step. Then, under the guarantee of weak consistency in the first step, we upper bound the loss (with high probability) attained in the local refinement step by an exponentially decaying function of the size of the hypergraph and characterize the decaying rate. Compared to existing works in$\mathtt {SBM}$, the main technical challenge lies in the complex structure of error events since community relations become much more complicated. The experimental results on both the synthetic data and real-world datasets validate our theoretical finding that the refinement step is critical in achieving the optimal statistical limit. For the special case$d=3$, it is further shown by analyzing the performance of MLE that the proposed lower bound of the minimax risk is tight, and hence, the exponential decaying rate of the asymptotic minimax risk is characterized. We conjecture that this continues to hold for general$d$as well.

In this paper, community detection in hypergraphs is explored. Under a generative hypergraph model called "d-wise hypergraph stochastic block model" (d-hSBM) which naturally extends the Stochastic Block Model (SBM) from graphs to d-uniform hypergraphs, the fundamental limit on the asymptotic minimax misclassified ratio is characterized. For proving the achievability, we propose a two-step polynomial time algorithm that provably achieves the fundamental limit in the sparse hypergraph regime. For proving the optimality, the lower bound of the minimax risk is set by finding a smaller parameter space which contains the most dominant error events, inspired by the analysis in the achievability part. It turns out that the minimax risk decays exponentially fast to zero as the number of nodes tends to infinity, and the rate function is a weighted combination of several divergence terms, each of which is the Renyi divergence of order 1/2 between two Bernoulli distributions. The Bernoulli distributions involved in the characterization of the rate function are those governing the random instantiation of hyperedges in d-hSBM. Experimental results on both synthetic and real-world data validate our theoretical finding.

In this paper we consider the problem of rumor source detection in a network. Our main contribution is an efficient Belief-Propagation-based (BP) algorithm to compute the joint likelihood function of the source location and the spreading time for the general continuous-time Susceptible-Infected epidemic model on trees. As a result, many probabilistic detection algorithms, including the joint maximum likelihood estimator, can be implemented with time complexity being nearly linear in the product of the size of the graph and the effective range of the spreading time. This is in sharp contrast to the widely employed discrete-time epidemic models where the complexity in computing the likelihood function of the source location is exponential. To extend the BP algorithm to general graphs, we propose a “Gamma Generated Tree” heuristic to convert the original graph to a tree with heterogeneous infection rates over edges. Compared to state-of-the-art methods, simulation results show that our algorithm provides better estimates of the source when the graph topology is similar to trees. As a byproduct, the spreading time can also be estimated, which is useful in some applications.

In this paper, we explore the fundamental limits of heterogeneous distributed detection in an anonymous sensor network with$n$sensors and a single fusion center. The fusion center collects the single observation from each of the$n$sensors to detect a binary parameter. The sensors are clustered into multiple groups, and different groups follow different discrete distributions under a given hypothesis. The key challenge for the fusion center is the anonymity of sensors - although it knows the exact number of sensors and the distribution of observations in each group, it does not know which group each sensor belongs to. It is hence natural to consider it as a composite hypothesis testing problem. We focus on the Neyman-Pearson setting and give upper and lower bounds of the error exponent of the worst-case type-II probability of error as$n$tends to infinity, assuming the number of sensors in each group is proportional to n. Our results elucidate the price of anonymity in heterogeneous distributed detection. The results are also applied to distributed detection under Byzantine attacks, which hints that the conventional simple hypothesis testing approach might be too pessimistic. A full version of this paper is accessible at: http://homepage.ntu.edu.tw/~ihwanglEprint/isit18hd.pdf

We study the effects of instantaneous feedback of channel topology on the degrees of freedom (DoF) of the bursty MIMO X channel, where the four transmitter-receiver links are intermittently on-and-off, governed by four independent Bernoulli (p) random sequences, and each transmitter and receiver are equipped with M and N antennas, respectively. We partially characterize this channel: The sum DoF is characterized when p ≤ [1/2] or when [min(M,N)/(mm(M,N))] ≤ [2/3]. In the remaining regime, the lower bound is within 5.2% of the upper bound. Strictly higher DoF is achieved by coding across channel topologies. In particular, codes over as many as 5 topologies are proposed to achieve the sum DoF of the channel when p ≤ [1/2]. A transfer function view of the network is employed to simplify the code design and to elucidate the fact that these are space-time codes, obtained by interference alignment over space and time. A full version of this paper is accessible at: https://arxiv.org/abs/1805.02527.

Context-based adaptive arithmetic coding (CAAC) has high coding efficiency and is adopted by the majority of advanced compression algorithms. In this paper, five new techniques are proposed to further improve the performance of CAAC. They make the frequency table (the table used to estimate the probability distribution of data according to the past input) of CAAC converge to the true probability distribution rapidly and hence improve the coding efficiency. Instead of varying only one entry of the frequency table, the proposed range-adjusting scheme adjusts the entries near to the current input value together. With the proposed mutual-learning scheme, the frequency tables of the contexts highly correlated to the current context are also adjusted. The proposed increasingly adjusting step scheme applies a greater adjusting step for recent data. The proposed adaptive initialization scheme uses a proper model to initialize the frequency table. Moreover, a local frequency table is generated according to local information. We perform several simulations on edge-directed prediction-based lossless image compression, coefficient encoding in JPEG, bit plane coding in JPEG 2000, and motion vector residue coding in video compression. All simulations confirm that the proposed techniques can reduce the bit rate and are beneficial for data compression.

We investigate the benefits of incorporating relays in future multi-user wireless networks that seek to exploit unexplored bands of very high frequency spectrum, where transmitted signals are known to be highly susceptible to outages. To this end, we examine a two-user bursty MIMO Gaussian interference channel with an in-band relay, where Bernoulli random states conceptually capture signal outages. As our main result, we show that an in-band relay can provide a degrees of freedom (DoF) gain in this bursty channel. This beneficial role of in-band relays in the bursty channel is in direct contrast to their role in the non-bursty channel which is not as significant to provide a DoF gain. More importantly, we demonstrate that in certain antenna configurations, an in-band relay can help achieve interference-free performances with increased DoF. We find the benefits particularly substantial in high-outage circumstances, as the DoF gain can grow linearly with the number of antennas at the relay. In this paper, first we derive an outer bound from which we obtain a necessary condition for interference-free DoF performances. Then we develop a novel scheme that exploits information of the bursty channel states to achieve them.

In wireless networks, the link connectivity may be intermittent due to shadowing, burstiness of data arrival, or uncoordinated resource allocation. In this paper, we model the intermittence of links as Bernoulli distributed random channel states, termed intermittence channel states, and study the impact of the corresponding channel state information at the transmitter (CSIT) in a two-user Gaussian broadcast channel (BC). Moreover, due to the heterogeneous timeliness of intermittence channel states, the CSIT considered in this paper is hybrid. More specifically, the CSIT of each link can be perfectly (causally or non-causally) available, delayed, or not available. When the links are connected, we adopt a general setting that the received signal-to-noise ratios can be different. Our contribution is the characterization of the capacity regions of intermittent Gaussian BC to within bounded gaps for all combinations of hybrid CSIT, except for scenario DN (delayed CSIT of receiver 1, no CSIT of receiver 2). For scenario DN, we propose an opportunistic physical layer network coding scheme that achieves a strictly larger degree-of-freedom (DoF) region than the no-CSIT DoF region. As a corollary, single-user CSIT is able to increase the sum DoF for intermittent Gaussian BC (also the capacity region for the erasure BC, as a by-product). This result is in sharp contrast to the recent negative result by Davoodi and Jafar, where it is shown that for fast-fading multiple-input single-output BC with continuous channel states, single-user CSIT does not help at all in terms of sum DoF.

We study the sum degrees of freedom (DoF) of the bursty MIMO X channel without feedback, where the four transmitter-receiver links are intermittently ON and OFF, controlled by four Bernoulli random sequences which may be arbitrarily correlated, subject to a symmetry assumption: The two direct-links have the same level of burstiness, modeled by Ber(pd), and so do the cross-links, modeled by Ber(pc). The sum DoF is fully characterized in the regime where (pc/pd) is small, i.e., below a certain threshold, and is partially characterized in the other regime where (pc/pd) is above the threshold. The achievability is proved with a combination of Han-Kobayashi strategy and interference alignment, which can achieve strictly higher DoF than interference alignment alone. The converse proof employs a channel-state-sequence pairing technique. We highlight that burstiness of the channel disrupts the network topology, turning the MIMO X channel into a network with time-varying topology. This fundamental difference has striking ramifications. In particular, various interference alignment schemes that achieve the DoF of non-bursty MIMO X channels become suboptimal on the bursty channels. The reciprocity between the forward and the reverse links is lost, and the sum DoF does not saturate when the ratio between the transmitter and the receiver antennas exceeds (2/3).

The problem of extracting categorical data via noisy histogram queries is investigated. The considered data set is a collection of n items, each of which carries a piece of categorical data taking values in a finite alphabet. Data analysts are allowed to query the data set through a curator by specifying a subset of items and then obtaining the histogram of the queried subset. The (unnormalized) histogram released by the curator, however, is perturbed by some additive noise with maximum magnitude δη. The goal of the data analyst is to reconstruct the categorical data set such that the Hamming distance between the reconstructed and the actual one is smaller than a tolerance parameter kn. In this work, we explore the fundamental limit on the minimum number of queries Tη*, required for the analyst to reconstruct the n-item data set within kn tolerance subject to δη noisy perturbation. We first show that if δn= O(√kn) the minimum query complexity Tη*= Θ(n / log n), where the achievability is based on random sampling, and the converse is based on counting and packing arguments. On the other hand, if δn= Ω(k(1+ε)/2n) for some ϵ> 0, we prove that Tη*= ω(np) for any positive integer p. In other words, no querying methods with polynomial-in-n query complexity can successfully reconstruct the data set in that regime. This impossibility result is established by a novel combinatorial lower bound on Tη*.

The problem of community detection in random hypergraphs is considered. We extend the Stochastic Block Model (SBM) from graphs to hypergraphs with d-uniform hyperedges, which we term “d-wise hyper stochastic block model” (d-hSBM) and consider a homogeneous and approximately equal-sized K community case. For d = 3, we fully characterize the exponentially decaying rate of the minimax risk in recovering the underlying communities, where the loss function is the mis-match ratio between the true community assignment and the recovered one. It turns out that the rate function is a weighted combination of several divergence terms, each of which is the Renyi divergence of order 1 between two Bernoulli distributions. The Bernoulli distributions involved in the characterization of the rate function are those governing the random instantiation of hyperedges in d-hSBM. The lower bound is set by finding a smaller parameter space where we can analyze the risk, while the upper bound is achieved with the Maximum Likelihood estimator. The technical contribution is to show that upper bound has the same decaying rate as the lower bound, which involves careful bounding of the various probabilities of errors. Finally, we relate the minimax risk to the recovery criterion under the Bayesian framework and derive a threshold condition for exact recovery.

The problem of computing the modulo-sum of messages over a finite-field erasure multiple access channel (MAC) is studied, and the role of feedback for function computation is explored. Our main contribution is two-fold. First, a new outer bound on the non-feedback computation capacity is proved, which strictly improves the state of the art [1]. The new outer bound answers a previously unsettled question in the affirmative: delayed state feedback strictly increases computation capacity for the two-user erasure MAC universally. The proof leverages the subset entropy inequality by Madiman and Tetali [2]. Second, focusing on the family of linear coding schemes with hybrid-ARQ-type retransmissions, we develop the optimal computation rate with delayed state feedback. For the considered family of schemes, it is always sub-optimal to compute modulo-sum by decoding all messages first. This is in contrast to the nonfeedback case [1] where sometimes the aforementioned “decode-all” strategy can reach the best known achievable rates.

The benefit of delayed channel state information (CSI) at the transmitter is investigated in fast-fading MIMO broadcast channels (BC) with local CSI at receivers (CSIR). The seminal work by Maddah-Ali and Tse shows that delayed CSI at the transmitter (DCSIT) can increase the degrees of freedom (DoF) in fast-fading MIMO BC. A caveat, however, is that each receiver was assumed to know the channel coefficients of other receivers, and the cost of distributing such global CSIR was not considered. In this paper, we propose a model to capture the cost of CSIR dissemination. In this model, each receiver only knows its own channel (local CSIR) while rate-limited capacitated links among the receivers are available. These rate-limited links can be used for exchanging CSIR or other purposes such as facilitating cooperative MIMO. Our main contribution is the evaluation of achievable DoF of two classes of schemes in two-user MISO BC. One class leverages delayed CSIT following the Maddah-Ali-and-Tse (MAT) scheme together with the rate-limited links for exchanging CSIR. The other uses cooperative MIMO and does not leverage delayed CSIT at all. We first show that when the transmitter has delayed CSI of both receivers, leveraging delayed CSIT with MAT scheme cannot outperform cooperative MIMO in terms of DoF. Next, we turn our attention to the hybrid CSIT scenario where the CSI of one receiver is instantaneously known at the transmitter and the other receiver. We show that delayed CSIT can strictly improve DoF in this case.

We investigate the end-to-end delay of multiple-unicast wireless networks. In contrast to previous works where the end-to-end delay is measured by the queuing delay, in this work we measure the delay by the total blocklength of the communication scheme. As the capacity characterization of multiple-unicast networks is open, we consider random wireless networks (the Gupta-Kumar model) and investigate the end-to-end delay scaling law with respect to the number of nodes. The end-to-end delay of delivering a file depends on the file size as well as the throughput. Our main contribution is the characterization of the end-to-end delay scaling law of the multihopping scheme, which depends on the file size. Our main finding is that if the file size is sufficiently large, the end-to-end delay scaling law is proportional to it. While this is expected, if the file size is not large enough, the end-to-end delay scaling law becomes independent of it. In particular, in a network with 2 k randomly one-to-one paired users and area k and a source with F (k) bits to send, we show that the delay is ω (√kF (k)) if F (k) = Ω(√klog k), while it is ω(k log k) if F (k) = o(√klog k). Our result is derived by studying the multihopping scheme for large random wireless networks. Using ideas from moderate deviations theory and finite length bounds in the literature, we derive a lower bound on the required blocklength for the network.

The modulo-sum computation of messages over a K-user finite-field erasure multiple access channel (MAC) is studied, with emphasis on the role of feedback in the large system regime. For the non-feedback case, we propose a grouping scheme which has higher computation rate than that of the conventional “compute-and-forward” (CF) scheme where each transmitter uses the same linear code and the receiver leverages the additive structure of the multiple access channel to compute the modulo sum. Furthermore, with a growing number of users, the proposed grouping scheme strictly outperforms the conventional “decode-and-forward (DF)” scheme when the erasure probability is smaller than 1-e1/e≈ 0.3078, where the receiver first decodes messages of all users and then computes the modulo sum. This is in contrast to the two-user case where the currently best known achievability, reported by Khisti, Hern, and Narayanan in 2013, coincides with the better one between DF and CF. For the case with delayed state feedback, a new hybrid-ARQ-type scheme is proposed, and in the large system regime, it achieves a computation rate scaling like Ω(1/log(K)), much higher than the scaling Θ(1/K) achieved by the grouping scheme without feedback. Our result hints at significant gain in function computation due to feedback in the large system regime when the transmitters are connected intermittently to the receiver, in sharp contrast to the static case where feedback provides no gain at all.

We study parallel two-user interference channels when the interference is bursty and feedback is available from the respective receivers. Presence of interference in each subcarrier is modeled as a memoryless Bernoulli random state. The states across subcarriers are drawn from an arbitrary joint distribution with the same marginal probability for each subcarrier and instantiated independent and identically distributed (i.i.d.) over time. For the linear deterministic setup with symmetric interference in each subcarrier, we give a complete characterization of the capacity region. For the analogous setup with Gaussian noise, we give outer bounds and a tight generalized degrees of freedom characterization. We propose a novel helping mechanism, which enables subcarriers in very strong interference regime to help in recovering interfered signals for subcarriers in strong and weak interference regimes. Depending on the interference and burstiness regime, the inner bounds either employ the proposed helping mechanism to code across subcarriers or treat the subcarriers separately. The outer bounds demonstrate a connection to a subset entropy inequality by Madiman and Tetali.

State-dependent broadcast channels (BC) with heterogeneous channel state information available at the transmitter (CSIT) are studied. The heterogeneity of CSIT lies in the timeliness of channel state that governs the link from the transmitter to different receivers - CSI of each link can be perfectly (causally or non-causally), delayed, or not available at the transmitter. We focus on the erasure BC and the bursty Gaussian BC, where the channel states are governed by memoryless Bernoulli processes, independent across users. For the erasure BC with perfect single-user CSIT, we characterize its capacity region regardless of the CSIT of the other user and show that this capacity region strictly contains that with no CSIT. For the case with delayed single-user CSIT, we propose an opportunistic network coding scheme that achieves a strictly larger rate region than the no-CSIT capacity region. These results are extended to the bursty Gaussian BC, where for the perfect single-user CSIT scenario, the capacity region is characterized to within a bounded gap; and for the delayed single-user CSIT scenario, a rate region based the opportunistic network coding scheme is derived. As a corollary, single-user CSIT is able to increase the sum degrees of freedom (DoF) for bursty Gaussian BC. Our result is in sharp contrast to the recent negative result by Davoodi and Jafar [1], where it is shown that for fast-fading MISO broadcast channel, single-user CSIT does not help at all in terms of sum DoF.

The problems of extracting information from a data set via histogram queries or arithmetic mean queries are considered. We first show that the fundamental limit on the number of histogram queries, m, so that the entire data set of size n can be extracted losslessly, is m = Θ(n/log n), sub-linear in the size of the data set. For proving the lower bound (converse), we use standard arguments based on simple counting. For proving the upper bound (achievability), we proposed two query mechanisms. The first mechanism is random sampling, where in each query, the items to be included in the queried subset are uniformly randomly selected. With random sampling, it is shown that the entire data set can be extracted with vanishing error probability using Ω(n/log n) queries. The second one is a non-adaptive deterministic algorithm. With this algorithm, it is shown that the entire data set can be extracted exactly (no error) using Ω(n/log n) queries. We then extend the results to arithmetic mean queries, and show that for data sets taking values in a real-valued finite arithmetic progression, the fundamental limit on the number of arithmetic mean queries to extract the entire data set is also Θ(n/log n).

We investigate the degrees of freedom (DoF) of the symmetric bursty MIMO X channel without feedback, where the presence of the two cross links is governed by a Bernoulli pcrandom state. The sum DoF is characterized for most of the antenna-burstiness configurations, except the case where pc> 0.5 and the ratio of the number of transmit and receive antennas is between 2/3 and 3/2. When pc≤ 0.5, the sum DoF of the bursty MIMO X channel is equal to that of the interference channel, and hence cross-link messaging does not help. When pc> 0.5, cross-link messaging is necessary, and we showed that simple interference alignment schemes suffice to achieve the sum DoF. For the case where the characterization of DoF remains open, we propose a combination of Han-Kobayashi coding and interference alignment that achieves higher DoF than interference alignment alone. This is in sharp contrast to the non-bursty case where interference alignment alone is DoF-optimal.

We explore the benefits of relays1in multi-user wireless networks with bursty user traffic, where intermittent data traffic restricts the users to bursty transmissions. Specifically, we investigate a two-user bursty MIMO Gaussian interference channel (IC) with a relay, where two Bernoulli random states govern the bursty user traffic. We show that an in-band relay can provide a degrees of freedom (DoF) gain in this bursty channel. This beneficial role is in contrast to the role in the non-bursty channel which is not as significant to provide a DoF gain. More importantly, we demonstrate that for certain antenna configurations, an in-band relay can help achieve an interference-free performance with increased DoF. Particularly, we find the benefits of a relay substantial with low user traffic, as the DoF gain can scale linearly with the number of antennas at the relay. To this end, we derive an outer bound from which we obtain a necessary condition for interference-free DoF performances. Then, we develop a novel scheme that exploits information of the bursty traffic states to achieve the performances.

When multiple users share the same resource for physical layer cooperation such as relay terminals in their vicinities, this shared resource may not be always available for every user, and it is critical for transmitting terminals to know whether other users have access to that common resource in order to better utilize it. Failing to learn this critical piece of information may cause severe issues in the design of such cooperative systems. In this paper, we address this problem by investigating a two-pair two-way relay channel with an intermittently available relay. In the model, each pair of users need to exchange their messages within their own pair via the shared relay. The shared relay, however, is only intermittently available for the users to access. The accessing activities of different pairs of users are governed by independent Bernoulli random processes. Our main contribution is the characterization of the capacity region to within a bounded gap in a symmetric setting, for both delayed and instantaneous state information at transmitters. An interesting observation is that the bottleneck for information flow is the quality of state information (delayed or instantaneous) available at the relay, not those at the end users. To the best of our knowledge, our work is the first result regarding how the shared intermittent relay should cooperate with multiple pairs of users in such a two-way cooperative network.

We investigate how to exploit intermittent feedback for interference management by studying the two-user Gaussian interference channel (IC). We approximately characterize (within a universal constant) the capacity region for the Gaussian IC with intermittent feedback. We exactly characterize the capacity region of the linear deterministic version of the problem, which gives us insight into the Gaussian problem. We find that the characterization only depends on the forward channel parameters and the marginal probability distribution of each feedback link. The result shows that passive and unreliable feedback can be harnessed to provide multiplicative capacity gain in Gaussian ICs. We find that when the feedback links are active with sufficiently large probabilities, the perfect feedback sum-capacity is achieved to within a constant gap. In contrast to other schemes developed for IC with feedback, our achievable scheme makes use of quantize-map-and-forward to relay the information obtained through feedback, performs forward decoding, and does not use structured codes. We also develop new outer bounds enabling us to obtain the (approximate) characterization of the capacity region.

Physical layer cooperation of a source with a relay can significantly boost the performance of a wireless connection. However, the best practical relaying scheme can vary depending on the relative strengths of the channels that connect the source, relay and destination. This paper proposes and evaluates QUILT, a system for physical-layer relaying that seamlessly adapts to the underlying network configuration to achieve competitive or better performance as compared to the best current approaches. QUILT combines on-demand, opportunistic use of Decode-Forward (DF) or Quantize-Map-Forward (QMF) followed by interleaving at the relay, with hybrid decoding at the destination that extracts information from received frames even if these are not decodable. We theoretically quantify how our design choices for QUILT affect the system performance. We also deploy QUILT on the WarpLab software radio platform, and show through over-the-air experiments up to 5 times FER improvement over the next best cooperative protocol.

We study parallel symmetric 2-user interference channels when the interference is bursty and feedback is available from the respective receivers. Presence of interference in each subcarrier is modeled as a memoryless Bernoulli random state. The states across subcarriers are drawn from an arbitrary joint distribution with the same marginal probability for each subcarrier and instantiated i.i.d. over time. For the linear deterministic setup, we give a complete characterization of the capacity region. For the setup with Gaussian noise, we give outer bounds and a tight generalized degrees of freedom characterization. We propose a novel helping mechanism which enables subcarriers in very strong interference regime to help in recovering interfered signals for subcarriers in strong and weak interference regimes. Depending on the interference and burstiness regime, the inner bounds either employ the proposed helping mechanism to code across subcarriers or treat the subcarriers separately. The outer bounds demonstrate a connection to a subset entropy inequality by Madiman and Tetali [4].

This paper contributes to the design and analysis of Quantize-Map-and-Forward (QMF) relaying by optimizing its performance for small relay networks. QMF was proved to achieve the capacity of arbitrary networks within a bounded gap, as well as the optimal diversity-multiplexing tradeoff over slow fading networks. The initial QMF scheme has each relay performing the same operation, agnostic to the network topology and the channel state information (CSI); this facilitates the analysis for arbitrary networks, yet comes at a performance penalty for small networks and medium SNR regimes. This paper demonstrates the benefits we can gain for QMF if we optimize its performance by leveraging topological and channel state information. We show that for the N-relay diamond network, by taking into account topological information, we can exponentially reduce the QMF additive approximation gap from Θ(N) bits/s/Hz to Θ(log N) bits/s/Hz, while for the one-relay and two-relay networks, use of topological information and CSI can help to gain as much as 6 dB. Moreover, we explore what benefits we can realize if we jointly optimize QMF and half-duplex scheduling, as well as if we employ hybrid schemes that combine QMF and Decode-and-Forward (DF) relay operations.

We study the channel coding problem when errors and uncertainty occur in the encoding process. For simplicity we assume the channel between the encoder and the decoder is perfect. Focusing on linear block codes, we model the encoding uncertainty as erasures on the edges in the factor graph of the encoder generator matrix. We first take a worst-case approach and find the maximum tolerable number of erasures for perfect error correction. Next, we take a probabilistic approach and derive a sufficient condition on the rate of a set of codes, such that decoding error probability vanishes as blocklength tends to infinity. In both scenarios, due to the inherent asymmetry of the problem, we derive the results from first principles, which indicates that robustness to encoding errors requires new properties of codes different from classical properties.

This paper presents system design aspects of a multi-relay half-duplex QMF cooperative system. We propose two simple algorithms that address the design of relay scheduling and inter-relay interference schemes. Proposed linear-complexity scheduling algorithm is proven to be optimal for a multi-relay diamond network under specific channel conditions. We demonstrate through simulations that for typical channel conditions, the achievable QMF rate of a five-relay cooperative system is up to 3 times higher compared to a system without cooperation.

We investigate how to exploit intermittent feedback for interference management. Focusing on the two-user linear deterministic interference channel, we completely characterize the capacity region. We find that the characterization only depends on the forward channel parameters and the marginal probability distribution of each feedback link. The scheme we propose makes use of block Markov encoding and quantize-map-and-forward at the transmitters, and backward decoding at the receivers. Matching outer bounds are derived based on novel genie-aided techniques. As a consequence, the perfect-feedback capacity can be achieved once the two feedback links are active with large enough probabilities.

We study opportunistic interference management when there is bursty interference in parallel 2-user linear deterministic interference channels. A degraded message set communication problem is formulated to exploit the burstiness of interference in M subcarriers allocated to each user. We focus on symmetric rate requirements based on the number of interfered subcarriers rather than the exact set of interfered subcarriers. Inner bounds are obtained using erasure coding, signal-scale alignment and Han-Kobayashi coding strategy. Tight outer bounds for a variety of regimes are obtained using the El Gamal-Costa injective interference channel bounds and a sliding window subset entropy inequality [7]. The result demonstrates an application of techniques from multilevel diversity coding to interference channels. We also conjecture outer bounds indicating the sub-optimality of erasure coding across subcarriers in certain regimes.

We explore the benefit of feedback for physical layer interference management in wireless networks without centralized upper layer control mechanisms. Lack of coordination in the upper layer could make the interference experienced in the physical layer bursty. To understand how to harness such burstiness with feedback, we investigate a two-user bursty interference channel (IC), where the presence of interference is governed by a Bernoulli random state. We completely characterize the capacity region of the symmetric two-user linear deterministic bursty IC with feedback. The proposed two-phase scheme exploits feedback either for refining the previous interfered reception or for relaying additional information to the legitimate receiver of the other user. Matching outer bounds are derived by novel techniques that take the effect of delayed state information into account. We also use insights from the deterministic case to characterize the approximate symmetric capacity for the symmetric Gaussian bursty IC with feedback in the weak interference regime.

In this paper we develop a low-complexity coding scheme and system design framework for the half duplex relay channel based on the Quantize-Map-and-Forward (QMF) relaying scheme. The proposed framework allows linear complexity operations at all network terminals. We propose the use of binary LDPC codes for encoding at the source and LDGM codes for mapping at the relay. We express joint decoding at the destination as a belief propagation algorithm over a factor graph. This graph has the LDPC and LDGM codes as subgraphs connected via probabilistic constraints that model the QMF relay operations. We show that this coding framework extends naturally to the high SNR regime using bit interleaved coded modulation (BICM). We develop density evolution analysis tools for this factor graph and demonstrate the design of practical codes for the half-duplex relay channel that perform within 1dB of information theoretic QMF threshold.

We consider two-way interference channels (ICs) where forward and backward channels are ICs but not necessarily the same. We first consider a scenario where there are only two forward messages and feedback is offered through the backward IC for aiding forward-message transmission. For a linear deterministic model of this channel, we develop inner and outer bounds that match for a wide range of channel parameters. We find that the backward IC can be more efficiently used for feedback rather than if it were used for independent backward-message transmission. As a consequence, we show that feedback can provide a net increase in capacity even if feedback cost is taken into consideration. Moreover we extend this to a more general scenario with two additional independent backward messages, from which we find that interaction can provide an arbitrarily large gain in capacity.

In this paper we study the role of feedback in layered two unicast wireless networks with arbitrary number of nodes and connectivity. The feedback model allows destinations to feedback their received signals to their respective sources. In the case of linear deterministic networks, we fully characterize the capacity region when the two individual minimum cut values are equal to 1 and show that feedback only helps increase capacity whenever the capacity region without feedback has (1, 1/2) or (1/2, 1) as its corner point but not both. Therefore, feedback helps balance the resource utilization of the two users, similar to the role of feedback in the two-user interference channel [1].

In this paper we study the two unicast information flow problem over layered Gaussian networks with arbitrary number of nodes and connectivity, under the model of delayed channel state information (CSI) at transmitters and instantaneous CSI at receivers. We show that similar to the case with instantaneous CSI at transmitters (CSIT), the degrees of freedom (DoF) region is strictly larger than the time-sharing DoF region if and only if there is no omniscient node, definition of which only depends on the topology of the network. Moreover, as in the case with instantaneous CSIT, 2/3 DoF per user is always achievable when there is no omniscient node in the network.

We evaluate the information-theoretic achievable rates of Quantize-Map-and-Forward (QMF) relaying schemes over Gaussian N-relay diamond networks. Focusing on vector Gaussian quantization at the relays, our goal is to understand how close to the cutset upper bound these schemes can achieve in the context of diamond networks, and how much benefit is obtained by optimizing the quantizer distortions at the relays. First, with noise-level quantization, we point out that the worst-case gap from the cutset upper bound is (N + log2N) bits/s/Hz. A better universal quantization level found without using channel state information (CSI) leads to a sharpened gap of log2N + log2(1 + N) + N log2(1 + 1/N) bits/s/Hz. On the other hand, it turns out that finding the optimal distortion levels depending on the channel gains is a non-trivial problem in the general N-relay setup. We manage to solve the two-relay problem and the symmetric N-relay problem analytically, and show the improvement via numerical evaluations both in static as well as slow-fading channels.

In this paper, we consider theK-user Gaussian multiple-access channel with multiple independent additive white Gaussian interferences. Each interference is known to exactly one transmitter non-causally. The capacity region is characterized to within a bounded gap regardless of channel parameters. These results are based on a layered modulo-lattice scheme which realizes distributed interference cancellation.

We study a multiple-terminal joint source-channel coding problem, where two remote correlated Gaussian sources are transmitted over a Gaussian multiple-access channel with two transmitters. Each transmitter observes one of the sources contaminated in Gaussian noise. The receiver wishes to reconstruct both sources. We derive necessary conditions and sufficient conditions for the receiver to be able to reconstruct the sources with given expected squared-error distortions. These conditions establish the optimality of uncoded transmission below some signal-to-noise ratio (SNR) threshold, and they also establish the high-SNR asymptotics. To achieve the latter, a coding scheme is proposed that superimposes analog uncoded transmission and digital combined source-channel Gaussian vector quantization.

We investigate the two unicast flow problem over layered linear deterministic networks with arbitrary number of nodes. When the minimum cut value between each source-destination pair is constrained to be 1, it is obvious that the triangular rate region {(R1, R2) : R1, R2≥ 0, R1+ R2≤ 1} can be achieved, and that one cannot achieve beyond the square rate region {(R1, R2) : R1, R2≥ 0, R1≤ 1, R2≤ 1}. Analogous to the work by Wang and Shroff for wired networks [1], we provide the necessary and sufficient conditions for the capacity region to be the triangular region and the necessary and sufficient conditions for it to be the square region. Moreover, we completely characterize the capacity region and conclude that there are exactly three more possible capacity regions of this class of networks, in contrast to the result in wired networks where only two rate regions are possible. Our achievability scheme is based on linear coding over an extension field with at most four nodes performing special linear coding operations, namely interference neutralization and zero forcing, while all other nodes perform random linear coding.

Interference is a major issue limiting the performance in wireless networks. Cooperation among receivers can help mitigate interference by forming distributed MIMO systems. The rate at which receivers cooperate, however, is limited in most scenarios. How much interference can one bit of receiver cooperation mitigate? In this paper, we study the two-user Gaussian interference channel with conferencing decoders to answer this question in a simple setting. We identify two regions regarding the gain from receiver cooperation: linear and saturation regions. In the linear region, receiver cooperation is efficient and provides a degrees-of-freedom gain, which is either one cooperation bit buys one over-the-air bit or two cooperation bits buy one over-the-air bit. In the saturation region, receiver cooperation is inefficient and provides a power gain, which is bounded regardless of the rate at which receivers cooperate. The conclusion is drawn from the characterization of capacity region to within two bits/s/Hz, regardless of channel parameters. The proposed strategy consists of two parts: 1) the transmission scheme, where superposition encoding with a simple power split is employed and 2) the cooperative protocol, where one receiver quantize-bin-and-forwards its received signal and the other after receiving the side information decode-bin-and-forwards its received signal.

Interference limits performance in wireless networks and cooperation among receivers or transmitters can help mitigate interference by forming distributed MIMO systems. Earlier work shows how limited receiver cooperation helps mitigate interference. The scenario with transmitter cooperation, however, is more difficult to tackle. In this paper we study the two-user Gaussian interference channel with conferencing transmitters to make progress towards this direction. We characterize the capacity region to within 6.5 bits/s/Hz, regardless of channel parameters. Based on the bounded-gap-to-optimality result, we show that there is an interesting reciprocity between the scenario with conferencing transmitters and the scenario with conferencing receivers and their capacity regions are within a bounded gap to each other. Hence, in the interference-limited regime, the behavior of the benefit brought by transmitter cooperation is the same as that by receiver cooperation.

Interference limits performance in wireless networks, and cooperation among receivers or transmitters can help mitigate interference by forming distributed MIMO systems. Earlier work shows how limited receiver cooperation helps mitigate interference. The scenario with transmitter cooperation, however, is more difficult to tackle. In this paper we study the two-user Gaussian interference channel with conferencing transmitters to make progress towards this direction. We characterize the capacity region to within a constant number of bits regardless of channel parameters. Based on the constant-to-optimality result, we show that there is an interesting reciprocity between the scenario with conferencing transmitters and the scenario with conferencing receivers, and their capacity regions are within a constant gap to each other. Hence in the interference-limited regime, the behavior of the benefit brought by transmitter cooperation is the same as that by receiver cooperation.