Colloquiums and Public Lectures 2012

Title:Sforza’s formula for the volume of a hyperbolic tetrahedron
Speaker:Dr Nikolay Abrosimov 
Date:20 November 2012
Time:4.30pm - 5.30pm
Venue:SPMS LT4 (SPMS-03-09)
Host:Dr Fedor Duzhin
Abstract: Dr Nikolay Abrosimov Colloquium Abstract


Title:Computing Game-Theoretic Solutions for Security
Speaker:Professor Vincent Conitzer 
Date:29 October 2012
Time:4.30pm - 5.30pm
Venue:SPMS LT5 (SPMS-03-08)
Abstract: Algorithms for computing game-theoretic solutions are now deployed in real-world security domains, including air travel and harbors. 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 modeled? What assumptions can we reasonably make about the utility functions of the attacker and the defender? And, last but not least, can we make all these modeling decisions in a way that allows us to scale to realistic instances? I will present our ongoing work on answering these questions. This is joint work with Dmytro Korzhyk, Joshua Letchford, Sayan Bhattacharya, Ronald Parr, Kamesh 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).


Title:Alan Turing and Computation
Speaker:Professor Rodney Downey 
Date:4 October 2012
Time:4.30pm - 5.30pm
Venue:SPMS LT3 (SPMS-03-02)
There is no doubt that Alan Turing was a brilliant mathematician. He was famously involved in code-breaking in the Second World War, in Hut 8 at Bletchley Park. It has been argued that this work of Turing and his gifted co-workers shortened the war by at least two years and saved several million lives. In 1936, Turing wrote a paper whose ideas formed the basis of the development of the digital computer, which would arguably be the most significant single development of the 20th Century. Turing had several other anticipations of modern ideas. These include areas ranging from computer chess, program verification, artificial intelligence, numerical analysis, and even morphogenesis-an area of biology seeking to explain things like how tigers get their stripes. In this last area, he wrote a fundamental paper which took 20 years to be verified experimentally and is now seen as a foundation of the area.

2012 is the centenary of Turing's birth and this fact is being celebrated worldwide. This lecture will explain a fragment of Turing's work and how it led to modern computing. Turing's work is a case study in the power of mathematics, and this lecture seeks also to explore this fact. For example, Turing's work that lead to computers came from a then seemingly obscure area of mathematics called mathematical logic. Modern life could not exist without this area. How did that occur? What message is there for us for the support of science?

This lecture will be accessible to undergraduate students.


Title:Bankruptcy in Byzantium
Speaker:Dr Maxwell Young
Date:29 August 2012
Time:4.30pm - 5.30pm
Venue:SPMS LT4 (SPMS-03-09)
In the context of tolerating malicious behavior, the notion of inflicting higher costs on an adversary has appeared in isolated instances in several areas of computer science. This talk will introduce a new approach for dealing with Byzantine attacks called ``resource-competitive analysis'' which aims to formalize the concept of imposing prohibitive resource costs on an attacker who seeks to disrupt the functionality of a distributed system. Here, a resource may correspond to computational power, bandwidth, or energy.

In order to provide concrete examples of how this new approach can be applied, I will summarize the results of two previous papers from PODC'11 and PODC'12 that address the challenge of achieving broadcast in a wireless sensor network in the presence of a jamming adversary. Specifically, in a setting where both correct and Byzantine devices are battery powered, energy is a scarce resource that can be treated as a common currency, and we demonstrate randomized algorithms that guarantee that either (1) broadcast is quickly achieved or (2) the Byzantine devices rapidly deplete their energy supply in attempting to jam communication. In the latter case, the adversary may delay broadcast for a time, but is quickly rendered bankrupt and unable to launch further attacks on the system. The talk will conclude with a discussion of some interesting open problems.

The work presented in this talk is joint with Seth Gilbert (National University of Singapore), Valerie King (University of Victoria), and Jared Saia (University of New Mexico).


Title:Schubert Eisenstein Series
Speaker:Professor YongJu Choie
Date:18 June 2012
Time:10.30am - 11.30am
Venue:SPMS LT3 (SPMS-03-02)
Abstract: We define Schubert Eisenstein series as sums like usual Eisenstein series but with the summation restricted to elements of a particular Schubert cell, indexed by an element of the Weyl group. They generally not fully automorphic. We will develop some results and methods for GL3 that may be suggestive about the general case. The six Schubert Eisenstein series are shown to have meromorphic continuation and some functional equations. The Schubert Eisenstein series Es1s2 and Es2s1 corresponding to the Weyl group elements of order three are particularly interesting: at the point where the full Eisenstein series is maximally polar, they unexpectedly become (with minor correction terms added) fully automorphic and related to each other. It is also shown for GL3 that the Whittaker coefficients of Schubert Eisenstein series may be expressed in terms of Demazure characters. This is a joint work with Dan Bump.


