Papers on selected topics

Information theory

  1. Download: tian_matched.pdf 
  2. Download: mishra_secure.pdf 
  3. Download: shirin_nested.pdf 
  4. Download: laszlo_lp.pdf 
  5. W. Mao, S. Diggavi, and K. Sreeram, "Models and information-theoretic bounds for nanopore sequencing," Preprint.
  6. A. Sengupta, Y. Ezzeldin, S. Brahma, C. Fragouli, and S. Diggavi, "Quantize-map-forward (QMF) relaying: an experimental study," Preprint.
  7. Download: winetsec_boe.pdf www 
  8. Download: isit16_ic_p2p.pdf 
  9. Download: twc17_ic_p2p.pdf 
  10. Download: twc16_d2d.pdf 
  11. Download: isit_nanopore.pdf 
  12. Download: mehrdad_cdc16.pdf www 
  13. Download: karam_hier.pdf 
  14. Download: jad_layered.pdf 
  15. Download: jad_multilevel.pdf 
  16. Download: jad_dof.pdf 
  17. Note: available on arXiv:1705.03852 [cs.IT]
    Download: jad_adaptive.pdf 
  18. Download: ledpuf.pdf 
  19. Download: pcisit2017.pdf 
  20. Download: on Arxiv 
    Abstract:
    Emerging heterogeneous wireless architectures consist of a dense deployment of local-coverage wireless access points (APs) with high data rates, along with sparsely-distributed, large-coverage macro-cell base stations (BS). We design a coded caching-and-delivery scheme for such architectures that equips APs with storage, enabling content pre-fetching prior to knowing user demands. Users requesting content are served by connecting to local APs with cached content, as well as by listening to a BS broadcast transmission. For any given content popularity profile, the goal is to design the caching-and-delivery scheme so as to optimally trade off the transmission cost at the BS against the storage cost at the APs and the user cost of connecting to multiple APs. We design a coded caching scheme for non-uniform content popularity that dynamically allocates user access to APs based on requested content. We demonstrate the approximate optimality of our scheme with respect to information-theoretic bounds. We numerically evaluate it on a YouTube dataset and quantify the trade-off between transmission rate, storage, and access cost. Our numerical results also suggest the intriguing possibility that, to gain most of the benefits of coded caching, it suffices to divide the content into a small number of popularity classes.
  21. Download: on Arxiv 
    Abstract:
    It has been recently established that joint design of content delivery and storage (coded caching) can significantly improve performance over conventional caching. This has also been extended to the case when content has non-uniform popularity through several models. In this paper we focus on a multi-level popularity model, where content is divided into levels based on popularity. We consider two extreme cases of user distribution across caches for the multi-level popularity model: a single user per cache (single-user setup) versus a large number of users per cache (multi-user setup). When the capacity approximation is universal (independent of number of popularity levels as well as number of users, files and caches), we demonstrate a dichotomy in the order-optimal strategies for these two extreme cases. In the multi-user case, sharing memory among the levels is order-optimal, whereas for the single-user case clustering popularity levels and allocating all the memory to them is the order-optimal scheme. In proving these results, we develop new information-theoretic lower bounds for the problem.
  22. Download: sse_mskdt.pdf 
  23. Download: pycra.pdf 
  24. Download: bds_fd.pdf www 
  25. Download: isit15_fd_kd.pdf 
  26. Download: kwd_it15.pdf www 
  27. Download: koltead_it15.pdf www 
  28. Download: secretcom_czap.pdf www 
  29. Download: snc_czapfpd.pdf www 
  30. S. Avestimehr, S. N. Diggavi, C. Tian, and D. Tse, An approximation approach to network information theory, NOW publishers, 2014.
  31. Download: shaunak_cdc.pdf 
  32. Download: isit14_mdpd.pdf 
  33. Download: fto_cod.pdf 
    Abstract:
    In this paper we examine the value of feedback that comes from overhearing, without dedicated feedback resources. We focus on a simple model for this purpose: a deterministic two-hop interference channel, where feedback comes from overhearing the forward-links. A new aspect brought by this setup is the dual-role of the relay signal. While the relay signal needs to convey the source message to its corresponding destination, it can also provide a feedback signal which can potentially increase the capacity of the first hop. We derive inner and outer bounds on the sum capacity which match for a large range of the parameter values. Our results identify the parameter ranges where overhearing can provide non-negative capacity gain and can even achieve the performance with dedicated-feedback resources. The results also provide insights into which transmissions are most useful to overhear.
  34. Download: on Arxiv 
    Abstract:
    We consider oblivious transfer between Alice and Bob in the presence of an eavesdropper Eve when there is a broadcast channel from Alice to Bob and Eve. In addition to the secrecy constraints of Alice and Bob, Eve should not learn the private data of Alice and Bob. When the broadcast channel consists of two independent binary erasure channels, we derive the oblivious transfer capacity for both 2-privacy (where the eavesdropper may collude with either party) and 1-privacy (where there are no collusions).
  35. Abstract:
    It has recently been demonstrated that for single-layer cache networks, jointly designing caching and delivery can enable significant benefits over conventional caching. This was based on strategically designing the cached content to induce coded multicasting opportunities even among users with different demands and without foreknowledge of the user demands. In this work, we extend this coded caching approach to a multi-hop hierarchical content delivery network with two layers of caches. We propose a new caching scheme that combines two basic approaches. The first approach provides coded multicasting opportunities within each layer (through decoding and forwarding); the second approach provides coded multicasting opportunities across multiple layers (through strategic forwarding without decoding). By striking the right balance between these two approaches, we show that the proposed scheme achieves the optimal communication rates to within a constant multiplicative and additive gap. We further show that there is no tension between the rates in each of the two layers up to the aforementioned gap. Thus, both layers can simultaneously operate at approximately the minimum rate.
  36. Download: tri_net_sec.pdf 
    Abstract:
    We characterize the secret message capacity of the triangle network, that consists of a source, a relay and a destination connected through orthogonal erasure channels. A passive eavesdropper, Eve, wiretaps any one of the three channels. The source and the relay can each generate unlimited private randomness; the relay and the destination can publicly provide strictly causal channel state information. Our achievable scheme is expressed through a linear program (LP) with 11 inequalities that captures a minimal set of secret key generation methods and the use of them for message encryption. Our outer bound is expressed also through a linear program, in this case with 41 constraints, constructed from general information inequalities. We prove that the optimal value of the outer bound LP is no larger than that of the scheme LP, which implies that the solution of the achievable scheme LP is the capacity. We find that equipping the relay with private randomness increases the secrecy rate by more than 40% in some cases and that cut-set bounds, directly applied in the network, are not always tight. Because the derivation of the inner and outer bound are both lengthy, we describe in this paper the achievability scheme, outline the outer bound, and provide the full derivations online [1]. We also make available Matlab functions that take as input the erasure probabilities and evaluate the inner and outer bounds.
  37. Download: on Arxiv 
    Abstract:
    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].
  38. Download: on Arxiv 
    Abstract:
    Recent work has demonstrated that, for content caching, joint design of storage and delivery can yield significant benefits over conventional caching approaches. This is based on storing content in the caches in a way that creates coded-multicast opportunities even among users with different demands. Such a coded-caching scheme has been shown to be order-optimal for a caching system with single-level content, i.e., one where all content is uniformly popular. In this work, we consider a system with content divided into multiple levels, based on varying degrees of popularity. The main contribution of this work is the derivation of an information-theoretic outer bound for the multi-level setup, and the demonstration that, under some natural regularity conditions, a memory-sharing scheme, which operates each level in isolation according to a single-level coded caching scheme, is in fact order-optimal with respect to this outer bound.
  39. Download: on Arxiv 
    Abstract:
    We consider the source-channel separation architecture for lossy source coding in communication networks. It is shown that the separation approach is optimal in two general scenarios and is approximately optimal in a third scenario. The two scenarios for which separation is optimal complement each other: the first is when the memoryless sources at source nodes are arbitrarily correlated, each of which is to be reconstructed at possibly multiple destinations within certain distortions, but the channels in this network are synchronized, orthogonal, and memoryless point-to-point channels; the second is when the memoryless sources are mutually independent, each of which is to be reconstructed only at one destination within a certain distortion, but the channels are general, including multi-user channels, such as multiple access, broadcast, interference, and relay channels, possibly with feedback. The third scenario, for which we demonstrate approximate optimality of source-channel separation, generalizes the second scenario by allowing each source to be reconstructed at multiple destinations with different distortions. For this case, the loss from optimality using the separation approach can be upper-bounded when a difference distortion measure is taken, and in the special case of quadratic distortion measure, this leads to universal constant bounds.
  40. Download: lattice_qmf.pdf 
    Abstract:
    Recently, a new relaying strategy, quantize-map-and-forward (QMF) scheme, has been demonstrated to approximately achieve (within an additive constant number of bits) the Gaussian relay network capacity, universally, i.e., for arbitrary topologies, channel gains, and SNRs. This was established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we develop structured lattice codes that implement the QMF strategy. The main result of this paper is that such structured lattice codes can approximately achieve the Gaussian relay network capacity universally, again within an additive constant. In addition, we establish a similar result for half-duplex networks, where we demonstrate that one can approximately achieve the capacity using fixed transmit-receive (TX-RX) schedules for the relays with no transmit power optimization across the different TX-RX states of the network.
  41. Abstract:
    Recent results in wireless full-duplex promise rate gains over the half-duplex counterpart when two nodes exchange messages with each other. However, when multiple full-duplex nodes operate simultaneously, the resulting network has increased internode interference compared to the half-duplex counterpart. The increased internode interference can potentially limit the rate gain achievable due to introduction of full-duplex capability. In this paper, we present new interference management strategies tha handle internode interference for full-duplex enabled network and achieve rate gains over its half-duplex counterpart.
  42. Download: secure_netcod.pdf 
    Abstract:
    Secure network coding assumes that the underlying network links are lossless, thus it can be applied over lossy networks after channel error correction. Yet it is well known that channel losses, such as packet erasures, can be constructively used for secrecy over a link. We address here the challenge of extending these results for arbitrary networks. We provide achievability schemes over erasure networks with feedback, that outperform the alternative approach of channel error correction followed by secure message transmission separation. We derive outer bounds on the securely achievable rate and as a consequence we show optimality of our proposed scheme in some special cases.
  43. Download: ach_gicifb.pdf 
    Abstract:
    We consider the two-user Gaussian interference channel with intermittent channel output feedback. We derive an achievable rate region that corresponds to the capacity region of the linear deterministic version of the problem. The result shows that passive and unreliable feedback can be harnessed to provide multiplicative capacity gain in Gaussian interference channels. In contrast to other schemes developed for interference channel 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 find that when the feedback links are active with sufficiently large probabilities, the perfect feedback sum-capacity is achieved to within a constant gap.
  44. I.-H. Wang and S. N. Diggavi, "Managing bursty interference with feedback," in Proc. IEEE Information Theory Workshop (ITW) 2013, 2013.
  45. Abstract:
    Current security systems often rely on the adversary's computational limitations. Wireless networks offer the opportunity for a different, complementary kind of security, which relies on the adversary's limited network presence (i.e., that the adversary cannot be located at many different points in the network at the same time). We present a system that leverages this opportunity to enable n wireless nodes to create a shared secret S, in a way that an eavesdropper, Eve, obtains very little information on S. Our system consists of two steps: (1) The nodes transmit packets following a special pattern, such that Eve learns very little about a given fraction of the transmitted packets. This is achieved through a combination of beam forming (from many different sources) and wiretap codes. (2) The nodes participate in a protocol that reshuffles the information known to each node, such that the nodes end up sharing a secret that Eve knows very little about. Our protocol is easily implementable in existing wireless devices and scales well with the number of nodes; these properties are achieved through a combination of public feedback, broadcasting, and network coding. We evaluate our system through a 5-node testbed. We demonstrate that a group of wireless nodes can generate thousands of new shared secret bits per second, with their secrecy being independent of the adversary's computational capabilities.
  46. Abstract:
    We investigate the problem of secure communication in a simple network with three communicating parties, two distributed sources who communicate over orthogonal channels to one destination node. The cooperation between the sources is restricted to a rate limited common random source they both observe. The communication channels are erasure channels with strictly causal channel state information of the destination available publicly. A passive adversary is present in the system eavesdropping on any one of the channels. We design a linear scheme that ensures secrecy against the eavesdropper. By deriving an outer bound for the problem we prove that the scheme is optimal in certain special cases.
  47. Download: fd_ul_dl.pdf 
    Abstract:
    Feasibility of full-duplex opens up the possibility of applying it to cellular networks to operate uplink and downlink simultaneously for multiple users. However, simultaneous operation of uplink and downlink poses a new challenge of intra-cell inter-node interference. In this paper, we identify scenarios where inter-node interference can be managed to provide significant gain in degrees of freedom over the conventional half-duplex cellular design.
  48. Download: bursty_ic.pdf 
    Abstract:
    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.
  49. Download: on Arxiv 
    Abstract:
    We study the problem of secure message multicasting over graphs in the presence of a passive (node) adversary who tries to eavesdrop in the network. We show that use of feedback, facilitated through the existence of cycles or undirected edges, enables higher rates than possible in directed acyclic graphs of the same mincut. We demonstrate this using code constructions for canonical combination networks (CCNs). We also provide general outer bounds as well as schemes for node adversaries over CCNs.
  50. Download: bme_broadcast.pdf 
    Abstract:
    Encoding schemes for broadcasting two nested message sets are studied. We start with a simple class of deterministic broadcast channels for which (variants of) linear superposition coding are optimal in several cases [1], [2]. Such schemes are sub-optimal in general, and we propose a block Markov encoding scheme which achieves (for some deterministic channels) rates not achievable by the previous schemes in [1], [2]. We adapt this block Markov encoding scheme to general broadcast channels, and show that it achieves a rate-region which includes the previously known rate-regions1.
  51. Download: on Arxiv 
    Abstract:
    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.
  52. Download: on Arxiv 
    Abstract:
    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.
  53. Download: on Arxiv 
    Abstract:
    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.
  54. Abstract:
    In this paper we study interference management in wireless networks with bursty user traffic. In each time slot, whether a user is on or off for transmission is governed by its own Bernoulli random state. At each transmitter, the states of activities of other users are only available via feedback. We investigate a canonical two-user bursty Gaussian interference channel (IC) with three different feedback models: (1) no feedback, (2) delayed state feedback, and (3) channel output feedback. In all three cases, we characterize the capacity region of the bursty Gaussian IC to within a bounded gap. It turns out that the near-optimal transmit strategies in the non-bursty IC suffice to establish the approximate characterization of capacity in all three cases. In other words, traffic burstiness does not change the high-SNR optimality of the schemes as long as receivers keep track of user activities. Moreover, the capacity region with delayed state feedback is within a bounded gap to that without feedback, and therefore delayed state feedback does not provide significant improvement at high SNR.
  55. Download: securing_bc.pdf 
    Abstract:
    Consider a sender, Alice, who wants to transmit private messages to two receivers, Bob and Calvin, using unreliable wireless broadcast transmissions and short public feedback from Bob and Calvin. In [1], we assumed that Bob and Calvin provide honest feedback, and characterized the secure capacity region of the private messages under the requirement that Bob and Calvin do not learn each other's message. In this paper, we assume that Bob (or Calvin) may provide dishonest feedback; or even control the input message distributions, as is commonly assumed in cryptography literature. We characterize the capacity region in the case of dishonest adversaries, as well as an achievable region for the case when the adversary has complete control on the distribution of the messages. We also design polynomial time protocols for both cases, that rely on the use of coding techniques to mix and secure the private messages. As a side result, we define an extended notion of semantic security for this problem and using a similar approach to [2], we show the equivalence of different security notions.
  56. Download: on Arxiv 
    Abstract:
    We consider the problem of distributed computation of a target function over a two-user deterministic multiple-access channel. If the target and channel functions are matched (i.e., compute the same function), significant performance gains can be obtained by jointly designing the communication and computation tasks. However, in most situations there is mismatch between these two functions. In this work, we analyze the impact of this mismatch on the performance gains achievable with joint communication and computation designs over separation-based designs. We show that for most pairs of target and channel functions there is no such gain, and separation of communication and computation is optimal.
  57. Abstract:
    We consider the problem where a group of wireless nodes, connected to the same broadcast domain, want to create pairwise secrets, in the presence of an adversary Eve, who tries to listen in and steal these secrets. Existing solutions assume that Eve cannot perform certain computations (e.g., large-integer factorization) in useful time. We ask the question: can we solve this problem without assuming anything about Eve's computational capabilities? We propose a simple secret-agreement protocol, where the wireless nodes keep exchanging bits until they have agreed on pairwise secrets that Eve cannot reconstruct with very high probability. Our protocol relies on Eve's limited network presence (the fact that she cannot be located at an arbitrary number of points in the network at the same time), but assumes nothing about her computational capabilities. We formally show that, under standard theoretical assumptions, our protocol is information-theoretically secure (it leaks zero information to Eve about the secrets). Using a small wireless testbed of smart-phones, we provide experimental evidence that it is feasible for 5 nodes to create thousands of secret bits per second, with their secrecy being independent from the adversary's capabilities.
  58. Download: on Arxiv 
    Abstract:
    We consider the Gaussian “diamond” or parallel relay network, in which a source node transmits a message to a destination node with the help of N relays. Even for the symmetric setting, in which the channel gains to the relays are identical and the channel gains from the relays are identical, the capacity of this channel is unknown in general. The best known capacity approximation is up to an additive gap of order N bits and up to a multiplicative gap of order N2, with both gaps independent of the channel gains. In this paper, we approximate the capacity of the symmetric Gaussian N-relay diamond network up to an additive gap of 1.8 bits and up to a multiplicative gap of a factor 14. Both gaps are independent of the channel gains and, unlike the best previously known result, are also independent of the number of relays N in the network. Achievability is based on bursty amplify-and-forward, showing that this simple scheme is uniformly approximately optimal, both in the low-rate as well as in the high-rate regimes. The upper bound on capacity is based on a careful evaluation of the cut-set bound. We also present approximation results for the asymmetric Gaussian N-relay diamond network. In particular, we show that bursty amplify-and-forward combined with optimal relay selection achieves a rate within a factor O(log4(N)) of capacity with preconstant in the order notation independent of the channel gains.
  59. Abstract:
    Current security systems typically rely on the adversary's computational limitations (e.g., the fact that it cannot invert a hash function or perform large-integer factorization). Wireless networks offer the opportunity for a different, complementary kind of security, which relies not on the adversary's computational limitations, but on its limited network presence (i.e., that the adversary cannot be located at many different points in the network at the same time). We take a first step toward designing and building a wireless security system that leverages this opportunity: We consider the problem where a group of n nodes, connected to the same broadcast wireless network, want to agree on a shared secret (e.g., an encryption key), in the presence of an adversary Eve who tries to listen in and steal the secret. We propose a secret-agreement protocol, where the n nodes of the group keep exchanging bits until they have all agreed on a bit sequence that Eve cannot reconstruct (with very high probability). We provide experimental evidence---to the best of our knowledge, the first one---that a group of wireless nodes can generate thousands of new shared secret bits per second, with their secrecy being independent of the adversary's computational capabilities.
  60. Abstract:
    Optimal precoder design for weighted sum-rate maximization in multiple-input multiple-output interference networks is studied. For this well known non-convex optimization problem, convex approximations based on interference alignment are developed, for both single-beam and multi-beam cases. Precoder design methods that consist of two phases, an interference alignment phase and a post-alignment optimization phase, are proposed. The interference alignment solution is taken as the input to the post-alignment optimization phase. For post-alignment weighted sum-rate maximization, novel iterative distributed algorithms are proposed based on the developed convex approximations. Simulation results show that the proposed algorithms achieve promising weighted sum-rate gains over existing interference alignment algorithms. Interestingly, for the multi-beam case, significant gain is achieved at all SNRs, including the high SNR regime.
  61. Abstract:
    We consider the problem of distributed computation of a target function over a multiple-access channel. If the target and channel functions are matched (i.e., compute the same function), significant performance gains can be obtained by jointly designing the computation and communication tasks. However, in most situations there is mismatch between these two functions. In this work, we analyze the impact of this mismatch on the performance gains achievable with joint computation and communication designs over separation-based designs. We show that for most pairs of target and channel functions there is no such gain, and separation of computation and communication is optimal.
  62. Download: dynamic_qmf.pdf 
    Abstract:
    The value of relay nodes to enhance the error performance versus rate trade-off in wireless networks has been studied extensively. However, wireless nodes currently are constrained to only transmit or receive at a given frequency, i.e., half-duplex constraint. The diversity-multiplexing tradeoff (DMT) for half-duplex networks are less understood. In the special cases where the DMT is currently known, such as the relay channel and the line network, it is achieved by either dynamic decoding or a quantize-map-forward (QMF) strategy with a fixed half-duplex schedule. The main question we investigate in this paper is whether these two strategies are sufficient to achieve the DMT of half-duplex wireless networks or we need new strategies for general setups. We propose a generalization of the two existing schemes through a dynamic QMF strategy and show that in a parallel relay channel it outperforms both earlier schemes. We also establish the DMT for the relay channel with multiple relays and multiple antennas in some special cases.
  63. Download: bc_private_msg.pdf 
    Abstract:
    Consider a source, Alice, broadcasting private messages to multiple receivers through a broadcast erasure channel; users send back to Alice public feedback that she causally uses to decide the coding strategy for her following transmissions. Recently, the multiple unicast capacity region for this problem has been exactly characterized for a number of special cases; namely the 2-user, 3-user, symmetric K-user, and one-sidedly fair K-user [1], [2]. In this paper, we show that for all the cases where such characterizations exist, we can also optimally characterize the “secure” communication rates, where the message that Alice transmits to each user is information theoretically secure from the other users, even if these collude. We show that a simple, two-phase strategy, where appropriate amounts of secret keys are first generated and then consumed, matches a new outer bound we derive.
  64. Download: dof_2_unicast.pdf 
    Abstract:
    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.
  65. Download: on Arxiv 
    Abstract:
    In mutiterminal communication systems, signals carrying messages meant for different destinations are often observed together at any given destination receiver. Han and Kobayashi (1981) proposed a receiving strategy which performs a joint unique decoding of messages of interest along with a subset of messages which are not of interest. It is now well-known that this provides an achievable region which is, in general, larger than if the receiver treats all messages not of interest as noise. Nair and El Gamal (2009) and Chong, Motani, Garg, and El Gamal (2008) independently proposed a generalization called indirect or non-unique decoding where the receiver uses the codebook structure of the messages to only uniquely decode its messages of interest. Indirect (non-unique) decoding has since been used in various scenarios. The main result in this paper is to provide an interpretation and a systematic proof technique for why indirect decoding, in all known cases where it has been employed, can be replaced by a particularly designed joint unique decoding strategy, without any penalty from a rate region viewpoint1.
  66. Download: suc_dec_ic.pdf 
    Abstract:
    In this paper, we investigate the maximum achievable sum-rate of the two-user Gaussian interference channel with Gaussian superposition coding and successive decoding. We first examine an approximate deterministic formulation of the problem, and introduce the complementarity conditions that capture the use of Gaussian coding and successive decoding. In the deterministic channel problem, we find the constrained sum-capacity and its achievable schemes with the minimum number of messages, first in symmetric channels, and then in general asymmetric channels. We show that the constrained sum-capacity oscillates as a function of the cross link gain parameters between the information theoretic sum-capacity and the sum-capacity with interference treated as noise. Furthermore, we show that if the number of messages of either of the two users is fewer than the minimum number required to achieve the constrained sum-capacity, the maximum achievable sum-rate drops to that with interference treated as noise. We provide two algorithms to translate the optimal schemes in the deterministic channel model to the Gaussian channel model. We also derive two upper bounds on the maximum achievable sum-rate of the Gaussian Han-Kobayashi schemes, which automatically upper bound the maximum achievable sum-rate using successive decoding of Gaussian codewords. Numerical evaluations show that, similar to the deterministic channel results, the maximum achievable sum-rate with successive decoding in the Gaussian channels oscillates between that with Han-Kobayashi schemes and that with single message schemes.
  67. Download: on Arxiv 
    Abstract:
    Systems that employ network coding for content distribution convey to the receivers linear combinations of the source packets. If we assume randomized network coding, during this process, the network nodes collect random subspaces of the space spanned by the source packets. We establish several fundamental properties of the random subspaces induced in such a system and show that these subspaces implicitly carry topological information about the network and its state that can be passively collected and inferred. We leverage this information toward a number of applications that are interesting in their own right, such as topology inference, bottleneck discovery in peer-to-peer systems, and locating Byzantine attackers. We thus argue that randomized network coding, apart from its better known properties for improving information delivery rate, can additionally facilitate network management and control.
  68. Download: secret_keygen.pdf 
    Abstract:
    We study the secret-key capacity in a joint source-channel coding setup-the terminals are connected over a discrete memoryless channel and have access to side information, modelled as a pair of discrete memoryless source sequences. As our main result, we establish the upper and lower bounds on the secret-key capacity. In the lower bound expression, the equivocation terms of the source and channel components are functionally additive even though the coding scheme generates a single secret-key by jointly taking into account the source and channel equivocations. Our bounds coincide, thus establishing the capacity, when the underlying wiretap channel can be decomposed into a set of independent, parallel, and reversely degraded channels. For the case of parallel Gaussian channels and jointly Gaussian sources we show that Gaussian codebooks achieve the secret-key capacity. In addition, when the eavesdropper also observes a correlated side information sequence, we establish the secret-key capacity when both the source and channel of the eavesdropper are a degraded version of the legitimate receiver. We finally also treat the case when a public discussion channel is available, propose a separation based coding scheme, and establish its optimality when the channel output symbols of the legitimate receiver and eavesdropper are conditionally independent given the input.
  69. Abstract:
    We study secret-key agreement with public discussion over a flat-fading wiretap channel model. The fading gains are correlated across the receivers and sampled independently at each time. Perfect receiver channel state information (CSI) is assumed, whereas a noisy CSI of the main channel is also available to the transmitter. We propose lower and upper bounds on the capacity. Our lower bound is achieved by a coding scheme that involves a separate binning of the receiver CSI sequence and its channel output sequence. In general it improves upon the joint-binning schemes considered in earlier works. Our upper and lower bounds coincide, establishing the capacity, when either the transmitter has no CSI or when the channel gains of the legitimate receiver and the eavesdropper are statistically independent.
  70. Download: graph_qmf.pdf 
    Abstract:
    We present a structured Quantize-Map-and-Forward (QMF) scheme for cooperative communication over wireless networks, that employs LDPC ensembles for the node operations and message-passing algorithms for decoding. We demonstrate through extensive simulation results over the full-duplex parallel relay network, that our scheme, with no transmit channel state information, offers a robust performance over fading channels and achieves the full diversity order of our network at moderate SNRs.
  71. Abstract:
    We characterize the secret message capacity of a wiretapped erasure channel where causal channel state information of the honest nodes is publicly available. In doing so, we establish an intimate connection between message secrecy and secret key generation for the same channel setup. We propose a linear coding scheme that has polynomial encoding/decoding complexity, and prove a converse that shows the optimality of our scheme. Our work also demonstrates the value of causal public feedback, which has previously been shown for the secret key generation problem.
  72. Download: on Arxiv 
    Abstract:
    We provide a complete characterization of the achievable distortion region for the problem of sending a bivariate Gaussian source over bandwidth-matched Gaussian broadcast channels, where each receiver is interested in only one component of the source. This setting naturally generalizes the simple single Gaussian source bandwidth-matched broadcast problem for which the uncoded scheme is known to be optimal. We show that a hybrid scheme can achieve the optimum for the bivariate case, but neither an uncoded scheme alone nor a separation-based scheme alone is sufficient. We further show that in this joint source channel coding setting, the Gaussian scenario is the worst scenario among the sources and channel noises with the same covariances.
  73. Abstract:
    Information-theoretic secrecy is studied for a parallel relay (diamond) network, in which a transmitter wishes to communicate to a receiver through two relay nodes. While there is no direct link between the transmitter and receiver and all flow of information has to be transmitted through the relays, the message has to be kept secret from each of them. The exact secrecy capacity is characterized for the network under the linear deterministic model. The problem is then studied when each terminal is equipped with multiple antennas, and the channels are parallel Gaussian links. Lower and upper bounds for the secrecy capacity are derived, and the gap is bounded by a constant independent of the channel parameters and SNR. This results in an approximate characterization for the secrecy capacity of the parallel Gaussian diamond network.
  74. Abstract:
    We consider the Gaussian “diamond” or parallel relay network, in which a source node transmits a message to a destination node with the help of N relays. Even for the symmetric setting, in which the channel gains to the relays are identical and the channel gains from the relays are identical, the capacity of this channel is unknown in general. The best known capacity approximation is up to an additive gap of order N bits and up to a multiplicative gap of order N2, with both gaps independent of the channel gains. In this paper, we approximate the capacity of the symmetric Gaussian N-relay diamond network up to an additive gap of 1.8 bits and up to a multiplicative gap of a factor 14. Both gaps are independent of the channel gains, and, unlike the best previously known result, are also independent of the number of relays N in the network. Achievability is based on bursty amplify-and-forward, showing that this simple scheme is uniformly approximately optimal, both in the low-rate as well as high-rate regimes. The upper bound on capacity is based on a careful evaluation of the cut-set bound.
  75. Abstract:
    We consider a group of m trusted nodes that aim to create a shared secret key K, using a state-dependent wireless broadcast channel that exists from one of the honest nodes to the rest of the nodes including a passive eavesdropper Eve. All of the trusted nodes can also discuss over a cost-free and unlimited rate public channel which is also observed by Eve. For this setup, we develop an information-theoretically secure secret key agreement protocol. We show the optimality of this protocol for linear deterministic wireless broadcast channels as well as in the high-SNR regime for wireless channels with large dynamic range over channel states.
  76. Abstract:
    In this paper, we investigate the sum-capacity of the two-user Gaussian interference channel with Gaussian superposition coding and successive decoding. We first examine an approximate deterministic formulation of the problem, and introduce the complementarity conditions that capture the use of Gaussian coding and successive decoding. In the deterministic channel problem, we show that the constrained sum-capacity oscillates as a function of the cross link gain parameters between the information theoretic sum-capacity and the sum-capacity with interference treated as noise. Furthermore, we show that if the number of messages of either user is fewer than the minimum number required to achieve the constrained sum-capacity, the maximum achievable sum-rate drops to that with interference treated as noise. We translate the optimal schemes in the deterministic channel model to the Gaussian channel model, and also derive two upper bounds on the constrained sum-capacity. Numerical evaluations show that the constrained sum-capacity in the Gaussian channels oscillates between the sum-capacity with Gaussian Han-Kobayashi schemes and that with single message schemes.
  77. Abstract:
    We consider a group of m trusted nodes that aim to create a shared secret key K over a wireless channel in the presence an eavesdropper Eve. We assume an erasure broadcast channel from one of the honest nodes to the rest of them including Eve. All of the trusted nodes can also discuss over a cost-free public channel which is observed by Eve. For this setup we characterize the secret key generation capacity and propose an achievability scheme that is computationally efficient and employs techniques from network coding. Surprisingly, whether we have m = 2 nodes, or an arbitrary number m of nodes, we can establish a shared secret key among them at the same rate, independently of m.
  78. Abstract:
    Hierarchical cooperation is a communication strategy introduced recently by Özgür et al., where it was shown to significantly outperform standard multi-hop communication in some wireless scenarios. To achieve this gain over multi-hop communication, full availability of channel state information at all the nodes in the network is required. In this paper, we investigate the impact of absence of channel state information on the performance of hierarchical cooperation. If the product of coherence time and coherence bandwidth of the wireless channel is on the order of the number of nodes in the network, we show that non-coherent hierarchical cooperation achieves the same order rate as the coherent version. If the product is smaller than the number of nodes, we show that non-coherent hierarchical cooperation can still yield sizable gains over multihop communication, but may not achieve the same order rate as the coherent version.
  79. Abstract:
    In this paper we study two-stage Gaussian relay-interference networks where there are weak cross-links, causing the networks to behave like a chain of Z Gaussian channels. Our main result is an approximate characterization of the capacity region for such networks. We propose a new interference management scheme, termed interference neutralization, which is implemented using structured lattice codes. This scheme allows for over-the-air interference removal, without the transmitters having complete access the interfering signals.
  80. Download: on Arxiv 
  81. Abstract:
    This paper approximately resolves the information flow over wireless (Gaussian) relay networks to within a constant number of bits. It introduced the linear deterministic model and established a max-flow min-cut result for linear deterministic networks. The insights from the deterministic approach led to the approximate max-flow min-cut characterization for noisy Gaussian networks, through the introduction of a new relaying strategy called quantize-map-forward (QMF).
  82. Abstract:
    We propose a channel model for the non-coherent network coding introduced by Koetter and Kschischang. The model captures the essence of such a network operation, and we use it to calculate the capacity of non-coherent network codes as a function of network parameters. We prove that use of subspace coding is optimal, and show that, in some cases, the capacity-achieving distribution uses subspaces of several dimensions, where the employed dimensions depend on the packet length.
  83. Abstract:
    We show that source-channel separation is approximately optimal for transmitting a Gaussian source over a bandwidth mismatched Gaussian channel, for quadratic distortion measures. Furthermore, we show that the results can be extended to general broadcast channels, and the performance of the source-channel separation based approach is also within the same constant multiplicative factors of the optimum.
  84. Download: asymmd.pdf on Arxiv 
    Abstract:
    This paper introduces the asymmetric multi-level lossless data compression problem and gives a complete characterization for the three-description version. It then uses insights from this characterization to provide an approximate characterization for the 3-description asymmetric multiple description problem.
  85. Abstract:
    Approximately solves symmetric Gaussian multiple description problem to within a bit, by sandwiching the MD rate region between two polytopes separated by at most a fraction of a bit.
  86. Abstract:
    We characterize the rate region of the two-description multiple description coding for stationary Gaussian sources under the squared error distortion measure.
  87. Abstract:
    We introduce the problem of side-information scalable data compression In this problem, the encoder constructs a progressive description, such that the receiver with high quality side information will be able to truncate the bit-stream and reconstruct in the rate distortion sense, while the receiver with low quality side information will have to receive further data in order to decode. We provide a complete characterization of the rate distortion region for the important quadratic Gaussian case with multiple jointly Gaussian side-informations, where the side information quality does not have to be monotonic along the scalable coding order. Inner and outer bounds are provided to the rate distortion region for general discrete memoryless sources.
  88. Abstract:
    We consider the problem of transmitting a Gaussian source on a slowly fading Gaussian channel, subject to the mean squared error distortion measure. We propose an efficient algorithm to compute the optimal expected distortion at the receiver in linear time O(M), when the total number of possible discrete fading states is M. We also provide a derivation of the optimal power allocation when the fading state is a continuum, using the classical variational method.
  89. Abstract:
    We study the multi-user successive refinement problem (posed in Pradhan and Ramchandran, 2002), where the users are connected to a central server through links with different noiseless capacities. Each user requires to reconstruct the source in a scalable manner. We provide the best known achievable strategy for the two-user, two-layer case and the complete characterization of the rate-distortion region for the Gaussian source under the mean-squared error (MSE) distortion measure.
  90. Abstract:
    This solves an open problem (posed by Steinberg and Merhav, 2004) on multi-stage successive refinement with side information, when successive stages are for decoders with improving quality side-information. In solving this problem, we identified the general notion of successive refinability of data compression with side-information. A source-channel separation theorem is provided when the descriptions are sent over independent channels for the multistage case.
  91. Download: finbuf.pdf 
    Abstract:
    This paper was motivated by the transmission of information over finite buffer channels. Analyzing the capacity of such channels naturally led us to the study of deletion channels. In deletion channels, in contrast to erasure channels, symbols of the transmitted sequence are removed, and the receiver does not know which symbols have been deleted. This was a classic problem from the 1960s in the context of modeling synchronization errors. This paper gave the best known (at the time of publication) lower bounds to capacity of deletion channels since the 1960s. It also studied erasure channels with arbitrary memory in the erasure process. It showed that even when the erasure process has memory, feedback does not increase the capacity.
  92. Download: final_mdc.pdf 
    Abstract:
    This designs asymmetric multiple description lattice quantizers, which covers the entire range of the distortion profile, from symmetric to successive refinement. We present a solution to the labeling problem, which is an important part of the construction. We show that this construction is optimal in the high-rate regime, by comparing it to the information-theoretic bounds.
  93. Download: worstnoise.pdf 
    Abstract:
    This paper started with a simple question: is the maximum entropy noise the worst noise for additive channels? In the case of scalar channels with a power constraint on the noise, this is true, as is well known. However, we show that in the vector case, with covariance constraints, the answer is yes and no. Yes, if the transmit power is large enough and no otherwise. Along the way we give a solution to the mutual information game with covariance constraints and show that Gaussian solutions form saddle points, but there could also be other saddlepoints. We also demonstrate that the information rates can be achieved using mismatched (Gaussian) decoders.
  94. Download: nbi.pdf 
    Abstract:
    Narrowband interference (NBI) could occur in transmission media such as twisted pair or coaxial cable. We analyzed the effect of such interference on the data throughput for finite-blocklength transmission over noisy inter-symbol interference channels. It was shown that the worst narrowband interference spreads its power over the “sweet spots” of the signal (i.e. where the signal puts highest power). More precisely, the auto-correlation matrix of worst-case narrowband (rank-deficient) interference is shown to have the same eigendirections as the signal. Moreover, if the rank of the covariance matrix of the NBI is M
  95. Download: fading.pdf 
    Abstract:
    This is an early study of the capacity of MIMO channels inspired by the work of Telatar and Foschini. It shows that the capacity grows linearly in the number of transmit and receive antennas (degrees of freedom) either when the SNR becomes large or when the number of antennas in the MIMO system becomes large. It shows that the linear rate growth can be achieved by simpler linear detector structures, such as a matched filter receiver. However, it shows that the price paid for simple matched filter receivers is that the SNR growth flattens. It also examines the case where the channel matrix has a constant expected Frobenius norm. In this case, even with isotropic fading, it is shown that the capacity of MIMO channels does not grow linear in the number of antennas, but grows linearly in SNR. Finally, the effect of time-variation within a transmission block for ISI fading channels is examined in terms of capacity.
  96. Download: md_itw10.pdf 
    Abstract:
    We study the problem where there is a single adversarial node which injects signals to disrupt this communication in a parallel relay network. Like the source, it can only influence the destination through the relays. We develop an approximate characterization of the reliable transmission rate in the presence of such an adversary. A deterministic version of the same problem is solved exactly, yielding insights which are used in the approximate characterization.
  97. Download: tcdsspcom10.pdf 
    Abstract:
    We consider the source-channel separation architecture for lossy source coding in communication networks. It is shown that the separation approach is optimal when the memoryless sources at source nodes are arbitrarily correlated, each of which is to be reconstructed at possibly multiple destinations within certain distortions, and the channels in this network are synchronized, orthogonal and memoryless (i.e., noisy graphs).
  98. Download: od_isit10.pdf on Arxiv 
    Abstract:
    An approximate max-flow min-cut result for arbitrary wireless relay network was recently established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we show that the approximation result can be established by using lattices for transmission and quantization along with structured mappings at the relays. This also extended the original scalar quantizer analysis to vector quantizers and obtained a slightly better approximation constant.
  99. C. Tian, S. N. Diggavi, and S. Shamai, "The achievable distortion region of bivariate Gaussian source on Gaussian broadcast channel," in Proc. Proc. of IEEE ISIT 2010, Austin, Texas, 2010, pp. 146-150.
  100. C. Tian, J. Chen, S. N. Diggavi, and S. Shamai, "Optimality and approximate optimality of source-channel separation in networks," in Proc. Proc. of IEEE ISIT 2010, Austin, Texas, 2010, pp. 495-499.
  101. Note: Invited paper surveying our results on wireless relay network secrecy.
    Download: pdtizs10.pdf 
  102. Download: pdtisit10.pdf 
    Abstract:
    In this paper we consider information-theoretically secure communication between two special nodes (“source” and “destination”) in a memoryless network with authenticated relays, where the secrecy is with respect to a class of eavesdroppers. We develop achievable secrecy rates when authenticated relays also help increase secrecy rate by inserting noise into the network.
  103. Abstract:
    Lossless transmission of a set of correlated sources over a deterministic relay network is considered for two traffic requirements. In distributed multicast, the set of sources are to be delivered to a set of destinations. The source exchange requires all the nodes with access to sources to be able to reconstruct all other sources observed at other nodes. We develop achievable regions and outer bounds for both these situations. For linear deterministic networks, these bounds coincide, yielding a characterization.
  104. Abstract:
    In this paper we consider secret communication between two special nodes (“source” and “destination”) in a wireless network with authenticated relays: the message communicated to the destination is to be kept information-theoretically (unconditionally) secret from any eavesdropper within a class. Since the transmissions are broadcast and interfere with each other, complex signal interactions occur. We develop cooperative schemes which utilize these interactions in wireless communication over networks with arbitrary topology, and give provable unconditional secrecy guarantees.
  105. Abstract:
    The compound wiretap channel generalizes the classical problem in broadcast information-theoretic secrecy by allowing a class of potential eavesdroppers. In this paper we present a new coding scheme that generalizes known approaches to this problem. The scheme prefixes an artificial multiple access channel to the transmission scheme in order to design a structured transmit codebook. The idea is that such a structure can potentially increase the perfect secrecy rate for the legitimate users in the presence of the class of eavesdroppers.
  106. Download: sdfpitw09.pdf 
    Abstract:
    Abstract—We consider the two message set problem, where a source broadcasts a common message W1 to an arbitrary set of receivers U and a private message W2 to a subset of the receivers P !U . Transmissions occur over linear deterministic channels. For the case where at most two receivers do not require the private message, we give an exact characterization of the capacity region, where achievability is through linear coding.
  107. S. Mohajer, S. N. Diggavi, C. Fragouli, and D. Tse, "Capacity of Deterministic Z-Chain Relay-Interference Network," in Proc. IEEE Information Theory Workshop (ITW), Volos, Greece, 2009, pp. 331-335.
  108. S. Mohajer, M. Jafarisiavoshani, S. N. Diggavi, and C. and Fragouli, "On the Capacity of Multisource Non-Coherent Network Coding," in Proc. IEEE Information Theory Workshop (ITW), Volos, Greece, 2009, pp. 130-134.
  109. S. Mohajer and S. N. Diggavi, "Deterministic approach to wireless network error correction," in Proc. IEEE Information Theory Workshop (ITW), Volos, Greece, 2009, pp. 5-9.
  110. M. Jafarisiavoshani, S. Mohajer, C. Fragouli, and S. N. Diggavi, "On the Capacity of Non-Coherent Network Coding," in Proc. IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, 2009, pp. 273-277.
  111. C. Tian, S. N. Diggavi, and S. Shamai, "An Approximate Characterization For the Gaussian Broadcasting Distortion Region," in Proc. IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, 2009, pp. 2477-2481.
  112. A. Khisti, S. N. Diggavi, and G. W. Wornell, "Secret key agreement using asymmetry in channel state knowledge," in Proc. IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, 2009, pp. 2286-2290.
  113. Download: pdtencsiisit09.pdf 
    Abstract:
    In this paper we find properties that are shared between two seemingly unrelated lossy source coding setups with side-information. The first setup is when the source and sideinformation are jointly Gaussian and the distortion measure is quadratic. The second setup is when the side-information is an erased version of the source. We begin with the observation that in both these cases the Wyner-Ziv and conditional ratedistortion functions are equal. Next, we consider the case when there are two decoders with access to different side-information sources. For the case when the encoder has access to the sideinformation we establish bounds on the rate-distortion function and a sufficient condition for tightness. Under this condition, we find a characterization of the rate-distortion function for physically degraded side-information. This characterization holds for both the Gaussian and erasure setups.
  114. S. Mohajer, S. N. Diggavi, and D. Tse, "Approximate Capacity of a Class of Gaussian Relay-Interference Networks," in Proc. IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, 2009, pp. 31-35.
  115. Download: pdt_icc09.pdf 
    Abstract:
    We introduce the interference-multiple-access channel, which is a discrete memoryless channel with two transmitters and two receivers, similar to the interference channel. One receiver is required to decode the information encoded at one transmitter, the other receiver is required to decode the messages from both transmitters. We provide an inner bound on the capacity region of this channel, as well as an outer bound for a special class of such channels. For this class, we also quantify the gap between inner and outer bound and show that the bounds match for a semi-deterministic channel, providing a complete characterization. For the Gaussian case, we show that the gap is at most 1 bit, yielding an approximate characterization.
  116. Download: pdtita09final.pdf 
    Abstract:
    This paper studies the idea of noise insertion by authenticated relays through friendly jamming. We develop the secrecy rate achievable in arbitrary (deterministic) networks when there are relays actively helping secrecy.
  117. Download: pdt_allerton08.pdf 
    Abstract:
    We study a line network with an eavesdropper having access to the relay transmission. We assume that there could also be a public feedback channel from the destination. We develop achievable strategies to achieve certain rate-equivocation pairs.
  118. S. Mohajer, S. N. Diggavi, C. Fragouli, and D. Tse, "Transmission techniques for relay-interference networks," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2008, pp. 464-474.
  119. S. Avestimehr, S. N. Diggavi, and D N C. Tse, "Approximate characterization of capacity in Gaussian relay networks," in Proc. IEEE International Wireless Communications and Mobile Computing Conference (IWCMC), Crete, Greece, 2008, pp. 56-61.
  120. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Approximate Capacity of Gaussian Relay Networks," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 474-478.
  121. C. Tian, S. Mohajer, and S N. Diggavi, "Approximating the Gaussian multiple description rate region under symmetric distortion constraints," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 1413-1417.
  122. S. Mohajer, C. Tian, and S. N. Diggavi, "Asymmetric Gaussian Multiple Descriptions and Asymmetric Multilevel Diversity Coding," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 1992-1996.
  123. M. Jafarisiavoshani, C. Fragouli, and S N. Diggavi, "Noncoherent Multisource Network Coding," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 817-821.
  124. A. Khisti, S. N. Diggavi, and G W. Wornell, "Secret key generation with correlated sources and noisy channels," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 1005-1009.
  125. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Information flow over compound wireless relay networks," in Proc. IEEE Zurich Seminar on Communications (IZS), Zurich, Switzerland, 2008, p. 92.
  126. C. Tian, S. Mohajer, and S. N. Diggavi, "On the symmetric Gaussian multiple description rate-distortion function," in Proc. IEEE Data Compression Conference (DCC), Snowbird, Utah, 2008, pp. 412-421.
  127. S. Mohajer, C. Tian, and S. N. Diggavi, "Asymmetric Multilevel Diversity Coding," in Proc. IEEE Data Compression Conference (DCC), Snowbird, Utah, 2008, pp. 402-411.
  128. C. Tian, S. Mohajer, and S. N. Diggavi, "On the Gaussian $K$-description problem under symmetric distortion constraints," in Proc. Information Theory and Applications Workshop, UCSD, San Diego, California, 2008, pp. 401-406.
  129. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Wireless network information flow," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2007.
  130. Download: degmsgsetbc07.pdf 
    Abstract:
    In this paper we study the nested (degraded) message set problem, where user i requires messages W_1, . . . ,W_i. We study this for a MIMO linear deterministic broadcast channel model, which is motivated by some recent successes in using such models to obtain insights into approximate characterizations for the Gaussian relay and interference channels. We establish the complete solution for the K = 3 user nested message problem for the MIMO linear deterministic broadcast channel. We also establish some extremal points for the general K-user case, where there are only two messages of interest.
  131. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "A Deterministic Approach to Wireless Relay Networks," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2007.
  132. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "A deterministic model for wireless relay networks and its capacity," in Proc. IEEE Information Theory Workshop (ITW) Bergen, Norway, 2007, pp. 6-11.
  133. C. Tian, A. Steiner, S. Shamai, and S. N. Diggavi, "Expected distortion for Gaussian source with broadcast transmission strategy over a fading channel," in Proc. IEEE Information Theory Workshop (ITW) Bergen, Norway, 2007, pp. 42-46.
  134. C. Tian and S. N. Diggavi, "On scalable source coding with decoder side informations," in Proc. IEEE International Symposium on Information Theory (ISIT), Nice,France, 2007, pp. 1461-1465.
  135. Download: delubisit07.pdf 
    Abstract:
    We present upper bounds on the capacity of the i.i.d. binary deletion channel, where each bit is independently deleted with a fixed probability d. We provide a general approach that gives a numerical answer for fixed d, and provide an argument that gives asymptotic upper bounds as d goes to 1. These appear to be the first non-trivial upper bounds for this probabilistic deletion channel.
  136. J. Chen, C. Tian, and S N. Diggavi, "Multiple description coding for stationary sources," in Proc. IEEE Data Compression Conference (DCC), Snowbird, Utah, 2007, pp. 73-82.
  137. Download: db_hbitw06.pdf 
  138. C. Tian, J. Chen, and S. N. Diggavi, "Multiuser successive refinement and multiple description coding," in Proc. IEEE Information Theory Workshop (ITW), Chengdu, China, 2006, pp. 293-297.
  139. Abstract:
    We investigate source coding in a cascade communication system consisting of an encoder, a relay and an end terminal, where both the relay and the end terminal wish to reconstruct source X with certain fidelities. Additionally, side-informations Z and Y are available at the relay and the end terminal, respectively. The side-information Z at the relay is a physically degraded version of side-information Y at the end terminal. We give an exact characterization for the Gaussian quadratic distortion version of the problem and develop inner and outer bounds for the general case.
  140. C.Tian and S. N. Diggavi, "Multistage successive refinement for Wyner-Ziv source coding with degraded side information," in Proc. IEEE International Symposium on Information Theory, Seattle, 2006.
  141. E. Perron, S. N. Diggavi, and I E. Telatar, "On the Role of Encoder Side-Information in Source Coding for Multiple Decoders," in Proc. IEEE International Symposium on Information Theory, Seattle, 2006.
  142. C.Tian and S. N. Diggavi, "On scalable source coding for multiple decoders with side-information," in Proc. Information Theory and Applications Workshop, San Diego, 2006.
    Note: invited paper
  143. Download: mdsi.pdf 
    Abstract:
    We formulate a multi-terminal source coding problem, where we are required to construct a multiple description source code for a source sequence when side information about dependent random processes is available at the decoder only, or at both the decoder and the encoder. We describe an achievable rate-distortion region for these problems. In the quadratic Gaussian case, and when there is common side information among the decoders, we show that the rate region when both the encoder and decoder have access to the side information coincides with that of decoder–only side information. This is analogous to the single-description (Wyner-Ziv) case, and an explicit characterization of the rate-distortion region is provided for this case.
  144. S. N. Diggavi and M. Grossglauser, "Bounds on capacity of deletion channels," in Proc. IEEE International Symposium on Information Theory (ISIT), Lausanne, 2002, p. 421.
  145. N. Al-Dhahir and S N. Diggavi, "On achievable rates on time-varying frequency-selective channels," in Proc. Conference on Information Sciences and Systems, Princeton, New Jersey, 2002, pp. 860-865.
  146. Download: allerton01.pdf 
    Abstract:
    This paper develops the best known (at the time of publication) capacity lower bounds to the deletion channel since the 1960s. It also makes a connection between deletion channels and the well studied problem of the length of the longest common subsequence. It shows that the capacity of the deletion channel for large alphabet size is close to the corresponding erasure channel, though the coding schemes for the two channels are drastically different.
  147. S. N. Diggavi and M. Grossglauser, "Information transmission over a finite buffer channel," in Proc. IEEE International Symposium on Information Theory (ISIT),Sorrento, Italy, 2000, p. 52.
  148. S. N. Diggavi, N. J. A. Sloane, and V. A. Vaishampayan, "Design of Asymmetric Multiple Description Lattice Vector Quantizers," in Proc. IEEE Data Compression Conference (DCC),Snowbird, Utah, 2000, pp. 490-499.
  149. N. Al-Dhahir and S. N. Diggavi, "Worst-Case Narrow-Band Interference over Noisy Dispersive Channels," in Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP, Istanbul, Turkey, 2000, pp. 2817-2820.
  150. S. N. Diggavi, "On achievable performance of spatial diversity fading channels," in Proc. International Symposium on Information Theory, Boston, ISIT'98, 1998, p. 396.
  151. S. N. Diggavi and T. M. Cover, "Is Maximum Entropy Noise the Worst?," in Proc. International Symposium on Information Theory, Ulm, 1997, p. 278.

