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

A. Salman Avestimehr

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

ResearcherUnclaimed source record
Information Theorymath.ITDistributed, Parallel, and Cluster ComputingMachine LearningCryptography and Securitymath.CONetworking and Internet Architecture

Catalog footprint

What is connected

48works
7topics
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)

preprint2021arXiv

Analog Lagrange Coded Computing

A distributed computing scenario is considered, where the computational power of a set of worker nodes is used to perform a certain computation task over a dataset that is dispersed among the workers. Lagrange coded computing (LCC), proposed by Yu et al., leverages the well-known Lagrange polynomial to perform polynomial evaluation of the dataset in such a scenario in an efficient parallel fashion while keeping the privacy of data amidst possible collusion of workers. This solution relies on quantizing the data into a finite field, so that Shamir's secret sharing, as one of its main building blocks, can be employed. Such a solution, however, is not properly scalable with the size of dataset, mainly due to computation overflows. To address such a critical issue, we propose a novel extension of LCC to the analog domain, referred to as analog LCC (ALCC). All the operations in the proposed ALCC protocol are done over the infinite fields of R/C but for practical implementations floating-point numbers are used. We characterize the privacy of data in ALCC, against any subset of colluding workers up to a certain size, in terms of the distinguishing security (DS) and the mutual information security (MIS) metrics. Also, the accuracy of outcome is characterized in a practical setting assuming operations are performed using floating-point numbers. Consequently, a fundamental trade-off between the accuracy of the outcome of ALCC and its privacy level is observed and is numerically evaluated. Moreover, we implement the proposed scheme to perform matrix-matrix multiplication over a batch of matrices. It is observed that ALCC is superior compared to the state-of-the-art LCC, implemented using fixed-point numbers, assuming both schemes use an equal number of bits to represent data symbols.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Byzantine-Resilient Secure Federated Learning

Secure federated learning is a privacy-preserving framework to improve machine learning models by training over large volumes of data collected by mobile users. This is achieved through an iterative process where, at each iteration, users update a global model using their local datasets. Each user then masks its local model via random keys, and the masked models are aggregated at a central server to compute the global model for the next iteration. As the local models are protected by random masks, the server cannot observe their true values. This presents a major challenge for the resilience of the model against adversarial (Byzantine) users, who can manipulate the global model by modifying their local models or datasets. Towards addressing this challenge, this paper presents the first single-server Byzantine-resilient secure aggregation framework (BREA) for secure federated learning. BREA is based on an integrated stochastic quantization, verifiable outlier detection, and secure model aggregation approach to guarantee Byzantine-resilience, privacy, and convergence simultaneously. We provide theoretical convergence and privacy guarantees and characterize the fundamental trade-offs in terms of the network size, user dropouts, and privacy protection. Our experiments demonstrate convergence in the presence of Byzantine users, and comparable accuracy to conventional federated learning benchmarks.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Coded Computing for Secure Boolean Computations

The growing size of modern datasets necessitates splitting a large scale computation into smaller computations and operate in a distributed manner. Adversaries in a distributed system deliberately send erroneous data in order to affect the computation for their benefit. Boolean functions are the key components of many applications, e.g., verification functions in blockchain systems and design of cryptographic algorithms. We consider the problem of computing a Boolean function in a distributed computing system with particular focus on \emph{security against Byzantine workers}. Any Boolean function can be modeled as a multivariate polynomial with high degree in general. However, the security threshold (i.e., the maximum number of adversarial workers can be tolerated such that the correct results can be obtained) provided by the recent proposed Lagrange Coded Computing (LCC) can be extremely low if the degree of the polynomial is high. We propose three different schemes called \emph{coded Algebraic normal form (ANF)}, \emph{coded Disjunctive normal form (DNF)} and \emph{coded polynomial threshold function (PTF)}. The key idea of the proposed schemes is to model it as the concatenation of some low-degree polynomials and threshold functions. In terms of the security threshold, we show that the proposed coded ANF and coded DNF are optimal by providing a matching outer bound.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

CodedPrivateML: A Fast and Privacy-Preserving Framework for Distributed Machine Learning

How to train a machine learning model while keeping the data private and secure? We present CodedPrivateML, a fast and scalable approach to this critical problem. CodedPrivateML keeps both the data and the model information-theoretically private, while allowing efficient parallelization of training across distributed workers. We characterize CodedPrivateML's privacy threshold and prove its convergence for logistic (and linear) regression. Furthermore, via extensive experiments on Amazon EC2, we demonstrate that CodedPrivateML provides significant speedup over cryptographic approaches based on multi-party computing (MPC).

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Edge Computing in the Dark: Leveraging Contextual-Combinatorial Bandit and Coded Computing

With recent advancements in edge computing capabilities, there has been a significant increase in utilizing the edge cloud for event-driven and time-sensitive computations. However, large-scale edge computing networks can suffer substantially from unpredictable and unreliable computing resources which can result in high variability of service quality. Thus, it is crucial to design efficient task scheduling policies that guarantee quality of service and the timeliness of computation queries. In this paper, we study the problem of computation offloading over unknown edge cloud networks with a sequence of timely computation jobs. Motivated by the MapReduce computation paradigm, we assume each computation job can be partitioned to smaller Map functions that are processed at the edge, and the Reduce function is computed at the user after the Map results are collected from the edge nodes. We model the service quality (success probability of returning result back to the user within deadline) of each edge device as function of context (collection of factors that affect edge devices). The user decides the computations to offload to each device with the goal of receiving a recoverable set of computation results in the given deadline. Our goal is to design an efficient edge computing policy in the dark without the knowledge of the context or computation capabilities of each device. By leveraging the \emph{coded computing} framework in order to tackle failures or stragglers in computation, we formulate this problem using contextual-combinatorial multi-armed bandits (CC-MAB), and aim to maximize the cumulative expected reward. We propose an online learning policy called \emph{online coded edge computing policy}, which provably achieves asymptotically-optimal performance in terms of regret loss compared with the optimal offline policy for the proposed CC-MAB problem.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Secure Aggregation for Buffered Asynchronous Federated Learning

