2012 talks

Asymptotic preserving methods for anisotropic elliptic problems and applications to simulation of plasma under large magnetic fields

By Fabrice Deluzet (Institut Mathematiques de Toulouse)

Wednesday, December 12
Location: DC 1304
Time: 3:30 - 4:30 p.m.

Abstract: In this talk, we present a class of numerical schemes developed for the approximation of elliptic or diffusion problems with large anisotropies. In the context of plasma simulation, this anisotropy is closely related to the magnetic field which explains different particle mobilities along and across the magnetic field lines.

Classical numerical methods are demonstrated to give rise to linear systems whose conditioning number blows up with increasing anisotropies. To tackle this difficulty an asymptotic preserving scheme is introduced. This method is designed to preserve a conditioning number independent of the anisotropy. It has been first developed using coordinates adapted to the anisotropy direction, then extended to coordinate independent of the anisotropy direction. Its efficiency is highlighted thanks to simulations of ionospheric plasma disturbances as well as magnetically confined plasmas representative of ITER (International Thermonuclear Experiment Reactor). 

Porting the Computer Science Toolbox to Game Theory and Economics

By Tim Roughgarden (Stanford University)

Monday, October 29
Location: DC 1302
Time: 3:30 - 4:30 p.m.

Tim Roughgarden

Abstract: Theoretical computer science has brought new ideas and techniques to game and economic theory. A primary signature of the computer science approach is {em approximation} --- the idea of building credibility for a proposed solution by proving that its performance is always within a small factor of an ideal (and typically unimplementable) solution. We explain two of our recent contributions in this area, one motivated by networks and one by auctions.

We first discuss the "price of anarchy": how well does decentralized (or "selfish") behavior approximates centralized optimization? This concept has been analyzed in many applications, including network routing, resource allocation, network formation, health care, and even models of basketball. We highlight a new theory of robust price of anarchy bounds, which apply even to systems that are not in equilibrium.

Second, we consider auction design: for example, what selling procedure should be used to maximize the revenue of a seller? On the analysis side, we highlight a new framework that explicitly connects average-case (i.e., Bayesian) analysis, the dominant paradigm in economics, with the worst-case analysis approach common in computer science. On the design side, we provide a distribution-independent auction that performs, for a wide class of input distributions, almost as well as the distribution-specific optimal auction.

Domain Adaptation for Learning in a Changing Environment

By Fei Sha (University of Southern California)

Friday, October 19
Location: M3 3127
Time: 3:30 - 4:30 p.m.

Fei Sha

Abstract: Statistical machine learning has become an important driving force behind many application fields. By large, however, its theoretical underpinning has hinged on the stringent assumption that the learning environment is stationary. In particular, the data distribution on which statistical models are optimized is the same as the distribution to which the models are applied.

Real-world applications are far more complex than the pristine condition. For instance, computer vision systems for recognizing objects in images often suffer from significant performance degradation if they are evaluated on image datasets that are different from the dataset on which they are designed.

In this talk, I will describe our efforts in addressing this important challenge of building intelligent systems that are robust to distribution disparity. The central theme is to learn invariant features and adapt probabilistic models across different distributions (i.e., domains). To this end, our key insight is to discover and exploit hidden structures in the data. These structures, such as manifolds and discriminative clusters, are intrinsic and thus resilient to distribution changes due to exogenous factors. I will present several learning algorithms we have proposed and demonstrate their effectiveness in pattern recognition tasks from computer vision and natural language processing.

This talk is based on the joint work with my students (Boqing Gong and Yuan Shi, both from USC) and our collaborator Prof. Kristen Grauman (U. of Texas, Austin).

Computing Game - Theoretic Solutions for Security

By Vincent Conitzer (Duke University, NC)

Monday, September 17
Location: M3 3103
Time 3:30 - 4:30 p.m.

Vincent Conitzer

Abstract: Algorithms for computing game-theoretic solutions are now deployed in real-world security domains, including air travel and harbours. These applications raise some hard questions. How do we deal with the equilibrium selection problem? How is the temporal and informational structure of the game best modelled? What assumptions can we reasonably make about the utility functions of the attacker and the defender? And, at last but not least, can we make all these modelling decisions in a way that allows us to scale to realistic instances? I will present our ongoing work on answering these questions.

Joint work with Dmytro Korzhyk, Joshua Letchford, Sayan Bhattacharya, Ronald Parr, Kamest Munagala (Duke): Manish Jain, Zhengyu Yin, Milind Tambe (USC); Christopher Kiekintveld (UT El Paso); Ondrej Vanek, Michal Pechoucek (Czech Technical University): Liam MacDermed, Charles Isbell (Georgia Tech); Tuomas Sandholm (CMU)

Constructing and computing equilibria for two-player games

