BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Urs Niesen

Urs Niesen contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Information Theorymath.ITNetworking and Internet Architecturemath.OC

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
12works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

12 published item(s)

preprint2015arXiv

Energy-Efficient Communication in the Presence of Synchronization Errors

Communication systems are traditionally designed to have tight transmitter-receiver synchronization. This requirement has negligible overhead in the high-SNR regime. However, in many applications, such as wireless sensor networks, communication needs to happen primarily in the energy-efficient regime of low SNR, where requiring tight synchronization can be highly suboptimal. In this paper, we model the noisy channel with synchronization errors as an insertion/deletion/substitution channel. For this channel, we propose a new communication scheme that requires only loose transmitter-receiver synchronization. We show that the proposed scheme is asymptotically optimal for the Gaussian channel with synchronization errors in terms of energy efficiency as measured by the rate per unit energy. In the process, we also establish that the lack of synchronization causes negligible loss in energy efficiency. We further show that, for a general discrete memoryless channel with synchronization errors and a general input cost function admitting a zero-cost symbol, the rate per unit cost achieved by the proposed scheme is within a factor two of the information-theoretic optimum.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Scaling of Interference Alignment Under Delay and Power Constraints

Future wireless standards such as 5G envision dense wireless networks with large number of simultaneously connected devices. In this context, interference management becomes critical in achieving high spectral efficiency. Orthogonal signaling, which limits the number of users utilizing the resource simultaneously, gives a sum-rate that remains constant with increasing number of users. An alternative approach called interference alignment promises a throughput that scales linearly with the number of users. However, this approach requires very high SNR or long time duration for sufficient channel variation, and therefore may not be feasible in real wireless systems. We explore ways to manage interference in large networks with delay and power constraints. Specifically, we devise an interference phase alignment strategy that combines precoding and scheduling without using power control to exploit the diversity inherent in a system with large number of users. We show that this scheme achieves a sum-rate that scales almost logarithmically with the number of users. We also show that no scheme using single symbol phase alignment, which is asymmetric complex signaling restricted to a single complex symbol, can achieve better than logarithmic scaling of the sum-rate.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Decentralized Coded Caching Attains Order-Optimal Memory-Rate Tradeoff

Replicating or caching popular content in memories distributed across the network is a technique to reduce peak network loads. Conventionally, the main performance gain of this caching was thought to result from making part of the requested data available closer to end users. Instead, we recently showed that a much more significant gain can be achieved by using caches to create coded-multicasting opportunities, even for users with different demands, through coding across data streams. These coded-multicasting opportunities are enabled by careful content overlap at the various caches in the network, created by a central coordinating server. In many scenarios, such a central coordinating server may not be available, raising the question if this multicasting gain can still be achieved in a more decentralized setting. In this paper, we propose an efficient caching scheme, in which the content placement is performed in a decentralized manner. In other words, no coordination is required for the content placement. Despite this lack of coordination, the proposed scheme is nevertheless able to create coded-multicasting opportunities and achieves a rate close to the optimal centralized scheme.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Fundamental Limits of Caching

Caching is a technique to reduce peak traffic rates by prefetching popular content into memories at the end users. Conventionally, these memories are used to deliver requested content in part from a locally cached copy rather than through the network. The gain offered by this approach, which we term local caching gain, depends on the local cache size (i.e, the memory available at each individual user). In this paper, we introduce and exploit a second, global, caching gain not utilized by conventional caching schemes. This gain depends on the aggregate global cache size (i.e., the cumulative memory available at all users), even though there is no cooperation among the users. To evaluate and isolate these two gains, we introduce an information-theoretic formulation of the caching problem focusing on its basic structure. For this setting, we propose a novel coded caching scheme that exploits both local and global caching gains, leading to a multiplicative improvement in the peak rate compared to previously known schemes. In particular, the improvement can be on the order of the number of users in the network. Moreover, we argue that the performance of the proposed scheme is within a constant factor of the information-theoretic optimum for all values of the problem parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Computation Alignment: Capacity Approximation without Noise Accumulation

Consider several source nodes communicating across a wireless network to a destination node with the help of several layers of relay nodes. Recent work by Avestimehr et al. has approximated the capacity of this network up to an additive gap. The communication scheme achieving this capacity approximation is based on compress-and-forward, resulting in noise accumulation as the messages traverse the network. As a consequence, the approximation gap increases linearly with the network depth. This paper develops a computation alignment strategy that can approach the capacity of a class of layered, time-varying wireless relay networks up to an approximation gap that is independent of the network depth. This strategy is based on the compute-and-forward framework, which enables relays to decode deterministic functions of the transmitted messages. Alone, compute-and-forward is insufficient to approach the capacity as it incurs a penalty for approximating the wireless channel with complex-valued coefficients by a channel with integer coefficients. Here, this penalty is circumvented by carefully matching channel realizations across time slots to create integer-valued effective channels that are well-suited to compute-and-forward. Unlike prior constant gap results, the approximation gap obtained in this paper also depends closely on the fading statistics, which are assumed to be i.i.d. Rayleigh.

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 Alignment: From Degrees-of-Freedom to Constant-Gap Capacity Approximations