Federated learning (FL) typically relies on synchronous training, which is slow due to stragglers. While asynchronous training handles stragglers efficiently, it does not ensure privacy due to the incompatibility with the secure aggregation protocols. A buffered asynchronous training protocol known as FedBuff has been proposed recently which bridges the gap between synchronous and asynchronous training to mitigate stragglers and to also ensure privacy simultaneously. FedBuff allows the users to send their updates asynchronously while ensuring privacy by storing the updates in a trusted execution environment (TEE) enabled private buffer. TEEs, however, have limited memory which limits the buffer size. Motivated by this limitation, we develop a buffered asynchronous secure aggregation (BASecAgg) protocol that does not rely on TEEs. The conventional secure aggregation protocols cannot be applied in the buffered asynchronous setting since the buffer may have local models corresponding to different rounds and hence the masks that the users use to protect their models may not cancel out. BASecAgg addresses this challenge by carefully designing the masks such that they cancel out even if they correspond to different rounds. Our convergence analysis and experiments show that BASecAgg almost has the same convergence guarantees as FedBuff without relying on TEEs.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning

Federated learning is a distributed framework for training machine learning models over the data residing at mobile devices, while protecting the privacy of individual users. A major bottleneck in scaling federated learning to a large number of users is the overhead of secure model aggregation across many users. In particular, the overhead of the state-of-the-art protocols for secure model aggregation grows quadratically with the number of users. In this paper, we propose the first secure aggregation framework, named Turbo-Aggregate, that in a network with $N$ users achieves a secure aggregation overhead of $O(N\log{N})$, as opposed to $O(N^2)$, while tolerating up to a user dropout rate of $50\%$. Turbo-Aggregate employs a multi-group circular strategy for efficient model aggregation, and leverages additive secret sharing and novel coding techniques for injecting aggregation redundancy in order to handle user dropouts while guaranteeing user privacy. We experimentally demonstrate that Turbo-Aggregate achieves a total running time that grows almost linear in the number of users, and provides up to $40\times$ speedup over the state-of-the-art protocols with up to $N=200$ users. Our experiments also demonstrate the impact of model size and bandwidth on the performance of Turbo-Aggregate.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier

In distributed matrix multiplication, a common scenario is to assign each worker a fraction of the multiplication task, by partitioning the input matrices into smaller submatrices. In particular, by dividing two input matrices into $m$-by-$p$ and $p$-by-$n$ subblocks, a single multiplication task can be viewed as computing linear combinations of $pmn$ submatrix products, which can be assigned to $pmn$ workers. Such block-partitioning based designs have been widely studied under the topics of secure, private, and batch computation, where the state of the arts all require computing at least "cubic" ($pmn$) number of submatrix multiplications. Entangled polynomial codes, first presented for straggler mitigation, provides a powerful method for breaking the cubic barrier. It achieves a subcubic recovery threshold, meaning that the final product can be recovered from \emph{any} subset of multiplication results with a size order-wise smaller than $pmn$. In this work, we show that entangled polynomial codes can be further extended to also include these three important settings, and provide a unified framework that order-wise reduces the total computational costs upon the state of the arts by achieving subcubic recovery thresholds.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Minimax Lower Bounds for Transfer Learning with Linear and One-hidden Layer Neural Networks

Transfer learning has emerged as a powerful technique for improving the performance of machine learning models on new domains where labeled training data may be scarce. In this approach a model trained for a source task, where plenty of labeled training data is available, is used as a starting point for training a model on a related target task with only few labeled training data. Despite recent empirical success of transfer learning approaches, the benefits and fundamental limits of transfer learning are poorly understood. In this paper we develop a statistical minimax framework to characterize the fundamental limits of transfer learning in the context of regression with linear and one-hidden layer neural network models. Specifically, we derive a lower-bound for the target generalization error achievable by any algorithm as a function of the number of labeled source and target data as well as appropriate notions of similarity between the source and target tasks. Our lower bound provides new insights into the benefits and limitations of transfer learning. We further corroborate our theoretical finding with various experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

PolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously

Today's blockchain designs suffer from a trilemma claiming that no blockchain system can simultaneously achieve decentralization, security, and performance scalability. For current blockchain systems, as more nodes join the network, the efficiency of the system (computation, communication, and storage) stays constant at best. A leading idea for enabling blockchains to scale efficiency is the notion of sharding: different subsets of nodes handle different portions of the blockchain, thereby reducing the load for each individual node. However, existing sharding proposals achieve efficiency scaling by compromising on trust - corrupting the nodes in a given shard will lead to the permanent loss of the corresponding portion of data. In this paper, we settle the trilemma by demonstrating a new protocol for coded storage and computation in blockchains. In particular, we propose PolyShard: ``polynomially coded sharding'' scheme that achieves information-theoretic upper bounds on the efficiency of the storage, system throughput, as well as on trust, thus enabling a truly scalable system. We provide simulation results that numerically demonstrate the performance improvement over state of the arts, and the scalability of the PolyShard system. Finally, we discuss potential enhancements, and highlight practical considerations in building such a system.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Privacy-Preserving Distributed Learning in the Analog Domain

