• The Capacity of Private Information Retrieval from Uncoded Storage Constrained Databases(1805.04104)

May 10, 2018 cs.IT, math.IT, cs.CR, cs.DB, cs.IR
Private information retrieval (PIR) allows a user to retrieve a desired message from a set of databases without revealing the identity of the desired message. The replicated databases scenario was considered by Sun and Jafar, 2016, where $N$ databases can store the same $K$ messages completely. A PIR scheme was developed to achieve the optimal download cost given by $\left(1+ \frac{1}{N}+ \frac{1}{N^{2}}+ \cdots + \frac{1}{N^{K-1}}\right)$. In this work, we consider the problem of PIR for uncoded storage constrained databases. Each database has a storage capacity of $\mu KL$ bits, where $L$ is the size of each message in bits, and $\mu \in [1/N, 1]$ is the normalized storage. On one extreme, $\mu=1$ is the replicated databases case previously settled. On the other hand, when $\mu= 1/N$, then in order to retrieve a message privately, the user has to download all the messages from the databases achieving a download cost of $1/K$. We aim to characterize the optimal download cost versus storage trade-off for any storage capacity in the range $\mu \in [1/N, 1]$. In the storage constrained PIR problem, there are two key challenges: a) construction of communication efficient schemes through storage content design at each database that allow download efficient PIR; and b) characterizing the optimal download cost via information-theoretic lower bounds. The novel aspect of this work is to characterize the optimum download cost of PIR with storage constrained databases for any value of storage. In particular, for any $(N,K)$, we show that the optimal trade-off between storage, $\mu$, and the download cost, $D(\mu)$, is given by the lower convex hull of the $N$ pairs $\left(\frac{t}{N}, \left(1+ \frac{1}{t}+ \frac{1}{t^{2}}+ \cdots + \frac{1}{t^{K-1}}\right)\right)$ for $t=1,2,\ldots, N$.
• Online Edge Caching and Wireless Delivery in Fog-Aided Networks with Dynamic Content Popularity(1711.10430)

April 22, 2018 cs.IT, math.IT, cs.NI
Fog Radio Access Network (F-RAN) architectures can leverage both cloud processing and edge caching for content delivery to the users. To this end, F-RAN utilizes caches at the edge nodes (ENs) and fronthaul links connecting a cloud processor to ENs. Assuming time-invariant content popularity, existing information-theoretic analyses of content delivery in F-RANs rely on offline caching with separate content placement and delivery phases. In contrast, this work focuses on the scenario in which the set of popular content is time-varying, hence necessitating the online replenishment of the ENs' caches along with the delivery of the requested files. The analysis is centered on the characterization of the long-term Normalized Delivery Time (NDT), which captures the temporal dependence of the coding latencies accrued across multiple time slots in the high signal-to-noise ratio regime. Online edge caching and delivery schemes are investigated for both serial and pipelined transmission modes across fronthaul and edge segments. Analytical results demonstrate that, in the presence of a time-varying content popularity, the rate of fronthaul links sets a fundamental limit to the long-term NDT of F- RAN system. Analytical results are further verified by numerical simulation, yielding important design insights.
• Context-aware Data Aggregation with Localized Information Privacy(1804.02149)

April 10, 2018 cs.IT, math.IT, cs.CR, cs.LG
In this paper, localized information privacy (LIP) is proposed, as a new privacy definition, which allows statistical aggregation while protecting users' privacy without relying on a trusted third party. The notion of context-awareness is incorporated in LIP by the introduction of priors, which enables the design of privacy-preserving data aggregation with knowledge of priors. We show that LIP relaxes the Localized Differential Privacy (LDP) notion by explicitly modeling the adversary's knowledge. However, it is stricter than $2\epsilon$-LDP and $\epsilon$-mutual information privacy. The incorporation of local priors allows LIP to achieve higher utility compared to other approaches. We then present an optimization framework for privacy-preserving data aggregation, with the goal of minimizing the expected squared error while satisfying the LIP privacy constraints. Utility-privacy tradeoffs are obtained under several models in closed-form. We then validate our analysis by {numerical analysis} using both synthetic and real-world data. Results show that our LIP mechanism provides better utility-privacy tradeoffs than LDP and when the prior is not uniformly distributed, the advantage of LIP is even more significant.
• Fog-Aided Wireless Networks for Content Delivery: Fundamental Latency Trade-Offs(1605.01690)

