We consider the problem of identifying the source of a rumor in a network. Given a snapshot observation of the network, in which a rumor has been spreading for some time, how to identify the source from which the rumor started to spread? In this paper, we point out the limitations of existing estimators in the literature. As a remedy, we put forth a new estimator by incorporating an independent random observation time. To capture the structure of information flow beyond graphs, our formulations consider rate constraints on the rumor and the multicast capacities for cyclic polylinking networks.

We introduce a class of channels, collectively referred to as the ‘chemical residual channel’, where the channel output is a probabilistic function of the current input and the previous output. When the channel is binary, there are 81 possible cases. For all these cases with known or unknown initial state, we completely characterize the maximal rate that can be achieved with zero error probability at any given finite block length. As a result, the zero-error capacities of these cases are obtained. We also show that feedback does not increase the zero-error capacity.

In the problem of classical group testing one aims to identify a small subset (of size$d$) of diseased individuals/defective items in a large population (of size$n$). This process is based on a minimal number of suitably-designed group tests on subsets of items, where the test outcome is positive iff the given test contains at least one defective item. Motivated by physical considerations, such as scenarios with imperfect test apparatus, we consider a generalized setting that includes as special cases multiple other group-testing-like models in the literature. In our setting the test outcome is governed by an arbitrarymonotonically increasing(stochastic) test function$f(\cdot)$, with the test outcome being positive with probability$f(x)$, where$x$is the number of defectives tested in that pool. This formulation subsumes as special cases a variety of noiseless and noisy group-testing models in the literature. Our main contributions are as follows. Firstly, for any monotone test function$f(\cdot)$we present a non-adaptive scheme that with probability$1-\varepsilon $identifies all defective items. Our scheme requires at most${\mathcal{ O}}\left ({{\Psi (f)} d\log \left ({\frac {n}{\varepsilon }}\right)}\right)$tests, where${\Psi (f)}$is a suitably defined “sensitivity parameter” of$f(\cdot)$, and is never larger than${\mathcal{ O}}(d^{1+o(1)})$, but indeed can be substantially smaller for a variety of$f(\cdot)$. Secondly, we argue that any non-adaptive group testing scheme needs at least$\Omega \left ({(1-\varepsilon) {\psi (f)} d\log \left ({\frac {n} d}\right)}\right)$tests to ensure high reliability recovery. Here${\psi (f)}$is a suitably defined “concentration parameter” of$f(\cdot)$, and${\psi (f)}\in \Omega {(1)}$. Thirdly, we prove that our sample-complexity bounds for generalized group testing are information-theoretically near-optimal for a variety of sparse-recovery group-testing models in the literature. That is, forany“noisy” test function$f(\cdot)$(i.e.,$0 < f(0) < f(d) < 1$), and for a variety of “(one-sided) noiseless” test functions$f(\cdot)$(i.e., either$f(0)=0$, or$f(d)=1$, or both) studied in the literature we show that$\frac {\Psi (f)} {\psi (f)} \in \Theta (1)$. As a by-product we tightly characterize the heretofore open information-theoretic order-wise sample-complexity for the well-studied model of threshold group-testing. For general (near)-noiseless test functions$f(\cdot)$we show that$\frac {\Psi (f)} {\psi (f)} \in {\mathcal{ O}}(d^{1+o(1)})$. We also demonstrate a “natural” test-function$f(\cdot)$whose sample complexity scales “extremally” as$\Theta (d^{2}\log n)$, rather than$\Theta (d\log n)$as in the case of classical group-testing. Some of our techniques may be of independent interest – in particular our achievability requires a delicate saddle-point approximation, our impossibility proof relies on a novel bound relating the mutual information of pair of random variables with the mean and variance of a specific function, and as a by-product of our proof showing that our sample-complexity upper and lower bounds are close we derive novel structural results about monotone functions.

