Communication, Control and Signal Processing Seminar

Abstracts of talks

Spring 2018

02/08 Ajaykrishnan Nageswaran (UMD), Data Privacy for a $\rho$-Recoverable Function

ABSTRACT: A user's data is represented by a finite-valued random variable. A querier seeks to compute a given function of the data based on a query response provided by the user. Under the requirement that the querier must recover the function value from the query response with at least a prescribed probability, we analyze single and multiple independent query responses that provide maximum data privacy to the user by inflicting a maximum probability of data-estimation error on the querier. Explicit achievability schemes for randomization in query responses are given and their privacy compared with converse upper bounds.

This is joint work with Prof. Prakash Narayan.

02/15 Abram Kagan (UMD), Efficiency Requires Innovation

ABSRTACT: [pdf]

02/22 Yi-Peng Wei (UMD), Cache-Aided Private Information Retrieval with Unknown and Uncoded Prefetching

ABSTRACT: Private information retrieval (PIR) is a canonical problem to investigate the privacy of the contents downloaded from public databases. In the classical form of the problem, a user requests to download a message from $K$ messages from $N$ non-communicating databases such that no database can distinguish individually which message has been retrieved. A naive though inefficient PIR scheme is to download all of the $K$ messages from a database. Consequently, the aim of the PIR problem is to retrieve the desired message correctly by downloading as few bits as possible from the $N$ databases under the privacy constraint.

In this talk, we consider PIR from $N$ non-colluding and replicated databases when the user is equipped with a cache that holds an uncoded fraction $r$ from each of the $K$ stored messages in the databases. We assume that the databases are unaware of the cache content. We investigate $D^*(r)$, the optimal download cost normalized with the message size as a function of $K$, $N$, $r$.

Joint work with Karim Banawan and Prof. Sennur Ulukus.

03/08 Radu Balan (UMD), Low-rank Matrix Estimation and Rank-one Matrix Decompositions: When Nonlinear Analysis meets Statistics

ABSTRACT: In this talk, we present two points of view to broad classes of inverse problems: Lipschitz inversion and Cramer-Rao Lower (CRL) bounds. Given a nonlinear transformation of some data (e.g. incomplete observations of a low-rank matrix, or measurements of magnitudes of a linear transform) one is presented with the problem of stable inversion of this transformation. In this talk, we are interested in finding fundamental lower bounds of any algorithm. We shall discuss the concept of Lipschitz retract and a universal class of signal estimators (Whitney-McShaun-Kirszbraun). Then we formulate the same problem from a frequentist statistical estimation perspective and discuss the associated CRL bound.

If time permits we discuss also a special matrix decomposition problem inspired by expansions of integral operators on modulation spaces. Here we seek a decomposition of the covariance matrix into a sum of rank-one matrices that minimize an l1-type penalty.

03/29 Hamed Hassani (University of Pennsylvania), Non-asymptotic Analysis of Codes and its Practical Significance

ABSTRACT: Since Shannon's 1948 landmark paper, coding theory has focused on achieving capacity in the asymptotic sense: design low-complexity codes that become reliable at rates approaching capacity in the limit of large blocklengths. Throughout the seven decades of the development of coding theory, we have witnessed many remarkable code designs. Today, we have two families of low-complexity codes that can asymptotically achieve the capacity for a wide range of channels: polar codes and spatially coupled codes.

In this talk, I will consider a practically significant question that has emerged in recent years as the new grand challenge in coding theory: Design practical codes that are optimal in the non-asymptotic sense (at short lengths). In the first part of the talk (in slides), I will explain why the performance of the state-of-the-art code designs are unsatisfactory with respect to this challenge. In the second part (on the board), I will discuss why Reed-Muller codes, which are among the oldest code designs but recently revisited, can be a promising candidate for short packet communication.

05/02 Mohammad Hassan Lotfi (UMD), Bayesian Congestion Games with Traffic Manager

ABSTRACT: In this talk, we study the problem of designing an efficient signaling policy for a traffic manager (TM) when parts of a network experience unpredictable congestion and delays due to external factors, such as accidents or construction that block some lanes. To this end, we consider a simple network with two parallel routes, one of which suffers from more unpredictable congestion than the other. In order to understand drivers' behavior, we consider two scenarios - (i) no information from TM and (ii) a binary signal from TM - and assume that a fraction of drivers, called informed drivers, can make use of the TM signal in the latter case and make decisions based on updated information in order to minimize their expected delay. We show that an optimal signaling policy for TM is a threshold policy: the TM warns the drivers of high congestion if and only if the observed congestion on the route with more unpredictable delays exceeds some threshold. Under a mild condition, this optimal signaling policy is guaranteed to reduce the expected overall network delay. Moreover, we examine how the optimal threshold policy behaves when the congestion delay is either very sensitive or insensitive to traffic and provide a lower bound on the optimal threshold.