April 3, 2018 cs.IT, math.IT, cs.NI
A fog-aided wireless network architecture is studied in which edge-nodes (ENs), such as base stations, are connected to a cloud processor via dedicated fronthaul links, while also being endowed with caches. Cloud processing enables the centralized implementation of cooperative transmission strategies at the ENs, albeit at the cost of an increased latency due to fronthaul transfer. In contrast, the proactive caching of popular content at the ENs allows for the low-latency delivery of the cached files, but with generally limited opportunities for cooperative transmission among the ENs. The interplay between cloud processing and edge caching is addressed from an information-theoretic viewpoint by investigating the fundamental limits of a high Signal-to-Noise-Ratio (SNR) metric, termed normalized delivery time (NDT), which captures the worst-case coding latency for delivering any requested content to the users. The NDT is defined under the assumptions of either serial or pipelined fronthaul-edge transmission, and is studied as a function of fronthaul and cache capacity constraints. Placement and delivery strategies across both fronthaul and wireless, or edge, segments are proposed with the aim of minimizing the NDT. Information-theoretic lower bounds on the NDT are also derived. Achievability arguments and lower bounds are leveraged to characterize the minimal NDT in a number of important special cases, including systems with no caching capabilities, as well as to prove that the proposed schemes achieve optimality within a constant multiplicative factor of 2 for all values of the problem parameters.
• Secure Retrospective Interference Alignment(1801.03494)

April 2, 2018 cs.IT, math.IT, cs.CR
In this paper, the $K$-user interference channel with secrecy constraints is considered with delayed channel state information at transmitters (CSIT). We propose a novel secure retrospective interference alignment scheme in which the transmitters carefully mix information symbols with artificial noises to ensure confidentiality. Achieving positive secure degrees of freedom (SDoF) is challenging due to the delayed nature of CSIT, and the distributed nature of the transmitters. Our scheme works over two phases: phase one in which each transmitter sends information symbols mixed with artificial noises, and repeats such transmission over multiple rounds. In the next phase, each transmitter uses delayed CSIT of the previous phase and sends a function of the net interference and artificial noises (generated in previous phase), which is simultaneously useful for all receivers. These phases are designed to ensure the decodability of the desired messages while satisfying the secrecy constraints. We present our achievable scheme for three models, namely: 1) $K$-user interference channel with confidential messages (IC-CM), and we show that $\frac{1}{2} (\sqrt{K} -6)$ SDoF is achievable, 2) $K$-user interference channel with an external eavesdropper (IC-EE), and 3) $K$-user IC with confidential messages and an external eavesdropper (IC-CM-EE). We show that for the $K$-user IC-EE, $\frac{1}{2} (\sqrt{K} -3)$ SDoF is achievable, and for the $K$-user IC-CM-EE, $\frac{1}{2} (\sqrt{K} -6)$ is achievable. To the best of our knowledge, this is the first result on the $K$-user interference channel with secrecy constrained models and delayed CSIT that achieves a SDoF which scales with $K$, the number of users.
• Near Optimal Coded Data Shuffling for Distributed Learning(1801.01875)

Jan. 5, 2018 cs.IT, math.IT, cs.DC, cs.LG
Data shuffling between distributed cluster of nodes is one of the critical steps in implementing large-scale learning algorithms. Randomly shuffling the data-set among a cluster of workers allows different nodes to obtain fresh data assignments at each learning epoch. This process has been shown to provide improvements in the learning process. However, the statistical benefits of distributed data shuffling come at the cost of extra communication overhead from the master node to worker nodes, and can act as one of the major bottlenecks in the overall time for computation. There has been significant recent interest in devising approaches to minimize this communication overhead. One approach is to provision for extra storage at the computing nodes. The other emerging approach is to leverage coded communication to minimize the overall communication overhead. The focus of this work is to understand the fundamental trade-off between the amount of storage and the communication overhead for distributed data shuffling. In this work, we first present an information theoretic formulation for the data shuffling problem, accounting for the underlying problem parameters (number of workers, $K$, number of data points, $N$, and the available storage, $S$ per node). We then present an information theoretic lower bound on the communication overhead for data shuffling as a function of these parameters. We next present a novel coded communication scheme and show that the resulting communication overhead of the proposed scheme is within a multiplicative factor of at most $\frac{K}{K-1}$ from the information-theoretic lower bound. Furthermore, we present the aligned coded shuffling scheme for some storage values, which achieves the optimal storage vs communication trade-off for $K<5$, and further reduces the maximum multiplicative gap down to $\frac{K-\frac{1}{3}}{K-1}$, for $K\geq 5$.
• The Capacity of Cache Aided Private Information Retrieval(1706.07035)

