BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Suhas Diggavi

Suhas Diggavi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITCryptography and SecurityMachine LearningDistributed, Parallel, and Cluster Computingmath.OCSystems and ControlNetworking and Internet ArchitectureApplications

Catalog footprint

What is connected

48works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

48 published item(s)

preprint2022arXiv

A Generative Framework for Personalized Learning and Estimation: Theory, Algorithms, and Privacy

A distinguishing characteristic of federated learning is that the (local) client data could have statistical heterogeneity. This heterogeneity has motivated the design of personalized learning, where individual (personalized) models are trained, through collaboration. There have been various personalization methods proposed in literature, with seemingly very different forms and methods ranging from use of a single global model for local regularization and model interpolation, to use of multiple global models for personalized clustering, etc. In this work, we begin with a generative framework that could potentially unify several different algorithms as well as suggest new algorithms. We apply our generative framework to personalized estimation, and connect it to the classical empirical Bayes' methodology. We develop private personalized estimation under this framework. We then use our generative framework for learning, which unifies several known personalized FL algorithms and also suggests new ones; we propose and study a new algorithm AdaPeD based on a Knowledge Distillation, which numerically outperforms several known algorithms. We also develop privacy for personalized learning methods with guarantees for user-level privacy and composition. We numerically evaluate the performance as well as the privacy for both the estimation and learning problems, demonstrating the advantages of our proposed methods.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Differentially Private Stochastic Linear Bandits: (Almost) for Free

In this paper, we propose differentially private algorithms for the problem of stochastic linear bandits in the central, local and shuffled models. In the central model, we achieve almost the same regret as the optimal non-private algorithms, which means we get privacy for free. In particular, we achieve a regret of $\tilde{O}(\sqrt{T}+\frac{1}ε)$ matching the known lower bound for private linear bandits, while the best previously known algorithm achieves $\tilde{O}(\frac{1}ε\sqrt{T})$. In the local case, we achieve a regret of $\tilde{O}(\frac{1}ε{\sqrt{T}})$ which matches the non-private regret for constant $ε$, but suffers a regret penalty when $ε$ is small. In the shuffled model, we also achieve regret of $\tilde{O}(\sqrt{T}+\frac{1}ε)$ %for small $ε$ as in the central case, while the best previously known algorithm suffers a regret of $\tilde{O}(\frac{1}ε{T^{3/5}})$. Our numerical evaluation validates our theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Improving Group Testing via Gradient Descent

We study the problem of group testing with non-identical, independent priors. So far, the pooling strategies that have been proposed in the literature take the following approach: a hand-crafted test design along with a decoding strategy is proposed, and guarantees are provided on how many tests are sufficient in order to identify all infections in a population. In this paper, we take a different, yet perhaps more practical, approach: we fix the decoder and the number of tests, and we ask, given these, what is the best test design one could use? We explore this question for the Definite Non-Defectives (DND) decoder. We formulate a (non-convex) optimization problem, where the objective function is the expected number of errors for a particular design. We find approximate solutions via gradient descent, which we further optimize with informed initialization. We illustrate through simulations that our method can achieve significant performance improvement over traditional approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On Leave-One-Out Conditional Mutual Information For Generalization

We derive information theoretic generalization bounds for supervised learning algorithms based on a new measure of leave-one-out conditional mutual information (loo-CMI). Contrary to other CMI bounds, which are black-box bounds that do not exploit the structure of the problem and may be hard to evaluate in practice, our loo-CMI bounds can be computed easily and can be interpreted in connection to other notions such as classical leave-one-out cross-validation, stability of the optimization algorithm, and the geometry of the loss-landscape. It applies both to the output of training algorithms as well as their predictions. We empirically validate the quality of the bound by evaluating its predicted generalization gap in scenarios for deep learning. In particular, our bounds are non-vacuous on large-scale image-classification tasks.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

QuPeD: Quantized Personalization via Distillation with Applications to Federated Learning