By Bernhard von Stengel (The London School of Economics and Political Science, UK)

Friday, June 22
Location: MC 5158
Time: 3:30 - 4:30 p.m.

*Joint Colloquium with Tutte Seminar

Bernhard von Stengel

Abstract: A bimatrix game is a two-player game in strategic form, a basic model in game theory. A Nash equilibrium is a pair of (possibly randomized) strategies, one for each player, so that no player can do better by unilaterally changing their strategy. We give an introduction to the structure of Nash equilibria of bimatrix games based on best-reply regions derived from the payoff matrices. The corresponding mathematical objects are two polytopes for the two players and their combinatorial properties. With this geometric insight, one can construct games with certain properties, and understand algorithms for computing equilibria. We explain the classic Lemke-Howson algorithm, a pivoting method similar to the simplex algorithm for linear programming, that finds one Nash equilibrium. It also shows that a generic game has an odd number of equilibria.We describe a class of square bimatrix games for which the shortest Lemke-Howson path grows exponentially in the dimension d of the game. We construct the games using pairs of dual cyclic polytopes with 2d facets in d-space and a suitable "labelling" of their facets.

The latter result is joint work with Rahul Savani, published in: R. Savani and B. von Stengel (2006), Hard-to-Solve Bimatrix Games. Econometrica 74, 397-429.

Computational Methods for Design and Optimization of PDE Systems

By John Burns (Virginia Tech Department of Mathematics)

Monday, April 23
Location: MC 5136
Time: 3:30 - 4:30 p.m.

John Burns

Abstract: The problem of constructing numerical schemes for optimization based design and control of systems of partial differential equations (PDEs) leads to technical and practical issues that are not present if one is interested only in forward simulation. On the other hand, if one does not have accurate simulation algorithms, then evaluating a particular design or control may not be possible. In this talk we focus on a problem of simulating nonlinear partial differential equations on long time intervals. The simple 1D Burgers’ equation on a finite interval is used to illustrate some rather surprising behavior of numerical approximations. The key point is that regardless of the particular numerical scheme, finite precision arithmetic will always lead to numerically generated equilibrium states that do not correspond to equilibrium states of the Burgers’ equation. By analyzing the stability properties of these numerical stationary solutions it is possible to provide a detailed mathematical explanation of why numerical schemes fail to capture the correct asymptotic dynamics. Moreover, these results are not dependent on a specific time marching scheme, but are generic to all numerical approximations of Burgers’ equation. Numerical results are given to illustrate the ideas and some open questions are discussed.

Flicker Hallucinations: Faraday waves in the brain

By G. Bard Ermentrout (University of Pittsburgh)

Tuesday, March 6
Location: MC 5158
Time: 3:30 - 4:30 p.m.

*Joint seminar with Centre for Theoretical Neuroscience

G. Bard Ermentrout

Abstract: In this talk which should be accessible to both students and faculty, I first describe a striking visual illusion that occurs when the visual system is subjected to uniform bright flickering light in the 8-20 Hz frequency range. Subjects consistently report specific patterns at certain frequencies. We use a simple firing rate model that is spatially distributed in one or two dimensions to model the phenomena. We then use Floquet theory to analyze the regimes of stability and finally use symmetric bifurcation theory to explain why some patterns are associated with some frequencies.

Animating Liquids for Visual Effects: Splashing Sheets, Viscous Coiling and Rigid Body Interaction

By Christopher Batty (Columbia University)

Monday, January 30
Location: MC 5136
Time: 3:30 - 4:30 p.m.

Christopher Batty

Abstract: An ongoing challenge in computer animation and visual effects is the development of robust, efficient, and flexible tools to automatically generate physically realistic motion for objects and materials. In particular, fluid flows exhibit a panoply of visually compelling behaviours that are challenging to animate and yet entirely ubiquitous in the physical world, from the splash of an anchor dropped from a ship, to the coiling and meandering of syrup drizzled onto a pancake, to the beading and rippling of water due to surface tension. In these and many other scenarios, the surfaces and boundaries that separate a fluid from its surroundings play a crucial role in dictating the resulting motion. In this talk I will present work addressing the animation of common viscous incompressible fluids in the presence of such boundaries. I will begin by discussing a variational finite difference method applied to two problems: first, the interaction between fluids and dynamic rigid objects with irregular shapes, and second, the motion of the free (liquid-air) surface in the case of high viscosity. This approach yields a simple and efficient simulation method that reproduces visually important qualitative phenomena such as the characteristic coiling and folding motions of highly viscous liquids. I will go on to present an adaptive technique for detailed surface tension effects and thin liquid splashes which exploits Voronoi meshes to allocate simulation degrees of freedom precisely where needed. I will conclude by touching on my ongoing work towards a reduced two-dimensional model for very thin liquid sheets.

Past CM Colloquiums