The two-user Gaussian interference channel (G-IC) is revisited, with a particular focus on practically amenable discrete input signalling and treating interference as noise (TIN) receivers. The corresponding deterministic interference channel (D-IC)
is first investigated and coding schemes that can achieve the entire capacity region of D-IC under TIN are proposed. These schemes are then systematically translate into multi-layer superposition coding schemes based on purely discrete inputs for the real-valued G-IC. Our analysis shows that the proposed scheme is able to achieve the entire capacity region to within a constant gap for all channel parameters. To the best of our knowledge, this is the first constant-gap result under purely discrete signalling and TIN for the entire capacity region and all the interference regimes. Furthermore, the approach is extended to obtain coding scheme based on discrete inputs for the complex-valued G-IC. For such a scenario, the minimum distance and the achievable rate of the proposed scheme under TIN are analyzed, which takes into account the effects of random phase rotations introduced by the channels. Simulation results show that our scheme is capable of approaching the capacity region of the complex-valued G-IC and significantly outperforms Gaussian signalling with TIN in various interference regimes.
Distributed computing, in which a resource-intensive task is divided into subtasks and distributed among different machines, plays a key role in solving large-scale problems, e.g., machine learning for large datasets or massive computational problems
arising in genomic research. Coded computing is a recently emerging paradigm where redundancy for distributed computing is introduced to alleviate the impact of slow machines, or stragglers, on the completion time. Motivated by recently available services in the cloud computing industry, e.g., EC2 Spot or Azure Batch, where spare/low-priority virtual machines are offered at a fraction of the price of the on-demand instances but can be preempted in a short notice, we investigate coded computing solutions over elastic resources, where the set of available machines may change in the middle of the computation. Our contributions are two-fold: We first propose an efficient method to minimize the transition waste, a newly introduced concept quantifying the total number of tasks that existing machines have to abandon or take on anew when a machine joins or leaves, for the cyclic elastic task allocation scheme recently proposed in the literature (Yang et al. ISIT19). We then proceed to generalize such a scheme and introduce new task allocation schemes based on finite geometry that achieve zero transition wastes as long as the number of active machines varies within a fixed range. The proposed solutions can be applied on top of every existing coded computing scheme tolerating stragglers.
The Byzantine distributed quickest change detection (BDQCD) is studied, where a fusion center monitors the occurrence of an abrupt event through a bunch of distributed sensors that may be compromised. We first consider the binary hypothesis case wher
e there is only one post-change hypothesis and prove a novel converse to the first-order asymptotic detection delay in the large mean time to a false alarm regime. This converse is tight in that it coincides with the currently best achievability shown by Fellouris et al.; hence, the optimal asymptotic performance of binary BDQCD is characterized. An important implication of this result is that, even with compromised sensors, a 1-bit link between each sensor and the fusion center suffices to achieve asymptotic optimality. To accommodate multiple post-change hypotheses, we then formulate the multi-hypothesis BDQCD problem and again investigate the optimal first-order performance under different bandwidth constraints. A converse is first obtained by extending our converse from binary to multi-hypothesis BDQCD. Two families of stopping rules, namely the simultaneous $d$-th alarm and the multi-shot $d$-th alarm, are then proposed. Under sufficient link bandwidth, the simultaneous $d$-th alarm, with $d$ being set to the number of honest sensors, can achieve the asymptotic performance that coincides with the derived converse bound; hence, the asymptotically optimal performance of multi-hypothesis BDQCD is again characterized. Moreover, although being shown to be asymptotically optimal only for some special cases, the multi-shot $d$-th alarm is much more bandwidth-efficient and energy-efficient than the simultaneous $d$-th alarm. Built upon the above success in characterizing the asymptotic optimality of the BDQCD, a corresponding leader-follower Stackelberg game is formulated and its solution is found.