Hardware security

Nanopore sequencing

  1. W. Mao, S. Diggavi, and K. Sreeram, "Models and information-theoretic bounds for nanopore sequencing," Preprint.
  2. Download: isit_nanopore.pdf 

Approximation in network information theory

  1. S. Avestimehr, S. N. Diggavi, C. Tian, and D. Tse, An approximation approach to network information theory, NOW publishers, 2014.
  2. Download: lattice_qmf.pdf 
    Abstract:
    Recently, a new relaying strategy, quantize-map-and-forward (QMF) scheme, has been demonstrated to approximately achieve (within an additive constant number of bits) the Gaussian relay network capacity, universally, i.e., for arbitrary topologies, channel gains, and SNRs. This was established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we develop structured lattice codes that implement the QMF strategy. The main result of this paper is that such structured lattice codes can approximately achieve the Gaussian relay network capacity universally, again within an additive constant. In addition, we establish a similar result for half-duplex networks, where we demonstrate that one can approximately achieve the capacity using fixed transmit-receive (TX-RX) schedules for the relays with no transmit power optimization across the different TX-RX states of the network.
  3. Download: on Arxiv 
    Abstract:
    We consider the Gaussian “diamond” or parallel relay network, in which a source node transmits a message to a destination node with the help of N relays. Even for the symmetric setting, in which the channel gains to the relays are identical and the channel gains from the relays are identical, the capacity of this channel is unknown in general. The best known capacity approximation is up to an additive gap of order N bits and up to a multiplicative gap of order N2, with both gaps independent of the channel gains. In this paper, we approximate the capacity of the symmetric Gaussian N-relay diamond network up to an additive gap of 1.8 bits and up to a multiplicative gap of a factor 14. Both gaps are independent of the channel gains and, unlike the best previously known result, are also independent of the number of relays N in the network. Achievability is based on bursty amplify-and-forward, showing that this simple scheme is uniformly approximately optimal, both in the low-rate as well as in the high-rate regimes. The upper bound on capacity is based on a careful evaluation of the cut-set bound. We also present approximation results for the asymmetric Gaussian N-relay diamond network. In particular, we show that bursty amplify-and-forward combined with optimal relay selection achieves a rate within a factor O(log4(N)) of capacity with preconstant in the order notation independent of the channel gains.
  4. Abstract:
    We consider the Gaussian “diamond” or parallel relay network, in which a source node transmits a message to a destination node with the help of N relays. Even for the symmetric setting, in which the channel gains to the relays are identical and the channel gains from the relays are identical, the capacity of this channel is unknown in general. The best known capacity approximation is up to an additive gap of order N bits and up to a multiplicative gap of order N2, with both gaps independent of the channel gains. In this paper, we approximate the capacity of the symmetric Gaussian N-relay diamond network up to an additive gap of 1.8 bits and up to a multiplicative gap of a factor 14. Both gaps are independent of the channel gains, and, unlike the best previously known result, are also independent of the number of relays N in the network. Achievability is based on bursty amplify-and-forward, showing that this simple scheme is uniformly approximately optimal, both in the low-rate as well as high-rate regimes. The upper bound on capacity is based on a careful evaluation of the cut-set bound.
  5. Abstract:
    In this paper we study two-stage Gaussian relay-interference networks where there are weak cross-links, causing the networks to behave like a chain of Z Gaussian channels. Our main result is an approximate characterization of the capacity region for such networks. We propose a new interference management scheme, termed interference neutralization, which is implemented using structured lattice codes. This scheme allows for over-the-air interference removal, without the transmitters having complete access the interfering signals.
  6. Abstract:
    This paper approximately resolves the information flow over wireless (Gaussian) relay networks to within a constant number of bits. It introduced the linear deterministic model and established a max-flow min-cut result for linear deterministic networks. The insights from the deterministic approach led to the approximate max-flow min-cut characterization for noisy Gaussian networks, through the introduction of a new relaying strategy called quantize-map-forward (QMF).
  7. Abstract:
    We show that source-channel separation is approximately optimal for transmitting a Gaussian source over a bandwidth mismatched Gaussian channel, for quadratic distortion measures. Furthermore, we show that the results can be extended to general broadcast channels, and the performance of the source-channel separation based approach is also within the same constant multiplicative factors of the optimum.
  8. Download: asymmd.pdf on Arxiv 
    Abstract:
    This paper introduces the asymmetric multi-level lossless data compression problem and gives a complete characterization for the three-description version. It then uses insights from this characterization to provide an approximate characterization for the 3-description asymmetric multiple description problem.
  9. Abstract:
    Approximately solves symmetric Gaussian multiple description problem to within a bit, by sandwiching the MD rate region between two polytopes separated by at most a fraction of a bit.
  10. Download: tcdsspcom10.pdf 
    Abstract:
    We consider the source-channel separation architecture for lossy source coding in communication networks. It is shown that the separation approach is optimal when the memoryless sources at source nodes are arbitrarily correlated, each of which is to be reconstructed at possibly multiple destinations within certain distortions, and the channels in this network are synchronized, orthogonal and memoryless (i.e., noisy graphs).
  11. Download: od_isit10.pdf on Arxiv 
    Abstract:
    An approximate max-flow min-cut result for arbitrary wireless relay network was recently established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we show that the approximation result can be established by using lattices for transmission and quantization along with structured mappings at the relays. This also extended the original scalar quantizer analysis to vector quantizers and obtained a slightly better approximation constant.
  12. C. Tian, J. Chen, S. N. Diggavi, and S. Shamai, "Optimality and approximate optimality of source-channel separation in networks," in Proc. Proc. of IEEE ISIT 2010, Austin, Texas, 2010, pp. 495-499.
  13. Abstract:
    Lossless transmission of a set of correlated sources over a deterministic relay network is considered for two traffic requirements. In distributed multicast, the set of sources are to be delivered to a set of destinations. The source exchange requires all the nodes with access to sources to be able to reconstruct all other sources observed at other nodes. We develop achievable regions and outer bounds for both these situations. For linear deterministic networks, these bounds coincide, yielding a characterization.
  14. S. Mohajer, S. N. Diggavi, C. Fragouli, and D. Tse, "Capacity of Deterministic Z-Chain Relay-Interference Network," in Proc. IEEE Information Theory Workshop (ITW), Volos, Greece, 2009, pp. 331-335.
  15. C. Tian, S. N. Diggavi, and S. Shamai, "An Approximate Characterization For the Gaussian Broadcasting Distortion Region," in Proc. IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, 2009, pp. 2477-2481.
  16. S. Mohajer, S. N. Diggavi, and D. Tse, "Approximate Capacity of a Class of Gaussian Relay-Interference Networks," in Proc. IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, 2009, pp. 31-35.
  17. Download: pdt_icc09.pdf 
    Abstract:
    We introduce the interference-multiple-access channel, which is a discrete memoryless channel with two transmitters and two receivers, similar to the interference channel. One receiver is required to decode the information encoded at one transmitter, the other receiver is required to decode the messages from both transmitters. We provide an inner bound on the capacity region of this channel, as well as an outer bound for a special class of such channels. For this class, we also quantify the gap between inner and outer bound and show that the bounds match for a semi-deterministic channel, providing a complete characterization. For the Gaussian case, we show that the gap is at most 1 bit, yielding an approximate characterization.
  18. Download: pdtita09final.pdf 
    Abstract:
    This paper studies the idea of noise insertion by authenticated relays through friendly jamming. We develop the secrecy rate achievable in arbitrary (deterministic) networks when there are relays actively helping secrecy.
  19. S. Mohajer, S. N. Diggavi, C. Fragouli, and D. Tse, "Transmission techniques for relay-interference networks," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2008, pp. 464-474.
  20. S. Avestimehr, S. N. Diggavi, and D N C. Tse, "Approximate characterization of capacity in Gaussian relay networks," in Proc. IEEE International Wireless Communications and Mobile Computing Conference (IWCMC), Crete, Greece, 2008, pp. 56-61.
  21. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Approximate Capacity of Gaussian Relay Networks," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 474-478.
  22. C. Tian, S. Mohajer, and S N. Diggavi, "Approximating the Gaussian multiple description rate region under symmetric distortion constraints," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 1413-1417.
  23. S. Mohajer, C. Tian, and S. N. Diggavi, "Asymmetric Gaussian Multiple Descriptions and Asymmetric Multilevel Diversity Coding," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 1992-1996.
  24. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Information flow over compound wireless relay networks," in Proc. IEEE Zurich Seminar on Communications (IZS), Zurich, Switzerland, 2008, p. 92.
  25. C. Tian, S. Mohajer, and S. N. Diggavi, "On the symmetric Gaussian multiple description rate-distortion function," in Proc. IEEE Data Compression Conference (DCC), Snowbird, Utah, 2008, pp. 412-421.
  26. S. Mohajer, C. Tian, and S. N. Diggavi, "Asymmetric Multilevel Diversity Coding," in Proc. IEEE Data Compression Conference (DCC), Snowbird, Utah, 2008, pp. 402-411.
  27. C. Tian, S. Mohajer, and S. N. Diggavi, "On the Gaussian $K$-description problem under symmetric distortion constraints," in Proc. Information Theory and Applications Workshop, UCSD, San Diego, California, 2008, pp. 401-406.
  28. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Wireless network information flow," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2007.
  29. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "A Deterministic Approach to Wireless Relay Networks," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2007.
  30. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "A deterministic model for wireless relay networks and its capacity," in Proc. IEEE Information Theory Workshop (ITW) Bergen, Norway, 2007, pp. 6-11.

