Applied Math Colloquium

Using the Nash equilibrium problem as a departure point, we explore the intricate and largely mysterious interplay between computational complexity and existence proofs in combinatorics. We present polynomial-time algorithms and complexity results for congestion games.

To reach their biologically active state, newly synthesized proteins spontaneously fold from an extended, linear conformation into a compact three-dimensional structure.

This remarkable self-assembly process, protein folding, is guided by the amino acid sequence of the protein to a unique final state. Despite several decades of intensive study the process by which sequence determines structure is still not well understood; in particular it is not currently possible to predict a protein's native three-dimensional structure given only its sequence. Recently, however, a class of prediction algorithms based on protein fragment assembly have made considerable headway towards the goal of generating low-resolution structure predictions. In this talk I will introduce the protein folding problem, describe these new algorithms, highlight their strengths and weaknesses, and discuss current research directed at improving the reliability and accuracy of their predictions.

A recent trend in discrete optimization is the study of game-theoretic environments, in which individual agents act according to their own independent and conflicting interests. The well-studied objective of routing traffic in a network to achieve the best possible network performance has emerged as a central problem in this area.

In large networks, it can be difficult or even impossible to impose optimal routing strategies on network traffic. On the other hand, permitting network users to act according to their own competing interests precludes any type of global optimality, and therefore carries the cost of decreased network performance. This inefficiency of noncooperative behavior is well known, and is most (in)famously illustrated in classical game theory by "The Prisoner's Dilemma" and in network routing by the counterintuitive "Braess's Paradox."

In this talk, I will discuss methods for quantifying the worst-possible loss in network performance arising from such noncooperative behavior --- the "price of anarchy". I will also briefly touch on methods for improving the noncooperative solution, including network design and edge pricing.

From its humble beginning as one of the first mathematics sites to appear on the internet, the site now known as mathworld.wolfram.com has come to be one of the world's most extensive and widely read sites for mathematics. The site features more than 11,000 individual entries, and contains thousands of diagrams and tens of thousands of equations. This site is extensively used by students, researchers, and practitioners of mathematics, and is still largely written and maintained by its original creator Eric Weisstein under the sponsorship of Wolfram Research, Inc., makers of the popular and full-featured mathematics package Mathematica.

In this talk, Dr. Weisstein will briefly discuss the history of the site, as well as highlight a number of its unique features. Work currently underway to add new features and new functionality to the site will be discussed, and an open invitation for collaboration and contribution will be extended to all interested parties.

________

Dr. Eric Weisstein received a BA in physics and astronomy from Cornell University in 1990, and holds a 1996 PhD in planetary astronomy from the California Institute of Technology. Since 1999, he has been at Wolfram Research, where he works as a full-time encyclopedist.

Computing the volume of a geometric body is an ancient, basic and surprisingly difficult task. Even for convex bodies in n -dimensional space, no polynomial-time deterministic algorithm can approximate the volume to within a factor that is exponential in n . On the other hand, Dyer, Frieze and Kannan showed that, using randomness, the volume can be approximated to arbitrary accuracy in polynomial time (the 23rd power of n ). This remarkable result has been improved several times; each improvement has yielded new techniques for algorithm design and has contributed to classical fields such as geometry and probability. In this talk, we will discuss the history of the volume problem, illustrate its difficulty and describe the latest algorithm whose complexity grows as the 4th power of n . The key ingredients of the algorithm are: (1) a method for rapidly “morphing” one convex body into another and (2) a geometric random walk that “mixes” rapidly from any starting point inside a convex body (the only walk known to have this property).

This is joint work with L. Lovasz (Microsoft Research).

The Laser Interferometer Gravitational wave Observatory (LIGO) aims to search for astrophysical sources of gravitational radiation. The instruments are nearing their design sensitivity, making this a realistic goal of the near future. Data collected during coincident, first observations of the LIGO instruments as well as with other European (GEO) and Japanese (TAMA) instruments are being analyzed by the working groups of the LIGO Scientific Collaboration. I will present an overview of the project, the search methods that are employed and the first upper limit results obtained with the instruments thus far.

We survey several aspects of an apparently simple matrix question: given two square matrices A and B, how to verify that all possible infinite products of the type ABBABAAAB... converge to zero?

This question arises in a number of applications, which we briefly describe (including hybrid systems, wavelets and the design of codes). We prove that the related problem of determining if all infinite products remain bounded, is algorithmically undecidable. We then exhibit the occurrence of Sturmian sequences and of a devil's staircase in the analysis of possible optimal periodic products. We conclude with a recent efficient approximation algorithm based on conic optimization and semi-definite liftings. All these results allow a better understanding of the problem, which we will nevertheless leave unsolved.

The results reported have been obtained in part with J. Tsitsiklis, A. Vladimirov and Y. Nesterov.