Traditionally, federated learning (FL) aims to train a single global model while collaboratively using multiple clients and a server. Two natural challenges that FL algorithms face are heterogeneity in data across clients and collaboration of clients with {\em diverse resources}. In this work, we introduce a \textit{quantized} and \textit{personalized} FL algorithm QuPeD that facilitates collective (personalized model compression) training via \textit{knowledge distillation} (KD) among clients who have access to heterogeneous data and resources. For personalization, we allow clients to learn \textit{compressed personalized models} with different quantization parameters and model dimensions/structures. Towards this, first we propose an algorithm for learning quantized models through a relaxed optimization problem, where quantization values are also optimized over. When each client participating in the (federated) learning process has different requirements for the compressed model (both in model dimension and precision), we formulate a compressed personalization framework by introducing knowledge distillation loss for local client objectives collaborating through a global model. We develop an alternating proximal gradient update for solving this compressed personalization problem, and analyze its convergence properties. Numerically, we validate that QuPeD outperforms competing personalized FL methods, FedAvg, and local training of clients in various heterogeneous settings.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

QuPeL: Quantized Personalization with Applications to Federated Learning

Traditionally, federated learning (FL) aims to train a single global model while collaboratively using multiple clients and a server. Two natural challenges that FL algorithms face are heterogeneity in data across clients and collaboration of clients with {\em diverse resources}. In this work, we introduce a \textit{quantized} and \textit{personalized} FL algorithm QuPeL that facilitates collective training with heterogeneous clients while respecting resource diversity. For personalization, we allow clients to learn \textit{compressed personalized models} with different quantization parameters depending on their resources. Towards this, first we propose an algorithm for learning quantized models through a relaxed optimization problem, where quantization values are also optimized over. When each client participating in the (federated) learning process has different requirements of the quantized model (both in value and precision), we formulate a quantized personalization framework by introducing a penalty term for local client objectives against a globally trained model to encourage collaboration. We develop an alternating proximal gradient update for solving this quantized personalization problem, and we analyze its convergence properties. Numerically, we show that optimizing over the quantization levels increases the performance and we validate that QuPeL outperforms both FedAvg and local training of clients in a heterogeneous setting.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Algorithms for reconstruction over single and multiple deletion channels

Recent advances in DNA sequencing technology and DNA storage systems have rekindled the interest in deletion channels. Multiple recent works have looked at variants of sequence reconstruction over a single and over multiple deletion channels, a notoriously difficult problem due to its highly combinatorial nature. Although works in theoretical computer science have provided algorithms which guarantee perfect reconstruction with multiple independent observations from the deletion channel, they are only applicable in the large blocklength regime and more restrictively, when the number of observations is also large. Indeed, with only a few observations, perfect reconstruction of the input sequence may not even be possible in most cases. In such situations, maximum likelihood (ML) and maximum aposteriori (MAP) estimates for the deletion channels are natural questions that arise and these have remained open to the best of our knowledge. In this work, we take steps to answer the two aforementioned questions. Specifically: 1. We show that solving for the ML estimate over the single deletion channel (which can be cast as a discrete optimization problem) is equivalent to solving its relaxation, a continuous optimization problem; 2. We exactly compute the symbolwise posterior distributions (under some assumptions on the priors) for both the single as well as multiple deletion channels. As part of our contributions, we also introduce tools to visualize and analyze error events, which we believe could be useful in other related problems concerning deletion channels.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Byzantine-Resilient High-Dimensional Federated Learning

We study stochastic gradient descent (SGD) with local iterations in the presence of malicious/Byzantine clients, motivated by the federated learning. The clients, instead of communicating with the central server in every iteration, maintain their local models, which they update by taking several SGD iterations based on their own datasets and then communicate the net update with the server, thereby achieving communication-efficiency. Furthermore, only a subset of clients communicate with the server, and this subset may be different at different synchronization times. The Byzantine clients may collaborate and send arbitrary vectors to the server to disrupt the learning process. To combat the adversary, we employ an efficient high-dimensional robust mean estimation algorithm from Steinhardt et al.~\cite[ITCS 2018]{Resilience_SCV18} at the server to filter-out corrupt vectors; and to analyze the outlier-filtering procedure, we develop a novel matrix concentration result that may be of independent interest. We provide convergence analyses for strongly-convex and non-convex smooth objectives in the heterogeneous data setting, where different clients may have different local datasets, and we do not make any probabilistic assumptions on data generation. We believe that ours is the first Byzantine-resilient algorithm and analysis with local iterations. We derive our convergence results under minimal assumptions of bounded variance for SGD and bounded gradient dissimilarity (which captures heterogeneity among local datasets). We also extend our results to the case when clients compute full-batch gradients.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data