Title:Automorphisms of necklaces and sandpile groups
Speaker:Professor Sergei Duzhin 
Date:3 May 2012
Time:4.30pm - 5.30pm
Venue:SPMS LT3 (SPMS-03-02)
Given two sets A and B of the same cardinality and a family of bijections fi:A->B, one can construct the groups GA and GB acting on the corresponding sets and generated by the products of fi-1 by fj (fi by fj-1, respectively).

We apply this obvious observation to the sets of Lyndon words (or necklaces) of length n with p colors (where p is prime) and the set of irreducible polynomials of degree n over the field Fp. In fact, there are two well-known sets of such bijections: one indexed by normal bases of the field extension Fpn:Fp and first appearing in a paper by C.Reutenauer and the other indexed by the generators of the multiplicative group of Fpn and discovered by S.Golomb.

For Reutenauer's bijections, the resulting automorphism group of necklaces Gnp is remarkable in many respects; in particular, its orbits are unexpected and enigmatic. Also, this group may be related to the structure of the Drinfeld associator, a remarkable series in two non-commuting letters.

In the email correspondence between Dmitrii Pasechnik and the speaker, it was noticed that Gnp is isomorphic to the group of circulant matrices if size n over Fp and then, after a convincing series of computer experiments, it was conjectured that Gnp is isomorphic to the so called sandpile group of the directed graph with vertex set Zn and the edges k->pk, k->pk+1,..., k->pk+p-1. The last conjecture was recently proved in the case n=pk by Chan Swee Hong, a student of D.Pasechnik.


Title:Real submanifolds in complex space: when Michael Artin meets Henri Poincaré
Speaker:Professor Nordine Mir 
Date:19 April 2012
Time:4.30pm - 5.30pm
Venue:SPMS LT3 (SPMS-03-02)
Abstract: We will discuss the problem of local holomorphic equivalence of real submanifolds in complex space going back to H. Poincaré. One of the most natural and important question arising there is to determine when the formal holomorphic equivalence of real submanifolds implies their biholomorphic equivalence. We will exhibit a few results along this question and discuss its connection with a well-known approximation theorem in analytic and algebraic geometry due to M. Artin.


Title:Computability in Analysis and Algebra
Speaker:Professor Russell Miller 
Date:18 April 2012
Time:4.30pm - 5.30pm
Venue:SPMS LT3 (SPMS-03-02)
Computability theory is the study of the mechanical computation of mathematical functions. The intuitive notion of an algorithm was formalized in the 1930's by Alan Turing, who defined the objects which came to be known as \emph{Turing machines}. Many other attempts to define computability of functions, often by very different approaches, have turned out to yield exactly the class of functions computable by Turing machines, and today this definition is widely regarded as having captured the notion of computability precisely. We will present these ideas using examples. First we will investigate how Turing machines can be used in the study of the real numbers. This topic, known as computable analysis, suggests both the style and the inherent limitations of computability theory.
A simple first example, with a surprisingly straightforward proof, shows directly that not all functions are computable, and we will describe briefly what can be done in computable analysis, and what other methods have been suggested for computation on the reals. Computability theory turns out to be better suited to the study of algebraic structures, rather than analytic ones, and especially to countable algebraic structures.
We will use countable fields as an example, suggesting the sorts of problems about fields for which one would like to compute answers, and showing how this can be done -- or, in certain cases, how it can be shown that there is no algorithm computing the desired function. Rabin's Theorem will be presented as a specific application, describing the extent to which the algebraic closure of a computable field can itself be presented computably.

For background on this portion of the talk, a good reference is the speaker's own expository paper: Computable Fields and Galois Theory, Notices of the AMS, 55 (August 2008) 7, 798--807. Chinese translation in Mathematical Advances in Translation, 29 (2010) 4, 319--330.


Title:Mystery of Point Charges
Speaker:Professor Boris Shapiro 
Date:12 April 2012
Time:3.30pm - 5.30pm 
Venue:SPMS LT3 (SPMS-03-02)
Abstract: Some years ago I found in the first volume of J.C.Maxwell's foundational book "A Treatise of Electricity and Magnetism" from 1869 an amazing claim saying that the maximal number of isolated equilibrium points of a system of N point charges in $\bR^3$ with the standard Newton potential can not exceed $(N-1)^2$. Maxwell's supporting arguments however turned out to be completely false. I will explain what part of Maxwell's statement can be saved and how it can be generalized. But in spite of all modern knowledge Maxwell's original 150-years' old claim is still open even in the simplest case of the 3 charges!


Title:Introduction to modular forms, with a hint of Linnik's problem and coding theory
Speaker:Dr Anne-Maria Ernvall-Hytönen
Date:22 March 2012
4.30pm - 5.30pm
Venue:SPMS LT3 (SPMS-03-02)
I will give an introduction to modular forms, and give some examples. However, the real emphasis of the talk will be in applications of modular forms: a beautiful solution of Linnik's problem (lattice points are uniformly distributed on a sphere) being a classic example.