We consider the critical problem of distributed learning over data while keeping it private from the computational servers. The state-of-the-art approaches to this problem rely on quantizing the data into a finite field, so that the cryptographic approaches for secure multiparty computing can then be employed. These approaches, however, can result in substantial accuracy losses due to fixed-point representation of the data and computation overflows. To address these critical issues, we propose a novel algorithm to solve the problem when data is in the analog domain, e.g., the field of real/complex numbers. We characterize the privacy of the data from both information-theoretic and cryptographic perspectives, while establishing a connection between the two notions in the analog domain. More specifically, the well-known connection between the distinguishing security (DS) and the mutual information security (MIS) metrics is extended from the discrete domain to the continues domain. This is then utilized to bound the amount of information about the data leaked to the servers in our protocol, in terms of the DS metric, using well-known results on the capacity of single-input multiple-output (SIMO) channel with correlated noise. It is shown how the proposed framework can be adopted to do computation tasks when data is represented using floating-point numbers. We then show that this leads to a fundamental trade-off between the privacy level of data and accuracy of the result. As an application, we also show how to train a machine learning model while keeping the data as well as the trained model private. Then numerical results are shown for experiments on the MNIST dataset. Furthermore, experimental advantages are shown comparing to fixed-point implementations over finite fields.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding

We consider the problem of massive matrix multiplication, which underlies many data analytic applications, in a large-scale distributed system comprising a group of worker nodes. We target the stragglers' delay performance bottleneck, which is due to the unpredictable latency in waiting for slowest nodes (or stragglers) to finish their tasks. We propose a novel coding strategy, named \emph{entangled polynomial code}, for designing the intermediate computations at the worker nodes in order to minimize the recovery threshold (i.e., the number of workers that we need to wait for in order to compute the final output). We demonstrate the optimality of entangled polynomial code in several cases, and show that it provides orderwise improvement over the conventional schemes for straggler mitigation. Furthermore, we characterize the optimal recovery threshold among all linear coding strategies within a factor of $2$ using \emph{bilinear complexity}, by developing an improved version of the entangled polynomial code. In particular, while evaluating bilinear complexity is a well-known challenging problem, we show that optimal recovery threshold for linear coding strategies can be approximated within a factor of $2$ of this fundamental quantity. On the other hand, the improved version of the entangled polynomial code enables further and orderwise reduction in the recovery threshold, compared to its basic version. Finally, we show that the techniques developed in this paper can also be extended to several other problems such as coded convolution and fault-tolerant computing, leading to tight characterizations.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Unified Coding Framework for Distributed Computing with Straggling Servers

We propose a unified coded framework for distributed computing with straggling servers, by introducing a tradeoff between "latency of computation" and "load of communication" for some linear computation tasks. We show that the coded scheme of [1]-[3] that repeats the intermediate computations to create coded multicasting opportunities to reduce communication load, and the coded scheme of [4], [5] that generates redundant intermediate computations to combat against straggling servers can be viewed as special instances of the proposed framework, by considering two extremes of this tradeoff: minimizing either the load of communication or the latency of computation individually. Furthermore, the latency-load tradeoff achieved by the proposed coded framework allows to systematically operate at any point on that tradeoff to perform distributed computing tasks. We also prove an information-theoretic lower bound on the latency-load tradeoff, which is shown to be within a constant multiplicative gap from the achieved tradeoff at the two end points.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Active Learning On Weighted Graphs Using Adaptive And Non-adaptive Approaches

This paper studies graph-based active learning, where the goal is to reconstruct a binary signal defined on the nodes of a weighted graph, by sampling it on a small subset of the nodes. A new sampling algorithm is proposed, which sequentially selects the graph nodes to be sampled, based on an aggressive search for the boundary of the signal over the graph. The algorithm generalizes a recent method for sampling nodes in unweighted graphs. The generalization improves the sampling performance using the information gained from the available graph weights. An analysis of the number of samples required by the proposed algorithm is provided, and the gain over the unweighted method is further demonstrated in simulations. Additionally, the proposed method is compared with an alternative state of-the-art method, which is based on the graph's spectral properties. It is shown that the proposed method significantly outperforms the spectral sampling method, if the signal needs to be predicted with high accuracy. On the other hand, if a higher level of inaccuracy is tolerable, then the spectral method outperforms the proposed aggressive search method. Consequently, we propose a hybrid method, which is shown to combine the advantages of both approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Fundamental Limits of Cache-Aided Interference Management