We study distributed stochastic gradient descent (SGD) in the master-worker architecture under Byzantine attacks. We consider the heterogeneous data model, where different workers may have different local datasets, and we do not make any probabilistic assumptions on data generation. At the core of our algorithm, we use the polynomial-time outlier-filtering procedure for robust mean estimation proposed by Steinhardt et al. (ITCS 2018) to filter-out corrupt gradients. In order to be able to apply their filtering procedure in our {\em heterogeneous} data setting where workers compute {\em stochastic} gradients, we derive a new matrix concentration result, which may be of independent interest. We provide convergence analyses for smooth strongly-convex and non-convex objectives. We derive our results under the bounded variance assumption on local stochastic gradients and a {\em deterministic} condition on datasets, namely, gradient dissimilarity; and for both these quantities, we provide concrete bounds in the statistical heterogeneous data model. We give a trade-off between the mini-batch size for stochastic gradients and the approximation error. Our algorithm can tolerate up to $\frac{1}{4}$ fraction Byzantine workers. It can find approximate optimal parameters in the strongly-convex setting exponentially fast and reach to an approximate stationary point in the non-convex setting with a linear speed, thus, matching the convergence rates of vanilla SGD in the Byzantine-free setting. We also propose and analyze a Byzantine-resilient SGD algorithm with gradient compression, where workers send $k$ random coordinates of their gradients. Under mild conditions, we show a $\frac{d}{k}$-factor saving in communication bits as well as decoding complexity over our compression-free algorithm without affecting its convergence rate (order-wise) and the approximation error.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Distortion based Light-weight Security for Cyber-Physical Systems

In Cyber-Physical Systems (CPS), inference based on communicated data is of critical significance as it can be used to manipulate or damage the control operations by adversaries. This calls for efficient mechanisms for secure transmission of data since control systems are becoming increasingly distributed over larger geographical areas. Distortion based security, recently proposed as one candidate for secure transmissions in CPS, is not only more appropriate for these applications but also quite frugal in terms of prior requirements on shared keys. In this paper, we propose distortion-based metrics to protect CPS communication and show that it is possible to confuse adversaries with just a few bits of pre-shared keys. In particular, we will show that a linear dynamical system can communicate its state in a manner that prevents an eavesdropper from accurately learning the state.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Generalized Degrees of Freedom of Noncoherent Diamond Networks

We study the generalized degrees of freedom (gDoF) of the block-fading noncoherent diamond (parallel relay) wireless network with asymmetric distributions of link strengths, and a coherence time of T symbol duration. We first derive an outer bound for this channel and then derive the optimal signaling structure for this outer bound. Using the optimal signaling structure we solve the outer bound optimization problem in terms of its gDoF. Using insights from our outer bound signaling solution, we devise an achievability strategy based on a novel scheme that we call train-scale quantize-map-forward (TS-QMF). This uses training in the links from the source to the relays, scaling and quantizing at the relays combined with nontraining-based schemes. We show the optimality of this scheme with respect to the outer bound in terms of the gDoF. In noncoherent point-to-point multiple-input-multiple-output (MIMO) channels, where the fading channel is unknown to transmitter and receiver, an important tradeoff between communication and channel learning was revealed by Zheng and Tse, by demonstrating that not all the available antennas might be used, as it is suboptimal to learn all their channel parameters. Our results in this paper for the diamond network demonstrates that in certain regimes the optimal scheme uses a subnetwork, demonstrating a tradeoff between channel learning and communications. In some regimes, it is gDoF optimal to do relay selection, i.e, use a part of the network. In the other regimes, even when it is essential to use the entire network, it is suboptimal to learn the channel states for all the links in the network, i.e, traditional training-based schemes are suboptimal in these regimes.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

SPARQ-SGD: Event-Triggered and Compressed Communication in Decentralized Stochastic Optimization

In this paper, we propose and analyze SPARQ-SGD, which is an event-triggered and compressed algorithm for decentralized training of large-scale machine learning models. Each node can locally compute a condition (event) which triggers a communication where quantized and sparsified local model parameters are sent. In SPARQ-SGD each node takes at least a fixed number ($H$) of local gradient steps and then checks if the model parameters have significantly changed compared to its last update; it communicates further compressed model parameters only when there is a significant change, as specified by a (design) criterion. We prove that the SPARQ-SGD converges as $O(\frac{1}{nT})$ and $O(\frac{1}{\sqrt{nT}})$ in the strongly-convex and non-convex settings, respectively, demonstrating that such aggressive compression, including event-triggered communication, model sparsification and quantization does not affect the overall convergence rate as compared to uncompressed decentralized training; thereby theoretically yielding communication efficiency for "free". We evaluate SPARQ-SGD over real datasets to demonstrate significant amount of savings in communication over the state-of-the-art.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Successive Refinement of Privacy