June 21, 2017 cs.IT, math.IT, cs.CR, cs.DC
The problem of cache enabled private information retrieval (PIR) is considered in which a user wishes to privately retrieve one out of $K$ messages, each of size $L$ bits from $N$ distributed databases. The user has a local cache of storage $SL$ bits which can be used to store any function of the $K$ messages. The main contribution of this work is the exact characterization of the capacity of cache aided PIR as a function of the storage parameter $S$. In particular, for a given cache storage parameter $S$, the information-theoretically optimal download cost $D^{*}(S)/L$ (or the inverse of capacity) is shown to be equal to $(1- \frac{S}{K})\left(1+ \frac{1}{N}+ \ldots + \frac{1}{N^{K-1}}\right)$. Special cases of this result correspond to the settings when $S=0$, for which the optimal download cost was shown by Sun and Jafar to be $\left(1+ \frac{1}{N}+ \ldots + \frac{1}{N^{K-1}}\right)$, and the case when $S=K$, i.e., cache size is large enough to store all messages locally, for which the optimal download cost is $0$. The intermediate points $S\in (0, K)$ can be readily achieved through a simple memory-sharing based PIR scheme. The key technical contribution of this work is the converse, i.e., a lower bound on the download cost as a function of storage $S$ which shows that memory sharing is information-theoretically optimal.
• Online Edge Caching in Fog-Aided Wireless Network(1701.06188)

May 10, 2017 cs.IT, math.IT, cs.NI
In a Fog Radio Access Network (F-RAN) architecture, edge nodes (ENs), such as base stations, are equipped with limited-capacity caches, as well as with fronthaul links that can support given transmission rates from a cloud processor. Existing information-theoretic analyses of content delivery in F-RANs have focused on offline caching with separate content placement and delivery phases. In contrast, this work considers an online caching set-up, in which the set of popular files is time-varying and both cache replenishment and content delivery can take place in each time slot. The analysis is centered on the characterization of the long-term Normalized Delivery Time (NDT), which captures the temporal dependence of the coding latencies accrued across multiple time slots in the high signal-to- noise ratio regime. Online caching and delivery schemes based on reactive and proactive caching are investigated, and their performance is compared to optimal offline caching schemes both analytically and via numerical results.
• Degrees of Freedom and Achievable Rate of Wide-Band Multi-cell Multiple Access Channels With No CSIT(1704.02732)

April 10, 2017 cs.IT, math.IT
This paper considers a $K$-cell multiple access channel with inter-symbol interference. The primary finding of this paper is that, without instantaneous channel state information at the transmitters (CSIT), the sum degrees-of-freedom (DoF) of the considered channel is $\frac{\beta -1}{\beta}K$ with $\beta \geq 2$ when the number of users per cell is sufficiently large, where $\beta$ is the ratio of the maximum channel-impulse-response (CIR) length of desired links to that of interfering links in each cell. Our finding implies that even without instantaneous CSIT, \textit{interference-free DoF per cell} is achievable as $\beta$ approaches infinity with a sufficiently large number of users per cell. This achievability is shown by a blind interference management method that exploits the relativity in delay spreads between desired and interfering links. In this method, all inter-cell-interference signals are aligned to the same direction by using a discrete-Fourier-transform-based precoding with cyclic prefix that only depends on the number of CIR taps. Using this method, we also characterize the achievable sum rate of the considered channel, in a closed-form expression.
• On the Worst-case Communication Overhead for Distributed Data Shuffling(1609.09823)

Sept. 30, 2016 cs.IT, math.IT, cs.DC, cs.LG
Distributed learning platforms for processing large scale data-sets are becoming increasingly prevalent. In typical distributed implementations, a centralized master node breaks the data-set into smaller batches for parallel processing across distributed workers to achieve speed-up and efficiency. Several computational tasks are of sequential nature, and involve multiple passes over the data. At each iteration over the data, it is common practice to randomly re-shuffle the data at the master node, assigning different batches for each worker to process. This random re-shuffling operation comes at the cost of extra communication overhead, since at each shuffle, new data points need to be delivered to the distributed workers. In this paper, we focus on characterizing the information theoretically optimal communication overhead for the distributed data shuffling problem. We propose a novel coded data delivery scheme for the case of no excess storage, where every worker can only store the assigned data batches under processing. Our scheme exploits a new type of coding opportunity and is applicable to any arbitrary shuffle, and for any number of workers. We also present an information theoretic lower bound on the minimum communication overhead for data shuffling, and show that the proposed scheme matches this lower bound for the worst-case communication overhead.
• Information Theoretic Limits of Data Shuffling for Distributed Learning(1609.05181)

