Project Highlights

Project Highlight: Finding the Culprit

In many scenarios such as the spread of viruses in computer networks, the spread of (mis)information in social networks and even the spread of Alzheimer’s disease in the brain, one wishes to find out the source or the culprit by observing who is infected. At first glance, this seems like finding a needle in a haystack and impossible to solve.

Project Highlight: Large-Deviation Analysis for the Learning of Markov Tree Structures

Learning the structure of a graphical model (or Bayesian network) from data is a fundamental task in many scientific domains. In this work, we are interested in the theoretical properties of a well-known structure learning algorithm known as the Chow-Liu algorithm. The Chow-Liu algorithm learns the “best” tree structure from independently drawn observations of a multivariate discrete tree distribution.

Project Highlight: Non-monotonic Lyapunov Functions for Analysis of Nonlinear Systems

Lyapunov’s stability theorem and its many variants comprise a central core of control theory and have a wide array of applications ranging from proving stability of nonlinear systems or designing stabilizing controllers to robustness analysis or proving convergence of combinatorial algorithms. The main challenge in the application of Lyapunov’s theorem is always to find a suitable Lyapunov function, a scalar function of the state that decreases monotonically along trajectories of a dynamical system.

Project Highlight: Influence of a Degraded Environment on Airspace Safety

The current air transportation system (ATS) is being pushed to operate ever closer to its critical capacity, leading to increases in both the frequency and duration of delays. This strain is expected to worsen in the coming years alongside an increase in the demand for air travel. As it stands, human air traffic controllers direct the bulk of traffic to travel along a limited number of predetermined routes. To improve efficiency and increase capacity, there has been a push for the next ATS to allow aircraft greater autonomy when planning routes and during flight.

Project Highlight: Sum of Squares and Polynomial Convexity

Given a multivariate polynomial how can we decide if it is globally nonnegative? This basic question appears ubiquitously in various areas of optimization and control, and unfortunately it is known to be difficult to answer from a computational complexity viewpoint. What if instead we ask the question: can the polynomial be written as a sum of squares (SOS) of other polynomials? It turns out that because of several appealing connections between real algebra and convex optimization, one can answer the latter question efficiently. It is clear that if a polynomial is a sum of squares, then it is globally nonnegative. But when do nonnegative polynomials admit a representation as a sum of squares? The study of this question, which belongs to the emerging field of convex algebraic geometry, has a prolonged and interesting history that dates back to prominent mathematicians such as David Hilbert.