In this paper, we explore the connection between secret key agreement and secure omniscience within the setting of the multiterminal source model with an eavesdropper having side information. While the secret key agreement problem considers the generation of a maximum-rate secret key through public discussion, the secure omniscience problem is concerned with communication protocols for omniscience that minimize the rate of information leakage to the eavesdropper. The starting point of our work is a lower bound on the minimum leakage rate for omniscience,$R_{ \text {L}}$, in terms of the wiretap secret key capacity,$C_{ \text {W}}$. Our interest is in identifying broad classes of sources for which this lower bound is met with equality, in which case we say that there is a duality between secure omniscience and secret key agreement. We show that this duality holds in the case of certain finite linear source (FLS) models, such as two-terminal FLS models and pairwise independent network models on trees with a linear eavesdropper. Duality also holds for any FLS model in which$C_{ \text {W}}$is achieved by a perfect linear secret key agreement scheme. We conjecture that the duality in fact holds unconditionally for any FLS model. On the negative side, we give an example of a (non-FLS) source model for which duality does not hold if we limit ourselves to communication-for-omniscience protocols with at most two (interactive) communications. We also address the secure function computation problem and explore the connection between the minimum leakage rate for computing a function and the wiretap secret key capacity.

In the problem of classical group testing one aims to identify a small subset (of size $d$) diseased individuals/defective items in a large population (of size $n$) via a minimal number of suitably-designed group tests on subsets of items, where the test outcome is positive iff the given test contains at least one defective item. Motivated by physical considerations, we consider a generalized setting that includes as special cases multiple other group-testing-like models in the literature. In our setting, which subsumes as special cases a variety of noiseless and noisy group-testing models in the literature, the test outcome is positive with probability $f(x)$, where $x$ is the number of defectives tested in a pool, and $f(\cdot)$ is an arbitrary {\it monotonically increasing} (stochastic) test function. Our main contributions are as follows. 1. We present a non-adaptive scheme that with probability $1-\varepsilon$ identifies all defective items. Our scheme requires at most ${\cal O}( H(f) d\log(n/\varepsilon))$ tests, where $H(f)$ is a suitably defined “sensitivity parameter" of $f(\cdot)$, and is never larger than ${\cal O}(d^{1+o(1)})$, but may be substantially smaller for many $f(\cdot)$. 2. We argue that any non-adaptive group testing scheme needs at least $\Omega (h(f) d\log(n/d))$ tests to ensure high reliability recovery. Here $h(f)$ is a suitably defined “concentration parameter" of $f(\cdot)$, and $h(f) \in \Omega{(1)}$. 3. We prove that our sample-complexity bounds for generalized group testing are information-theoretically near-optimal for a variety of sparse-recovery group-testing models in the literature. That is, for {\it any} “noisy" test function $f(\cdot)$ (i.e. $0< f(0) < f(d) <1$), and for a variety of “(one-sided) noiseless" test functions $f(\cdot)$ (i.e., either $f(0)=0$, or $f(d)=1$, or both) studied in the literature we show that $H(f)/h(f) \in \Theta(1)$. As a by-product we tightly characterize the heretofore open information-theoretic sample-complexity for the well-studied model of threshold group-testing. For general (near)-noiseless test functions $f(\cdot)$ we show that $H(f)/h(f) \in {\cal O}(d^{1+o(1)})$. We also demonstrate a “natural" test-function $f(\cdot)$ whose sample complexity scales “extremally" as $\Theta ( d^2\log(n))$, rather than $\Theta ( d\log(n))$ as in the case of classical group-testing. Some of our techniques may be of independent interest – in particular our achievability requires a delicate saddle-point approximation, and our impossibility proof relies on a novel bound relating the mutual information of pair of random variables with the mean and variance of a specific function, and we derive novel structural results about monotone functions.

We consider a class of channels, collectively referred to as the ‘chemical residual channel’, where the channel output is determined by the current input and the previous output. When the channel is binary and the output is a deterministic function of the current input and the previous output, there are 16 possible cases. For all these cases, we characterize the maximal rate that can be achieved with zero error probability at any given finite block length. As a result, the zero-error capacities of these cases are obtained.