We consider a system comprising a library of $N$ files (e.g., movies) and a wireless network with $K_T$ transmitters, each equipped with a local cache of size of $M_T$ files, and $K_R$ receivers, each equipped with a local cache of size of $M_R$ files. Each receiver will ask for one of the $N$ files in the library, which needs to be delivered. The objective is to design the cache placement (without prior knowledge of receivers' future requests) and the communication scheme to maximize the throughput of the delivery. In this setting, we show that the sum degrees-of-freedom (sum-DoF) of $\min\left\{\frac{K_T M_T+K_R M_R}{N},K_R\right\}$ is achievable, and this is within a factor of 2 of the optimum, under one-shot linear schemes. This result shows that (i) the one-shot sum-DoF scales linearly with the aggregate cache size in the network (i.e., the cumulative memory available at all nodes), (ii) the transmitters' and receivers' caches contribute equally in the one-shot sum-DoF, and (iii) caching can offer a throughput gain that scales linearly with the size of the network. To prove the result, we propose an achievable scheme that exploits the redundancy of the content at transmitters' caches to cooperatively zero-force some outgoing interference and availability of the unintended content at receivers' caches to cancel (subtract) some of the incoming interference. We develop a particular pattern for cache placement that maximizes the overall gains of cache-aided transmit and receive interference cancellations. For the converse, we present an integer optimization problem which minimizes the number of communication blocks needed to deliver any set of requested files to the receivers. We then provide a lower bound on the value of this optimization problem, hence leading to an upper bound on the linear one-shot sum-DoF of the network, which is within a factor of 2 of the achievable sum-DoF.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Are Generalized Cut-Set Bounds Tight for the Deterministic Interference Channel?

We propose the idea of extended networks, which is constructed by replicating the users in the two-user deterministic interference channel (DIC) and designing the interference structure among them, such that any rate that can be achieved by each user in the original network can also be achieved simultaneously by all replicas of that user in the extended network. We demonstrate that by carefully designing extended networks and applying the generalized cut-set (GCS) bound to them, we can derive a tight converse for the two-user DIC. Furthermore, we generalize our techniques to the three-user DIC, and demonstrate that the proposed approach also results in deriving a tight converse for the three-user DIC in the symmetric case.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Asymptotic Justification of Bandlimited Interpolation of Graph signals for Semi-Supervised Learning

Graph-based methods play an important role in unsupervised and semi-supervised learning tasks by taking into account the underlying geometry of the data set. In this paper, we consider a statistical setting for semi-supervised learning and provide a formal justification of the recently introduced framework of bandlimited interpolation of graph signals. Our analysis leads to the interpretation that, given enough labeled data, this method is very closely related to a constrained low density separation problem as the number of data points tends to infinity. We demonstrate the practical utility of our results through simple experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Blind Index Coding

We introduce the blind index coding (BIC) problem, in which a single sender communicates distinct messages to multiple users over a shared channel. Each user has partial knowledge of each message as side information. However, unlike classic index coding, in BIC, the sender is uncertain of what side information is available to each user. In particular, the sender only knows the amount of bits in each user's side information but not its content. This problem can arise naturally in caching and wireless networks. In order to blindly exploit side information in the BIC problem, we develop a hybrid coding scheme that XORs uncoded bits of a subset of messages with random combinations of bits from other messages. This scheme allows us to strike the right balance between maximizing the transmission rate to each user and minimizing the interference leakage to others. We also develop a general outer bound, which relies on a strong data processing inequality to effectively capture the senders uncertainty about the users' side information. Additionally, we consider the case where communication takes place over a shared wireless medium, modeled by an erasure broadcast channel, and show that surprisingly, combining repetition coding with hybrid coding improves the achievable rate region and outperforms alternative strategies of coping with channel erasure and while blindly exploiting side information.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Coded MapReduce

MapReduce is a commonly used framework for executing data-intensive jobs on distributed server clusters. We introduce a variant implementation of MapReduce, namely "Coded MapReduce", to substantially reduce the inter-server communication load for the shuffling phase of MapReduce, and thus accelerating its execution. The proposed Coded MapReduce exploits the repetitive mapping of data blocks at different servers to create coding opportunities in the shuffling phase to exchange (key,value) pairs among servers much more efficiently. We demonstrate that Coded MapReduce can cut down the total inter-server communication load by a multiplicative factor that grows linearly with the number of servers in the system and it achieves the minimum communication load within a constant multiplicative factor. We also analyze the tradeoff between the "computation load" and the "communication load" of Coded MapReduce.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Rover-to-Orbiter Communication in Mars: Taking Advantage of the Varying Topology

In this paper, we study the communication problem from rovers on Mars' surface to Mars-orbiting satellites. We first justify that, to a good extent, the rover-to-orbiter communication problem can be modelled as communication over a $2 \times 2$ X-channel with the network topology varying over time. For such a fading X-channel where transmitters are only aware of the time-varying topology but not the time-varying channel state (i.e., no CSIT), we propose coding strategies that code across topologies, and develop upper bounds on the sum degrees-of-freedom (DoF) that is shown to be tight under certain pattern of the topology variation. Furthermore we demonstrate that the proposed scheme approximately achieves the ergodic sum-capacity of the network. Using the proposed coding scheme, we numerically evaluate the ergodic rate gain over a time-division-multiple-access (TDMA) scheme for Rayleigh and Rice fading channels. We also numerically demonstrate that with practical orbital parameters, a 9.6% DoF gain, as well as more than 11.6% throughput gain can be achieved for a rover-to-orbiter communication network.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Topological Interference Management with just Retransmission: What are the "Best" Topologies?

We study the problem of interference management in fast fading wireless networks, in which the transmitters are only aware of network topology. We consider a class of retransmission-based schemes, where transmitters in the network are only allowed to resend their symbols in order to assist with the neutralization of interference at the receivers. We introduce a necessary and sufficient condition on the network topology, under which half symmetric degrees-of-freedom (DoF) is achievable through the considered retransmission-based schemes. This corresponds to the "best" topologies since half symmetric DoF is the highest possible value for the symmetric DoF in the presence of interference. We show that when the condition is satisfied, there always exists a set of carefully chosen transmitters in the network, such that by retransmission of their symbols at an appropriate time slot, we can neutralize all the interfering signals at the receivers. Quite surprisingly, we also show that for any given network topology, if we cannot achieve half symmetric DoF by retransmission-based schemes, then there does not exist any linear scheme that can do so. We also consider a practical network scenario that models cell edge users in a heterogeneous network, and show that the characterized condition on the network topology occurs frequently. Furthermore, we numerically evaluate the achievable rates of the DoF-optimal retransmission-based scheme in such network scenario, and show that its throughput gain is not restricted to the asymptotic DoF analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

When Does an Ensemble of Matrices with Randomly Scaled Rows Lose Rank?

We consider the problem of determining rank loss conditions for a concatenation of full-rank matrices, such that each row of the composing matrices is scaled by a random coefficient. This problem has applications in wireless interference management and recommendation systems. We determine necessary and sufficient conditions for the design of each matrix, such that the random ensemble will almost surely lose rank by a certain amount. The result is proved by converting the problem to determining rank loss conditions for the union of some specific matroids, and then using tools from matroid and graph theories to derive the necessary and sufficient conditions. As an application, we discuss how this result can be applied to the problem of topological interference management, and characterize the linear symmetric degrees of freedom for a class of network topologies.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Generalized Cut-Set Bound for Deterministic Multi-Flow Networks and its Applications

We present a new outer bound for the sum capacity of general multi-unicast deterministic networks. Intuitively, this bound can be understood as applying the cut-set bound to concatenated copies of the original network with a special restriction on the allowed transmit signal distributions. We first study applications to finite-field networks, where we obtain a general outer-bound expression in terms of ranks of the transfer matrices. We then show that, even though our outer bound is for deterministic networks, a recent result relating the capacity of AWGN KxKxK networks and the capacity of a deterministic counterpart allows us to establish an outer bound to the DoF of KxKxK wireless networks with general connectivity. This bound is tight in the case of the "adjacent-cell interference" topology, and yields graph-theoretic necessary and sufficient conditions for K DoF to be achievable in general topologies.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Interference Networks with No CSIT: Impact of Topology

We consider partially-connected $K$-user interference networks, where the transmitters have no knowledge about the channel gain values, but they are aware of network topology (or connectivity). We introduce several linear algebraic and graph theoretic concepts to derive new topology-based outer bounds and inner bounds on the symmetric degrees-of-freedom (DoF) of these networks. We evaluate our bounds for two classes of networks to demonstrate their tightness for most networks in these classes, quantify the gain of our inner bounds over benchmark interference management strategies, and illustrate the effect of network topology on these gains.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

ITLinQ: A New Approach for Spectrum Sharing in Device-to-Device Communication Systems

We consider the problem of spectrum sharing in device-to-device communication systems. Inspired by the recent optimality condition for treating interference as noise, we define a new concept of "information-theoretic independent sets" (ITIS), which indicates the sets of links for which simultaneous communication and treating the interference from each other as noise is information-theoretically optimal (to within a constant gap). Based on this concept, we develop a new spectrum sharing mechanism, called "information-theoretic link scheduling" (ITLinQ), which at each time schedules those links that form an ITIS. We first provide a performance guarantee for ITLinQ by characterizing the fraction of the capacity region that it can achieve in a network with sources and destinations located randomly within a fixed area. Furthermore, we demonstrate how ITLinQ can be implemented in a distributed manner, using an initial 2-phase signaling mechanism which provides the required channel state information at all the links. Through numerical analysis, we show that distributed ITLinQ can outperform similar state-of-the-art spectrum sharing mechanisms, such as FlashLinQ, by more than a 100% of sum-rate gain, while keeping the complexity at the same level. Finally, we discuss a variation of the distributed ITLinQ scheme which can also guarantee fairness among the links in the network and numerically evaluate its performance.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Linear Degrees of Freedom of the MIMO X-Channel with Delayed CSIT

We study the degrees of freedom (DoF) of the multiple-input multiple-output X-channel (MIMO XC) with delayed channel state information at the transmitters (delayed CSIT), assuming linear coding strategies at the transmitters. We present two results: 1) the linear sum DoF for MIMO XC with general antenna configurations, and 2) the linear DoF region for MIMO XC with symmetric antennas. The converse for each result is based on developing a novel rank-ratio inequality that characterizes the maximum ratio between the dimensions of received linear subspaces at the two multiple-antenna receivers. The achievability of the linear sum DoF is based on a three-phase strategy, in which during the first two phases only the transmitter with fewer antennas exploits delayed CSIT in order to minimize the dimension of its signal at the unintended receiver. During Phase 3, both transmitters use delayed CSIT to send linear combinations of past transmissions such that each receiver receives a superposition of desired message data and known interference, thus simultaneously serving both receivers. We also derive other linear DoF outer bounds for the MIMO XC that, in addition to the outer bounds from the sum DoF converse and the proposed transmission strategy, allow us to characterize the linear DoF region for symmetric antenna configurations.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Linear Degrees of Freedom of the X-Channel with Delayed CSIT

