Bandlimited Signal Reconstruction With Samples Obtained at Unknown but Statistically Distributed Locations -- Animesh Kumar

In spatial sampling applications, the knowledge of sensor's location requires extra resources (GPS) or energy (in the form of localization algorithms). In this talk, an alternate sampling paradigm will be introduced, where the knowledge of sensor-locations is _not known_. It will be assumed that sensors are deployed according to a statistical distribution, and then with the knowledge of recorded values the underlying spatial field will be reconstructed. Spatially bandlimited fields will be considered and reconstruction performance guarantees (such as the mean-squared error) will be established.

Resources: [Slides]

A Convex Analytic Approach to Stochastic Control and Finite Block-length Joint Source-Channel Coding -- Ankur Kulkarni

The classical textbook treatment of optimal stochastic control relies on the `classical' information structure, wherein the controllers are co-located, have perfect and infinite recall and have the same information about the state. A departure from this information structure has devastating consequences, making even the simplest problems inordinately hard to solve.
On the other side of the fence, communication and information theorists have routinely coped with the lack classical information structure -- indeed the non-colocation of sender and the receiver is the raison d'etre of communication theory. Their approach to nonclassicality can be understood as being via the exploitation of the statistical properties of random variables. The crux of this approach is the `long rope' provided by arbitrarily large block lengths. This leads to tractable and convex characterizations for various notions and sharp answers for what is doable and what is not.
The luxury of variable blocks is not available in stochastic control -- the control problem is defined for a fixed and finite block length. The state of the art in stochastic control with nonclassical information structure, with a few exceptions, has largely been accomplished by embedding the control problem into a communication problem with large block lengths and then leveraging the aforementioned sharp results. This leads to bounds that are tight in some exceptional cases, but in general quite loose.
This talk will argue that at the finite block length, the aspect of probability that is perhaps most relevant is its convex analytic geometry. And that the state of the art in stochastic control can be recovered as a special case of a more general optimization-based paradigm that appeals to convex analytic properties of distributions. This leads to significant generalizations of classical results in control and new converses for joint source channel coding with finite block lengths.

Aap Qataar Mein Hain -- Jayakrishnan Nair

The main problem in call center staffing is to determine the optimal number of agents required, taking both QoS and staffing costs into consideration. It is well known that user abandonment behavior plays a key role in determining the optimal staffing level. However, how to model this abandonment behavior is not yet well understood. We show that two `standard' techniques of modeling abandonment can lead to very different optimal staffing regimes.

Resources: [Slides]

Distributed Asynchronous Non-convex optimization via ADMM -- Ketan Rajawat

We consider the problem of distributed optimization of a sum of locally observable non-convex functions. The optimization is performed over a network, where each node knows a local function that depends only on a subset of variables. Alternating directions method of multipliers (ADMM) is utilized to obtain a stationary point of the problem in a distributed fashion. The algorithm is asynchronous, and allows some of the updates to be old. As an example, an asynchronous and distributed solution to the cooperative localization problem is developed.

Adaptive CSMA under the SINR Model: Fast Convergence through the Bethe Approximation -- Krishna Jagannathan

In this work, we propose an adaptive CSMA based scheduling algorithm for a single-hop wireless network under a realistic SINR (signal-to-interference-plus-noise ratio) model for the interference. Recent work has shown that adaptive CSMA based algorithms can achieve throughput optimality, by sampling feasible schedules from a product form Gibbs distribution. In order to support a desired service rate vector using adaptive CSMA, certain parameters of the Gibbs distribution, called fugacities, must be estimated. Unfortunately, estimating the optimal fugacities for a desired service rate vector is an NP-hard problem. Further, the existing adaptive CSMA algorithms use a stochastic gradient descent based method, which usually entails an impractically slow convergence to the optimal fugacities. We propose an efficient and scalable approximation based on a local Gibbs optimization technique to estimate the fugacities corresponding to the desired service rates. We show that the proposed local Gibbs optimization corresponds exactly to performing the well-known Bethe approximation to the global Gibbs optimization. Numerical results indicate that the proposed method achieves an almost instantaneous convergence to near-optimal fugacities, and often outperforms the convergence rate of the stochastic gradient descent by a few orders of magnitude. Notably, the proposed method is also quite robust to gradual changes in the desired service rates, as well as to changes in the topology.

Resources: [Slides]

An Information Processing View of Reaction Networks -- Manoj Gopalkrishnan

A living cell and a piece of clay are both bags of molecules, yet one displays vastly more sophisticated behavior than the other. How? One answer is that the ballet of molecular interactions within cells leads to the emergence of an intricate network of reactions which behaves like a "biochemical circuit," processing information about the cellular environment. In recent times, the study of these reaction networks has been an exciting bridge between Mathematics and Biology. The mathematical actors involved are Markov chains, ordinary differential equations, Lyapunov functions, relative entropy, Poisson distributions, etc., all of which are very familiar to the communications and networks community. I will give an introduction to this area from an information processing point of view.

Resources: [Slides]

Coded Caching: The Dichotomy of the One and the Many -- Nikhil Karamchandani

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. 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: a single user per cache versus a large number of users per cache. We demonstrate a dichotomy in the order-optimal strategies for these two extreme cases. In the multi-user case, sharing memory among the various levels, in proportion to their popularity, is order-optimal. On the other hand, for the single-user case, clustering all levels with popularity higher than a threshold into a single level and allocating all the memory to this `super-level' is the order-optimal scheme. In proving these results, we develop new information-theoretic lower bounds for the problem.