The characterization of the secret key capacity with wiretapper side information is a challenging open problem. In this paper, we give a necessary and sufficient condition for the positivity of wiretap secret key capacity for the multiterminal source model. This result extends the existing works for two-terminal sources. However, in the case of hypergraphical source models with a linear wiretapper, we derive a simpler equivalent condition for the positivity. We also show that blocklength need not be larger than the logarithm of the number of edges in order to generate a positive rate key. The proofs of these results involve a subclass called minimally connected hypergraphical sources with a linear wiretapper, for which we obtain a single-letter characterization of wiretap secret key capacity.

In this paper, we obtain a single-letter characterization of the wiretap secret key capacity for a large class of multiterminal source models (namely, tree-PIN models) with a linear wiretapper that can observe arbitrary linear combinations of the source. For this class of sources, we also show a duality between the problems of wiretap secret key agreement and secure omniscience, which suggests that such duality potentially holds for more general sources.

We show that, under the info-clustering framework, correlated random variables can be clustered in an agglomerative manner. While the existing divisive approach successively segregates the random variables into subsets with increasing multivariate mutual information, our agglomerative approach successively merges subsets of random variables sharing a large amount of normalized total correlation. We show that both approaches result in the same hierarchy of clusters, but the agglomerative approach is an order of magnitude faster than the divisive one. The uniqueness of the hierarchy produced by the two approaches is due to a fundamental connection that we uncover between the well-known total correlation and the recently proposed measure of multivariate mutual information. We implement the new algorithm and provide a data structure for efficient storage and retrieval of the hierarchical clustering solution.

We consider the problem of exchanging sensitive information in public and provide a general formulation that can unify and extend various existing scenarios of information exchange, such as the problems of private information extraction and information bottleneck. The formulation also gives rise to a new scenario called secure omniscience (SO), where users want to exchange all their private information with minimum leakage to a wiretapper with side information. Single-letter lower and upper bounds are obtained for the minimum leakage, and the bounds are shown to be tight under the finite linear source model with two users. The bounds are derived in terms of the solutions of the closely related problems of communication for omniscience (CO) and secret key agreement (SKA). However, we find examples where the bounds are not tight, and so the connections to CO and SKA are not precise. In particular, it is possible that any optimal CO scheme that minimizes communication does not minimize leakage, and any optimal SO scheme that minimizes leakage does not attain the capacity for SKA. Nevertheless, we identify a useful notion of information alignment that can modify an optimal CO scheme to reduce leakage for SO.

The discussion rate region in the multiterminal source model is the individual discussion rate required for generating a secret key of maximum rate. We give an explicit single-letter characterization of the discussion rate region for a large class of pairwise independent network (PIN) models. Besides, we also establish a sufficient condition for identifying whether a PIN model belongs to this class, which can be checked in strongly polynomial time. As a by-product, the discussion rate region reduces to a very simple expression for PIN model satisfying such condition.

This paper investigates the secret key generation in the multiterminal source model, where users observing correlated sources discuss interactively under limited rates to agree on a secret key. We focus on a class of sources representable by minimally connected hypergraphs. For such sources, we give a single-letter explicit characterization of the region of achievable secret key rate and public discussion rate tuple. This is the first result that completely characterizes the achievable rate region for a multiterminal source model, which is beyond the PIN model on a tree. We also obtain an explicit formula for the maximum achievable secret key rate, called the constrained secrecy capacity, as a function of the total discussion rate.

We consider a non-asymptotic (one-shot) version of the multiterminal secret key agreement problem on a finite linear source model. In this model, the observation of each terminal is a linear function of an underlying random vector composed of finitely many i.i.d. uniform random variables. By restricting the public discussion to be a linear function of the terminals' observations, we obtain a characterization of the communication complexity (minimum number of symbols of public discussion) of generating a secret key of maximum length. More precisely, we show that the minimum discussion can be achieved by a non-interactive protocol in which each terminal first does a linear processing of its own private observations, following which the terminals all execute a discussion-optimal communication-for-omniscience protocol. The secret key can be chosen to be a linear function of the vector of all observations.

