IMSE Hot TIME Symposium: Applied Geometry, Topology, and Networks

Symposium on Hot Topics at the Interface of Mathematics and Engineering-2014

Monday and Tuesday February 24 and 25

Organized by IMSE at the University of Illinois at Urbana-Champaign.

Symposium leaflet

Plenary Speakers:

  • Frank Sottile, Texas A&M University, Toric degenerations of Bezier Patches
    Ideally, the applications of mathematics are a two-way-street: not only does mathematics help to understand problems arising in engineering, but that work can enrich the mathematical enterprise. I will present a small, but textbook example of such interactions. A question of de Boor about the meaning of certain control structures in geometric modeling was answered by Garcia-Puente, Zhu, and me by appealing to toric degenerations, using work of Kapranov, Sturmfels, and Zelevinsky on the toric variety of secondary polytopes. These algebraic geometry methods do not extend to irrational toric varieties (a natural real analytic generalization of toric varieties). The work I will describe with Postinghel and Villamizar extends this a natural real analytic generalization of toric varieties, giving a dictionary between a space of degenerations of an irrational toric variety and the corresponding secondary fan of the corresponding point configuration. Strengthening this dictionary leads to a richer theory of irrational toric varieties.
  • Ruth Williams, University of California San Diego, Resource Sharing in Stochastic Networks
    Stochastic models of processing networks arise in a wide variety of applications in science and engineering, e.g., in high-tech manufacturing, transportation, telecommunications, computer systems, customer service systems, and biochemical reaction networks. These “stochastic processing networks” typically have entities, such as jobs, vehicles, packets, customers or molecules, that move along paths or routes, receive processing from various resources, and that are subject to the effects of stochastic variability through such variables as arrival times, processing times and routing protocols. Networks arising in modern applications are often heterogeneous in that different entities share (i.e., compete for) common network resources. Frequently the processing capacity of resources is limited and there are bottlenecks, resulting in congestion and delay due to entities waiting for processing. The control and analysis of such networks present challenging mathematical problems.This talk will explore the effects of resource sharing in stochastic networks and describe associated mathematical analysis based on elegant fluid and diffusion approximations. Illustrative examples will be drawn from biology and telecommunications.
