Skip to main content
Portrait photo of Mai Gehrke.

Using abstract mathematical structures to study algorithmic complexity questions: The 34th Annual Lonseth Lecture

Image Credit: Mai Gehrke in the Fondation Meaght Museum in St. Paul de Vence. Text editing done by Joy King.

The 34th Annual Lonseth Lecture : The Department of Mathematics is pleased to announce that Professor Mai Gehrke from the Laboratoire Jean Alexandre Dieudonné at the Université Côte d’Azur in Nice, France, will deliver our 34th annual Lonseth Lecture at 5pm on April 19, 2019, in the Willamette room of the CH2M Hill Alumni Center. Professor Gehrke will give a talk titled, Using abstract mathematical structures to study algorithmic complexity questions. In this talk Professor Gehrke will discuss automata, which are very simple computational models. They are important in applications of computer science but also serve as a laboratory for studying the complexity of algorithms. Dr. Gehrke will introduce automata and show how finite monoids, certain very abstract algebraic structures, may be assigned as invariants of automata. llustrating how these invariants are powerful enough to make deep computational questions decidable, she will give a glimpse of an idea for how this can be generalized to provide sophisticated mathematical tools for the study of computational complexity classes.

Mai Gehkre is a Senior Research Director in Theoretical Computer Science at the Centre National de la Recherche Scientifique (CNRS), currently affiliated with the Institut Jean Alexandre Dieudonné in Nice where she moved from the Institut de Recherche en Informatique Fondamentale of Université Paris Diderot. Previously she held the chair in Algebra and Logic at Radboud Universiteit Nijmegen in the Netherlands and a Full Professorship in mathematics at New Mexico State University in the United States. She holds an MS and a PhD in mathematics from the University of Houston. Professor Gehrke is an editor of Mathematical Logic Quarterly and of the Houston Journal of Mathematics. She is co-founder of the Topology, Algebra and Categories in Logic (TACL) conference series and has served on numerous scientific committees in Europe and the United States. Dr. Gehrke was awarded an ERC Advanced grant on Duality in Formal Languages and Logic in 2015. Her main contributions are in Stone duality, a theory which links algebraic and spatial mathematics in the realm of logic. More recently, Professor Gehrke has been working on duality theoretic extensions of the profinite algebraic tools of automata theory and their application in complexity theory.

A Mathematical Journey: Dr. Gehrke studied in the French school in Alger in North Africa, and attended high school in Denmark. She described her experiences studying mathematics in these places for a women in maths site:

For the first year, each addition, subtraction, or multiplication problem came with the specification of which base it should be done in (up through 11 - we especially liked when it was base 11 because we might have to use the extra digit we had been allowed to invent). It wasn’t till the start of the second grade that the mathematics teacher told us, by the way, at this time, in this culture, we happen to use base 10. Soon we also had (partial) Cayley tables and specifications of functions and we had to check or complete them to get neutral and absorbant elements, commutativity, and even once associativity! We had to make the functions injective, surjective or bijective, or to compose them. We had Venn diagrams and Cartesian planes and much more. This was the ill-fated Bourbaki mathematics experiment, which soon was phased out of the French national education, but I loved it and the memory of these early primary school classes is what kept me considering mathematics as something beautiful, exciting, and fun.

In high school in Denmark I did math-physics because that was the line with most maths, but mathematics was a semi-arid field not good for anything but a technical handmaiden to physics, only recommended for the most extreme physics enthusiasts. During this time I decided I wanted to be a painter, and that is what I studied in Houston during a year abroad at the end of high school. In Houston, along all my art classes, I did take one mathematics class (mainly because I thought it would be an easy way to learn English…). My teacher happened to be a Polish topologist, who, in an `Intermediate Analysis’ course, taught us point set topology on the real line by the `Texas Method’ (another strange quirk of mathematics education, initiated by R. L. Moore who thought the best way to learn mathematics was to rediscover it for yourself). I loved doing proofs, and before the first year was out, painting had paled and this strange newfound abstract mathematics was all I cared about. I have been doing it ever since and I love it as much as at first sight.

On the Nature of Mathematics: Professor Gehrke spoke about her relationship to mathematics at the Nijmegen inaugural lecture in the Netherlands. Here are some excerpts from that talk.

My passion, and the subject of my oratie, lies within the field of mathematics. It has been my experience that what mathematics is, is not very well understood by most nonmathematicians. While living in New Mexico, I was once asked by an old cowboy and farmer over a can of Coors Light: “So, what kind of figurin’ do you do?”. Most people know what ‘figuring’ or ‘rekenen’ is, but mathematics or ‘wiskunde’ is something quite different. I want to say a few words about mathematics as I see it. Mathematics is a deeply intellectual and creative endeavour. It might involve some calculation but this is certainly not what it is about. Many mathematicians enter the field through the far end of science, but, to me, mathematics is more of a humanity than a science and I claim that there is another way in than through the sciences. Mathematics is 100% human-made and it draws much of its strength, beauty, and character in general from the fact that it does not talk about anything in particular. The work of a mathematician lies in distilling out the essential features of some aspect of experience, and understanding it as deeply and as fully as possible.

Sofya Kovaleskaya, the first woman who was appointed to a professorship in mathematics in Europe (this was at Stockholm University in 1889), drew a parallel between mathematics and poetry. Many have drawn similar parallels between art and mathematics. One important difference between art and mathematics is that the expression remains more intuitive in art and creative work is encoded in highly subjective and personal forms. The reason it is still of wide interest is of course because deep personal experience often is quite universal and because the avoidance of a symbolic language allows the expression to be more direct and thus does not require realisations to become fully conscious. Mathematics chooses the opposite path, opting for a language far removed from the complexities of everyday in order to allow a language with complete precision. This has its definite drawbacks for communication: it limits what you can say and especially who you can say it to, but it also has some advantages for communication: Among mathematicians, the content and nature of a piece of mathematics can be very precisely communicated. As an 18 years old female student of mathematics, I had the experience of stopping by the office of a much older male colleague of my adviser coming from a culture I have little understanding of while on summer holiday, and, within minutes, we could share deep and intricate aspects of a theorem and the beauty of its proof.

This article was written by Vrushali Bokil for the Newsletter/Website Committee. Please email with any comments.