Batched network coding is a variation of random linear network coding which has low computational and storage costs. In order to adapt random fluctuations in the number of erasures in individual batches, it is not optimal to recode and transmit the same number of packets for all batches. Different distributed optimization problems, which are called adaptive recoding, were formulated for this purpose. The key component of these optimization problems is the expected value of the rank distribution of a batch at the next network node, which also known as the expected rank. In this paper, we put forth a unified adaptive recoding framework. We show that the expected rank functions are concave when the packet loss pattern follows a stationary stochastic process regardless of the field size, which covers but not limited to independent packet loss and burst packet loss. Under this concavity property, we show that there always exists a preferred solution which not only can make the number of recoded packets almost deterministic but can also tolerate rank distribution errors due to inaccurate measurements or limited precision of the machine. To obtain such an optimal solution, we propose tuning schemes that can turn any feasible solution into one with the above desired properties.

Hypergraphical sources are a natural class of sources for secret key generation, within which different subsets of terminals sharing secrets are allowed to discuss publicly in order to agree upon a global secret key. While their secrecy capacity, i.e., the maximum rate of a secret key that can be agreed upon by the entire set of terminals, is well-understood, what remains open is the maximum rate of a secret key that can be generated when there is a restriction on the overall rate of public discussion allowed. In this paper, we obtain a family of explicitly computable upper bounds on the number of bits of secret key that can be generated per bit of public discussion. These upper bounds are derived using a lamination technique based on the submodularity of the entropy function. In particular, a specific instance of these upper bounds, called the edge-partition bound, is shown to be tight for the pairwise independent network model, a special case of the hypergraphical source when the hypergraph is a graph. The secret key generation scheme achieving this upper bound is the tree-packing protocol of Nitinawarat et al., thereby resolving in the affirmative the discussion rate optimality of the tree-packing protocol.

We show that correlated random variables can be clustered more efficiently in an agglomerative manner rather than a divisive one. The agglomerative approach successively merges subsets of random variables sharing a large amount of normalized total correlation. Compared to the existing divisive approach that successively segregates the random variables into subsets with increasing multivariate mutual information, the agglomerative approach gives the same hierarchy of clusters faster by an order of magnitude. The underlying results justifying the agglomerative approach are also of theoretical interest since they reveal a fundamental connection between the well-known total correlation and the recently proposed multivariate mutual information.

In the multiterminal secret key agreement problem, a set of users want to discuss with each other until they share a common secret key independent of their discussion. We want to characterize the maximum secret key rate, called the secrecy capacity, asymptotically when the total discussion rate goes to zero. In the case of only two users, the capacity is equal to the Gács-Körner common information. However, when there are more than two users, the capacity is unknown. It is plausible that a multivariate extension of the Gács-Kömer common information is the capacity, however, proving the converse is challenging. We resolved this for the hypergraphical sources and finite linear sources, and provide efficiently computable characterizations. We also give some ideas of extending the techniques to more general source models.

We investigate the secret key generation in the multiterminal source model, where the users discuss under limited rate. For the minimally connected hypergraphical sources, we give an explicit formula of the maximum achievable secret key rate, called the secrecy capacity, under any given total discussion rate. Besides, we also partially characterize the region of achievable secret key rate and discussion rate tuple. When specializes to the hypertree sources, our results give rise to a complete characterization of the region.

We study the change of multivariate mutual information among a set of random variables when some common randomness is added to or removed from a subset of the random variables. This is formulated more precisely as two new multiterminal secret key agreement problems that, respectively, ask how one can increase the secrecy capacity efficiently by adding common randomness to a small subset of users, and how one can simplify the source model by removing redundant common randomness that does not contribute to the secrecy capacity. Characterizations and strongly polynomial-time computations are derived for the rates of change, maximum usable increment, and redundancy. These results can be applied to study the communication complexity for secret key agreement.