This work examines a novel question: how much randomness is needed to achieve local differential privacy (LDP)? A motivating scenario is providing {\em multiple levels of privacy} to multiple analysts, either for distribution or for heavy-hitter estimation, using the \emph{same} (randomized) output. We call this setting \emph{successive refinement of privacy}, as it provides hierarchical access to the raw data with different privacy levels. For example, the same randomized output could enable one analyst to reconstruct the input, while another can only estimate the distribution subject to LDP requirements. This extends the classical Shannon (wiretap) security setting to local differential privacy. We provide (order-wise) tight characterizations of privacy-utility-randomness trade-offs in several cases for distribution estimation, including the standard LDP setting under a randomness constraint. We also provide a non-trivial privacy mechanism for multi-level privacy. Furthermore, we show that we cannot reuse random keys over time while preserving privacy of each user.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Layered Caching Architecture for the Interference Channel

Recent work has studied the benefits of caching in the interference channel, particularly by placing caches at the transmitters. In this paper, we study the two-user Gaussian interference channel in which caches are placed at both the transmitters and the receivers. We propose a separation strategy that divides the physical and network layers. While a natural separation approach might be to abstract the physical layer into several independent bit pipes at the network layer, we argue that this is inefficient. Instead, the separation approach we propose exposes interacting bit pipes at the network layer, so that the receivers observe related (yet not identical) quantities. We find the optimal strategy within this layered architecture, and we compute the degrees-of-freedom it achieves. Finally, we show that separation is optimal in regimes where the receiver caches are large.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Attack Resilience and Recovery using Physical Challenge Response Authentication for Active Sensors Under Integrity Attacks

Embedded sensing systems are pervasively used in life- and security-critical systems such as those found in airplanes, automobiles, and healthcare. Traditional security mechanisms for these sensors focus on data encryption and other post-processing techniques, but the sensors themselves often remain vulnerable to attacks in the physical/analog domain. If an adversary manipulates a physical/analog signal prior to digitization, no amount of digital security mechanisms after the fact can help. Fortunately, nature imposes fundamental constraints on how these analog signals can behave. This work presents PyCRA, a physical challenge-response authentication scheme designed to protect active sensing systems against physical attacks occurring in the analog domain. PyCRA provides security for active sensors by continually challenging the surrounding environment via random but deliberate physical probes. By analyzing the responses to these probes, and by using the fact that the adversary cannot change the underlying laws of physics, we provide an authentication mechanism that not only detects malicious attacks but provides resilience against them. We demonstrate the effectiveness of PyCRA through several case studies using two sensing systems: (1) magnetic sensors like those found wheel speed sensors in robotics and automotive, and (2) commercial RFID tags used in many security-critical applications. Finally, we outline methods and theoretical proofs for further enhancing the resilience of PyCRA to active attacks by means of a confusion phase---a period of low signal to noise ratio that makes it more difficult for an attacker to correctly identify and respond to PyCRA's physical challenges. In doing so, we evaluate both the robustness and the limitations of PyCRA, concluding by outlining practical considerations as well as further applications for the proposed authentication mechanism.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Capacity Results for Multicasting Nested Message Sets over Combination Networks

The problem of multicasting two nested messages is studied over a class of networks known as combination networks. A source multicasts two messages, a common and a private message, to several receivers. A subset of the receivers (called the public receivers) only demand the common message and the rest of the receivers (called the private receivers) demand both the common and the private message. Three encoding schemes are discussed that employ linear superposition coding and their optimality is proved in special cases. The standard linear superposition scheme is shown to be optimal for networks with two public receivers and any number of private receivers. When the number of public receivers increases, this scheme stops being optimal. Two improvements are discussed: one using pre-encoding at the source, and one using a block Markov encoding scheme. The rate-regions that are achieved by the two schemes are characterized in terms of feasibility problems. Both inner-bounds are shown to be the capacity region for networks with three (or fewer) public and any number of private receivers. Although the inner bounds are not comparable in general, it is shown through an example that the region achieved by the block Markov encoding scheme may strictly include the region achieved by the pre-encoding/linear superposition scheme. Optimality results are founded on the general framework of Balister and Bollobás (2012) for sub-modularity of the entropy function. An equivalent graphical representation is introduced and a lemma is proved that might be of independent interest. Motivated by the connections between combination networks and broadcast channels, a new block Markov encoding scheme is proposed for broadcast channels with two nested messages. The rate-region that is obtained includes the previously known rate-regions. It remains open whether this inclusion is strict.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Wiretapped Oblivious Transfer

