2015 Joint Telematics Group/IEEE Information Theory Society Summer School

on Signal Processing, Communications and Networks.

IISc Bangalore, July 20-23, 2015.

Invited Workshop

IISc Bangalore, July 24, 2015.

**Links to videos: ** Morning session Afternoon session

Time | Title and abstract |
---|---|

09:00-09:30 | 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] |

09:30-10:00 | 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. |

10:00-10:30 | 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] |

10:30-11:00 | 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. |

11:15-11:45 | 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] |

11:45-12:15 | 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] |

12:15-12:45 | 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] |

12:45-13:15 | 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. |

14:00-14:30 | 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] |

14:30-15:00 | 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. |

15:15-15:45 | 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] |

15:45-16:15 | 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] |

16:15-16:45 | 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] |

17:00-17:30 | 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. Parts of this work were presented at Infocom 2015 [IEEE link]. |

17:30-18:00 | 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. |

18:00-18:30 | 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). |