For the multiterminal secret key agreement problem under a private source model, it is known that the maximum key rate, i.e., the secrecy capacity, can be achieved through communication for omniscience, but the omniscience strategy can be strictly suboptimal in terms of minimizing the public discussion rate. While a single-letter characterization is not known for the minimum discussion rate needed for achieving the secrecy capacity, we derive single-letter lower bounds that yield some simple conditions for omniscience to be discussion-rate optimal. These conditions turn out to be enough to deduce the optimality of omniscience for a large class of sources, including the hypergraphical sources. We also extend our results to more general class of multiterminal sources with helpers and silent users.

This paper considers the communication for omniscience problem: a set of users observe a discrete memoryless multiple source and want to recover the entire multiple source via noise-free broadcast communications. We study the problem of how to determine an optimal rate vector that attains omniscience with the minimum sum rate, the total number of communications. The results cover both asymptotic and non-asymptotic models where the transmission rates are real and integral, respectively. We propose a modified decomposition algorithm (MDA) and a sum-rate increment algorithm (SIA) for the asymptotic and non-asymptotic models, respectively, both of which determine the value of the minimum sum rate and a corresponding optimal rate vector in polynomial time. For the coordinate saturation capacity algorithm, a nesting algorithm in MDA and SIA, we propose to implement it by a fusion method and show by experimental results that this fusion method contributes to a reduction in computation complexity. Finally, we show that the separable convex minimization problem over the optimal rate vector set in the asymptotic model can be decomposed by the fundamental partition, the optimal partition of the user set that determines the minimum sum rate, so that the problem can be solved more efficiently.

For the multiterminal secret key agreement problem, new single-letter lower bounds are obtained on the minimum public discussion rate required to achieve any given secret key rate below the secrecy capacity. The results apply to the general source model without helpers or wiretapper's side information, but can be strengthened for hypergraphical sources. In particular, for the pairwise independent network, our results yield a complete characterization of the maximum secret key rate achievable under a constraint on the total discussion rate.

We study the rate of change of the multivariate mutual information among a set of random variables when some common randomness is added to or removed from a subset. This is formulated more precisely as two new multiterminal secret key agreement problems which ask how one can increase the secrecy capacity efficiently by adding common randomness to a small subset of users, and how one can simplify the source model by removing redundant common randomness that does not contribute to the secrecy capacity. The combinatorial structure has been clarified along with some meaningful open problems.

We consider the problem of how to fairly distribute the minimum sum-rate among the users in communication for omniscience (CO). We formulate a problem of minimizing a weighted quadratic function over a submodular base polyhedron which contains all achievable rate vectors, or transmission strategies, for CO that have the same sum-rate. By solving it, we can determine the rate vector that optimizes the Jain's fairness measure, a more commonly used fairness index than the Shapley value in communications engineering. We show that the optimizer is a lexicographically optimal (lex-optimal) base and can be determined by a decomposition algorithm (DA) that is based on submodular function minimization (SFM) algorithm and completes in strongly polynomial time. We prove that the lex-optimal minimum sum-rate strategy for CO can be determined by finding the lex-optimal base in each user subset in the fundamental partition and the complexity can be reduced accordingly.

In the multiterminal source model of Csiszár and Narayan, the communication complexity, RSK, for secret key (SK) generation is the minimum rate of communication required to achieve SK capacity. An obvious upper bound to RSKis given by RCO, which is the minimum rate of communication required for omniscience. In this paper we derive a better upper bound to RSKfor the hypergraphical source model, which is a special instance of the multiterminal source model. The upper bound is based on the idea of fractional removal of hyperedges. It is further shown that this upper bound can be computed in polynomial time. We conjecture that our upper bound is tight. For the special case of a graphical source model, we also give an explicit lower bound on RSK. This bound, however, is not tight, as demonstrated by a counterexample.