In this paper, we study the problem of obtaining $1$-of-$2$ string oblivious transfer (OT) between users Alice and Bob, in the presence of a passive eavesdropper Eve. The resource enabling OT in our setup is a noisy broadcast channel from Alice to Bob and Eve. Apart from the OT requirements between the users, Eve is not allowed to learn anything about the users' inputs. When Alice and Bob are honest-but-curious and the noisy broadcast channel is made up of two independent binary erasure channels (connecting Alice-Bob and Alice-Eve), we derive the $1$-of-$2$ string OT capacity for both $2$-privacy (when Eve can collude with either Alice or Bob) and $1$-privacy (when no such collusion is allowed). We generalize these capacity results to $1$-of-$N$ string OT and study other variants of this problem. When Alice and/or Bob are malicious, we present a different scheme based on interactive hashing. This scheme is shown to be optimal for certain parameter regimes. We present a new formulation of multiple, simultaneous OTs between Alice-Bob and Alice-Cathy. For this new setup, we present schemes and outer bounds that match in all but one regime of parameters. Finally, we consider the setup where the broadcast channel is made up of a cascade of two independent binary erasure channels (connecting Alice-Bob and Bob-Eve) and $1$-of-$2$ string OT is desired between Alice and Bob with $1$-privacy. For this setup, we derive an upper and lower bound on the $1$-of-$2$ string OT capacity which match in one of two possible parameter regimes.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Coded Caching for Multi-level Popularity and Access

To address the exponentially rising demand for wireless content, use of caching is emerging as a potential solution. It has been recently established that joint design of content delivery and storage (coded caching) can significantly improve performance over conventional caching. Coded caching is well suited to emerging heterogeneous wireless architectures which 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). This enables design of coded caching-and-delivery schemes that equip APs with storage, and place content in them in a way that creates coded-multicast opportunities for combining with macro-cell broadcast to satisfy users even with different demands. Such coded-caching schemes have been shown to be order-optimal with respect to the BS transmission rate, for a system with single-level content, i.e., one where all content is uniformly popular. In this work, we consider a system with non-uniform popularity content which is divided into multiple levels, based on varying degrees of popularity. The main contribution of this work is the derivation of an order-optimal scheme which judiciously shares cache memory among files with different popularities. To show order-optimality we derive new information-theoretic lower bounds, which use a sliding-window entropy inequality, effectively creating a non-cutset bound. We also extend the ideas to when users can access multiple caches along with the broadcast. Finally 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), and demonstrate a dichotomy in the order-optimal strategies for these two extreme cases.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Content Caching and Delivery over Heterogeneous Wireless Networks

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Effect of Number of Users in Multi-level Coded Caching

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Gaussian Interference Channel with Intermittent Feedback

We investigate how to exploit intermittent feedback for interference management by studying the two-user Gaussian interference channel (IC). We approximately characterize (within a universal constant) the capacity region for the Gaussian IC with intermittent feedback. We exactly characterize the the capacity region of the linear deterministic version of the problem, which gives us insight into the Gaussian problem. We find that the characterization only depends on the forward channel parameters and the marginal probability distribution of each feedback link. The result shows that passive and unreliable feedback can be harnessed to provide multiplicative capacity gain in Gaussian interference channels. 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. 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 also develop new outer bounds enabling us to obtain the (approximate) characterization of the capacity region.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Oblivious Transfer Capacity of the Degraded Wiretapped Binary Erasure Channel