Interference alignment is a key technique for communication scenarios with multiple interfering links. In several such scenarios, interference alignment was used to characterize the degrees-of-freedom of the channel. However, these degrees-of-freedom capacity approximations are often too weak to make accurate predictions about the behavior of channel capacity at finite signal-to-noise ratios (SNRs). The aim of this paper is to significantly strengthen these results by showing that interference alignment can be used to characterize capacity to within a constant gap. We focus on real, time-invariant, frequency-flat X-channels. The only known solutions achieving the degrees-of-freedom of this channel are either based on real interference alignment or on layer-selection schemes. Neither of these solutions seems sufficient for a constant-gap capacity approximation. In this paper, we propose a new communication scheme and show that it achieves the capacity of the Gaussian X-channel to within a constant gap. To aid in this process, we develop a novel deterministic channel model. This deterministic model depends on the 0.5log(SNR) most-significant bits of the channel coefficients rather than only the single most-significant bit used in conventional deterministic models. The proposed deterministic model admits a wider range of achievable schemes that can be translated to the Gaussian channel. For this deterministic model, we find an approximately optimal communication scheme. We then translate this scheme for the deterministic channel to the original Gaussian X-channel and show that it achieves capacity to within a constant gap. This is the first constant-gap result for a general, fully-connected network requiring interference alignment.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Online Coded Caching

We consider a basic content distribution scenario consisting of a single origin server connected through a shared bottleneck link to a number of users each equipped with a cache of finite memory. The users issue a sequence of content requests from a set of popular files, and the goal is to operate the caches as well as the server such that these requests are satisfied with the minimum number of bits sent over the shared link. Assuming a basic Markov model for renewing the set of popular files, we characterize approximately the optimal long-term average rate of the shared link. We further prove that the optimal online scheme has approximately the same performance as the optimal offline scheme, in which the cache contents can be updated based on the entire set of popular files before each new request. To support these theoretical results, we propose an online coded caching scheme termed coded least-recently sent (LRS) and simulate it for a demand time series derived from the dataset made available by Netflix for the Netflix Prize. For this time series, we show that the proposed coded LRS algorithm significantly outperforms the popular least-recently used (LRU) caching algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Degrees of Freedom of Compute-and-Forward

We analyze the asymptotic behavior of compute-and-forward relay networks in the regime of high signal-to-noise ratios. We consider a section of such a network consisting of K transmitters and K relays. The aim of the relays is to reliably decode an invertible function of the messages sent by the transmitters. An upper bound on the capacity of this system can be obtained by allowing full cooperation among the transmitters and among the relays, transforming the network into a K times K multiple-input multiple-output (MIMO) channel. The number of degrees of freedom of compute-and-forward is hence at most K. In this paper, we analyze the degrees of freedom achieved by the lattice coding implementation of compute-and-forward proposed recently by Nazer and Gastpar. We show that this lattice implementation achieves at most 2/(1+1/K)\leq 2 degrees of freedom, thus exhibiting a very different asymptotic behavior than the MIMO upper bound. This raises the question if this gap of the lattice implementation to the MIMO upper bound is inherent to compute-and-forward in general. We answer this question in the negative by proposing a novel compute-and-forward implementation achieving K degrees of freedom.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Caching in Wireless Networks

We consider the problem of delivering content cached in a wireless network of n nodes randomly located on a square of area n. The network performance is described by the n2^n-dimensional caching capacity region of the wireless network. We provide an inner bound on this caching capacity region, and, in the high path-loss regime, a matching (in the scaling sense) outer bound. For large path-loss exponent, this provides an information-theoretic scaling characterization of the entire caching capacity region. The proposed communication scheme achieving the inner bound shows that the problems of cache selection and channel coding can be solved separately without loss of order-optimality. On the other hand, our results show that the common architecture of nearest-neighbor cache selection can be arbitrarily bad, implying that cache selection and load balancing need to be performed jointly.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Interference Alignment in Dense Wireless Networks

We consider arbitrary dense wireless networks, in which $n$ nodes are placed in an arbitrary (deterministic) manner on a square region of unit area and communicate with each other over Gaussian fading channels. We provide inner and outer bounds for the $n\times n$-dimensional unicast and the $n\times 2^n$-dimensional multicast capacity regions of such a wireless network. These inner and outer bounds differ only by a factor $O(\log(n))$, yielding a fairly tight scaling characterization of the entire regions. The communication schemes achieving the inner bounds use interference alignment as a central technique and are, at least conceptually, surprisingly simple.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Adaptive Alternating Minimization Algorithms

The classical alternating minimization (or projection) algorithm has been successful in the context of solving optimization problems over two variables. The iterative nature and simplicity of the algorithm has led to its application to many areas such as signal processing, information theory, control, and finance. A general set of sufficient conditions for the convergence and correctness of the algorithm is quite well-known when the underlying problem parameters are fixed. In many practical situations, however, the underlying problem parameters are changing over time, and the use of an adaptive algorithm is more appropriate. In this paper, we study such an adaptive version of the alternating minimization algorithm. As a main result of this paper, we provide a general set of sufficient conditions for the convergence and correctness of the adaptive algorithm. Perhaps surprisingly, these conditions seem to be the minimal ones one would expect in such an adaptive setting. We present applications of our results to adaptive decomposition of mixtures, adaptive log-optimal portfolio selection, and adaptive filter design.

0 citations0 reviewsNo code linkedOpen access