12 September 2022 in IEEE Transactions on Information Theory
This paper investigates fundamental limits of exact recovery in the general $d$ -uniform hypergraph stochastic block model ( $d$ -HSBM), wherein $n$ nodes are partitioned into $k$ disjoint communities with relative sizes $(p_{1},\ldots , p_{k})$ . Each subset of nodes with cardinality $d$ is generated independently as an order- $d$ hyperedge with a certain probability that depends on the ground-truth communities that the $d$ nodes belong to. The goal is to exactly recover the $k$ hidden communities based on the observed hypergraph. We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below the threshold (apart from a small regime of parameters that will be specified precisely). This threshold is represented in terms of a quantity which we term as the generalized Chernoff-Hellinger divergence between communities. Our result for this general model recovers prior results for the standard SBM and $d$ -HSBM with two symmetric communities as special cases. En route to proving our achievability results, we develop a polynomial-time two-stage algorithm that meets the threshold. The first stage adopts a certain hypergraph spectral clustering method to obtain a coarse estimate of communities, and the second stage refines each node individually via local refinement steps to ensure exact recovery.
12 July 2021 in IEEE Transactions on Information Theory
Suppose that a transmitter Alice potentially wishes to communicate with a receiver Bob over an adversarially jammed binary channel. An active adversary James eavesdrops on their communication over a binary symmetric channel (BSC( q)), and may maliciously flip (up to) a certain fraction p of their transmitted bits based on his observations. We consider a setting where the communication must be simultaneously covert as well as reliable, i.e., James should be unable to accurately distinguish whether or not Alice is communicating, while Bob should be able to correctly recover Alice's message with high probability regardless of the adversarial jamming strategy. We show that, unlike the setting with passive adversaries, covert communication against active adversaries requires Alice and Bob to have a shared key (of length at least Ω(logn)) even when Bob has a better channel than James. We present lower and upper bounds on the information-theoretically optimal throughput as a function of the channel parameters, the desired level of covertness, and the amount of shared key available. These bounds match for a wide range of parameters of interest. We also develop a computationally efficient coding scheme (based on concatenated codes) when the amount of shared key available is Ω(√n logn), and further show that this scheme can be implemented with much less amount of shared key when the adversary is assumed to be computationally bounded.
18 January 2021 in IEEE Transactions on Signal Processing
We consider the problem of recovering a binary rating matrix as well as clusters of users and items based on a partially observed matrix together with side-information in the form of social and item similarity graphs. These two graphs are both generated according to the celebrated stochastic block model (SBM). We develop lower and upper bounds on sample complexity that match for various scenarios. Our information-theoretic results quantify the benefits of the availability of the social and item similarity graphs. Further analysis reveals that under certain scenarios, the social and item similarity graphs produce an interesting synergistic effect. This means that observing two graphs is strictly better than observing just one in terms of reducing the sample complexity.
1 May 2023 in IEEE Transactions on Information Forensics and Security
This work investigates the phase gain of intelligent reflecting surface (IRS) covert communication over complex-valued additive white Gaussian noise (AWGN) channels. The transmitter Alice intends to transmit covert messages to the legitimate receiver Bob via reflecting the broadcast signals from a radio frequency (RF) source, while rendering the adversary Willie’s detector arbitrarily close to ineffective. Our analyses show that, compared to the covert capacity for classical AWGN channels, we can achieve a covertness gain of value 2 by leveraging Willie’s uncertainty of phase angles. This covertness gain is achieved when the number of possible phase angle pairs N = 2. More interestingly, our results show that the covertness gain will not further increase with N as long as N ≥ 2, even if it approaches infinity.