Sept. 16, 2016 cs.IT, math.IT, cs.DC, cs.LG
Data shuffling is one of the fundamental building blocks for distributed learning algorithms, that increases the statistical gain for each step of the learning process. In each iteration, different shuffled data points are assigned by a central node to a distributed set of workers to perform local computations, which leads to communication bottlenecks. The focus of this paper is on formalizing and understanding the fundamental information-theoretic trade-off between storage (per worker) and the worst-case communication overhead for the data shuffling problem. We completely characterize the information theoretic trade-off for $K=2$, and $K=3$ workers, for any value of storage capacity, and show that increasing the storage across workers can reduce the communication overhead by leveraging coding. We propose a novel and systematic data delivery and storage update strategy for each data shuffle iteration, which preserves the structural properties of the storage across the workers, and aids in minimizing the communication overhead in subsequent data shuffling iterations.
• Improved Approximation of Storage-Rate Tradeoff for Caching with Multiple Demands(1606.04202)

June 14, 2016 cs.IT, math.IT, cs.NI
Caching at the network edge has emerged as a viable solution for alleviating the severe capacity crunch in modern content centric wireless networks by leveraging network load-balancing in the form of localized content storage and delivery. In this work, we consider a cache-aided network where the cache storage phase is assisted by a central server and users can demand multiple files at each transmission interval. To service these demands, we consider two delivery models - $(1)$ centralized content delivery where user demands at each transmission interval are serviced by the central server via multicast transmissions; and $(2)$ device-to-device (D2D) assisted distributed delivery where users multicast to each other in order to service file demands. For such cache-aided networks, we present new results on the fundamental cache storage vs. transmission rate tradeoff. Specifically, we develop a new technique for characterizing information theoretic lower bounds on the storage-rate tradeoff and show that the new lower bounds are strictly tighter than cut-set bounds from literature. Furthermore, using the new lower bounds, we establish the optimal storage-rate tradeoff to within a constant multiplicative gap. We show that, for multiple demands per user, achievable schemes based on repetition of schemes for single demands are order-optimal under both delivery models.
• Hierarchical Quickest Change Detection via Surrogates(1603.09739)

March 31, 2016 cs.IT, math.IT, cs.LG, stat.ML
Change detection (CD) in time series data is a critical problem as it reveal changes in the underlying generative processes driving the time series. Despite having received significant attention, one important unexplored aspect is how to efficiently utilize additional correlated information to improve the detection and the understanding of changepoints. We propose hierarchical quickest change detection (HQCD), a framework that formalizes the process of incorporating additional correlated sources for early changepoint detection. The core ideas behind HQCD are rooted in the theory of quickest detection and HQCD can be regarded as its novel generalization to a hierarchical setting. The sources are classified into targets and surrogates, and HQCD leverages this structure to systematically assimilate observed data to update changepoint statistics across layers. The decision on actual changepoints are provided by minimizing the delay while still maintaining reliability bounds. In addition, HQCD also uncovers interesting relations between changes at targets from changes across surrogates. We validate HQCD for reliability and performance against several state-of-the-art methods for both synthetic dataset (known changepoints) and several real-life examples (unknown changepoints). Our experiments indicate that we gain significant robustness without loss of detection delay through HQCD. Our real-life experiments also showcase the usefulness of the hierarchical setting by connecting the surrogate sources (such as Twitter chatter) to target sources (such as Employment related protests that ultimately lead to major uprisings).
• Flow of Information in Feed-Forward Deep Neural Networks(1603.06220)

March 20, 2016 cs.IT, math.IT, cs.LG
Feed-forward deep neural networks have been used extensively in various machine learning applications. Developing a precise understanding of the underling behavior of neural networks is crucial for their efficient deployment. In this paper, we use an information theoretic approach to study the flow of information in a neural network and to determine how entropy of information changes between consecutive layers. Moreover, using the Information Bottleneck principle, we develop a constrained optimization problem that can be used in the training process of a deep neural network. Furthermore, we determine a lower bound for the level of data representation that can be achieved in a deep neural network with an acceptable level of distortion.
• Cache Aided Wireless Networks: Tradeoffs between Storage and Latency(1512.07856)