Thematic sessions: Applied Geometry and Topology and Networks, Learning, and Games.
Invited Talks: Speakers, Titles, Abstracts
  • Carolyn Beck, University of Illinois at Urbana-Champaign, “Aggregation and Comparison of Graphs and Markov Chains”
  • Mireille “Mimi” Boutin, Purdue, “High-dimensional Data Clustering using Local Projections”
  • Tim Bretl, University of Illinois at Urbana-Champaign, A few interesting things about the Kirchhoff elastic rod
    Any framed curve traced by a Kirchhoff elastic rod in static equilibrium can be described as a local solution to an optimal control problem on the special Euclidean group SE(3). By application of Lie-Poisson reduction, I will show that the set of all normal extremals for this problem is a smooth manifold of finite dimension that admits a single global chart. I will also show that the subset of all local optima is open and is locally diffeomorphic to the space of boundary conditions. Finally, I will discuss a number of interesting questions that are raised by these results, and perhaps say something about their application to hard problems in robotics.
  • Misha Chertkov, Los Alamos National Laboratory, Complex Energy Systems
    Today’s energy systems, such as electric power grids and gas grids, already demonstrate complex nonlinear dynamics where, e.g., collective effects in one exert uncertainty and irregularities on other. These collective dynamics are not well understood and are expected to become more complex tomorrow as the grids are pushed to reliability limits, interdependencies grow, and appliances become more intelligent and autonomous. Tomorrow’s will have to integrate the intermittent power from wind and solar farms whose fluctuating outputs create far more complex stress on power grid operations, often dependent, e.g. in providing fast regulation control, on the gas supply. Guarding against the worst of those perturbations will require taking protective measures based on ideas from optimization, control, statistics and physics.
    In this talk we introduce a few of the physical, optimization and control principles and phenomena in today’s energy grids and those that are expected to play a major role in tomorrow’s grids.
    We illustrate the new science of the energy grids on three examples: (a) discussing an efficient and highly scalable Chance Constrained Optimal Power Flow algorithm providing risk-aware control of the power transmission system under uncertainty associated with fluctuating renewables (wind farms); (b) describing effect of the intermittent power generation on reliability and compression control of the gas grid operations; and (c) briefly discussing examples of interdependencies, reliability troubles and solutions in the low level (distribution) grids.
  • Wendy Cho, University of Illinois at Urbana-Champaign, An Extreme-Scale Computational Approach to Redistricting Optimization
    Redistricting occurs every 10 years following the decennial census. Ideally, the resulting districts are created to provide fair representation for each citizen. In the current system, the redistricting process is easily manipulated so that future election results are essentially known even before votes are cast. Drawing district lines to favor a specific outcome is generally called gerrymandering. We approach redistricting from a non-legal perspective. Rather than proposing regulations intended to constrain map-making, we develop a tool to illuminate and open up the redistricting process. Our project takes advantage of the massive computational power provided by the Blue Waters supercomputer for computationally intensive redistricting analysis by extending and enhancing a scalable parallel genetic algorithm (PGA) library. The redistricting problem amounts to arranging a finite number of indivisible geographic units into a smaller number of aggregated areas or districts. It is an application of the set-partitioning problem that is known to be NP- complete. We define the problem as a multi-objective discrete optimization problem with a configuration of objectives and constraints that are reflective of the legal environment in which redistricting proceeds. Technologically, the world has undergone an unmistakable and immense transformation. The power of information and computing has already demonstrated its extensive and often surprising reach in many realms of life. We must take advantage of these technological advances to facilitate societal tasks. We are at the threshold of making unprecedented use of statistical and mathematical modeling and computing technology in the redistricting process. Instead of merely tinkering with endless possibilities, we develop computationally intensive models to synthesize and organize massive amounts of computation/data to help us evaluate redistricting schemes and tailor them to our notions of “fairness” and democratic rule.
  • Howie Choset, Carnegie Mellon University, Locomotion for Whole Body Locomotors.
    The locomotion of articulated mechanical systems is often complex and unintuitive, even when considered with the aid of reduction principles from geometric mechanics. In this talk, I will present tools for gaining insight on the underlying principles of locomotion. One such tool is the connection vector field which illustrates the geometric structure of the relationship between internal shape changes and the system body velocities they produce. We apply these tools for the classic three-link system swimming at low Reynolds numbers, and then in a granular media. While granular media are not yet described by equations like the Navier-Stokes equations that describe the flow of Newtonian fluids, recently developed empirical resistive force laws predict the performance of undulatory sand-swimmers. We use this understanding to empirically create an connection vector field, and then can readily design gaits. Finally, this talk will describe how to lift the ideas to a 16 degree-of-freedom snake robot.
  • Vin de Silva, Pomona College, Reeb graphs, levelset persistence, and category theory
    Reeb graphs are objects which track the connected components of a topological space as it varies along a 1-parameter family. Levelset persistence has a similar goal, tracking the appearance, persistence and disappearance of higher-dimensional topological features. I will explain how both of these theories benefit from a little category theory. One application is the construction of a distance between a pair of Reeb graphs.
  • Jeff Erickson, University of Illinois at Urbana-Champaign, Hex-meshing things with topology
    A topological quadrilateral mesh Q of a connected surface in R^3 can be extended to a topological hexahedral mesh of the interior domain M if and only if Q has an even number of quadrilaterals and no odd cycle in Q bounds a surface inside M. Moreover, if such a mesh exists, the required number of hexahedra is within a constant factor of the minimum number of tetrahedra in a triangulation of M that respects Q. Finally, if Q is given as a polyhedron in R^3 with quadrilateral facets, a topological hexahedral mesh of the polyhedron can be constructed in polynomial time if such a mesh exists. All our results extend to domains with disconnected boundaries. Our results naturally generalize results of Thurston, Mitchell, and Eppstein for genus-zero and bipartite meshes, for which the odd-cycle criterion is trivial.
  • Brighten Godfrey, University of Illinois at Urbana-Champaign, Networking at the Speed of Light
    Human experience on the Internet is increasingly affected by latency of low-level communications. But today even simple operations can be more than an order of magnitude worse than the ideal. In this talk, I’ll lay out a ‘grand challenge’ for computer networking: achieving a speed-of-light Internet. We’ll discuss how truly low latency would transform the networking landscape, and areas where we can begin to improve. We’ll dive deeper into two technologies that hold significant promise — using redundant requests to reduce latency, and rearchitecting transport control using performance-oriented learning algorithms — with a focus on their core mathematical problems, some solved and some open.
  • David Goldberg, Georgia Institute of Technology, Higher order Markov Random Fields for Independent Sets
    The independent sets of a network, i.e. sets of nodes with no internal edges, arise in optimization models when agents must simultaneously utilize a scarce resource. It is known that if one samples from the independent sets of a large regular graph of large girth using a pairwise Markov random field (i.e. hardcore model) in the uniqueness regime (i.e. no long-range correlations), each excluded node has a binomially distributed number of included neighbors in the limit. Motivated by applications to the design of communication networks, we pose the question of how to sample from the independent sets of such a graph so that the number of included neighbors of each excluded node has a different distribution of our choosing.
    We observe that higher order Markov random fields are well-suited to this task, and investigate the properties of these models. For the family of so-called reverse ultra log-concave distributions, which includes the truncated Poisson and geometric, we give necessary and sufficient conditions for the associated higher order Markov random field to be in the uniqueness regime. We also show that these Markov random fields undergo a phase transition, and give explicit bounds on the associated critical activity, which we prove to exhibit a certain robustness. For distributions which are small perturbations around the binomial distribution realized by the hardcore model at critical activity, we give a description of the corresponding uniqueness regime in terms of a simple polyhedral cone. Our analysis reveals an interesting non-monotonicity with regards to biasing towards excluded nodes with no included neighbors. We conclude with a broader discussion of the potential use of higher order Markov random fields for analyzing independent sets in graphs, as well as other stochastic models which arise in various network applications.
  • Jonathan Hauenstein, North Carolina State University, Applications of Numerical Real Algebraic Geometry
    Classically, numerical algebraic geometric algorithms are designed to compute complex solutions to systems of polynomial equations. By incorporating techniques from geometry, new algorithms for computing real solutions have emerged and are being utilized to compute real solutions to large-scale systems of polynomial equations. This talk with explore such algorithms as well as applications in enumerative geometry and mechanism design.
  • Naira Hovakimyan, University of Illinois at Urbana-Champaign, Time-Critical Cooperative Path-Following Control of Multiple UAVs
    Worldwide, there has been growing interest in the use of autonomous vehicles to execute cooperative missions of increasing complexity without constant supervision of human operators. Despite significant progress in the field of cooperative control, several challenges need to be addressed to develop strategies capable of yielding robust performance of a fleet in the presence of complex vehicle dynamics, communications constraints, and partial vehicle failures. In this talk, we will present a theoretical framework for the development of decentralized strategies for cooperative motion control of multiple vehicles that must meet stringent spatial and temporal constraints. The approach adopted applies to teams of heterogeneous systems, and does not necessarily lead to swarming behavior. Flight test results of a coordinated road search mission involving multiple small tactical UAVs will be discussed to demonstrate the efficacy of the multi-vehicle cooperative control framework presented.
  • Lek-Heng Lim, University of Chicago Subspace Distances
    Modern data are often characterized by their principal subspaces and it is important to be able to define a notion of distance between subspaces. For two subspaces of the same dimension, there is a well-known intrinsic notion of distance — the geodesic distance between two points on a Grassmannian. This is independent of the choice of coordinates and can be readily related to the principal angles and thus computed via the SVD. But what if the subspaces are of distinct dimensions and what if we have affine subspaces? In this talk, we will describe a generalization of the aforementioned Grassmann distance to these cases. We will show that (i) the distance between subspaces of different dimensions may be defined as the distance between a point and a subvariety in a Grassmannian; (ii) the distance between affine subspaces may be defined as the distance on the universal quotient bundle of a Grassmannian. Furthermore, these distances restrict to the usual one for subspaces of the same dimension and share its properties of being coordinate independent and readily computable via SVD. This is joint work with Ke Ye of Chicago.
  • Sewoong Oh, University of Illinois at Urbana-Champaign, Learning Mixtures of Discrete Product Distributions
    Motivated by several practical applications such as crowd-sourcing, recommendation systems, and learning Boolean functions, we study the problem of learning a distribution from samples, when the underlying distribution is a mixture of product distributions over discrete domains. We introduce a polynomial time/sample complexity method for learning a mixture of r discrete product distributions over {1,…,L}, for general L and r. We show that our approach is statistically consistent and further provide finite sample guarantees. We use techniques from the recent work on tensor decompositions for higher-order moment matching. A crucial step in these moment matching methods is to construct a certain matrix and a certain tensor with low-rank spectral decompositions. These tensors are typically estimated directly from the samples. The main challenge in learning mixtures of discrete product distributions is that these low-rank tensors cannot be obtained directly from the sample moments. Instead, we reduce the tensor estimation problem to: a) estimating a low-rank matrix using only off-diagonal block elements; and b) estimating a tensor using a small number of linear measurements. Leveraging on recent developments in matrix completion, we give an alternating minimization based method to estimate the low-rank matrix, and formulate the tensor completion problem as a least-squares problem.
  • Alex Olshevsky, University of Illinois at Urbana-Champaign, Distributed Learning and the Combinatorics of Noisy Linear Systems
    We consider the problem of learning of an unknown vector from noise-corrupted samples which arrive intermittently at different nodes in a network. We study the convergence rate of a natural diffusion-type learning scheme under the assumption that the network itself is unpredictably time-varying. Our goal is to obtain a tight relationship between the combinatorial properties of the (time-varying) network and the speed at which the nodes in the network learn the unknown vector. This is closely related to the problem of obtaining combinatorial bounds on the steady-state deviation of a so-called consensus process driven by noise. We show that the steady-state deviation of a noisy consensus process can be closely bounded in terms of the Kemeny constant of the underlying Markov chains and this in turn is related to the combinatorial bounds we obtain on the speed of diffusion-based distributed learning.
  • Venkatesh Saligrama, Boston University,Sub-Graph Detection
    We are motivated by anomaly detection that arises in a number of applications including sensor network intrusion, disease outbreak detection, community detection and video surveillance. In these applications anomalies have a local signature, namely, if an anomaly exists the observations outside the anomalous region appear normal.We formulate this problem as an instance of connected sub-graph detection. In this setup observations are associated with nodes of a graph and the goal is to detect whether or not there is some connected sub-graph where the observations are anomalous. The problem involves optimizing graph functions under connectivity constraints. We deal with combinatorial issues associated with connected sub-graphs by deriving a new convex parameterization for connected subgraphs. This parameterization can be expressed in terms of linear matrix inequalities (LMI) and allows for computationally tractable schemes for optimizing arbitrary graph functionals under connectivity constraints. We then show that when observations under the null and anomalous hypothesis belong to exponential family of distributions our method is asymptotically optimal for a number of interesting families of graphs. We also demonstrate our method on both synthetic and real examples.
  • Venu Veeravalli, Illinois, Universal Outlier Sequence Detection
    The following outlier detection problem is studied in a universal setting. A large number of sequences are observed simultaneously, a small subset of which are outlier sequences. When a sequence is an outlier, the observations in that sequence are assumed to be distributed according to an “outlier” distribution, distinct from the “typical” distribution governing the observations in all the other sequences. Nothing is known about the outlier and typical distributions except that they are distinct and have full supports on a finite set. The goal is to design a universal test to best discern the outlier sequences. We show that it is possible to construct provably exponentially consistent tests for this problem under various settings.
  • Shmuel Weinberger, University of Chicago, Homology theories on graphs and some aspects of nonlinear network aggregation
    We consider the following general kind of problem: there are n agents, with some mutual interactions (modeled by an undirected graph), each choosing a point in some space X, and we want to aggregate their choices to obtain a value (ideally computed in a distributed fashion) for the graph. We shall see some homological and analytic aspects to the problem (as X varies). We will also consider some aspects of the limit theory as n goes to infinity.
  • Adam Wierman, California Institute of Technology, The Empirical Implications of Complexity for Economics
    The task of understanding the computational complexity of economic models has received considerable focus within computer science in recent years. Results have emerged for a variety of models, and the general message is that economic models tend to be computationally hard in the worst case. However, the question remains as to whether this hardness can be revealed by data, i.e., whether computational complexity has empirical implications. In this talk I will discuss our that begins to address this question in the context of consumer choice theory and bimatrix games using tools from revealed preference theory. Additionally, I will highlight the broader role that revealed preference theory can play in bringing data and empirical issues into the algorithmic game theory community.
  • Tauhid Zaman, Massachusetts Institute of Technology, The Dynamics of Retweeting on Twitter
    In this work we analyze the dynamics retweeting in the micro-blogging site Twitter. We propose a model for Twitter users’ retweeting behavior which incorporates two key elements: the arrival patterns of users to Twitter and the design of the Twitter user interface. Using only these elements, our model predicts a distribution of user retweet times which agrees with observations on over 2.4 million retweets in Twitter. Our model allows us to predict the probability of a tweet being viewed by a specific user and the impact of promotional activity on the visibility of a tweet. This suggests that our model can serve as a tool to optimize advertising services provided by Twitter which promote tweets.