Coded caching in wireless networks

  1. Download: karam_hier.pdf 
  2. Download: jad_layered.pdf 
  3. Download: jad_multilevel.pdf 
  4. Download: jad_dof.pdf 
  5. Note: available on arXiv:1705.03852 [cs.IT]
    Download: jad_adaptive.pdf 
  6. Download: on Arxiv 
    Abstract:
    Emerging heterogeneous wireless architectures consist of a dense deployment of local-coverage wireless access points (APs) with high data rates, along with sparsely-distributed, large-coverage macro-cell base stations (BS). We design a coded caching-and-delivery scheme for such architectures that equips APs with storage, enabling content pre-fetching prior to knowing user demands. Users requesting content are served by connecting to local APs with cached content, as well as by listening to a BS broadcast transmission. For any given content popularity profile, the goal is to design the caching-and-delivery scheme so as to optimally trade off the transmission cost at the BS against the storage cost at the APs and the user cost of connecting to multiple APs. We design a coded caching scheme for non-uniform content popularity that dynamically allocates user access to APs based on requested content. We demonstrate the approximate optimality of our scheme with respect to information-theoretic bounds. We numerically evaluate it on a YouTube dataset and quantify the trade-off between transmission rate, storage, and access cost. Our numerical results also suggest the intriguing possibility that, to gain most of the benefits of coded caching, it suffices to divide the content into a small number of popularity classes.
  7. Download: on Arxiv 
    Abstract:
    It has been recently established that joint design of content delivery and storage (coded caching) can significantly improve performance over conventional caching. This has also been extended to the case when content has non-uniform popularity through several models. In this paper we focus on a multi-level popularity model, where content is divided into levels based on popularity. We consider two extreme cases of user distribution across caches for the multi-level popularity model: a single user per cache (single-user setup) versus a large number of users per cache (multi-user setup). When the capacity approximation is universal (independent of number of popularity levels as well as number of users, files and caches), we demonstrate a dichotomy in the order-optimal strategies for these two extreme cases. In the multi-user case, sharing memory among the levels is order-optimal, whereas for the single-user case clustering popularity levels and allocating all the memory to them is the order-optimal scheme. In proving these results, we develop new information-theoretic lower bounds for the problem.
  8. Abstract:
    It has recently been demonstrated that for single-layer cache networks, jointly designing caching and delivery can enable significant benefits over conventional caching. This was based on strategically designing the cached content to induce coded multicasting opportunities even among users with different demands and without foreknowledge of the user demands. In this work, we extend this coded caching approach to a multi-hop hierarchical content delivery network with two layers of caches. We propose a new caching scheme that combines two basic approaches. The first approach provides coded multicasting opportunities within each layer (through decoding and forwarding); the second approach provides coded multicasting opportunities across multiple layers (through strategic forwarding without decoding). By striking the right balance between these two approaches, we show that the proposed scheme achieves the optimal communication rates to within a constant multiplicative and additive gap. We further show that there is no tension between the rates in each of the two layers up to the aforementioned gap. Thus, both layers can simultaneously operate at approximately the minimum rate.
  9. Download: on Arxiv 
    Abstract:
    Recent work has demonstrated that, for content caching, joint design of storage and delivery can yield significant benefits over conventional caching approaches. This is based on storing content in the caches in a way that creates coded-multicast opportunities even among users with different demands. Such a coded-caching scheme has been shown to be order-optimal for a caching system with single-level content, i.e., one where all content is uniformly popular. In this work, we consider a system with content divided into multiple levels, based on varying degrees of popularity. The main contribution of this work is the derivation of an information-theoretic outer bound for the multi-level setup, and the demonstration that, under some natural regularity conditions, a memory-sharing scheme, which operates each level in isolation according to a single-level coded caching scheme, is in fact order-optimal with respect to this outer bound.

