Colloquium Talk

Title: Riemann’s Memoir and the Related

Date: 18 Nov 2009, Wednesday, 3.30pm – 4.30pm

Venue: SPMS LT 3, SPMS-03-02

Speaker:
Asst Prof Zhao Liangyi
Division of Mathematical Sciences
School of Physical and Mathematical Sciences
Nanyang Technological University

Abstract: 
This colloquium lecture is taking part in the RH Day (http://aimath.org/RH150/), 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.

Slides for this lecture is available here.

Title: How Fast Can You Walk in a Distributed Network?

Date: 29 Oct 2009, Thursday, 3.30pm – 4.30pm

Venue: SPMS-MAS-03-07, EC2

Speaker:
Professor Gopal Pandurangan
Division of Mathematical Sciences,
School of Physical and Mathematical Sciences,
Nanyang Technological University

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

Date: 15 Oct 2009, Thursday, 3pm – 4pm

Venue: SPMS-MAS-03-07, EC2

Speaker:
Professor Carsten Thomassen
Professor of Mathematics,
Technical University of Denmark

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

Date: 27 Aug 2009, Thursday, 4pm –5pm

Venue: SPMS-MAS-03-07, EC2

Speaker:
Dr. Piotr Faliszewski

Department of Computer Science,

AGH University of Science and Technology, Krakow, Poland

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

Date: 16 Apr 2009, Thursday, 4.30pm –5.30pm

Venue: SPMS-MAS-03-07, EC2

Speaker:
Professor Elizabeth Winstanley
Department of Applied Mathematics
University of Sheffield, UK

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

Date: 9 Apr 2009, Thursday, 5.30pm – 6.30pm

Venue: SPMS-MAS-03-07, EC2

Speaker:

Prof. Dr. Dieter Spreen
Department of Theoretical Computer Science,
University of Siegen, Germany

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.

Date: 26 Mar 2009, Wednesday, 3.30pm – 4.30pm

Venue: SPMS-MAS-03-07, EC2

Speaker:

Prof. Etienne de Klerk
Department of Econometrics and Operations Research,
Faculty of Economic Sciences,
Tilburg University,
The Netherlands

Abstract: 
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

Slides for the tutorial is available here.

Title: On $q$-Product Expansios of Modular Forms

Date: 19 Mar 2009, Friday, 4.30 – 5.30pm

Venue: SPMS-MAS-03-07, EC2

Speaker:

Prof.Dr. Winfried Kohnen
Professor of Mathematics
Faculty of Mathematics and Computer Sciences
University of Heidelberg

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.

Date: 5 mar 2009, Friday, 4.30 – 5.30pm

Venue: SPMS-MAS-03-07, EC2 (Please note change in venue to SPMS LT5, SPMS-03-08)

Speaker:

Prof. John Allen Paulos
Professor of Mathematics,
Temple University,
USA

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?