Resources: [Slides]

Equivalence of 2D Color Codes to Surface Codes* -- Pradeep Sarvepalli

Surface codes and color codes are among the most important quantum codes for achieving fault-tolerance in quantum computers. Both can be viewed as quantum LDPC codes, but there are significant differences in their construction and properties which might lead one to believe that they are inequivalent. However, Bombin, Duclos-Cianci, and Poulin showed that every local translationally invariant 2D topological stabilizer code, including color codes, is locally equivalent to a finite number of copies of a surface code. Using an approach based on chain complexes and hypergraphs, Delfosse relaxed the constraint on translation invariance and mapped a 2D color code onto three surface codes. In this talk, we propose an alternate map using a substantially simpler framework based on linear algebra. We show that any 2D color code can be mapped onto exactly two copies of a related surface code. The surface code in our map is induced by the color code and easily derived from the color code. This has immediate application for decoding of color codes and additionally leads to lower decoding complexity.
*Joint work with Arjun Bhagoji.
Reference: http://arxiv.org/abs/1503.03009

Asymptotics of the SIR Distribution in General Cellular Networks -- Radha Krishna Ganti

It has recently been observed that the SIR distributions of a variety of cellular network models and transmission techniques look very similar in shape. We try to explain the similar shape of the SIR distributions generated by various point processes using the asymptotics of the CDF at zero and infinity. It is shown that the gain at 0 is determined by the so-called mean interference-to-signal ratio (MISR) between the PPP and the network model under consideration, while the gain at infinity is determined by the expected fading-to-interference ratio (EFIR). The analysis is based on mapped point process, the so-called relative distance process, which is a one-dimensional point process on [0, 1] and fully determines the SIR.

Resources: [Slides]

Amplify-and-Forward in Wireless Relay Networks -- Samar Agnihotri

The information-theoretic capacity of general relay channel has been an open problem for more than the last forty years, since first posed by van der Meulen in his seminal 1971 paper. Since then numerous achievability schemes have been proposed. However, none of these schemes consistently provides tight characterization of the capacity or outperforms all other schemes in all scenarios. Further, the computational complexity of the most of such schemes render their end-to-end performance characterization intractable. Toward our pursuit of constructing low-complexity schemes to tightly characterize the capacity of general relay channel, we analyze the performance of one of the simplest relaying schemes: amplify-and-forward in Gaussian relay networks. In this talk, we discuss some of the major results and insights that we obtained from this work and which we hope to be useful for addressing the general problem.

On Content Delivery via Heterogeneous Devices -- Sharayu Moharir

Modern Content Delivery Networks (CDNs) deliver content to users via a multitude of devices like smartphones, tablets, etc., and therefore, have to deliver each content in multiple formats. We focus on CDNs consisting of one or more back-end servers, with large storage capacity, assisted by front-end servers located near the users. These front-end servers have limited storage/service capabilites, and have access to computational resources in the form of transcoders, which can convert content from one format to another. The content replication policy, i.e., which contents/formats are stored on the front-end servers, is an important component of the service and storage architechture. We first show that any policy which employs the transcode on the fly approach, i.e., replicate content on the front-end servers only in one high-quality master format, and use computational resources to transcode on the fly to serve user requests for other formats, is strictly suboptimal. Next, we show that a class of distributed content replication policies which allows multiple formats of the same content to be stored on the front-end servers is asymptotically optimal, even without any coordination across various front-end servers.