We study oblivious transfer (OT) between Alice and Bob in the presence of an eavesdropper Eve over a degraded wiretapped binary erasure channel from Alice to Bob and Eve. In addition to the privacy goals of oblivious transfer between Alice and Bob, we require privacy of Alice and Bob's private data from Eve. In previous work we derived the OT capacity (in the honest-but-curious model) of the wiretapped binary independent erasure channel where the erasure processes of Bob and Eve are independent. Here we derive a lower bound on the OT capacity in the same secrecy model when the wiretapped binary erasure channel is degraded in favour of Bob.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Opportunistic Scheduling for Full-Duplex Uplink-Downlink Networks

We study opportunistic scheduling and the sum capacity of cellular networks with a full-duplex multi-antenna base station and a large number of single-antenna half-duplex users. Simultaneous uplink and downlink over the same band results in uplink-to-downlink interference, degrading performance. We present a simple opportunistic joint uplink-downlink scheduling algorithm that exploits multiuser diversity and treats interference as noise. We show that in homogeneous networks, our algorithm achieves the same sum capacity as what would have been achieved if there was no uplink-to-downlink interference, asymptotically in the number of users. The algorithm does not require interference CSI at the base station or uplink users. It is also shown that for a simple class of heterogeneous networks without sufficient channel diversity, it is not possible to achieve the corresponding interference-free system capacity. We discuss the potential for using device-to-device side-channels to overcome this limitation in heterogeneous networks.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Secure State Estimation against Sensor Attacks in the Presence of Noise

We consider the problem of estimating the state of a noisy linear dynamical system when an unknown subset of sensors is arbitrarily corrupted by an adversary. We propose a secure state estimation algorithm, and derive (optimal) bounds on the achievable state estimation error given an upper bound on the number of attacked sensors. The proposed state estimator involves Kalman filters operating over subsets of sensors to search for a sensor subset which is reliable for state estimation. To further improve the subset search time, we propose Satisfiability Modulo Theory based techniques to exploit the combinatorial nature of searching over sensor subsets. Finally, as a result of independent interest, we give a coding theoretic view of attack detection and state estimation against sensor attacks in a noiseless dynamical system.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Secure State Estimation: Optimal Guarantees against Sensor Attacks in the Presence of Noise

Motivated by the need to secure cyber-physical systems against attacks, we consider the problem of estimating the state of a noisy linear dynamical system when a subset of sensors is arbitrarily corrupted by an adversary. We propose a secure state estimation algorithm and derive (optimal) bounds on the achievable state estimation error. In addition, as a result of independent interest, we give a coding theoretic interpretation for prior work on secure state estimation against sensor attacks in a noiseless dynamical system.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

When are dynamic relaying strategies necessary in half-duplex wireless networks?

We study a simple question: when are dynamic relaying strategies essential in optimizing the diversity-multiplexing tradeoff (DMT) in half-duplex wireless relay networks? This is motivated by apparently two contrasting results even for a simple 3 node network, with a single half-duplex relay. When all channels are assumed to be i.i.d. fading, a static schedule where the relay listens half the time and transmits half the time combined with quantize-map-forward (QMF) relaying is known to achieve the full-duplex performance. However, when there is no direct link between source and destination, a dynamic-decode-forward (DDF) strategy is needed to achieve the optimal tradeoff. In this case, a static schedule is strictly suboptimal and the optimal tradeoff is significantly worse than the full-duplex performance. In this paper we study the general case when the direct link is neither as strong as the other links nor fully non-existent, and identify regimes where dynamic schedules are necessary and those where static schedules are enough. We identify 4 qualitatively different regimes for the single relay channel where the tradeoff between diversity and multiplexing is significantly different. We show that in all these regimes one of the above two strategies is sufficient to achieve the optimal tradeoff by developing a new upper bound on the best achievable tradeoff under channel state information available only at the receivers. A natural next question is whether these two strategies are sufficient to achieve the DMT of more general half-duplex wireless networks. We propose a generalization of the two existing schemes through a dynamic QMF (DQMF) strategy, where the relay listens for a fraction of time depending on received CSI but not long enough to be able to decode. We show that such a DQMF strategy is needed to achieve the optimal DMT in a parallel channel with two relays.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Feedback through Overhearing

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Harnessing Bursty Interference in Multicarrier Systems with Feedback

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Secret Communication over Broadcast Erasure Channels with State-feedback