Wireless interference management

  1. Download: isit16_ic_p2p.pdf 
  2. Download: twc17_ic_p2p.pdf 
  3. Download: twc16_d2d.pdf 
  4. Download: bds_fd.pdf www 
  5. Download: isit15_fd_kd.pdf 
  6. Download: kwd_it15.pdf www 
  7. Download: on Arxiv 
    Abstract:
    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].
  8. Abstract:
    Recent results in wireless full-duplex promise rate gains over the half-duplex counterpart when two nodes exchange messages with each other. However, when multiple full-duplex nodes operate simultaneously, the resulting network has increased internode interference compared to the half-duplex counterpart. The increased internode interference can potentially limit the rate gain achievable due to introduction of full-duplex capability. In this paper, we present new interference management strategies tha handle internode interference for full-duplex enabled network and achieve rate gains over its half-duplex counterpart.
  9. Download: ach_gicifb.pdf 
    Abstract:
    We consider the two-user Gaussian interference channel with intermittent channel output feedback. We derive an achievable rate region that corresponds to the capacity region of the linear deterministic version of the problem. The result shows that passive and unreliable feedback can be harnessed to provide multiplicative capacity gain in Gaussian interference channels. In contrast to other schemes developed for interference channel 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 find that when the feedback links are active with sufficiently large probabilities, the perfect feedback sum-capacity is achieved to within a constant gap.
  10. I.-H. Wang and S. N. Diggavi, "Managing bursty interference with feedback," in Proc. IEEE Information Theory Workshop (ITW) 2013, 2013.
  11. Download: fd_ul_dl.pdf 
    Abstract:
    Feasibility of full-duplex opens up the possibility of applying it to cellular networks to operate uplink and downlink simultaneously for multiple users. However, simultaneous operation of uplink and downlink poses a new challenge of intra-cell inter-node interference. In this paper, we identify scenarios where inter-node interference can be managed to provide significant gain in degrees of freedom over the conventional half-duplex cellular design.
  12. Download: bursty_ic.pdf 
    Abstract:
    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.
  13. Download: on Arxiv 
    Abstract:
    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.
  14. Download: on Arxiv 
    Abstract:
    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.
  15. Abstract:
    In this paper we study interference management in wireless networks with bursty user traffic. In each time slot, whether a user is on or off for transmission is governed by its own Bernoulli random state. At each transmitter, the states of activities of other users are only available via feedback. We investigate a canonical two-user bursty Gaussian interference channel (IC) with three different feedback models: (1) no feedback, (2) delayed state feedback, and (3) channel output feedback. In all three cases, we characterize the capacity region of the bursty Gaussian IC to within a bounded gap. It turns out that the near-optimal transmit strategies in the non-bursty IC suffice to establish the approximate characterization of capacity in all three cases. In other words, traffic burstiness does not change the high-SNR optimality of the schemes as long as receivers keep track of user activities. Moreover, the capacity region with delayed state feedback is within a bounded gap to that without feedback, and therefore delayed state feedback does not provide significant improvement at high SNR.
  16. Download: suc_dec_ic.pdf 
    Abstract:
    In this paper, we investigate the maximum achievable sum-rate of the two-user Gaussian interference channel with Gaussian superposition coding and successive decoding. We first examine an approximate deterministic formulation of the problem, and introduce the complementarity conditions that capture the use of Gaussian coding and successive decoding. In the deterministic channel problem, we find the constrained sum-capacity and its achievable schemes with the minimum number of messages, first in symmetric channels, and then in general asymmetric channels. We show that the constrained sum-capacity oscillates as a function of the cross link gain parameters between the information theoretic sum-capacity and the sum-capacity with interference treated as noise. Furthermore, we show that if the number of messages of either of the two users is fewer than the minimum number required to achieve the constrained sum-capacity, the maximum achievable sum-rate drops to that with interference treated as noise. We provide two algorithms to translate the optimal schemes in the deterministic channel model to the Gaussian channel model. We also derive two upper bounds on the maximum achievable sum-rate of the Gaussian Han-Kobayashi schemes, which automatically upper bound the maximum achievable sum-rate using successive decoding of Gaussian codewords. Numerical evaluations show that, similar to the deterministic channel results, the maximum achievable sum-rate with successive decoding in the Gaussian channels oscillates between that with Han-Kobayashi schemes and that with single message schemes.
  17. Abstract:
    In this paper, we investigate the sum-capacity of the two-user Gaussian interference channel with Gaussian superposition coding and successive decoding. We first examine an approximate deterministic formulation of the problem, and introduce the complementarity conditions that capture the use of Gaussian coding and successive decoding. In the deterministic channel problem, we show that the constrained sum-capacity oscillates as a function of the cross link gain parameters between the information theoretic sum-capacity and the sum-capacity with interference treated as noise. Furthermore, we show that if the number of messages of either user is fewer than the minimum number required to achieve the constrained sum-capacity, the maximum achievable sum-rate drops to that with interference treated as noise. We translate the optimal schemes in the deterministic channel model to the Gaussian channel model, and also derive two upper bounds on the constrained sum-capacity. Numerical evaluations show that the constrained sum-capacity in the Gaussian channels oscillates between the sum-capacity with Gaussian Han-Kobayashi schemes and that with single message schemes.