BATS codes were proposed for communication through networks with packet loss. A BATS code consists of an outer code and an inner code. The outer code is a matrix generalization of fountain codes, which works with the inner code that comprises random linear network coding at the intermediate network nodes. In this paper, we propose a new inner code scheme for BATS codes, called adaptive recoding, which can be applied distributively at the intermediate network nodes, requiring only local knowledge of the received packets and the outgoing network link erasure probability. We show that adaptive recoding has significant throughput gain for relatively small batch sizes, compared with the baseline recoding scheme used in existing works.

For the multiterminal secret key agreement problem under a private source model, it is known that the communication complexity required to achieve the capacity can be strictly smaller than the minimum rate of communication for omniscience, but a single-letter characterization is not known. We obtain a single-letter lower bound on the communication complexity as well as some conditions for the communication complexity to be maximal (equal to the smallest rate of communication for omniscience). The results are are stated and derived using a meaningful multivariate mutual information measure. They are stronger than existing ones because 1) they apply to a general discrete memoryless multiple source rather than a special source model, 2) the problem formulation allows private randomization by individual users, 3) the bound is single-letter and the condition can be checked easily, and so 4) more scenarios in which the communication complexity is maximal are discovered. We conjecture that the lower bound can be further improved by giving a concrete example.

In practical cellular communication systems, perfect channel state information is not available at the base stations. Assuming that the channel uncertainty is bounded within a known spherical region, the authors consider in this study robust rank‐two multicast beamforming for multiple groups of users in multicell systems. Worst‐case robust beamforming is designed to guarantee that the predefined signal‐to‐interference‐plus‐noise ratio targets of all users are met for any channel instance in the bounded region. The Alamouti code is employed to double the degrees of freedom in the beamformer design. The authors apply the semi‐definite relaxation (SDR) technique to address the formulated non‐convex robust rank‐two beamforming problem. Analytical results show that the SDR is tight when the number of users in each multicast group is no more than two and the channel uncertainty is sufficiently small. Finally, extensive simulations are carried out to validate the proposed beamforming design and the analytical studies.

Because the exchange of information among all the users in a large network can take a long time, a successive omniscience protocol is proposed. Namely, subgroups of users first recover the information of other users in the same subgroup at an earlier stage called local omniscience. Then, the users recover the information of all other users at a later stage called global omniscience. To facilitate the information exchange, a distributed storage system is used, so that users can conveniently upload and download messages through some reliable central servers. The minimum upload bandwidth is characterized and a bandwidth-storage trade-off is discovered. The results reveal the new connections to the problem of secret key agreement and, consequently, provide meaningful interpretations of a recently proposed multivariate mutual information measure that was inspired by the secret key agreement problem.

This paper investigates robust rank-two multicast beamforming for multiple groups of users in multicell systems. We consider the practical scenario when perfect channel state information is not available at the base stations. The channel uncertainty is assumed to be bounded within a spherical region. Robust beamforming is designed to guarantee that the predefined signal-to-interference-plus-noise ratio targets of all users are met for any channel instance in the bounded region. The Alamouti code is employed to double the degrees of freedom in the beamformer design. We apply the semidefinite relaxation (SDR) technique to address this nonconvex beamforming problem. Interestingly, our theoretical analysis shows that the SDR is tight when the number of users in each multicast group is no more than two and the channel uncertainty is sufficiently small.

In this paper, we investigate the pricing and resource allocation strategies in the two-tier sensing-based cognitive fem-tocell networks, where the macrocell and femtocells are operating over the same frequency band. The macrocell base station protects itself by setting the maximum aggregate interference constraint and makes profit by pricing the interference from femtocell users. Different from the conventional underlay-based networks where there is one price only, in the proposed sensing-based networks two prices are adopted corresponding to the idle and busy states of the macrocell. We consider both cases of perfect and imperfect sensing at the femtocells and solve the pricing and power allocation for both macrocell and femtocells using the energy efficiency as the utility function. Simulation results show that the proposed scheme can improve the energy efficiency significantly in spectrum sharing femtocell networks.