We establish the degrees of freedom of the two-user X-channel with delayed channel knowledge at transmitters (i.e., delayed CSIT), assuming linear coding strategies at the transmitters. We derive a new upper bound and characterize the linear degrees of freedom of this network to be 6/5. The converse builds upon our development of a general lemma that shows that, if two distributed transmitters employ linear strategies, the ratio of the dimensions of received linear subspaces at the two receivers cannot exceed 3/2, due to delayed CSIT. As a byproduct, we also apply this general lemma to the three-user interference channel with delayed CSIT, thereby deriving a new upper bound of 9/7 on its linear degrees of freedom. This is the first bound that captures the impact of delayed CSIT on the degrees of freedom of this network, under the assumption of linear encoding strategies.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Sampling Large Data on Graphs

We consider the problem of sampling from data defined on the nodes of a weighted graph, where the edge weights capture the data correlation structure. As shown recently, using spectral graph theory one can define a cut-off frequency for the bandlimited graph signals that can be reconstructed from a given set of samples (i.e., graph nodes). In this work, we show how this cut-off frequency can be computed exactly. Using this characterization, we provide efficient algorithms for finding the subset of nodes of a given size with the largest cut-off frequency and for finding the smallest subset of nodes with a given cut-off frequency. In addition, we study the performance of random uniform sampling when compared to the centralized optimal sampling provided by the proposed algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Approximate Sum-Capacity of the Y-channel