Wireless networks

  1. A. Sengupta, Y. Ezzeldin, S. Brahma, C. Fragouli, and S. Diggavi, "Quantize-map-forward (QMF) relaying: an experimental study," Preprint.
  2. Download: isit16_ic_p2p.pdf 
  3. Download: twc17_ic_p2p.pdf 
  4. Download: twc16_d2d.pdf 
  5. Download: karam_hier.pdf 
  6. Download: jad_layered.pdf 
  7. Download: jad_multilevel.pdf 
  8. Download: jad_dof.pdf 
  9. Note: available on arXiv:1705.03852 [cs.IT]
    Download: jad_adaptive.pdf 
  10. Download: on Arxiv 
    Abstract:
    Emerging heterogeneous wireless architectures consist of a dense deployment of local-coverage wireless access points (APs) with high data rates, along with sparsely-distributed, large-coverage macro-cell base stations (BS). We design a coded caching-and-delivery scheme for such architectures that equips APs with storage, enabling content pre-fetching prior to knowing user demands. Users requesting content are served by connecting to local APs with cached content, as well as by listening to a BS broadcast transmission. For any given content popularity profile, the goal is to design the caching-and-delivery scheme so as to optimally trade off the transmission cost at the BS against the storage cost at the APs and the user cost of connecting to multiple APs. We design a coded caching scheme for non-uniform content popularity that dynamically allocates user access to APs based on requested content. We demonstrate the approximate optimality of our scheme with respect to information-theoretic bounds. We numerically evaluate it on a YouTube dataset and quantify the trade-off between transmission rate, storage, and access cost. Our numerical results also suggest the intriguing possibility that, to gain most of the benefits of coded caching, it suffices to divide the content into a small number of popularity classes.
  11. Download: on Arxiv 
    Abstract:
    It has been recently established that joint design of content delivery and storage (coded caching) can significantly improve performance over conventional caching. This has also been extended to the case when content has non-uniform popularity through several models. In this paper we focus on a multi-level popularity model, where content is divided into levels based on popularity. We consider two extreme cases of user distribution across caches for the multi-level popularity model: a single user per cache (single-user setup) versus a large number of users per cache (multi-user setup). When the capacity approximation is universal (independent of number of popularity levels as well as number of users, files and caches), we demonstrate a dichotomy in the order-optimal strategies for these two extreme cases. In the multi-user case, sharing memory among the levels is order-optimal, whereas for the single-user case clustering popularity levels and allocating all the memory to them is the order-optimal scheme. In proving these results, we develop new information-theoretic lower bounds for the problem.
  12. Download: bds_fd.pdf www 
  13. Download: isit15_fd_kd.pdf 
  14. Download: kwd_it15.pdf www 
  15. Download: koltead_it15.pdf www 
  16. Abstract:
    Wireless network topologies change over time and maintaining routes requires frequent updates. Updates are costly in terms of consuming throughput available for data transmission, which is precious in wireless networks. In this paper, we ask whether there exist low-overhead schemes that produce near-optimal routes. We show that random geometric graphs and variants have a nice property that they are doubling metric spaces, with high probability. This enables us to design hierarchical routing schemes with provable performance that account for the user mobility and scale well with network size.
  17. Download: fto_cod.pdf 
    Abstract:
    In this paper we examine the value of feedback that comes from overhearing, without dedicated feedback resources. We focus on a simple model for this purpose: a deterministic two-hop interference channel, where feedback comes from overhearing the forward-links. A new aspect brought by this setup is the dual-role of the relay signal. While the relay signal needs to convey the source message to its corresponding destination, it can also provide a feedback signal which can potentially increase the capacity of the first hop. We derive inner and outer bounds on the sum capacity which match for a large range of the parameter values. Our results identify the parameter ranges where overhearing can provide non-negative capacity gain and can even achieve the performance with dedicated-feedback resources. The results also provide insights into which transmissions are most useful to overhear.
  18. Abstract:
    It has recently been demonstrated that for single-layer cache networks, jointly designing caching and delivery can enable significant benefits over conventional caching. This was based on strategically designing the cached content to induce coded multicasting opportunities even among users with different demands and without foreknowledge of the user demands. In this work, we extend this coded caching approach to a multi-hop hierarchical content delivery network with two layers of caches. We propose a new caching scheme that combines two basic approaches. The first approach provides coded multicasting opportunities within each layer (through decoding and forwarding); the second approach provides coded multicasting opportunities across multiple layers (through strategic forwarding without decoding). By striking the right balance between these two approaches, we show that the proposed scheme achieves the optimal communication rates to within a constant multiplicative and additive gap. We further show that there is no tension between the rates in each of the two layers up to the aforementioned gap. Thus, both layers can simultaneously operate at approximately the minimum rate.
  19. Download: on Arxiv 
    Abstract:
    Recent work has demonstrated that, for content caching, joint design of storage and delivery can yield significant benefits over conventional caching approaches. This is based on storing content in the caches in a way that creates coded-multicast opportunities even among users with different demands. Such a coded-caching scheme has been shown to be order-optimal for a caching system with single-level content, i.e., one where all content is uniformly popular. In this work, we consider a system with content divided into multiple levels, based on varying degrees of popularity. The main contribution of this work is the derivation of an information-theoretic outer bound for the multi-level setup, and the demonstration that, under some natural regularity conditions, a memory-sharing scheme, which operates each level in isolation according to a single-level coded caching scheme, is in fact order-optimal with respect to this outer bound.
  20. Download: quilt.pdf 
    Abstract:
    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.
  21. Download: lattice_qmf.pdf 
    Abstract:
    Recently, a new relaying strategy, quantize-map-and-forward (QMF) scheme, has been demonstrated to approximately achieve (within an additive constant number of bits) the Gaussian relay network capacity, universally, i.e., for arbitrary topologies, channel gains, and SNRs. This was established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we develop structured lattice codes that implement the QMF strategy. The main result of this paper is that such structured lattice codes can approximately achieve the Gaussian relay network capacity universally, again within an additive constant. In addition, we establish a similar result for half-duplex networks, where we demonstrate that one can approximately achieve the capacity using fixed transmit-receive (TX-RX) schedules for the relays with no transmit power optimization across the different TX-RX states of the network.
  22. Download: ach_gicifb.pdf 
    Abstract:
    We consider the two-user Gaussian interference channel with intermittent channel output feedback. We derive an achievable rate region that corresponds to the capacity region of the linear deterministic version of the problem. The result shows that passive and unreliable feedback can be harnessed to provide multiplicative capacity gain in Gaussian interference channels. In contrast to other schemes developed for interference channel 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 find that when the feedback links are active with sufficiently large probabilities, the perfect feedback sum-capacity is achieved to within a constant gap.
  23. I.-H. Wang and S. N. Diggavi, "Managing bursty interference with feedback," in Proc. IEEE Information Theory Workshop (ITW) 2013, 2013.
  24. Download: fd_ul_dl.pdf 
    Abstract:
    Feasibility of full-duplex opens up the possibility of applying it to cellular networks to operate uplink and downlink simultaneously for multiple users. However, simultaneous operation of uplink and downlink poses a new challenge of intra-cell inter-node interference. In this paper, we identify scenarios where inter-node interference can be managed to provide significant gain in degrees of freedom over the conventional half-duplex cellular design.
  25. Abstract:
    We present the design and experimental evaluation of a wireless system that exploits relaying in the context of WiFi. We opt for WiFi given its popularity and wide spread use for a number of applications, such as smart homes. Our testbed consists of three nodes, a source, a relay and a destination, that operate using the physical layer procedures of IEEE802.11. We deploy three main competing strategies that have been proposed for relaying, Decode-and-Forward (DF), Amplify-and-Forward (AF) and Quantize-Map-Forward (QMF). QMF is the most recently introduced of the three, and although it was shown in theory to approximately achieve the capacity of arbitrary wireless networks, its performance in practice had not been evaluated. We present in this work experimental results---to the best of our knowledge, the first ones---that compare QMF, AF and DF in a realistic indoor setting. We find that QMF is a competitive scheme to the other two, offering in some cases up to 12% throughput benefits and up to 60% improvement in frame error-rates over the next best scheme.
  26. Download: bursty_ic.pdf 
    Abstract:
    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.
  27. Download: on Arxiv 
    Abstract:
    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.
  28. Download: on Arxiv 
    Abstract:
    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.
  29. Abstract:
    In this paper we study interference management in wireless networks with bursty user traffic. In each time slot, whether a user is on or off for transmission is governed by its own Bernoulli random state. At each transmitter, the states of activities of other users are only available via feedback. We investigate a canonical two-user bursty Gaussian interference channel (IC) with three different feedback models: (1) no feedback, (2) delayed state feedback, and (3) channel output feedback. In all three cases, we characterize the capacity region of the bursty Gaussian IC to within a bounded gap. It turns out that the near-optimal transmit strategies in the non-bursty IC suffice to establish the approximate characterization of capacity in all three cases. In other words, traffic burstiness does not change the high-SNR optimality of the schemes as long as receivers keep track of user activities. Moreover, the capacity region with delayed state feedback is within a bounded gap to that without feedback, and therefore delayed state feedback does not provide significant improvement at high SNR.
  30. Download: on Arxiv 
    Abstract:
    We consider the Gaussian “diamond” or parallel relay network, in which a source node transmits a message to a destination node with the help of N relays. Even for the symmetric setting, in which the channel gains to the relays are identical and the channel gains from the relays are identical, the capacity of this channel is unknown in general. The best known capacity approximation is up to an additive gap of order N bits and up to a multiplicative gap of order N2, with both gaps independent of the channel gains. In this paper, we approximate the capacity of the symmetric Gaussian N-relay diamond network up to an additive gap of 1.8 bits and up to a multiplicative gap of a factor 14. Both gaps are independent of the channel gains and, unlike the best previously known result, are also independent of the number of relays N in the network. Achievability is based on bursty amplify-and-forward, showing that this simple scheme is uniformly approximately optimal, both in the low-rate as well as in the high-rate regimes. The upper bound on capacity is based on a careful evaluation of the cut-set bound. We also present approximation results for the asymmetric Gaussian N-relay diamond network. In particular, we show that bursty amplify-and-forward combined with optimal relay selection achieves a rate within a factor O(log4(N)) of capacity with preconstant in the order notation independent of the channel gains.
  31. Abstract:
    Optimal precoder design for weighted sum-rate maximization in multiple-input multiple-output interference networks is studied. For this well known non-convex optimization problem, convex approximations based on interference alignment are developed, for both single-beam and multi-beam cases. Precoder design methods that consist of two phases, an interference alignment phase and a post-alignment optimization phase, are proposed. The interference alignment solution is taken as the input to the post-alignment optimization phase. For post-alignment weighted sum-rate maximization, novel iterative distributed algorithms are proposed based on the developed convex approximations. Simulation results show that the proposed algorithms achieve promising weighted sum-rate gains over existing interference alignment algorithms. Interestingly, for the multi-beam case, significant gain is achieved at all SNRs, including the high SNR regime.
  32. Download: dynamic_qmf.pdf 
    Abstract:
    The value of relay nodes to enhance the error performance versus rate trade-off in wireless networks has been studied extensively. However, wireless nodes currently are constrained to only transmit or receive at a given frequency, i.e., half-duplex constraint. The diversity-multiplexing tradeoff (DMT) for half-duplex networks are less understood. In the special cases where the DMT is currently known, such as the relay channel and the line network, it is achieved by either dynamic decoding or a quantize-map-forward (QMF) strategy with a fixed half-duplex schedule. The main question we investigate in this paper is whether these two strategies are sufficient to achieve the DMT of half-duplex wireless networks or we need new strategies for general setups. We propose a generalization of the two existing schemes through a dynamic QMF strategy and show that in a parallel relay channel it outperforms both earlier schemes. We also establish the DMT for the relay channel with multiple relays and multiple antennas in some special cases.
  33. Download: dof_2_unicast.pdf 
    Abstract:
    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.
  34. Download: graph_qmf.pdf 
    Abstract:
    We present a structured Quantize-Map-and-Forward (QMF) scheme for cooperative communication over wireless networks, that employs LDPC ensembles for the node operations and message-passing algorithms for decoding. We demonstrate through extensive simulation results over the full-duplex parallel relay network, that our scheme, with no transmit channel state information, offers a robust performance over fading channels and achieves the full diversity order of our network at moderate SNRs.
  35. Download: on Arxiv 
    Abstract:
    We provide a complete characterization of the achievable distortion region for the problem of sending a bivariate Gaussian source over bandwidth-matched Gaussian broadcast channels, where each receiver is interested in only one component of the source. This setting naturally generalizes the simple single Gaussian source bandwidth-matched broadcast problem for which the uncoded scheme is known to be optimal. We show that a hybrid scheme can achieve the optimum for the bivariate case, but neither an uncoded scheme alone nor a separation-based scheme alone is sufficient. We further show that in this joint source channel coding setting, the Gaussian scenario is the worst scenario among the sources and channel noises with the same covariances.
  36. Abstract:
    Information-theoretic secrecy is studied for a parallel relay (diamond) network, in which a transmitter wishes to communicate to a receiver through two relay nodes. While there is no direct link between the transmitter and receiver and all flow of information has to be transmitted through the relays, the message has to be kept secret from each of them. The exact secrecy capacity is characterized for the network under the linear deterministic model. The problem is then studied when each terminal is equipped with multiple antennas, and the channels are parallel Gaussian links. Lower and upper bounds for the secrecy capacity are derived, and the gap is bounded by a constant independent of the channel parameters and SNR. This results in an approximate characterization for the secrecy capacity of the parallel Gaussian diamond network.
  37. Abstract:
    We consider the Gaussian “diamond” or parallel relay network, in which a source node transmits a message to a destination node with the help of N relays. Even for the symmetric setting, in which the channel gains to the relays are identical and the channel gains from the relays are identical, the capacity of this channel is unknown in general. The best known capacity approximation is up to an additive gap of order N bits and up to a multiplicative gap of order N2, with both gaps independent of the channel gains. In this paper, we approximate the capacity of the symmetric Gaussian N-relay diamond network up to an additive gap of 1.8 bits and up to a multiplicative gap of a factor 14. Both gaps are independent of the channel gains, and, unlike the best previously known result, are also independent of the number of relays N in the network. Achievability is based on bursty amplify-and-forward, showing that this simple scheme is uniformly approximately optimal, both in the low-rate as well as high-rate regimes. The upper bound on capacity is based on a careful evaluation of the cut-set bound.
  38. Abstract:
    In this paper, we investigate the sum-capacity of the two-user Gaussian interference channel with Gaussian superposition coding and successive decoding. We first examine an approximate deterministic formulation of the problem, and introduce the complementarity conditions that capture the use of Gaussian coding and successive decoding. In the deterministic channel problem, we show that the constrained sum-capacity oscillates as a function of the cross link gain parameters between the information theoretic sum-capacity and the sum-capacity with interference treated as noise. Furthermore, we show that if the number of messages of either user is fewer than the minimum number required to achieve the constrained sum-capacity, the maximum achievable sum-rate drops to that with interference treated as noise. We translate the optimal schemes in the deterministic channel model to the Gaussian channel model, and also derive two upper bounds on the constrained sum-capacity. Numerical evaluations show that the constrained sum-capacity in the Gaussian channels oscillates between the sum-capacity with Gaussian Han-Kobayashi schemes and that with single message schemes.
  39. Abstract:
    Hierarchical cooperation is a communication strategy introduced recently by Özgür et al., where it was shown to significantly outperform standard multi-hop communication in some wireless scenarios. To achieve this gain over multi-hop communication, full availability of channel state information at all the nodes in the network is required. In this paper, we investigate the impact of absence of channel state information on the performance of hierarchical cooperation. If the product of coherence time and coherence bandwidth of the wireless channel is on the order of the number of nodes in the network, we show that non-coherent hierarchical cooperation achieves the same order rate as the coherent version. If the product is smaller than the number of nodes, we show that non-coherent hierarchical cooperation can still yield sizable gains over multihop communication, but may not achieve the same order rate as the coherent version.
  40. Download: divincomm.pdf 
    Abstract:
    This paper brings together how diversity plays a role in diverse topics like source coding, physical layer wireless communication and mobility in wireless networks.
  41. Abstract:
    In this paper we study two-stage Gaussian relay-interference networks where there are weak cross-links, causing the networks to behave like a chain of Z Gaussian channels. Our main result is an approximate characterization of the capacity region for such networks. We propose a new interference management scheme, termed interference neutralization, which is implemented using structured lattice codes. This scheme allows for over-the-air interference removal, without the transmitters having complete access the interfering signals.
  42. Abstract:
    This paper approximately resolves the information flow over wireless (Gaussian) relay networks to within a constant number of bits. It introduced the linear deterministic model and established a max-flow min-cut result for linear deterministic networks. The insights from the deterministic approach led to the approximate max-flow min-cut characterization for noisy Gaussian networks, through the introduction of a new relaying strategy called quantize-map-forward (QMF).
  43. Download: gc.pdf 
    Abstract:
    This paper studies the scaling capacity of asymptotically large wireless networks. It shows that even restricted one-dimensional mobility allows the total capacity of the wireless network scales linearly with the number of nodes. This implies that per-node capacity scales as a constant, demonstrating that even restricted mobility can be used to provide non-diminishing throughput for large-scale wireless networks. This is demonstrated by utilizing the multi-user diversity which is instantiated through node-mobility.
  44. Download: dimacs.pdf 
    Abstract:
    This studied the online scheduling problem of allocating time or frequency slots to multiple users in a wireless broadcast channel. The study was from a CS algorithms viewpoint, with criteria such as delay (average/maximal) and stretch (relative delay). We gave a resource-augmented competitive analysis of many scheduling algorithms, and demonstrated that a small amount of overprovisioning (resource-augmentation) will make the scheduling algorithms competitive to the off-line optimal, even for adversarial demand inputs.
  45. Note: This paper won the 2006 IEEE Donald Fink Prize prize paper award, which is an IEEE-wide paper award across all IEEE journals and magazines.
    Download: procieee.pdf 
    Abstract:
    Spatial diversity is realized through multiple independently fading transmit/receive antenna paths in single-user communications; through independently fading links in multi-user communications; through multiple independent routing paths in networks. Adopting spatial diversity as a central theme, we study its information-theoretic foundations, then we examine its benefits across the physical (signal transmission/coding and receiver signal processing) and networking (resource allocation, routing, and applications) layers.
  46. Download: publications 
    Abstract:
    Hierarchical cooperation, introduced by Ozgur, Leveque and Tse showed that linear scaling is possible in wireless network capacity, asymptotically in network size. In this paper, we investigate the impact of absence of channel state information on the performance of hierarchical cooperation. If the product of coherence time and coherence bandwidth of the wireless channel is on the order of the number of nodes in the network, we show that non-coherent hierarchical cooperation achieves the same order rate as the coherent version. If the product is smaller than the number of nodes, we show that non-coherent hierarchical cooperation can still yield sizable gains over multihop communication, but may not achieve the same order rate as the coherent version.
  47. Download: md_itw10.pdf 
    Abstract:
    We study the problem where there is a single adversarial node which injects signals to disrupt this communication in a parallel relay network. Like the source, it can only influence the destination through the relays. We develop an approximate characterization of the reliable transmission rate in the presence of such an adversary. A deterministic version of the same problem is solved exactly, yielding insights which are used in the approximate characterization.
  48. Download: od_isit10.pdf on Arxiv 
    Abstract:
    An approximate max-flow min-cut result for arbitrary wireless relay network was recently established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we show that the approximation result can be established by using lattices for transmission and quantization along with structured mappings at the relays. This also extended the original scalar quantizer analysis to vector quantizers and obtained a slightly better approximation constant.
  49. Note: Invited paper surveying our results on wireless relay network secrecy.
    Download: pdtizs10.pdf 
  50. Download: pdtisit10.pdf 
    Abstract:
    In this paper we consider information-theoretically secure communication between two special nodes (“source” and “destination”) in a memoryless network with authenticated relays, where the secrecy is with respect to a class of eavesdroppers. We develop achievable secrecy rates when authenticated relays also help increase secrecy rate by inserting noise into the network.
  51. Abstract:
    Lossless transmission of a set of correlated sources over a deterministic relay network is considered for two traffic requirements. In distributed multicast, the set of sources are to be delivered to a set of destinations. The source exchange requires all the nodes with access to sources to be able to reconstruct all other sources observed at other nodes. We develop achievable regions and outer bounds for both these situations. For linear deterministic networks, these bounds coincide, yielding a characterization.
  52. Abstract:
    In this paper we consider secret communication between two special nodes (“source” and “destination”) in a wireless network with authenticated relays: the message communicated to the destination is to be kept information-theoretically (unconditionally) secret from any eavesdropper within a class. Since the transmissions are broadcast and interfere with each other, complex signal interactions occur. We develop cooperative schemes which utilize these interactions in wireless communication over networks with arbitrary topology, and give provable unconditional secrecy guarantees.
  53. S. Mohajer, S. N. Diggavi, C. Fragouli, and D. Tse, "Capacity of Deterministic Z-Chain Relay-Interference Network," in Proc. IEEE Information Theory Workshop (ITW), Volos, Greece, 2009, pp. 331-335.
  54. S. Mohajer and S. N. Diggavi, "Deterministic approach to wireless network error correction," in Proc. IEEE Information Theory Workshop (ITW), Volos, Greece, 2009, pp. 5-9.
  55. S. Mohajer, S. N. Diggavi, and D. Tse, "Approximate Capacity of a Class of Gaussian Relay-Interference Networks," in Proc. IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, 2009, pp. 31-35.
  56. Download: pdt_icc09.pdf 
    Abstract:
    We introduce the interference-multiple-access channel, which is a discrete memoryless channel with two transmitters and two receivers, similar to the interference channel. One receiver is required to decode the information encoded at one transmitter, the other receiver is required to decode the messages from both transmitters. We provide an inner bound on the capacity region of this channel, as well as an outer bound for a special class of such channels. For this class, we also quantify the gap between inner and outer bound and show that the bounds match for a semi-deterministic channel, providing a complete characterization. For the Gaussian case, we show that the gap is at most 1 bit, yielding an approximate characterization.
  57. Download: pdtita09final.pdf 
    Abstract:
    This paper studies the idea of noise insertion by authenticated relays through friendly jamming. We develop the secrecy rate achievable in arbitrary (deterministic) networks when there are relays actively helping secrecy.
  58. Abstract:
    We ask whether there exist low- overhead schemes for dynamic wireless networks, that produce routes that are within a small constant factor (stretch) of the op- timal route-length. For a class of models for wireless network that ful- fill some mild conditions on the connectivity and on mobility over the time of interest, we can design distributed routing algorithm that maintain the routes over a changing topol- ogy with provable performance guarantees. This scheme needs only node identities and integrates location service along with routing, therefore accounting for the complete overhead.
  59. Download: pdt_allerton08.pdf 
    Abstract:
    We study a line network with an eavesdropper having access to the relay transmission. We assume that there could also be a public feedback channel from the destination. We develop achievable strategies to achieve certain rate-equivocation pairs.
  60. S. Mohajer, S. N. Diggavi, C. Fragouli, and D. Tse, "Transmission techniques for relay-interference networks," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2008, pp. 464-474.
  61. A. Sabharwal and S. N. Diggavi, "Compound Gaussian multiple access channels with noisy feedback," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2008, pp. 887-894.
  62. S. Avestimehr, S. N. Diggavi, and D N C. Tse, "Approximate characterization of capacity in Gaussian relay networks," in Proc. IEEE International Wireless Communications and Mobile Computing Conference (IWCMC), Crete, Greece, 2008, pp. 56-61.
  63. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Approximate Capacity of Gaussian Relay Networks," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 474-478.
  64. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Information flow over compound wireless relay networks," in Proc. IEEE Zurich Seminar on Communications (IZS), Zurich, Switzerland, 2008, p. 92.
  65. D. Tschopp, S. N. Diggavi, and M. Grossglauser, "Routing in mobile wireless networks," in Proc. IEEE Zurich Seminar on Communications (IZS), Zurich, Switzerland, 2008, p. 38.
  66. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Wireless network information flow," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2007.
  67. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "A Deterministic Approach to Wireless Relay Networks," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2007.
  68. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "A deterministic model for wireless relay networks and its capacity," in Proc. IEEE Information Theory Workshop (ITW) Bergen, Norway, 2007, pp. 6-11.
  69. Abstract:
    We develop wireless routing based on an embedding of the connectivity graph to overcome shortcomings of geographic routing and topology-based routing.
  70. Note: invited paper
    Download: tdgwita2007.pdf 
  71. Download: lhp.pdf 
    Abstract:
    Implementing end-to-end TCP in wireless networks faces two problems. First, it is well known that TCP can not distinguish packet losses due to link failures and that due to network congestion. Second, TCP congestion control mechanism does not deal effectively with large amount of out-oforder packet retransmissions; this problem has received less attention in literature. In this paper, we present solutions to both these problems. In particular, we present a Link-Layer Header Protection (LHP) protocol which implements Explicit Loss Notification (ELN) in a simple, scalable manner, addressing the first problem. We also modify the congestion control mechanism to incorporate knowledge of ELN and packet loss pattern into retransmission decisions, solving the second problem. We combine both these solutions with TCP to present scalable, reliable end-to-end wireless transport protocol.
  72. Download: spaa02.pdf 
  73. S. N. Diggavi, M. Grossglauser, and D. N. C. Tse, "Even one-dimensional mobility increases capacity of wireless adhoc networks," in Proc. IEEE International Symposium on Information Theory (ISIT), Lausanne, 2002, p. 352.
  74. N. Al-Dhahir and S N. Diggavi, "On achievable rates on time-varying frequency-selective channels," in Proc. Conference on Information Sciences and Systems, Princeton, New Jersey, 2002, pp. 860-865.
  75. Download: icc95.pdf 
  76. Download: asil94.pdf 
    Abstract:
    This was among the first papers to develop statistical models for multiple antenna wireless channels. It extends the well accepted fading models for single-antenna channels to multiple antennas by incorporating antenna response and geometry.

