Colloquiums and Public Lectures 2012

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.

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).

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.

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.

4.30pm - 5.30pm

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.

SPMS LT2 (SPMS-03-03)

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)