A network where three users want to establish multiple unicasts between each other via a relay is considered. This network is called the Y-channel and resembles an elemental ingredient of future wireless networks. The sum-capacity of this network is studied. A characterization of the sum-capacity within an additive gap of 2 bits, and a multiplicative gap of 4, for all values of channel gains and transmit powers is obtained. Contrary to similar setups where the cut-set bounds can be achieved within a constant gap, they can not be achieved in our case, where they are dominated by our new genie-aided bounds. Furthermore, it is shown that a time-sharing strategy, in which at each time two users exchange information using coding strategies of the bi-directional relay channel, achieves the upper bounds to within a constant gap. This result is further extended to the K-user case, where it is shown that the same scheme achieves the sum-capacity within 2log(K-1) bits.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Communication Through Collisions: Opportunistic Utilization of Past Receptions

When several wireless users are sharing the spectrum, packet collision is a simple, yet widely used model for interference. Under this model, when transmitters cause interference at any of the receivers, their collided packets are discarded and need to be retransmitted. However, in reality, that receiver can still store its analog received signal and utilize it for decoding the packets in the future (for example, by successive interference cancellation techniques). In this work, we propose a physical layer model for wireless packet networks that allows for such flexibility at the receivers. We assume that the transmitters will be aware of the state of the channel (i.e. when and where collisions occur, or an unintended receiver overhears the signal) with some delay, and propose several coding opportunities that can be utilized by the transmitters to exploit the available signal at the receivers for interference management (as opposed to discarding them). We analyze the achievable throughput of our strategy in a canonical interference channel with two transmitter-receiver pairs, and demonstrate the gain over conventional schemes. By deriving an outer-bound, we also prove the optimality of our scheme for the corresponding model.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Degrees of Freedom of Two-Hop Wireless Networks: "Everyone Gets the Entire Cake"

We show that fully connected two-hop wireless networks with K sources, K relays and K destinations have K degrees of freedom both in the case of time-varying channel coefficients and in the case of constant channel coefficients (in which case the result holds for almost all values of constant channel coefficients). Our main contribution is a new achievability scheme which we call Aligned Network Diagonalization. This scheme allows the data streams transmitted by the sources to undergo a diagonal linear transformation from the sources to the destinations, thus being received free of interference by their intended destination. In addition, we extend our scheme to multi-hop networks with fully connected hops, and multi-hop networks with MIMO nodes, for which the degrees of freedom are also fully characterized.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Layered Interference Networks with Delayed CSI: DoF Scaling with Distributed Transmitters

The layered interference network is investigated with delayed channel state information (CSI) at all nodes. It is demonstrated how multi-hopping can be utilized to increase the achievable degrees of freedom (DoF). In particular, a multi-phase transmission scheme is proposed for the $K$-user $2K$-hop interference network in order to systematically exploit the layered structure of the network and delayed CSI to achieve DoF values that scale with $K$. This result provides the first example of a network with distributed transmitters and delayed CSI whose DoF scales with the number of users.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Network Compression: Worst-Case Analysis

We study the problem of communicating a distributed correlated memoryless source over a memoryless network, from source nodes to destination nodes, under quadratic distortion constraints. We establish the following two complementary results: (a) for an arbitrary memoryless network, among all distributed memoryless sources of a given correlation, Gaussian sources are least compressible, that is, they admit the smallest set of achievable distortion tuples, and (b) for any memoryless source to be communicated over a memoryless additive-noise network, among all noise processes of a given correlation, Gaussian noise admits the smallest achievable set of distortion tuples. We establish these results constructively by showing how schemes for the corresponding Gaussian problems can be applied to achieve similar performance for (source or noise) distributions that are not necessarily Gaussian but have the same covariance.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Min-Cut Algorithms for Half-Duplex Relay Networks

Computing the cut-set bound in half-duplex relay networks is a challenging optimization problem, since it requires finding the cut-set optimal half-duplex schedule. This subproblem in general involves an exponential number of variables, since the number of ways to assign each node to either transmitter or receiver mode is exponential in the number of nodes. We present a general technique that takes advantage of specific structures in the topology of a given network and allows us to reduce the complexity of computing the half-duplex schedule that maximizes the cut-set bound (with i.i.d. input distribution). In certain classes of network topologies, our approach yields polynomial time algorithms. We use simulations to show running time improvements over alternative methods and compare the performance of various half-duplex scheduling approaches in different SNR regimes.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the Optimality of Treating Interference as Noise

It is shown that in the K-user interference channel, if for each user the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all values in dB scale), then the simple scheme of using point to point Gaussian codebooks with appropriate power levels at each transmitter and treating interference as noise at every receiver (in short, TIN scheme) achieves all points in the capacity region to within a constant gap. The generalized degrees of freedom (GDoF) region under this condition is a polyhedron, which is shown to be fully achieved by the same scheme, without the need for time-sharing. The results are proved by first deriving a polyhedral relaxation of the GDoF region achieved by TIN, then providing a dual characterization of this polyhedral region via the use of potential functions, and finally proving the optimality of this region in the desired regime.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Timely Throughput of Heterogeneous Wireless Networks: Fundamental Limits and Algorithms