Secure Cyber-Physical Systems

  1. Download: mishra_secure.pdf 
  2. Download: mehrdad_cdc16.pdf www 
  3. Download: sse_mskdt.pdf 
  4. Download: pycra.pdf 
  5. Download: shaunak_cdc.pdf 
  6. Download: on Arxiv 
    Abstract:
    The vast majority of today's critical infrastructure is supported by numerous feedback control loops and an attack on these control loops can have disastrous consequences. This is a major concern since modern control systems are becoming large and decentralized and thus more vulnerable to attacks. This paper is concerned with the estimation and control of linear systems when some of the sensors or actuators are corrupted by an attacker. We give a new simple characterization of the maximum number of attacks that can be detected and corrected as a function of the pair (A,C) of the system and we show in particular that it is impossible to accurately reconstruct the state of a system if more than half the sensors are attacked. In addition, we show how the design of a secure local control loop can improve the resilience of the system. When the number of attacks is smaller than a threshold, we propose an efficient algorithm inspired from techniques in compressed sensing to estimate the state of the plant despite attacks. We give a theoretical characterization of the performance of this algorithm and we show on numerical simulations that the method is promising and allows to reconstruct the state accurately despite attacks. Finally, we consider the problem of designing output-feedback controllers that stabilize the system despite sensor attacks. We show that a principle of separation between estimation and control holds and that the design of resilient output feedback controllers can be reduced to the design of resilient state estimators.
  7. Download: security_cdc.pdf 
    Abstract:
    We consider the problem of estimation and control of a linear system when some of the sensors or actuators are attacked by a malicious agent. In our previous work [1] we studied systems with no control inputs and we formulated the estimation problem as a dynamic error correction problem with sparse attack vectors. In this paper we extend our study and look at the role of inputs and control. We first show that it is possible to increase the resilience of the system to attacks by changing the dynamics of the system using state-feedback while having (almost) total freedom in placing the new poles of the system. We then look at the problem of stabilizing a plant using output-feedback despite attacks on sensors, and we show that a principle of separation of estimation and control holds. Finally we look at the effect of attacks on actuators in addition to attacks on sensors: we characterize the resilience of the system with respect to actuator and sensor attacks and we formulate an efficient optimization-based decoder to estimate the state of the system despite attacks on actuators and sensors.
  8. Abstract:
    We consider the problem of state-estimation of a linear dynamical system when some of the sensor measurements are corrupted by an adversarial attacker. The errors injected by the attacker in the sensor measurements can be arbitrary and are not assumed to follow a specific model (in particular they can be of arbitrary magnitude). We first characterize the number of attacked sensors that can be tolerated so that the state of the system can still be correctly recovered by any decoding algorithm. We then propose a specific computationally feasible decoding algorithm and we give a characterization of the number of errors this decoder can correct. For this we use ideas from compressed sensing and error correction over the reals and we exploit the dynamical nature of the problem. We show using numerical simulations that this decoder performs very well in practice and allows to correct a large number of errors.