Finally, I will tell how modular forms can be used to choose the best lattice in coding theory, which is a very recent application.


Title:The Well-Tempered Clavier and Rational Approximation
Speaker:Professor Stephan Baier 
Date:8 March 2012
Time:3.30pm - 4.30pm
SPMS LT2 (SPMS-03-03)
Abstract: Nowadays, every standard piano is tuned in equal temperament, i.e. an octave is divided into 12 notes in such a way that every pair of adjacent notes has an identical frequency ratio. It took a long time for this tuning to become prevalent in musical practice (until the beginning of the twentieth century, actually). Johann Sebastian Bach's Well-Tempered Clavier was an early example of piano music that demonstrated the possibilities of well temperament, which was an intermediate step between pure intonation and equal temperament. In this talk, I shall give a brief overview of the history of equal temperament tuning and explain its mathematical reasons, in particular, why the division into precisely 12 notes makes sense. I shall also talk about different tuning systems, in particular, microtonal tuning, and give a number of audio examples.


Title:Exponential Diophantine Equations
Speaker:Professor Yann Bugeaud
Date:1 March 2012
Time:4.30pm - 5.30pm
Venue:SPMS LT3 (SPMS-03-02)
Abstract: The theory of linear forms in the logarithms of algebraic numbers, developed by Alan Baker, provides us with explicit upper bounds for the size of the solutions of certain families of Diophantine equations. Unfortunately, these upper bounds are huge, and we cannot hope to list all the solutions by brutal enumeration. However, many important progress have been accomplished during the last ten years and, by combining various methods, it is now possible to completely solve certain famous exponential Diophantine equations. For instance, jointly with Mignotte and Siksek, we have proved recently that 1, 8 and 144 are the only perfect powers in the Fibonacci sequence.


Title:Extremal problems for convex lattice polytopes
Speaker:Professor Imre Barany
Date:7 February 2012
Time:4.30pm - 5.30pm
Venue:SPMS LT3 (SPMS-03-02)
Abstract: In this survey I will present several extremal problems, and some solutions, concerning convex lattice polytopes. A typical example is to determine the minimal volume that a convex lattice polytope can have if it has exactly n vertices. Other examples are the minimal surface area, or the minimal lattice width in the same class of polytopes. These problems are related to a question of V I Arnold from 1980 asking for the number of (equivalence classes of) lattice polytopes of volume V in d-dimensional space, where two convex lattice polytopes are equivalent if one can be carried to the other by a lattice preserving affine transformation.


Title:Improved lower bounds on crossing numbers of graphs through optimization
Speaker:Professor Etienne de Klerk 
Date:2 February 2012
Time:4.30pm - 5.30pm
Venue:SPMS LT3 (SPMS-03-02)
The crossing number problem for graphs is to draw (or embed) a graph in the plane with a minimum number of edge crossings. Crossing numbers are of interest for graph visualization, VLSI design, quantum dot cellular automata, RNA folding, and other applications. On the other hand, the problem is notoriously difficult. In 1973, Erdös and Guy wrote that: "Almost all questions that one can ask about crossing numbers remain unsolved." For example, the crossing numbers of complete and complete bipartite graphs are still unknown. The case of the complete bipartite graph is known as Turán's brickyard problem, and was already posed by Paul Turán in the 1940's. Moreover, even for cubic graphs, it is NP-hard to compute the crossing number.

Different types of crossing numbers may be defined by restricting drawings; thus the two-page crossing number corresponds to drawings where all vertices are drawn or a circle, and all edges either inside or outside the circle. It is conjectured that the two-page and normal crossing numbers coincide for complete and complete bipartite graphs. In this talk, we will survey some recent results, where improved lower bounds were obtained for (two-page) crossing numbers of complete and complete bipartite graphs through the use of optimization techniques. (Joint work with D.V. Pasechnik)


Title:Partition Dynamics
Speaker:Professor Brian Hopkins
Date:19 January 2012
Time:4.30pm - 5.30pm
Venue:SPMS LT5 (SPMS-03-08)
Abstract: We will explore the impact of ideas from dynamical systems on the venerable topic of integer partitions. Given an operation on partitions, the partitions of a fixed integer can be thought of as a finite dynamical system. There are three immediate natural questions: How many components are in the system? Which partitions are fixed points or in cycles? Which partitions are Garden of Eden states, with no predecessor? Answers to these questions use generating functions and combinatorial proofs. This approach helps in analyzing Bulgarian Solitaire popularized by Martin Gardner and various sand pile model examples of "self-organized criticality" in theoretical physics. It can also be enlightening to "operationalize" bijections of partition identities, such as Glaisher's proof that there are as many partitions of n into distinct parts as there are partitions of n into just odd parts.