The proliferation of different wireless access technologies, together with the growing number of multi-radio wireless devices suggest that the opportunistic utilization of multiple connections at the users can be an effective solution to the phenomenal growth of traffic demand in wireless networks. In this paper we consider the downlink of a wireless network with $N$ Access Points (AP's) and $M$ clients, where each client is connected to several out-of-band AP's, and requests delay-sensitive traffic (e.g., real-time video). We adopt the framework of Hou, Borkar, and Kumar, and study the maximum total timely throughput of the network, denoted by $C_{T^3}$, which is the maximum average number of packets delivered successfully before their deadline. Solving this problem is challenging since even the number of different ways of assigning packets to the AP's is $N^M$. We overcome the challenge by proposing a deterministic relaxation of the problem, which converts the problem to a network with deterministic delays in each link. We show that the additive gap between the capacity of the relaxed problem, denoted by $C_{det}$, and $C_{T^3}$ is bounded by $2\sqrt{N(C_{det}+N/4)}$, which is asymptotically negligible compared to $C_{det}$, when the network is operating at high-throughput regime. In addition, our numerical results show that the actual gap between $C_{T^3}$ and $C_{det}$ is in most cases much less than the worst-case gap proven analytically. Moreover, using LP rounding methods we prove that the relaxed problem can be approximated within additive gap of $N$. We extend the analytical results to the case of time-varying channel states, real-time traffic, prioritized traffic, and optimal online policies. Finally, we generalize the model for deterministic relaxation to consider fading, rate adaptation, and multiple simultaneous transmissions.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Two-Hop Interference Channels: Impact of Linear Schemes

We consider the two-hop interference channel (IC), which consists of two source-destination pairs communicating with each other via two relays. We analyze the degrees of freedom (DoF) of this network when the relays are restricted to perform linear schemes, and the channel gains are constant (i.e., slow fading). We show that, somewhat surprisingly, by using vector-linear strategies at the relays, it is possible to achieve 4/3 sum-DoF when the channel gains are real. The key achievability idea is to alternate relaying coefficients across time, to create different end-to-end interference structures (or topologies) at different times. Although each of these topologies has only 1 sum-DoF, we manage to achieve 4/3 by coding across them. Furthermore, we develop a novel outer bound that matches our achievability, hence characterizing the sum-DoF of two-hop interference channels with linear schemes. As for the case of complex channel gains, we characterize the sum-DoF with linear schemes to be 5/3. We also generalize the results to the multi-antenna setting, characterizing the sum-DoF with linear schemes to be 2M-1/3 (for complex channel gains), where M is the number of antennas at each node.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Two-Hop Interference Channels: Impact of Linear Time-Varying Schemes

We consider the two-hop interference channel (IC) with constant real channel coefficients, which consists of two source-destination pairs, separated by two relays. We analyze the achievable degrees of freedom (DoF) of such network when relays are restricted to perform scalar amplify-forward (AF) operations, with possibly time-varying coefficients. We show that, somewhat surprisingly, by providing the flexibility of choosing time-varying AF coefficients at the relays, it is possible to achieve 4/3 sum-DoF. We also develop a novel outer bound that matches our achievability, hence characterizing the sum-DoF of two-hop interference channels with time-varying AF relaying strategies.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Worst-Case Additive Noise in Wireless Networks

A classical result in Information Theory states that the Gaussian noise is the worst-case additive noise in point-to-point channels, meaning that, for a fixed noise variance, the Gaussian noise minimizes the capacity of an additive noise channel. In this paper, we significantly generalize this result and show that the Gaussian noise is also the worst-case additive noise in wireless networks with additive noises that are independent from the transmit signals. More specifically, we show that, if we fix the noise variance at each node, then the capacity region with Gaussian noises is a subset of the capacity region with any other set of noise distributions. We prove this result by showing that a coding scheme that achieves a given set of rates on a network with Gaussian additive noises can be used to construct a coding scheme that achieves the same set of rates on a network that has the same topology and traffic demands, but with non-Gaussian additive noises.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Diamond Networks with Bursty Traffic: Bounds on the Minimum Energy-Per-Bit

When data traffic in a wireless network is bursty, small amounts of data sporadically become available for transmission, at times that are unknown at the receivers, and an extra amount of energy must be spent at the transmitters to overcome this lack of synchronization between the network nodes. In practice, pre-defined header sequences are used with the purpose of synchronizing the different network nodes. However, in networks where relays must be used for communication, the overhead required for synchronizing the entire network may be very significant. In this work, we study the fundamental limits of energy-efficient communication in an asynchronous diamond network with two relays. We formalize the notion of relay synchronization by saying that a relay is synchronized if the conditional entropy of the arrival time of the source message given the received signals at the relay is small. We show that the minimum energy-per-bit for bursty traffic in diamond networks is achieved with a coding scheme where each relay is either synchronized or not used at all. A consequence of this result is the derivation of a lower bound to the minimum energy-per-bit for bursty communication in diamond networks. This bound allows us to show that schemes that perform the tasks of synchronization and communication separately (i.e., with synchronization signals preceding the communication block) can achieve the minimum energy-per-bit to within a constant fraction that ranges from 2 in the synchronous case to 1 in the highly asynchronous regime.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Two-Unicast Wireless Networks: Characterizing the Degrees-of-Freedom

We consider two-source two-destination (i.e., two-unicast) multi-hop wireless networks that have a layered structure with arbitrary connectivity. We show that, if the channel gains are chosen independently according to continuous distributions, then, with probability 1, two-unicast layered Gaussian networks can only have 1, 3/2 or 2 sum degrees-of-freedom (unless both source-destination pairs are disconnected, in which case no degrees-of-freedom can be achieved). We provide sufficient and necessary conditions for each case based on network connectivity and a new notion of source-destination paths with manageable interference. Our achievability scheme is based on forwarding the received signals at all nodes, except for a small fraction of them in at most two key layers. Hence, we effectively create a "condensed network" that has at most four layers (including the sources layer and the destinations layer). We design the transmission strategies based on the structure of this condensed network. The converse results are obtained by developing information-theoretic inequalities that capture the structures of the network connectivity. Finally, we extend this result and characterize the full degrees-of-freedom region of two-unicast layered wireless networks.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Divide-and-conquer: Approaching the capacity of the two-pair bidirectional Gaussian relay network

The capacity region of multi-pair bidirectional relay networks, in which a relay node facilitates the communication between multiple pairs of users, is studied. This problem is first examined in the context of the linear shift deterministic channel model. The capacity region of this network when the relay is operating at either full-duplex mode or half-duplex mode for arbitrary number of pairs is characterized. It is shown that the cut-set upper-bound is tight and the capacity region is achieved by a so called divide-and-conquer relaying strategy. The insights gained from the deterministic network are then used for the Gaussian bidirectional relay network. The strategy in the deterministic channel translates to a specific superposition of lattice codes and random Gaussian codes at the source nodes and successive interference cancelation at the receiving nodes for the Gaussian network. The achievable rate of this scheme with two pairs is analyzed and it is shown that for all channel gains it achieves to within 3 bits/sec/Hz per user of the cut-set upper-bound. Hence, the capacity region of the two-pair bidirectional Gaussian relay network to within 3 bits/sec/Hz per user is characterized.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Improving the Thresholds of Sparse Recovery: An Analysis of a Two-Step Reweighted Basis Pursuit Algorithm

It is well known that $\ell_1$ minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. In fact, exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from i.i.d. Gaussian measurements, have been computed and are referred to as "weak thresholds" \cite{D}. In this paper, we introduce a reweighted $\ell_1$ recovery algorithm composed of two steps: a standard $\ell_1$ minimization step to identify a set of entries where the signal is likely to reside, and a weighted $\ell_1$ minimization step where entries outside this set are penalized. For signals where the non-sparse component entries are independent and identically drawn from certain classes of distributions, (including most well known continuous distributions), we prove a \emph{strict} improvement in the weak recovery threshold. Our analysis suggests that the level of improvement in the weak threshold depends on the behavior of the distribution at the origin. Numerical simulations verify the distribution dependence of the threshold improvement very well, and suggest that in the case of i.i.d. Gaussian nonzero entries, the improvement can be quite impressive---over 20% in the example we consider.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Sum-Capacity with Successive Decoding in Interference Channels

In this paper, we investigate the sum-capacity of the two-user Gaussian interference channel with Gaussian superposition coding and successive decoding. We first examine an approximate deterministic formulation of the problem, and introduce the complementarity conditions that capture the use of Gaussian coding and successive decoding. In the deterministic channel problem, we find the constrained sum-capacity and its achievable schemes with the minimum number of messages, first in symmetric channels, and then in general asymmetric channels. We show that the constrained sum-capacity oscillates as a function of the cross link gain parameters between the information theoretic sum-capacity and the sum-capacity with interference treated as noise. Furthermore, we show that if the number of messages of either of the two users is fewer than the minimum number required to achieve the constrained sum-capacity, the maximum achievable sum-rate drops to that with interference treated as noise. We provide two algorithms (a simple one and a finer one) to translate the optimal schemes in the deterministic channel model to the Gaussian channel model. We also derive two upper bounds on the sum-capacity of the Gaussian Han-Kobayashi schemes, which automatically upper bound the sum-capacity using successive decoding of Gaussian codewords. Numerical evaluations show that, similar to the deterministic channel results, the constrained sum-capacity in the Gaussian channels oscillates between the sum-capacity with Han-Kobayashi schemes and that with single message schemes.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Analyzing Weighted $\ell_1$ Minimization for Sparse Recovery with Nonuniform Sparse Models\footnote{The results of this paper were presented in part at the International Symposium on Information Theory, ISIT 2009}

In this paper we introduce a nonuniform sparsity model and analyze the performance of an optimized weighted $\ell_1$ minimization over that sparsity model. In particular, we focus on a model where the entries of the unknown vector fall into two sets, with entries of each set having a specific probability of being nonzero. We propose a weighted $\ell_1$ minimization recovery algorithm and analyze its performance using a Grassmann angle approach. We compute explicitly the relationship between the system parameters-the weights, the number of measurements, the size of the two sets, the probabilities of being nonzero- so that when i.i.d. random Gaussian measurement matrices are used, the weighted $\ell_1$ minimization recovers a randomly selected signal drawn from the considered sparsity model with overwhelming probability as the problem dimension increases. This allows us to compute the optimal weights. We demonstrate through rigorous analysis and simulations that for the case when the support of the signal can be divided into two different subclasses with unequal sparsity fractions, the optimal weighted $\ell_1$ minimization outperforms the regular $\ell_1$ minimization substantially. We also generalize the results to an arbitrary number of classes.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On Achieving Local View Capacity Via Maximal Independent Graph Scheduling

"If we know more, we can achieve more." This adage also applies to communication networks, where more information about the network state translates into higher sumrates. In this paper, we formalize this increase of sum-rate with increased knowledge of the network state. The knowledge of network state is measured in terms of the number of hops, h, of information available to each transmitter and is labeled as h-local view. To understand how much capacity is lost due to limited information, we propose to use the metric of normalized sum-capacity, which is the h-local view sum-capacity divided by global-view sum capacity. For the cases of one and two-local view, we characterize the normalized sum-capacity for many classes of deterministic and Gaussian interference networks. In many cases, a scheduling scheme called maximal independent graph scheduling is shown to achieve normalized sum-capacity. We also show that its generalization for 1-local view, labeled coded set scheduling, achieves normalized sum-capacity in some cases where its uncoded counterpart fails to do so.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Two-User Deterministic Interference Channel with Rate-Limited Feedback

In this paper we study the effect of rate-limited feedback on the sum-rate capacity of the deterministic interference channel. We characterize the sum-rate capacity of this channel in the symmetric case and show that having feedback links can increase the sum-rate capacity by at most the rate of the available feedback. Our proof includes a novel upper-bound on the sum-rate capacity and a set of new achievability strategies.

0 citations0 reviewsNo code linkedOpen access