Communication, Control and Signal Processing Seminar 

Abstracts of talks

Fall 2013

08/23 Ioannis Lambadaris (Carleton University, Canada), Stability Analysis and Delay Optimality in Multi-Queue Multi-Server (MQMS) Systems

ABSTRACT: The first part of the talk presents an explicit characterization of the stability region of stationary Multi-Queue Multi-Server (MQMS) queuing systems by means of a finite set of linear inequalities. More specifically, we compute the coefficients of the linear inequalities describing the facet-defining hyperplanes of the stability region polytope. Such a characterization is useful for performance evaluation of certain scheduling algorithms such as Maximum Weight (MW) policy. Our results can be used for studying the asymptotic behavior of the MW policy and computing bounds for the average queuing delay, as well as limiting moments of the queue sizes in heavy traffic regime. In the second part of the talk we consider symmetric MQMS systems. We study the problem of assigning K identical servers to a set of N parallel queues in a time-slotted system. The connectivity of each queue to each server is assumed to be i.i.d Bernoulli process; each server can serve at most one queue and each queue can be served by at most one server during each time slot. It has been previously proven that Maximum Weighted Matching (MWM) is a throughput optimal server assignment policy for such a system. We prove that for a symmetric system with i.i.d. Bernoulli arrivals and connectivities, MWM minimizes, in stochastic ordering sense, a range of cost functions of the queue lengths such as total queue occupancy (which implies minimization of average queuing delay).

09/18 Sirin Nitinawarat (UIUC), Controlled Sensing for Sequential Multihypothesis Testing

ABSTRACT: The problem of multiple hypothesis testing with observation control is considered in the sequential setting. In the case of uniform sensing cost, a sequential test is proposed generalizing the one studied in earlier work by Chernoff for binary hypothesis testing. Using the notion of decision making risk in place of the overall probability of error, the proposed test is shown to be first-order asymptotically optimal for multihypothesis testing {\em in a strong sense.} Another test is also proposed to meet {\em distinctly predefined} constraints on the various decision risks {\em non-asymptotically,} while retaining asymptotic optimality. Then a new model for controlled sensing for sequential multihypothesis testing is proposed. This new model generalizes the existing one in two aspects. First, it includes a more complicated memory structure in the controlled observations. Second, it allows for a general cost structure which entails accumulating up to the final decision time the total control cost with respect to an arbitrary cost function. Consequently, this new model is relevant to a wider class of applications, particularly in distributed and mobile sensor networks. A sequential test is proposed for this new model and is shown to be strongly asymptotically optimal. Interestingly, it is shown that the optimal causal control policy for the controlled sensing problem is {\em self-tuning,} i.e., maximizing an inherent "inferential" reward simultaneously under every hypothesis, with the maximal value being the best possible, even when the true hypothesis is known at the outset. Joint work with Dr. George Atia and Professor Venugopal V. Veeravalli.

09/26 Itzhak Tamo (UMD), Non-linear index coding outperforming the linear optimum

ABSTRACT: In the seminar I will present the paper: Non-linear index coding outperforming the linear optimum, by Eyal Lebetzky and Uri Stav from 2007. The paper talks about the following source coding problem: A sender holds a binary word of length n, and wishes to broadcast a codeword (which is a function of the binary word) to n receivers. The i-th receiver is interested in the i-th bit of the length n binary word, and he has prior side information comprising some subset of the n bits. An index code for this problem is an encoding scheme which enables each receiver to always reconstruct his desired bit, given his side information. The minimal codeword length of an index code was studied by Bar-Yossef, Birk, Jayram and Kol, and conjectured that linear index coding is in fact always optimal. In the seminar I will present the result in the paper which disproves this conjecture. This is achieved by an explicit construction of an index coding problem. No prior knowledge will be assumed.

10/07 Shlomo Shamai (Technion—Israel Institute of Technology), Cloud Radio Access Downlinks, with Backhaul Constrained Oblivious Processing

ABSTRACT: The talk considers the downlink of cloud radio access networks, in which a central encoder is connected to multiple multi-antenna base stations (BSs) via finite-capacity backhaul links. The processing is done at the central encoder, while the distributed BSs employ only oblivious (robust) processing. We first review state-of-the-art approaches, where the signals intended for different BSs are compressed independently, or alternatively the recently introduced structured coding ideas (reverse compute-and-forward) are employed. We propose to leverage joint compression, also referred to as multivariate compression, of the signals of different BSs in order to better control the effect of the additive quantization noises at the mobile stations. We address the maximization of a weighted sum rate. For joint compression this is associated with the optimization of the precoding matrix and the joint correlation matrix of the quantization noises, subject to power and backhaul capacity constraints. An iterative algorithm is described that achieves a stationary point, and a practically appealing architecture is proposed based on successive steps of minimum mean-squared error estimation and per-BS compression. We conclude by comparing different processing techniques, discussing a robust design concerning the available accuracy of the channel state information and overviewing aspects for future research. Joint work with S.-H. Park, O. Simeone (NJIT), and O. Sahin (InterDigital).

10/08 Amos Lapidoth (ETH, Switzerland) , Source Coding with Lists and Rényi Entropy