Dec. 24, 2015 cs.IT, math.IT
We investigate the fundamental information theoretic limits of cache-aided wireless networks, in which edge nodes (or transmitters) are endowed with caches that can store popular content, such as multimedia files. This architecture aims to localize popular multimedia content by proactively pushing it closer to the edge of the wireless network, thereby alleviating backhaul load. An information theoretic model of such networks is presented, that includes the introduction of a new metric, namely normalized delivery time (NDT), which captures the worst case time to deliver any requested content to the users. We present new results on the trade-off between latency, measured via the NDT, and the cache storage capacity of the edge nodes. In particular, a novel information theoretic lower bound on NDT is presented for cache aided networks. The optimality of this bound is shown for several system parameters.
• Perfect Output Feedback in the Two-User Decentralized Interference Channel(1306.2878)

Aug. 9, 2015 cs.IT, math.IT
In this paper, the $\eta$-Nash equilibrium ($\eta$-NE) region of the two-user Gaussian interference channel (IC) with perfect output feedback is approximated to within $1$ bit/s/Hz and $\eta$ arbitrarily close to $1$ bit/s/Hz. The relevance of the $\eta$-NE region is that it provides the set of rate-pairs that are achievable and stable in the IC when both transmitter-receiver pairs autonomously tune their own transmit-receive configurations seeking an $\eta$-optimal individual transmission rate. Therefore, any rate tuple outside the $\eta$-NE region is not stable as there always exists one link able to increase by at least $\eta$ bits/s/Hz its own transmission rate by updating its own transmit-receive configuration. The main insights that arise from this work are: $(i)$ The $\eta$-NE region achieved with feedback is larger than or equal to the $\eta$-NE region without feedback. More importantly, for each rate pair achievable at an $\eta$-NE without feedback, there exists at least one rate pair achievable at an $\eta$-NE with feedback that is weakly Pareto superior. $(ii)$ There always exists an $\eta$-NE transmit-receive configuration that achieves a rate pair that is at most $1$ bit/s/Hz per user away from the outer bound of the capacity region.
• On the Latency and Energy Efficiency of Erasure-Coded Cloud Storage Systems(1405.2833)

May 22, 2015 cs.DC
The increase in data storage and power consumption at data-centers has made it imperative to design energy efficient Distributed Storage Systems (DSS). The energy efficiency of DSS is strongly influenced not only by the volume of data, frequency of data access and redundancy in data storage, but also by the heterogeneity exhibited by the DSS in these dimensions. To this end, we propose and analyze the energy efficiency of a heterogeneous distributed storage system in which $n$ storage servers (disks) store the data of $R$ distinct classes. Data of class $i$ is encoded using a $(n,k_{i})$ erasure code and the (random) data retrieval requests can also vary across classes. We show that the energy efficiency of such systems is closely related to the average latency and hence motivates us to study the energy efficiency via the lens of average latency. Through this connection, we show that erasure coding serves the dual purpose of reducing latency and increasing energy efficiency. We present a queuing theoretic analysis of the proposed model and establish upper and lower bounds on the average latency for each data class under various scheduling policies. Through extensive simulations, we present qualitative insights which reveal the impact of coding rate, number of servers, service distribution and number of redundant requests on the average latency and energy efficiency of the DSS.
• MISO Broadcast Channel with Hybrid CSIT: Beyond Two Users(1504.04615)

April 17, 2015 cs.IT, math.IT
We study the impact of heterogeneity of channel-state-information available at the transmitters (CSIT) on the capacity of broadcast channels with a multiple-antenna transmitter and $k$ single-antenna receivers (MISO BC). In particular, we consider the $k$-user MISO BC, where the CSIT with respect to each receiver can be either instantaneous/perfect, delayed, or not available; and we study the impact of this heterogeneity of CSIT on the degrees-of-freedom (DoF) of such network. We first focus on the $3$-user MISO BC; and we completely characterize the DoF region for all possible heterogeneous CSIT configurations, assuming linear encoding strategies at the transmitters. The result shows that the state-of-the-art achievable schemes in the literature are indeed sum-DoF optimal, when restricted to linear encoding schemes. To prove the result, we develop a novel bound, called Interference Decomposition Bound, which provides a lower bound on the interference dimension at a receiver which supplies delayed CSIT based on the average dimension of constituents of that interference, thereby decomposing the interference into its individual components. Furthermore, we extend our outer bound on the DoF region to the general $k$-user MISO BC, and demonstrate that it leads to an approximate characterization of linear sum-DoF to within an additive gap of $0.5$ for a broad range of CSIT configurations. Moreover, for the special case where only one receiver supplies delayed CSIT, we completely characterize the linear sum-DoF.
• Secure Degrees of Freedom Region of the Two-User MISO Broadcast Channel with Alternating CSIT(1502.02647)