We consider a 1-to-$K$ communication scenario, where a source transmits private messages to $K$ receivers through a broadcast erasure channel, and the receivers feed back strictly causally and publicly their channel states after each transmission. We explore the achievable rate region when we require that the message to each receiver remains secret - in the information theoretical sense - from all the other receivers. We characterize the capacity of secure communication in all the cases where the capacity of the 1-to-$K$ communication scenario without the requirement of security is known. As a special case, we characterize the secret-message capacity of a single receiver point-to-point erasure channel with public state-feedback in the presence of a passive eavesdropper. We find that in all cases where we have an exact characterization, we can achieve the capacity by using linear complexity two-phase schemes: in the first phase we create appropriate secret keys, and in the second phase we use them to encrypt each message. We find that the amount of key we need is smaller than the size of the message, and equal to the amount of encrypted message the potential eavesdroppers jointly collect. Moreover, we prove that a dishonest receiver that provides deceptive feedback cannot diminish the rate experienced by the honest receivers. We also develop a converse proof which reflects the two-phase structure of our achievability scheme. As a side result, our technique leads to a new outer bound proof for the non-secure communication problem.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Oblivious Transfer Capacity of the Wiretapped Binary Erasure Channel

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).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Coding with Encoding Uncertainty

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Computation over Mismatched Channels

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Interference Channel with Intermittent Feedback

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Opportunistic Interference Management for Multicarrier systems

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. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Optimality and Approximate Optimality of Source-Channel Separation in Networks

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 by 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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Using Feedback for Secrecy over Graphs

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Approximately achieving Gaussian relay network capacity with lattice codes

Recently, it has been shown that a quantize-map-and-forward scheme approximately achieves (within a constant number of bits) the Gaussian relay network capacity for arbitrary topologies. This was established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we show that the same approximation result can be established by using lattices for transmission and quantization along with structured mappings at the relays.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Exchanging Secrets without Using Cryptography

We consider the problem where a group of n nodes, connected to the same broadcast channel (e.g., a wireless network), want to generate a common secret bitstream, in the presence of an adversary Eve, who tries to obtain information on the bitstream. We assume that the nodes initially share a (small) piece of information, but do not have access to any out-of-band channel. We ask the question: can this problem be solved without relying on Eve's computational limitations, i.e., without using any form of public-key cryptography? 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. In this task, the nodes are assisted by a small number of interferers, whose role is to create channel noise in a way that bounds the amount of information Eve can overhear. Our protocol has polynomial-time complexity and requires no changes to the physical or MAC layer of network devices. First, we formally show that, under standard theoretical assumptions, our protocol is information-theoretically secure, achieves optimal secret-generation rate for n = 2 nodes, and scales well to an arbitrary number of nodes. Second, we adapt our protocol to a small wireless 14-square-meter testbed; we experimentally show that, if Eve uses a standard wireless physical layer and is not too close to any of the nodes, 8 nodes can achieve a secret-generation rate of 38 Kbps. To the best of our knowledge, ours is the first experimental demonstration of information-theoretic secret exchange on a wireless network at a rate beyond a few tens of bits per second.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Secure estimation and control for cyber-physical systems under adversarial attacks

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. In the first part we look at the estimation problem where we characterize the resilience of a system to attacks and study the possibility of increasing its resilience by a change of parameters. We then propose an efficient algorithm to estimate the state despite the attacks and we characterize its performance. Our approach is inspired from the areas of error-correction over the reals and compressed sensing. In the second part we consider the problem of designing output-feedback controllers that stabilize the system despite 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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Approximate Capacity of the Gaussian N-Relay Diamond Network

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 N^2, 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(log^4(N)) of capacity with pre-constant in the order notation independent of the channel gains.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Secure Capacity Region for Erasure Broadcast Channels with Feedback

We formulate and study a cryptographic problem relevant to wireless: a sender, Alice, wants to transmit private messages to two receivers, Bob and Calvin, using unreliable wireless broadcast transmissions and short public feedback from Bob and Calvin. We ask, at what rates can we broadcast the private messages if we also provide (information-theoretic) unconditional security guarantees that Bob and Calvin do not learn each-other's message? We characterize the largest transmission rates to the two receivers, for any protocol that provides unconditional security guarantees. We design a protocol that operates at any rate-pair within the above region, uses very simple interactions and operations, and is robust to misbehaving users.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Subspace Properties of Network Coding and their Applications

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 towards 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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Wireless Network Information Flow: A Deterministic Approach