Schedule

All plenary talks are in CSL Auditorium.

Monday
8:30-9:00 Registration
9:00-9:30 Welcome, Overview and Opening remarks by Deans Brian Ross and Martin Wong
9:30-10:30 Ruth Williams – Plenary talk
10:30-11:00 Coffee break
Invited talks Session Chair: R. Srikant, Auditorium Session Chair: Richard Sowers, CSL 301
11:00-11:45 Adam Wierman Shmuel Weinberger
11:45-12:30 Alex Olshevsky Vin de Silva
12:30-2:00 Lunch
Invited talks Session Chair: Lav Varshney, Auditorium Session Chair: Anil Hirani, CSL 301
2:00-2:45 Venkatesh Saligrama Howie Choset
3:00-3:45 Venu Veeravalli Lek-Heng Lim
4:00-4:45 David Goldberg Jeff Erickson
Tuesday
9:00-10:00 Frank Sottile – Plenary talk
10:00-10:30 Coffee break
Invited talks Session Chair: Negar Kiyavash CSL 301 Session Chair: Hal Schenck, Auditorium
10:30-11:15 Carolyn Beck Jonathan Hauenstein
11:15-12:00 Tauhid Zaman Tim Bretl
12:00-2:00 Lunch
Invited talks Session Chair: Venu Veeravalli CSL 301 Session Chair: Prashant Mehta, Auditorium
2:00-2:45 Brighten Godfrey Mireille Boutin
3:00-3:45 Michael Chertkov Wendy Cho
4:00-4:45 Sewoong Oh Naira Hovakimyan

Registration is free but required - here.

For more information contact Antonnete Peppers, apeppers@illinois.edu.

Accommodations:

A hotel block at the Illini Union Hotel has been held for this conference.
If you are attending and need a hotel room, you can book a room in the IMSE Symposium room block by calling (217) 333-3030.

In need of a hotel after the Symposium?  Here are links to other hotels in the area:

Hawthorn Suites; Hilton Garden Inn; I Hotel; Hampton Inn.

Whereabouts

icon-car.pngKML-LogoFullscreen-LogoQR-code-logoGeoJSON-LogoGeoRSS-LogoWikitude-Logo
IMSE Symposium location - Coordinated Science Laboratory

loading map - please wait...

IMSE Symposium location - Coordinated Science Laboratory 40.114954, -88.226721 Symposium takes place in Coordinated Science Laboratory

IMSE is supported by the Vice Chancellor for Research, the College of Liberal Arts and Sciences, and the College of Engineering at the University of Illinois at Urbana-Champaign.