Network data compression

  1. Download: on Arxiv 
    Abstract:
    We provide a complete characterization of the achievable distortion region for the problem of sending a bivariate Gaussian source over bandwidth-matched Gaussian broadcast channels, where each receiver is interested in only one component of the source. This setting naturally generalizes the simple single Gaussian source bandwidth-matched broadcast problem for which the uncoded scheme is known to be optimal. We show that a hybrid scheme can achieve the optimum for the bivariate case, but neither an uncoded scheme alone nor a separation-based scheme alone is sufficient. We further show that in this joint source channel coding setting, the Gaussian scenario is the worst scenario among the sources and channel noises with the same covariances.
  2. Abstract:
    We show that source-channel separation is approximately optimal for transmitting a Gaussian source over a bandwidth mismatched Gaussian channel, for quadratic distortion measures. Furthermore, we show that the results can be extended to general broadcast channels, and the performance of the source-channel separation based approach is also within the same constant multiplicative factors of the optimum.
  3. Download: asymmd.pdf on Arxiv 
    Abstract:
    This paper introduces the asymmetric multi-level lossless data compression problem and gives a complete characterization for the three-description version. It then uses insights from this characterization to provide an approximate characterization for the 3-description asymmetric multiple description problem.
  4. Abstract:
    We study end-to-end network utility maximization (NUM) approach to allocate resources to multiple flows, each encoding multiple description data compression streams, by taking into account the end-to-end distortion measures.
  5. Abstract:
    Approximately solves symmetric Gaussian multiple description problem to within a bit, by sandwiching the MD rate region between two polytopes separated by at most a fraction of a bit.
  6. Abstract:
    We characterize the rate region of the two-description multiple description coding for stationary Gaussian sources under the squared error distortion measure.
  7. Abstract:
    We introduce the problem of side-information scalable data compression In this problem, the encoder constructs a progressive description, such that the receiver with high quality side information will be able to truncate the bit-stream and reconstruct in the rate distortion sense, while the receiver with low quality side information will have to receive further data in order to decode. We provide a complete characterization of the rate distortion region for the important quadratic Gaussian case with multiple jointly Gaussian side-informations, where the side information quality does not have to be monotonic along the scalable coding order. Inner and outer bounds are provided to the rate distortion region for general discrete memoryless sources.
  8. Abstract:
    We study the multi-user successive refinement problem (posed in Pradhan and Ramchandran, 2002), where the users are connected to a central server through links with different noiseless capacities. Each user requires to reconstruct the source in a scalable manner. We provide the best known achievable strategy for the two-user, two-layer case and the complete characterization of the rate-distortion region for the Gaussian source under the mean-squared error (MSE) distortion measure.
  9. Abstract:
    This solves an open problem (posed by Steinberg and Merhav, 2004) on multi-stage successive refinement with side information, when successive stages are for decoders with improving quality side-information. In solving this problem, we identified the general notion of successive refinability of data compression with side-information. A source-channel separation theorem is provided when the descriptions are sent over independent channels for the multistage case.
  10. Download: final_mdc.pdf 
    Abstract:
    This designs asymmetric multiple description lattice quantizers, which covers the entire range of the distortion profile, from symmetric to successive refinement. We present a solution to the labeling problem, which is an important part of the construction. We show that this construction is optimal in the high-rate regime, by comparing it to the information-theoretic bounds.
  11. Download: tcdsspcom10.pdf 
    Abstract:
    We consider the source-channel separation architecture for lossy source coding in communication networks. It is shown that the separation approach is optimal when the memoryless sources at source nodes are arbitrarily correlated, each of which is to be reconstructed at possibly multiple destinations within certain distortions, and the channels in this network are synchronized, orthogonal and memoryless (i.e., noisy graphs).
  12. C. Tian, S. N. Diggavi, and S. Shamai, "The achievable distortion region of bivariate Gaussian source on Gaussian broadcast channel," in Proc. Proc. of IEEE ISIT 2010, Austin, Texas, 2010, pp. 146-150.
  13. C. Tian, J. Chen, S. N. Diggavi, and S. Shamai, "Optimality and approximate optimality of source-channel separation in networks," in Proc. Proc. of IEEE ISIT 2010, Austin, Texas, 2010, pp. 495-499.
  14. Abstract:
    Lossless transmission of a set of correlated sources over a deterministic relay network is considered for two traffic requirements. In distributed multicast, the set of sources are to be delivered to a set of destinations. The source exchange requires all the nodes with access to sources to be able to reconstruct all other sources observed at other nodes. We develop achievable regions and outer bounds for both these situations. For linear deterministic networks, these bounds coincide, yielding a characterization.
  15. C. Tian, S. N. Diggavi, and S. Shamai, "An Approximate Characterization For the Gaussian Broadcasting Distortion Region," in Proc. IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, 2009, pp. 2477-2481.
  16. Download: pdtencsiisit09.pdf 
    Abstract:
    In this paper we find properties that are shared between two seemingly unrelated lossy source coding setups with side-information. The first setup is when the source and sideinformation are jointly Gaussian and the distortion measure is quadratic. The second setup is when the side-information is an erased version of the source. We begin with the observation that in both these cases the Wyner-Ziv and conditional ratedistortion functions are equal. Next, we consider the case when there are two decoders with access to different side-information sources. For the case when the encoder has access to the sideinformation we establish bounds on the rate-distortion function and a sufficient condition for tightness. Under this condition, we find a characterization of the rate-distortion function for physically degraded side-information. This characterization holds for both the Gaussian and erasure setups.
  17. Y. Li, C. Tian, S. N. Diggavi, M. Chiang, and A. R. Calderbank, "Network Resource Allocation for Competing Multiple-Description Transmissions," in Proc. IEEE Globecom, New Orleans, 2008, pp. 1-6.
  18. C. Tian, S. Mohajer, and S N. Diggavi, "Approximating the Gaussian multiple description rate region under symmetric distortion constraints," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 1413-1417.
  19. S. Mohajer, C. Tian, and S. N. Diggavi, "Asymmetric Gaussian Multiple Descriptions and Asymmetric Multilevel Diversity Coding," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 1992-1996.
  20. C. Tian, S. Mohajer, and S. N. Diggavi, "On the symmetric Gaussian multiple description rate-distortion function," in Proc. IEEE Data Compression Conference (DCC), Snowbird, Utah, 2008, pp. 412-421.
  21. S. Mohajer, C. Tian, and S. N. Diggavi, "Asymmetric Multilevel Diversity Coding," in Proc. IEEE Data Compression Conference (DCC), Snowbird, Utah, 2008, pp. 402-411.
  22. C. Tian, S. Mohajer, and S. N. Diggavi, "On the Gaussian $K$-description problem under symmetric distortion constraints," in Proc. Information Theory and Applications Workshop, UCSD, San Diego, California, 2008, pp. 401-406.
  23. C. Tian and S. N. Diggavi, "On scalable source coding with decoder side informations," in Proc. IEEE International Symposium on Information Theory (ISIT), Nice,France, 2007, pp. 1461-1465.
  24. J. Chen, C. Tian, and S N. Diggavi, "Multiple description coding for stationary sources," in Proc. IEEE Data Compression Conference (DCC), Snowbird, Utah, 2007, pp. 73-82.
  25. Download: db_hbitw06.pdf 
  26. C. Tian, J. Chen, and S. N. Diggavi, "Multiuser successive refinement and multiple description coding," in Proc. IEEE Information Theory Workshop (ITW), Chengdu, China, 2006, pp. 293-297.
  27. Abstract:
    We investigate source coding in a cascade communication system consisting of an encoder, a relay and an end terminal, where both the relay and the end terminal wish to reconstruct source X with certain fidelities. Additionally, side-informations Z and Y are available at the relay and the end terminal, respectively. The side-information Z at the relay is a physically degraded version of side-information Y at the end terminal. We give an exact characterization for the Gaussian quadratic distortion version of the problem and develop inner and outer bounds for the general case.
  28. C.Tian and S. N. Diggavi, "Multistage successive refinement for Wyner-Ziv source coding with degraded side information," in Proc. IEEE International Symposium on Information Theory, Seattle, 2006.
  29. E. Perron, S. N. Diggavi, and I E. Telatar, "On the Role of Encoder Side-Information in Source Coding for Multiple Decoders," in Proc. IEEE International Symposium on Information Theory, Seattle, 2006.
  30. C.Tian and S. N. Diggavi, "On scalable source coding for multiple decoders with side-information," in Proc. Information Theory and Applications Workshop, San Diego, 2006.
    Note: invited paper
  31. Download: mdsi.pdf 
    Abstract:
    We formulate a multi-terminal source coding problem, where we are required to construct a multiple description source code for a source sequence when side information about dependent random processes is available at the decoder only, or at both the decoder and the encoder. We describe an achievable rate-distortion region for these problems. In the quadratic Gaussian case, and when there is common side information among the decoders, we show that the rate region when both the encoder and decoder have access to the side information coincides with that of decoder–only side information. This is analogous to the single-description (Wyner-Ziv) case, and an explicit characterization of the rate-distortion region is provided for this case.
  32. S. N. Diggavi, N. J. A. Sloane, and V. A. Vaishampayan, "Design of Asymmetric Multiple Description Lattice Vector Quantizers," in Proc. IEEE Data Compression Conference (DCC),Snowbird, Utah, 2000, pp. 490-499.