Feb. 9, 2015 cs.IT, math.IT, cs.CR
The two user multiple-input single-output (MISO) broadcast channel with confidential messages (BCCM) is studied in which the nature of channel state information at the transmitter (CSIT) from each user can be of the form $I_{i}$, $i=1,2$ where $I_{1}, I_{2}\in \{\mathsf{P}, \mathsf{D}, \mathsf{N}\}$, and the forms $\mathsf{P}$, $\mathsf{D}$ and $\mathsf{N}$ correspond to perfect and instantaneous, completely delayed, and no CSIT, respectively. Thus, the overall CSIT can alternate between $9$ possible states corresponding to all possible values of $I_{1}I_{2}$, with each state occurring for $\lambda_{I_{1}I_{2}}$ fraction of the total duration. The main contribution of this paper is to establish the secure degrees of freedom (s.d.o.f.) region of the MISO BCCM with alternating CSIT with the symmetry assumption, where $\lambda_{I_{1} I_{2}}=\lambda_{I_{2}I_{1}}$. The main technical contributions include developing a) novel achievable schemes for MISO BCCM with alternating CSIT with security constraints which also highlight the synergistic benefits of inter-state coding for secrecy, b) new converse proofs via local statistical equivalence and channel enhancement; and c) showing the interplay between various aspects of channel knowledge and their impact on s.d.o.f.
• Fundamental Limits of Caching with Secure Delivery(1312.3961)

Dec. 11, 2014 cs.IT, math.IT, cs.NI
Caching is emerging as a vital tool for alleviating the severe capacity crunch in modern content-centric wireless networks. The main idea behind caching is to store parts of popular content in end-users' memory and leverage the locally stored content to reduce peak data rates. By jointly designing content placement and delivery mechanisms, recent works have shown order-wise reduction in transmission rates in contrast to traditional methods. In this work, we consider the secure caching problem with the additional goal of minimizing information leakage to an external wiretapper. The fundamental cache memory vs. transmission rate trade-off for the secure caching problem is characterized. Rather surprisingly, these results show that security can be introduced at a negligible cost, particularly for large number of files and users. It is also shown that the rate achieved by the proposed caching scheme with secure delivery is within a constant multiplicative factor from the information-theoretic optimal rate for almost all parameter values of practical interest.
• Distributed Space-Time Interference Alignment with Moderately-Delayed CSIT(1405.0032)

Oct. 13, 2014 cs.IT, math.IT
This paper proposes an interference alignment method with distributed and delayed channel state information at the transmitter (CSIT) for a class of interference networks. The core idea of the proposed method is to align interference signals over time at the unintended receivers in a distributed manner. With the proposed method, achievable trade-offs between the sum of degrees of freedom (sum-DoF) and feedback delay of CSI are characterized in both the X-channel and three-user interference channel to reveal the impact on how the CSI feedback delay affects the sum-DoF of the interference networks. A major implication of derived results is that distributed and moderately- delayed CSIT is useful to strictly improve the sum-DoF over the case of no CSI at the transmitter in a certain class of interference networks. For a class of X-channels, the results show how to optimally use distributed and moderately-delayed CSIT to yield the same sum-DoF as instantaneous and global CSIT. Further, leveraging the proposed transmission method and the known outer bound results, the sum-capacity of the two-user X-channel with a particular set of channel coefficients is characterized within a constant number of bits.
• On the Degrees-of-freedom of the 3-user MISO Broadcast Channel with Hybrid CSIT(1402.4729)