Resources: [Slides]

Impact of Correlated Interference on Coverage Probability and Rate in Cellular Systems -- Sheetal Kalyani

Coverage probability and rate expressions in the presence of interference are studied for generalized fading channels. It is analytically shown that the coverage probability in the presence of correlated interferers is greater than or equal to the coverage probability in the presence of non-identical independent interferers when the shape parameter of the channel between the user and its base station is not greater than one. It is further analytically shown that the average rate in the presence of correlated interferers is greater than or equal to the average rate in the presence of non-identical independent interferers. The implications of these results on system design are discussed.

Resources: [Slides]

Decentralized Access: Power Control and Rate adaptation -- Sibi Raj B Pillai

Decentralized multiple access leads to interesting power control and rate-adaptation problems, which may often need to respect delay constraints. We present information theoretic models for wireless decentralized access, and identify suitable distributed power-control and rate-adaptation schemes. Further relaxations on the delay constraints will lead to ergodic setups, we revisit some of the unsolved power-control problems in this framework, and provide improved upper and lower-bounds.

Resources: [Slides]

Fairness, Priority Schedulers and Price of Fairness -- Veeraruna Kavitha

In the context of multi-agent resource allocation problems, fairness is a paradigm shift in the recent past. When agents compete for common resource and when the utilities derived by them, upon allocation, are independent across the agents and time slots, an opportunistic scheduler is used. The instantaneous utility of one agent can be low, however few among many would have `good' utility with high probability. Opportunistic schedulers utilize these opportunities, allocate resource at any time to a `good' agent. An efficient scheduler always allocates resources to the 'best' agent. These schedulers maximize the sum of accumulated utilities. This can result in negligible (unfair) accumulations for some agents: some of the agents, who are most often in 'bad' conditions, are starved. Fair opportunistic schedulers are thus introduced (e.g., alpha-fair schedulers). We discuss some well known fair schedulers and the first part of the talk observes that these are essentially a form of priority schedulers.
We then study their price of fairness (PoF). We group the agents into finite classes, each class having identical utilities and QoS requirements. We study the asymptotic PoF as agents increase, while maintaining class-wise proportions constant. Asymptotic PoF is less than one, depends only upon the differences in the largest utilities of individual classes and is less than the maximum such normalized differences. In fact the asymptotic PoF is zero if the utilities of all the classes are upper bounded by the same constant (L infinity norms are same). Further the PoF increases with increase in fairness requirements to an upper bound strictly less than one, even for max min fairness.

Parts of this work were presented at Infocom 2015 [IEEE link].

Sequential Frame Synchronization in Asynchronous Communication Channels -- Venkatesh Ramaiyan

We study the problem of sequential frame synchronization for a frame transmitted randomly and Uniformly in an interval of size $A$ slots. For a discrete memory-less channel, it is known that the sync frame size $N$ must scale as $e^{\alpha N} \geq A$ for the frame detection error to go to zero (where $\alpha$ is defined as the synchronization threshold for the discrete memory-less channel). We propose a general framework that permits a tradeoff between sync frame size $N$ and channel parameter $\alpha$ to support asynchronism. The framework allows us to characterize asynchronism with sync frame energy instead of the sync frame size $N$. Finally, for the AWGN channel, we show the equivalence of sync frame size $N$ and symbol energy $P$ to support asynchronism.

Tension Bounds for Interactive Systems -- Vinod M Prabhakaran

We will present new lower bounds on the communication required for two users to compute interactively. We consider both computation with and without security requirements. For secure function computation, where users should not gain additional information about each other's inputs and outputs than what the functions they compute reveal, it is well known that access to additional stochastic resources such as a discrete memoryless channel (DMC) or discrete memoryless source (DMS) is required, in general. In this setting, we give bounds on the rate of secure computation for DMCs and DMSs. These bounds strictly improve the oblivious transfer capacity upper bounds of Ahlswede-Csiszár (2007). For function computation without security requirements, we give lower bounds on the rate of communication over a noiseless channel. Our bounds are based on certain monotonicity properties of the tension region of a pair of random variables introduced in Prabhakaran and Prabhakaran (2014).