Space-time wireless communications

  1. J. Chui, S. Das, N. Al-Dhahir, S. N. Diggavi, and A. R. Calderbank, "Space-time codes and application in WiMAX." , 2007.
  2. Download: acdbookchapter.pdf 
    Abstract:
    This was a survey on space-time codes and signal processing with a focus on recent (when the chapter was written) developments.
  3. Download: divincomm.pdf 
    Abstract:
    This paper brings together how diversity plays a role in diverse topics like source coding, physical layer wireless communication and mobility in wireless networks.
  4. Download: dimacschap.pdf 
    Abstract:
    Diversity embedded codes give different levels of diversity protection to different information streams. This was the short paper that introduced diversity embedded codes.
  5. S. N. Diggavi, N. Al-Dhahir, and A. R. Calderbank, "Diversity Order of Space-Time Block Codes in Inter-Symbol Interference Multiple-Access Channels." , 2003, vol. 62.
  6. Abstract:
    We show that the diversity-multiplexing tradeoff in fading inter-symbol interference (ISI) channels with a single degree of freedom (MISO/SIMO) is successively refinable. This demonstrates that ideal opportunistic codes can be designed asymptotically in SNR.
  7. Download: lccdfinal.pdf 
    Abstract:
    This paper studies how to use the NUM framework in conjunction with diversity embedded codes to allow multiple streams with different QoS requirements to share wireless links.
  8. Abstract:
    This paper introduces the problem of diversity embedded codes for inter-symbol interference (ISI) channels and gives algebraic constructions for them. These constructions are based on designing binary rank-distance codes with a specific (Toeplitz-like) constraint and lifting them to the complex domain through set-partitioning maps. As a special case these algebraic constructions also give rate-diversity optimal codes for transmission over ISI channels when there are transmit alphabet constraints.
  9. Download: ddac.pdf 
    Abstract:
    This paper develops in a unified way the theory for diversity embedded codes for broadband (ISI) channels, both from an information theory viewpoint as well as an algebraic coding perspective. It also develops practical aspects by connecting it to unequal error protection for image transmission as well as using diversity embedded codes in conjunction with NUM.
  10. Abstract:
    This paper introduces diversity embedded codes, which are space-time codes that simultaneously give different levels of diversity protection to different information streams. The paper provides algebraic constructions based on binary codes designed for rank distance and lifts them to the complex domain. It also gives several example of linear diversity embedded codes.
  11. Download: subsp.pdf 
    Abstract:
    This paper was motivated by non-coherent space-time codes with fixed transmit alphabet constraints. To obtain maximal diversity order, the subspaces represented by the space-time codeword matrix needs to be non-intersecting. This led to the study of how many non-intersecting subspaces can be constructed from a finite alphabet.
  12. Download: quatstbc_final.pdf 
  13. Note: This paper won the 2006 IEEE Donald Fink Prize prize paper award, which is an IEEE-wide paper award across all IEEE journals and magazines.
    Download: procieee.pdf 
    Abstract:
    Spatial diversity is realized through multiple independently fading transmit/receive antenna paths in single-user communications; through independently fading links in multi-user communications; through multiple independent routing paths in networks. Adopting spatial diversity as a central theme, we study its information-theoretic foundations, then we examine its benefits across the physical (signal transmission/coding and receiver signal processing) and networking (resource allocation, routing, and applications) layers.
  14. Download: tdis.pdf 
    Abstract:
    This paper studies time-reversed space-time block codes, which is an extension of the Alamouti code to inter-symbol interference (ISI) channels. We study the algebraic properties of this code by demonstrating that the polynimial matrices representing the time-reversed space-time block codes form a multiplicative group. This property enables us to analyze the diversity (error) performance of a ISI multiple access channel where each user uses such a code. We also study the finite-block length implementation of such codes.
  15. Download: mimo_ofdm.pdf 
    Abstract:
    This paper studies the impact of time-variation within a transmission block on multiple-input multiple output (MIMO) OFDM, which is the chosen modulation strategy of 4G wireless systems. We demonstrate how time-variation can lead to inter-carrier interference, and give algorithms that can mitigate its effects. A central challenge is how to estimate the channel, when it varies within a block. We devise pilot tone placement strategies that enable better channel estimation. We show that in time-varying channels it may be better to group pilot tones together into clumps equispaced onto the FFT grid; this placement technique is in contrast to the common wisdom for time-invariant channels.
  16. S. N. Diggavi, N. Al-Dhahir, A. Stamoulis, and A. R. Calderbank, "Differential Space-Time Transmission for Frequency-Selective Channels," IEEE Communication Letters, vol. 6, iss. 6, pp. 253-255, 2002.
  17. Download: guardtcomm.pdf 
    Abstract:
    In block transmission a guard sequence (prefix) is sent to prevent inter-block interference. A cyclic prefix is used in OFDM and an all-zero sequence is used in vector coding.The question we asked is, what should such a sequence be to maximize throughput under the constraint that the sequence itself carries no new information. This paper answers this question by showing that the optimal guard sequence is a linear combination of the information symbols, with the particular optimal combination characterized (depending on the channel and the signal power). Both vector coding and DMT are special cases of this transmission scheme and significant gains in throughput over DMT can be obtained by using such a guard sequence optimization.
  18. Download: mbcjr.pdf 
  19. Download: fading.pdf 
    Abstract:
    This is an early study of the capacity of MIMO channels inspired by the work of Telatar and Foschini. It shows that the capacity grows linearly in the number of transmit and receive antennas (degrees of freedom) either when the SNR becomes large or when the number of antennas in the MIMO system becomes large. It shows that the linear rate growth can be achieved by simpler linear detector structures, such as a matched filter receiver. However, it shows that the price paid for simple matched filter receivers is that the SNR growth flattens. It also examines the case where the channel matrix has a constant expected Frobenius norm. In this case, even with isotropic fading, it is shown that the capacity of MIMO channels does not grow linear in the number of antennas, but grows linearly in SNR. Finally, the effect of time-variation within a transmission block for ISI fading channels is examined in terms of capacity.
  20. Download: intsup.pdf 
  21. S. Dusad and S N. Diggavi, "Successive refinement of diversity for fading ISI MISO channels," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 1273-1277.
  22. Y. Li, M. Chiang, A. R. Calderbank, and S. N. Diggavi, "Optimal Delay-Rate-Reliability Tradeoff in Networks with Composite Links," in Proc. IEEE INFOCOM conference, Alaska, 2007, pp. 526-534.
  23. S. Dusad and S N. Diggavi, "On successive refinement of diversity for fading ISI channels," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2006.
  24. Download: digtseitw06.pdf 
    Abstract:
    Diversity embedded codes are opportunistic codes which take advantage of good channel realizations while ensuring at least part of the information is received reliably for bad channels. We establish a connection between these codes and degraded message set broadcast codes. We characterize the achievable rate region for the parallel Gaussian degraded message set broadcast problem, when only the strongest user needs the private information. Using this, we partially characterize the set of achievable rate-diversity tuples for the diversity embedded problem for parallel fading channels. This shows that the diversity-multiplexing tradeoff for the parallel fading channel is not successively refinable.
  25. Download: sucrefisit05.pdf 
    Abstract:
    This paper shows that the diversity multiplexing tradeoff for flat fading channels with a single degree of freedom (MISO/SIMO) is successively refinable.
  26. A. R. Calderbank, S. Das, N. Al-Dhahir, and S. N. Diggavi, "A Novel Full-Rate Full-Diversity STBC with Application to WiMAX," in Proc. Proceedings of IEEE Vehicular Technology Conference, Dallas, Texas, USA, 2005, pp. 1791-1795.
  27. S. Das, N. Al-Dhahir, S. N. Diggavi, and A. R. Calderbank, "Opportunistic Space-Time Block Codes," in Proc. Proceedings of IEEE Vehicular Technology Conference, Dallas, Texas, USA, 2005, pp. 2025-2029.
  28. S. N. Diggavi and D. N. C. Tse, "On successive refinement of diversity," in Proc. Allerton Conference on Communication, Control, and Computing, Illinois, 2004.
  29. F. Oggier, N. J. A. Sloane, S. N. Diggavi, and A. R. Calderbank, "Non-intersecting subspaces with finite alphabet," in Proc. IEEE International Symposium on Information Theory (ISIT) Chicago, 2004, p. 455.
  30. A. R. Calderbank, S. N. Diggavi, S. Das, and N. Al-Dhahir, "Construction and Analysis of a New 4x4 Orthogonal Space-Time Block Code," in Proc. IEEE International Symposium on Information Theory (ISIT) Chicago, 2004, p. 310.
  31. S. N. Diggavi, N. Al-Dhahir, and A. R. Calderbank, "Multiuser Joint Equalization and Decoding of Space-Time Codes," in Proc. IEEE International Conference on Communications (ICC), Anchorage, Alaska, 2003, pp. 2643-2647.
  32. S. N. Diggavi, N. Al-Dhahir, A. Stamoulis, and A. R. Calderbank, "Differential Space-Time Transmission for Frequency-Selective Channels," in Proc. Conference on Information Sciences and Systems, Princeton, New Jersey, 2002, pp. 259-264.
  33. N. Al-Dhahir and S N. Diggavi, "On achievable rates on time-varying frequency-selective channels," in Proc. Conference on Information Sciences and Systems, Princeton, New Jersey, 2002, pp. 860-865.
  34. S. N. Diggavi, N. Al-Dhahir, and A. Stamoulis, "Inter-carrier interference for MIMO OFDM," in Proc. IEEE International Conference on Communications, New York, 2002, pp. 485-489.
  35. A. Stamoulis, S. N. Diggavi, and N. Al-Dhahir, "Estimation of fast-fading channels in OFDM," in Proc. IEEE Wireless Communications and Networking Conference, Florida, 2002, pp. 465-470.
  36. C. Fragouli, N. Al-Dhahir, S. N. Diggavi, and W. Turin, "Prefiltered Space-Time M-BCJR Equalizer for Frequency-Selective Channels," in Proc. Conference on Information Sciences and Systems, Baltimore, Maryland, 2001.
  37. N. Al-Dhahir and S. N. Diggavi, "Guard Sequence Optimization for block transmission over linear dispersive channels," in Proc. IEEE Global Telecommunications Conference (GLOBECOM), San Francisco, 2000, pp. 970-973.
  38. S. N. Diggavi, "On achievable performance of spatial diversity fading channels," in Proc. International Symposium on Information Theory, Boston, ISIT'98, 1998, p. 396.
  39. B. C. Ng, S. N. Diggavi, and A. Paulraj, "Joint Structured Channel and Data Estimation over time-varying channels," in Proc. Globecom 1997, Phoenix, 1997, pp. 409-413.
  40. S. N. Diggavi, "Analysis of multicarrier transmission in time-varying channels," in Proc. International Conference on Communications, Montreal, , pp. 1191-1195.
  41. Download: multiuserdmt.pdf 
    Abstract:
    In this paper we propose a multiuser DMT scheme for use in a frequency dispersive multiple access channel. We formulate the problem as an optimization problem for maximizing the rate-sum or a weighted sum of the rates. We establish the rate-sum maximizing solution which is a multiuser waterfilling scheme over the DMT tones. We propose a multiuser bit-loading algorithm which finds the rate-maximizing solution in a finite number of steps.
  42. Download: icc95.pdf 
  43. Download: asil94.pdf 
    Abstract:
    This was among the first papers to develop statistical models for multiple antenna wireless channels. It extends the well accepted fading models for single-antenna channels to multiple antennas by incorporating antenna response and geometry.

For all material posted on this page: This material is presented to ensure timely dissemination of scholarly and technical work. All persons copying this material are expected to adhere to the terms and constraints invoked by the copyright holder. In most cases, these works may not be reposted without the explicit permission of the copyright holder.