|Title:||The complexity issues on stochastic games|
|Speaker:||Associate Professor Kazuhisa Makino|
|Date:||9 December 2013|
|Time:||3.00pm – 4.00pm|
|Venue:||MAS Executive Classroom 2 (SPMS-03-07), School of Physical and Mathematical Sciences|
|Abstract:||Stochastic games were introduced in 1953 by Shapley for the discounted case, and extended to the undiscounted case in 1957 by Gillette. Each such game is a dynamic game with probabilistic transitions played by two players on a finite set of states. The game is played in the infinite sequence of rounds. In the round, the game is in some state. The players choose actions. Then they receive payoffs and the game moves to a new random state, where the payoffs and the transition probability depend on the previous state and the actions chosen by the players. The procedure is repeated at the new state. Stochastic games generalize parity games, cyclic games, simple stochastic games, and BWR games, which all belong to NP and coNP, but are not known to be solved in polynomial time. In this talk, I briefly survey the algorithmic issues on these games, as well as the properties on the optimal strategies for them. I also|
|Title:||Partition Regular Equations|
|Speaker:||Professor Imre Leader|
|Date:||29 August 2013|
|Time:||3.30pm – 5.30pm|
|Venue:||SPMS-LT2 (SPMS-03-03), School of Physical and Mathematical Sciences|
A finite or infinite matrix M is called `partition regular' if whenever the natural numbers are finitely coloured there exists a monochromatic vector x with Mx=0. Many of the classical results of Ramsey theory, such as van der Waerden's theorem or Schur's theorem, may be naturally rephrased as assertions that certain matrices are partition regular. While the structure of finite partition regular matrices is well understood, little is known in the infinite case. In this talk we will review some known results and then proceed to some recent developments. The talk will not assume any previous knowledge of the area.
|Title:||Stories vs. Statistics|
|Speaker:||Professor John Allen Paulos|
|Date:||30 May 2013|
|Time:||4.30pm – 5.30pm|
|Venue:||SPMS – LT3, SPMS-03-02|
|Abstract:||This colloquium deals with the complicated relation and tension between these two ways (in the title) of understanding the world. Mathematical logic is extensional, for example, and allows for substitution of equals for equals, whereas intentional or narrative logic does not. Statistical notions are usually a refinement and formalization of everyday ideas, but the formalization is often counter-intuitive, Bayes theorem for example. When listening to stories we readily suspend disbelief and risk a so-called type I error (false positive); when evaluating statistics we usually suspend belief and risk a so-called type II error (false negative). Coincidence, the role of common knowledge, and various cognitive foibles (conjunction fallacy, anchoring, etc.) are dealt with differently in stories and statistics (a variant of C.P. Snow's two cultures, the literary and scientific). The talk would give lots of topical examples and would require no mathematical background.|
|Title:||Tropical Linear Algebra and Its Applications|
|Speaker:||Professor Alexander Guterman|
|Date:||4 April 2013|
|Time:||4.30pm - 5.30pm|
|Abstract:||Tropical algebra (sometimes called max algebra) is the set of real numbers with additional symbol, −∞, with unusual way to define the operations, namely, the sum of two elements is their maximum, and the product is their sum. Under these operations tropical algebra is an algebraic structure called a semiring. Note that there is no subtraction in this semiring, however addition and multiplication are commutative, associative, and satisfy usual distributivity lows. The other typical examples of semirings are non-negative integers, non-negative reals, boolean algebras. Tropical algebra naturally appears in modern scheduling theory, game theory and optimization. Tropical arithmetic allows to reduce difficult non-linear problems to the linear problems but over tropical algebra. Therefore, to investigate these problems it is necessary to develop linear algebra in the tropical case. The main purpose of our talk is to discuss tropical linear algebra and different its applications.|
We plan to consider the modern progress in the theory including our recent results. Among the other topics we shall discuss our recent joint research results with Marianne Akian, LeRoy Beasley, Stephane Gaubert, and Yaroslav Shitov.
|Title:||Teaching Differential Equations|
|Speaker:||Professor John Hubbard|
|Date:||27 March 2013|
|Time:||10.30am - 11.30am|
|Venue:||MAS Executive Classroom 2, MAS-03-07|
|Abstract:||Many students, at the end of even a fairly demanding course on differential equations, when asked a question like: |
Are the solutions of x’ = x^2 - t with x(0) = 0 deﬁned for all t > 0?
would try various methods of solutions. After failing to ﬁnd a solution (there actually are no solutions that can be written in elementary terms, or their iterated indeﬁnite integrals) they would eventually claim: this equation has no solutions. Even colleagues will claim: “We need to go to numerical methods”. Often these are students who, in a different part of the examination could state, and perhaps even prove, the existence and uniqueness theorem for differential equations. After some years of teaching such courses, I realized that “exist” means something different if you can write down a solution, and if you only know existence by the existence and uniqueness theorem. Students can think effectively about the first, but the solutions given by the second are too nebulous. Very few differential equations can be “solved” in elementary terms, so one deﬁnitely wants the students to work effectively with equations that cannot be solved.
In the first part of the talk, I will describe a collection of techniques (fences and funnels) and associated software that I developed to help students think effectively about such differential equations. In the second half, I will show some things that can be done by such methods: they open a whole new world of fascinating mathematics to the undergraduate curriculum that was previously accessible only to a few researchers (and perhaps out of reach for them too).