Colloquiums and Public Lectures 2009

Title: Riemann’s Memoir and the Related
Speaker:Assistant Professor Zhao Liangyi
Date:18 November 2009
Time:3.30pm – 4.30pm
Venue:SPMS LT 3, SPMS-03-02
Abstract:This colloquium lecture is taking part in the RH Day (, marked by a 
series of lectures world-wide in celebration of the 150th anniversary of the Riemann hypothesis. In 1859, George Friedrich Bernhard Riemann, a newly elected member of the Berlin Academy of Sciences who had to report on his recent research, submitted a manuscript entitled “Ueber die Anzahl der Primzahlen unter einer gegebenen Groesse” to the academy. In this ground-breaking paper (now dubbed Riemann’s Memoir), Riemann formulated theorems and conjectures for what is now known as the Riemann zeta-function. All, save one, of these conjectures have been resolved, the sole exception being the Riemann hypothesis. In this lecture, I will discuss the history of the zeta-function and the content of Riemann’s Memoir. No pre-requisite beyond the residue theorems in complex analysis will be needed.


Title: How Fast Can You Walk in a Distributed Network?
Speaker:Professor Gopal Pandurangan
Date:29 October 2009
Time:3.30pm – 4.30pm
Venue:SPMS-MAS-03-07, EC2
Abstract:Performing random walks in networks is a fundamental primitive that has found applications in 
many areas of computer science, including distributed computing. In this talk, we focus on the
problem of performing random walks efficiently in a distributed network. Given bandwidth
constraints, the goal is to minimize the number of rounds required to obtain a random walk sample. All previous algorithms that compute a random walk sample of length L as a subroutine always do so naively, i.e., in O(L) rounds. We present a fast distributed algorithm for performing random walks. We show that a random walk sample of length L can be computed in O(L^{2/3}D^{1/3}) rounds on an undirected unweighted network, where D is the diameter of the network. For small diameter graphs, this is a significant improvement over the naive O(L) bound. We also show that our algorithm can be applied to speed up the more general Metropolis-Hastings sampling. We extend our algorithms to perform a large number, k, of random walks efficiently. We show how k destinations can be sampled in O((kL)^{2/3}D^{1/3}) rounds if k <= L^2 and O((kL)^{1/2}) rounds otherwise. We also present faster algorithms for performing random walks of length larger than (or equal to) the mixing time of the underlying graph. Our techniques can be useful in speeding up distributed algorithms for a variety of applications that use random walks as a subroutine. We mention one such application involving the decentralized computation of spectral gap and mixing time, subroutines that can be useful in the design of self-regulating and self-aware networks.

This is joint work with Atish Das Sarma and Danupon Nanongkai (Georgia Tech.).


Title: Rendezvous numbers and von Neumann’s mini-max theorem
Speaker:Professor Carsten Thomassen
Date:15 October 2009
Time:3.00pm – 4.00pm
Venue:SPMS-MAS-03-07, EC2
Abstract:A rendezvous number for a metric space M is a number a such that, for every finite subset Q of M, there is an element p in M, such that the average distance from p to the elements in Q is a. O.Gross showed in 1964 that every compact connected metric space has precisely one rendezvous number. This result is a consequence of von Neumann’s mini-max theorem in game theory. In an article in the American Math. Monthly 93 (1986) 260-275 J.Cleary and A.A.Morris asked if a (more) elementary proof of Gross’ result exists. In this talk, I shall formulate a mini-max result for real matrices which immediately implies these results of Gross and von Neumann.

The proof is easy and involves only mathematical induction.


Title: Algorithmic Aspects of Manipulating Elections
Speaker:Dr Piotr Faliszewski
Date:27 August 2009
Time:4.00pm – 5.00pm
Venue:SPMS-MAS-03-07, EC2
Abstract:Voting and elections are at the core of democratic societies. People vote to elect leaders, decide policies, and organize their lives but elections also have natural applications in computer science where agents in multi-agent systems often need to reach a common decision. However, elections can be manipulated in multiple ways, e.g., voters may act dishonestly, election's chair might try to rag them via procedural tricks and some voters might be bribed. In this talk, I will give an algorithmic perspective on manipulating elections and attempts to protect elections via computational complexity.


Title: Furry black holes
Speaker:Professor Elizabeth Winstanley
Date:16 April 2009
Time:4.30pm – 5.30pm
Venue:SPMS-MAS-03-07, EC2
Abstract:Black hole solutions of the Einstein equations of general relativity have been studied for over 90 years. Traditionally, the simplest types of black hole solutions have been studied, but over the past 20 years there has been an explosion of interest in more complicated black holes which arise when the Einstein equations are coupled to different types of matter field. These more complicated black holes are known as "hairy" black holes.  In this talk we describe some black hole solutions of the Einstein equation with a particular type of matter (a Yang-Mills gauge field), in which the black hole solutions can have unlimited amounts of "hair", which we call "furry" black holes.


Title: Mathematics Inspired by Computing
Speaker:Professor Dr Dieter Spreen
Date:9 April 2009
Time:5.30pm – 6.30pm
Venue:SPMS-MAS-03-07, EC2
Abstract:Without doubt, physics had a strong influence on the development of mathematics and certainly still has. We will report on a development due to needs in computing science.


Title: Applications of Semi-definite Programming: A Tutorial
Speaker:Professor Etienne de Klerk
Date:26 March 2009
Time:3.30pm – 4.30pm
Venue:SPMS-MAS-03-07, EC2
Semi-definite programming (SDP) is one of the most active areas in mathematical programming, due to varied applications and the availability of interior point algorithms.

In this tutorial we will review various applications of SDP, including:

- The Lovasz theta number and Shannon capacity of a graph;
- Approximation algorithms for the MAXIMUM k-CUT problem in graphs;
- Certifying positivity of a polynomial;
- The S-lemma in control theory


Title: On $q$-Product Expansios of Modular Forms
Speaker:Professor Dr Winfried Kohnen
Date:19 March 2009
Time:4.30pm – 5.30pm
Venue:SPMS-MAS-03-07, EC2
Abstract:Modular forms are (meromorphic) functions on the complex upper half-plane that satisfy simple transformation formulas under fractional linear transformations. In particular, a modular form has a Fourier expansion in the variable $q=e^{2\pi iz}, and the Fourier coefficients often are interesting arithmetical functions. Modular forms are fundamental objects in complex analysis and number theory. What seems to be less known is that modular forms also have infinite product expansions of the form $\prod_n(1-q^n)^{c(n)}$ and the exponents $c(n)$ also often seem to carry important information on the function. For example, there is famous work by Borcherds that relates the exponents of modular forms with so called "Heegner divisors" to Fourier coefficients of modular forms of half-integral weight.

In this talk, I would like to show how these exponents can also be used to characterize those modular forms which do not have zeros or poles on the upper half-plane.


Title: A Mathematician Plays the Stock Market 
Speaker:Professor John Allen Paulos
Date:5 March 2009
Time:4.30pm – 5.30pm
Venue:SPMS LT5, SPMS-03-08
Abstract:Intended for a general audience, we attempt to lay out, elucidate, and explore some of the basic conceptual mathematics of the market. We will examine - largely via vignettes and stories rather than formulas and equations - various approaches to investing as well as a number of problems, paradoxes, and puzzles, some old, some new, that encapsulate issues associated with the market. Is it efficient? random? Is there anything to technical analysis, fundamental analysis, and other supposedly time-tested methods of picking stocks? How can one quantify risk? What is the role of cognitive illusion and psychological foible (to which, alas, I am not immune)? What are the most common scams? What are options, portfolio theory, short-selling, the efficient market hypothesis? Does the normal bell-shaped curve really explain the market's occasionally extreme volatility? What about fractals, chaos, and other non-standard tools? In short, what can the tools of mathematics tell us about the vagaries of the stock market?