Communication, Control and Signal Processing Seminar 

Abstracts of talks

Spring 2016

02/11 Berk Gurakan (UMD), Energy Harvesting Multiple Access Channel with Data Arrivals

ABSTRACT: We consider the energy harvesting two user Gaussian multiple access channel (MAC), where both of the users harvest energy from nature and their data packets arrive intermittently over time. We find the optimal offline transmit power and rate allocations that maximize the sum rate. First, we show that the optimization problem can be formulated in terms of the data rates only, instead of both transmission powers and data rates. Next, we show that the optimal sum rates are non-decreasing in time, similar to the single-user optimal powers. Then, we use a dual decomposition method to solve this problem efficiently. Specifically, we show that this problem is equivalent to three subproblems where each subproblem is a throughput maximization problem with fading, data and energy arrival constraints. We decompose the problem into inner and outer optimization problems and solve the overall problem using the subgradient descent.

02/11 Min Ye (UMD), Explicit constructions of MDS array codes with optimal repair bandwidth.

ABSTRACT: Maximum distance separable (MDS) codes are optimal error-correcting codes in the sense that they provide the maximum failure-tolerance for a given number of parity nodes. Dimakis et. al. showed that in order to recover the failure of a single node in an MDS code with r parity nodes, at least 1/r fraction of the data stored in each of the surviving nodes is required. An MDS code is said to have the optimal repair property if this lower bound is achieved when repairing any single node failure. We study high-rate MDS codes with optimal repair property. Explicit constructions of such codes in the literature are only available for the cases where there are at most 3 parity nodes. In this paper, we give explicit constructions of MDS codes with optimal repair property for any r and any code length n. We also consider the case when only d surviving nodes are contacted for the repair of a single node failure, where n-r <= d < n. We construct explicit MDS array codes that achieve the lower bound on the repair bandwidth for any n, r and d.

02/18 Ameera Chowdhury (Rutgers University), Inclusion Matrices and the MDS Conjecture

ABSTRACT: Let $\mathbb{F}_{q}$ be a finite field of order $q$ with characteristic $p$. An arc is an ordered family of vectors in $\mathbb{F}_{q}^{k}$ in which every subfamily of size $k$ is a basis of $\mathbb{F}_{q}^{k}$. The MDS conjecture, which was posed by Segre in 1955, states that if $k \leq q$, then an arc in $\mathbb{F}_{q}^{k}$ has size at most $q+1$, unless $q$ is even and $k=3$ or $k=q-1$, in which case it has size at most $q+2$. We propose a conjecture which would imply that the MDS conjecture is true for almost all values of $k$ when $q$ is odd. We prove our conjecture in two cases and thus give simpler proofs of the MDS conjecture when $k \leq p$, and if $q$ is not prime, for $k \leq 2p-2$. To accomplish this, given an arc $G \subset \mathbb{F}_{q}^{k}$ and a nonnegative integer $n$, we construct a matrix $M_{G}^{\uparrow n}$, which is related to an inclusion matrix, a well-studied object in combinatorics. Our main results relate algebraic properties of the matrix $M_{G}^{\uparrow n}$ to properties of the arc $G$ and may provide new tools in the computational classification of large arcs.

02/25 Itzhak Tamo (Tel Aviv University), The polynomial method and the entropy function applied to counting

ABSTRACT: In Combinatorics, Information theory and Computer Science we would often like to derive bounds on the number of objects with a certain property. In recent years, two relatively new techniques were found to be useful for these type of problems. The first technique is termed as the polynomial method, this technique exploits the algebraic structure of the problem to derive the desired bounds. If no algebraic structure exists, then occasionally some structure can be added to the problem. In contrast to the first technique, the second one has an information theoretic flavor. It uses the basic properties of various entities such as the entropy function to derive bounds on the number of objects. In this talk, I will present these elegant techniques via several examples. No prior knowledge will be assumed.

03/10 Alexander Barg (UMD), On the Construction of Polar Codes for Arbitrary DMCs

ABSTRACT: In their 2013 work, Tal and Vardy presented a low-complexity algorithm for construction of binary polar codes. Despite several years of work, results of this kind for general alphabets seemed difficult to obtain. In this talk we present such an algorithm together with provable performance guarantees as well as some experimental results. This is a joint work with T.C. Gulcu and Min Ye.

03/31 Konstantinos Gatsis (UPenn), Resource Management for Wireless Sensor-Actuator Systems

ABSTRACT: Modern cyber-physical systems appearing in, e.g, smart homes, building and industrial automation, or infrastructure monitoring, leverage wireless communication to spatially separate sensing and actuation. Wireless sensors collect measurements of the dynamical process of interest from various locations and transmit them wirelessly to controllers and actuators. To achieve desirable performance for the physical system and to overcome the inherent uncertainties of wireless communication, it is important to efficiently manage the available communication resources. This work focuses on the design of resource allocation mechanisms that adapt to the control requirements of the physical system and exploit wireless medium opportunities. Recent developments include management of transmit power resources, as well as mechanisms for sensor-actuator systems over shared wireless channels.

04/7 Udit Halder (UMD), Pursuit and Classical Mechanics

ABSTRACT: The talk will be divided into two main parts. The classical problem of two bodies (Kepler problem) moving under (Newtonian) gravitational force will be discussed in the first part. An inverse calculation which deduces Newton's law of gravitation from Kepler's laws of planetary motion will be carried out. In the second part, we will give a comparison of the Kepler problem with that of a pursuit problem arising from a biological context. Finally, if time permitted, a recent result giving more intimate relationship with the Kepler problem will be mentioned.

04/14 Marcos Vasconcelos (UMD), Estimation of discrete random variables over the collision channel with minimum probability of error

ABSTRACT: In this talk, we will discuss the problem of estimating a pair of independent discrete random variables over a collision channel. Each random variable is observed by a different sensor which decides whether or not to attempt to transmit it to a remote receiver. The communication constraint introduced by the collision channel is such that if more than one sensor transmits, a collision occurs. The goal is to design policies at the sensors and the estimator such as to minimize an aggregate probability of estimation error criterion. We show that person-by-person optimal policies for this problem have a certain deterministic structure and use this result to find team-optimal policies for any probability distributions for the observations. This is joint work with Prof. Nuno Martins.

06/16 Alexander Barg (UMD), Codes, metrics and applications

ABSTRACT(a version of this talk will be presented at ISIT'16 in July): Applications of coding in communication and computer science give rise to various metrics on strings over a finite alphabet. We consider a class of metrics induced by partial orders on the code coordinates, paying special attention to one such metric (the Niederreiter-Rosenbloom-Tsfasman metric) and its applications in wireless, list decoding, approximation theory, and polar coding. We discuss combinatorics of the ordered metric space, and extend some of the results to general partial orders. We continue with several results related to distance distributions of linear codes and their extentions to the ordered case, as well as links with matroids on partial orders. In conclusion, we mention a further extension to infinite orders and an unexpected appearance of wavelet-like functions. This line of work has developed over a number of years and draws on joint papers with many colleagues, including, in particular, (former) students Andrew McGregor, Punarbasu Purkayastna, and Woomyoung Park.