Feb. 19, 2014 cs.IT, math.IT
The 3-user multiple-input single-output (MISO) broadcast channel (BC) with hybrid channel state information at the transmitter (CSIT) is considered. In this framework, there is perfect and instantaneous CSIT from a subset of users and delayed CSIT from the remaining users. We present new results on the degrees of freedom (DoF) of the 3-user MISO BC with hybrid CSIT. In particular, for the case of 2 transmit antennas, we show that with perfect CSIT from one user and delayed CSIT from the remaining two users, the optimal DoF is 5/3. For the case of 3 transmit antennas and the same hybrid CSIT setting, it is shown that a higher DoF of 9/5 is achievable and this result improves upon the best known bound. Furthermore, with 3 transmit antennas, and the hybrid CSIT setting in which there is perfect CSIT from two users and delayed CSIT from the third one, a novel scheme is presented which achieves 9/4 DoF. Our results also reveal new insights on how to utilize hybrid channel knowledge for multi-user scenarios.
• Towards Optimal Secure Distributed Storage Systems with Exact Repair(1310.0054)

Feb. 19, 2014 cs.IT, math.IT
Distributed storage systems in the presence of a wiretapper are considered. A distributed storage system (DSS) is parameterized by three parameters (n, k,d), in which a file stored across n distributed nodes, can be recovered from any k out of n nodes. If a node fails, any d out of (n-1) nodes help in the repair of the failed node. For such a (n,k,d)-DSS, two types of wiretapping scenarios are investigated: (a) Type-I (node) adversary which can wiretap the data stored on any l<k nodes; and a more severe (b) Type-II (repair data) adversary which can wiretap the contents of the repair data that is used to repair a set of l failed nodes over time. The focus of this work is on the practically relevant setting of exact repair regeneration in which the repair process must replace a failed node by its exact replica. We make new progress on several non-trivial instances of this problem which prior to this work have been open. The main contribution of this paper is the optimal characterization of the secure storage-vs-exact-repair-bandwidth tradeoff region of a (n,k,d)-DSS, with n<=4 and any l<k in the presence of both Type-I and Type-II adversaries. While the problem remains open for a general (n,k,d)-DSS with n>4, we present extensions of these results to a (n, n-1,n-1)-DSS, in presence of a Type-II adversary that can observe the repair data of any l=(n-2) nodes. The key technical contribution of this work is in developing novel information theoretic converse proofs for the Type-II adversarial scenario. From our results, we show that in the presence of Type-II attacks, the only efficient point in the storage-vs-exact-repair-bandwidth tradeoff is the MBR (minimum bandwidth regenerating) point. This is in sharp contrast to the case of a Type-I attack in which the storage-vs-exact-repair-bandwidth tradeoff allows a spectrum of operating points beyond the MBR point.
• Retroactive Anti-Jamming for MISO Broadcast Channels(1308.6316)

Aug. 28, 2013 cs.IT, math.IT
Jamming attacks can significantly impact the performance of wireless communication systems. In addition to reducing the capacity, such attacks may lead to insurmountable overhead in terms of re-transmissions and increased power consumption. In this paper, we consider the multiple-input single-output (MISO) broadcast channel (BC) in the presence of a jamming attack in which a subset of the receivers can be jammed at any given time. Further, countermeasures for mitigating the effects of such jamming attacks are presented. The effectiveness of these anti-jamming countermeasures is quantified in terms of the degrees-of-freedom (DoF) of the MISO BC under various assumptions regarding the availability of the channel state information (CSIT) and the jammer state information at the transmitter (JSIT). The main contribution of this paper is the characterization of the DoF region of the two user MISO BC under various assumptions on the availability of CSIT and JSIT. Partial extensions to the multi-user broadcast channels are also presented.
• On the Feedback Capacity of the Fully Connected $K$-User Interference Channel(1110.6487)

Dec. 21, 2012 cs.IT, math.IT
The symmetric K user interference channel with fully connected topology is considered, in which (a) each receiver suffers interference from all other (K-1) transmitters, and (b) each transmitter has causal and noiseless feedback from its respective receiver. The number of generalized degrees of freedom (GDoF) is characterized in terms of \alpha, where the interference-to-noise ratio (INR) is given by INR=SNR^\alpha. It is shown that the per-user GDoF of this network is the same as that of the 2-user interference channel with feedback, except for \alpha=1, for which existence of feedback does not help in terms of GDoF. The coding scheme proposed for this network, termed cooperative interference alignment, is based on two key ingredients, namely, interference alignment and interference decoding. Moreover, an approximate characterization is provided for the symmetric feedback capacity of the network, when the SNR and INR are far apart from each other.