ABSTRACT: It is generally accepted that Rényi entropy is fundamental to Information Theory, even if its operational meaning is not as compelling as that of Shannon entropy. In this talk I shall discuss a variation on the source-coding problem whose solution is the source's Rényi entropy. This problem, which may also be of interest in its own right, will allow us to derive many of the properties of Rényi entropy using information-theoretic arguments. The problem will also provide an operational meaning to the lesser-known conditional Rényi entropy. I shall conclude with extensions to lossy source-coding. Based on joint work with Christoph Bunte.

10/17 Talha Cihad Gulcu (UMD), Polar codes: Speed of polarization and polynomial gap to capacity

ABSTRACT: In the seminar I will present the paper: Polar codes: Speed of polarization and polynomial gap to capacity, by Venkatesan Guruswami and Patrick Xia, submitted to arXiv in April 2013.
Shannon's channel coding theorem implies that for every memoryless binary input channel W, there exists a constant a_W such that for any N > a_W/\eps^2, there exists a binary code of length N and rate I(W)-\eps which enables reliable communication on W.
One might wonder what the corresponding situation is when it comes to polar codes. Guruswami-Xia answers this question as follows: There exists a constant \mu (indpt of channel) such that the statement in the previous paragraph remains to be true, if "N>a_W/\eps^2" is replaced by "N>a_W/\eps^(\mu)" and if "there exists a binary code" is replaced by "there exists a polar code".
The authors also give a concrete poly(N) time construction having N*poly(log N) decoding complexity.

10/24 Raef Bassily (Pennsylvania State University), Causal Erasure Channels

ABSTRACT: We consider the communication problem over binary causal adversarial erasure channels. Such a channel maps n input bits to n output symbols in {0, 1, ^}, where ^ denotes erasure. The channel is causal if, for every i, the channel adversarially decides whether to erase the i-th bit of its input based on inputs 1, ..., i, before it observes bits i+1 to n. Such a channel is p-bounded if it can erase at most a p fraction of the input bits over the whole transmission duration. Causal channels provide a natural model for channels that obey basic physical restrictions but are otherwise unpredictable or highly variable.
For a given erasure rate p, our goal is to understand the capacity at which a randomized (stochastic) encoder/decoder can transmit reliably across all causal p- bounded erasure channels.
In this talk, I will present the causal erasure model and give new upper bounds and lower bounds on the achievable rate. Our bounds separate the capacity in the causal erasures setting from the capacity in two related models: random erasure channels (strictly weaker) and fully adversarial erasure channels (strictly stronger). Specifically, we show:
-A strict separation between random and causal erasures for all constant erasure rates p \in (0, 1). In particular, we show that the capacity of causal erasure channels is 0 for p \geq 1/2 (while it is nonzero for random erasures).
-A strict separation between causal and fully adversarial erasures for p \in (0, \phi) where \phi \approxeq 0.348.
-For p \in [\phi, 1/2), we show existence of codes for causal erasures that achieve higher rate than the best known constructions for fully adversarial channels.
Our results contrast with existing results on correcting causal bit-flip errors (as opposed to erasures) [Dey et. al 08, 09], [Haviv-Langberg 11] . For the separations we provide, the analogous separations for bit-flip models are either not known at all or much weaker.
This talk is based on a joint work with Adam Smith (Pennsylvania State University). It is to appear in the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2014.

10/31,11/21 Itzhak Tamo (UMD), A Family of Locally Recoverable Codes

ABSTRACT: In today's information era, data centers are facing challenging tasks of managing, analyzing, and storing enormous amounts of data. One such task is recovery, namely, the problem of storing information with added redundancy in order to provide resiliency to erasures. The key requirement of the problem is the locality property, which assumes that it is possible to recover each element of the information by accessing a small of amount of other information blocks. Clearly, the property of local recovery translates to a faster recovery of lost data.
The more formal definition is as follows: A code over a finite alphabet is called locally recoverable (LRC) if every symbol in the encoding is afunction of a small number other symbols.
In the talk I will present a family of LRC codes that attain the maximum possible value of the distance for a given locality parameter and code cardinality.
This is a joint work with Alexander Barg.

11/07,11/14 Shun Watanabe (UMD), Non-Asymptotic and Second-Order Achievability Bounds for Source Coding with Side-Information

ABSTRACT: We present a novel achievability bound for the Wyner-Ahlswede-Korner (WAK) problem of lossless source coding with rate-limited side-information. This bound is proved using ideas from channel simulation and channel resolvability. The bound improves on all previous non-asymptotic bounds on the error probability of WAK problem. We also present achievable second-order rates by applying the multidimensional Berry-Esseen theorem to our new non-asymptotic bound.
In this talk, I will review some backgrounds on the non-asymptotic and second-order analyses, and present our results and ideas of proofs. This talk is based on a joint work with Shigeaki Kuzuoka and Vincent Y. F. Tan, which was presented at ISIT 2013 (see also ).

12/5 Praneeth Boda (UMD), Source Coding Problem for Sources with Additional Outputs to Keep Secret from the Receiver or Wiretappers

ABSTRACT: In the seminar I will present a work of H.Yamamoto and some related problems.
A source coding problem is considered for a communication system with correlated source outputs. One of the source outputs must be transmitted to the receiver within a prescribed distortion tolerance, and the other source output has to be kept as secret as possible from the receiver or wiretappers. For this case, the equivocation-distortion function and the rate-distortion-equivocation function are defined and evaluated. Some applications and related problems will be looked at.