In a wireless network with a single source and a single destination and an arbitrary number of relay nodes, what is the maximum rate of information flow achievable? We make progress on this long standing problem through a two-step approach. First we propose a deterministic channel model which captures the key wireless properties of signal strength, broadcast and superposition. We obtain an exact characterization of the capacity of a network with nodes connected by such deterministic channels. This result is a natural generalization of the celebrated max-flow min-cut theorem for wired networks. Second, we use the insights obtained from the deterministic analysis to design a new quantize-map-and-forward scheme for Gaussian networks. In this scheme, each relay quantizes the received signal at the noise level and maps it to a random Gaussian codeword for forwarding, and the final destination decodes the source's message based on the received signal. We show that, in contrast to existing schemes, this scheme can achieve the cut-set upper bound to within a gap which is independent of the channel parameters. In the case of the relay channel with a single relay as well as the two-relay Gaussian diamond network, the gap is 1 bit/s/Hz. Moreover, the scheme is universal in the sense that the relays need no knowledge of the values of the channel parameters to (approximately) achieve the rate supportable by the network. We also present extensions of the results to multicast networks, half-duplex networks and ergodic networks.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Approximate Characterizations for the Gaussian Source Broadcast Distortion Region

We consider the joint source-channel coding problem of sending a Gaussian source on a K-user Gaussian broadcast channel with bandwidth mismatch. A new outer bound to the achievable distortion region is derived using the technique of introducing more than one additional auxiliary random variable, which was previously used to derive sum-rate lower bound for the symmetric Gaussian multiple description problem. By combining this outer bound with the achievability result based on source-channel separation, we provide approximate characterizations of the achievable distortion region within constant multiplicative factors. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On the Capacity of Non-Coherent Network Coding

We consider the problem of multicasting information from a source to a set of receivers over a network where intermediate network nodes perform randomized network coding operations on the source packets. We propose a channel model for the non-coherent network coding introduced by Koetter and Kschischang in [6], that captures the essence of such a network operation, and calculate the capacity 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. This model and the results also allow us to give guidelines on when subspace coding is beneficial for the proposed model and by how much, in comparison to a coding vector approach, from a capacity viewpoint. We extend our results to the case of multiple source multicast that creates a virtual multiple access channel.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Secret-key Agreement with Channel State Information at the Transmitter

We study the capacity of secret-key agreement over a wiretap channel with state parameters. The transmitter communicates to the legitimate receiver and the eavesdropper over a discrete memoryless wiretap channel with a memoryless state sequence. The transmitter and the legitimate receiver generate a shared secret key, that remains secret from the eavesdropper. No public discussion channel is available. The state sequence is known noncausally to the transmitter. We derive lower and upper bounds on the secret-key capacity. The lower bound involves constructing a common state reconstruction sequence at the legitimate terminals and binning the set of reconstruction sequences to obtain the secret-key. For the special case of Gaussian channels with additive interference (secret-keys from dirty paper channel) our bounds differ by 0.5 bit/symbol and coincide in the high signal-to-noise-ratio and high interference-to-noise-ratio regimes. For the case when the legitimate receiver is also revealed the state sequence, we establish that our lower bound achieves the the secret-key capacity. In addition, for this special case, we also propose another scheme that attains the capacity and requires only causal side information at the transmitter and the receiver.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Secret-Key Generation using Correlated Sources and Channels

We study the problem of generating a shared secret key between two terminals in a joint source-channel setup -- the sender communicates to the receiver over a discrete memoryless wiretap channel and additionally the terminals have access to correlated discrete memoryless source sequences. We establish lower and upper bounds on the secret-key capacity. These bounds coincide, establishing the capacity, when the underlying channel consists of independent, parallel and reversely degraded wiretap channels. In the lower bound, the equivocation terms of the source and channel components are functionally additive. The secret-key rate is maximized by optimally balancing the the source and channel contributions. This tradeoff is illustrated in detail for the Gaussian case where it is also shown that Gaussian codebooks achieve the capacity. When the eavesdropper also observes a source sequence, the secret-key capacity is established when the sources and channels of the eavesdropper are a degraded version of the legitimate receiver. Finally the case when the terminals also have access to a public discussion channel is studied. We propose generating separate keys from the source and channel components and establish the optimality of this approach when the when the channel outputs of the receiver and the eavesdropper are conditionally independent given the input.

0 citations0 reviewsNo code linkedOpen access