Oregon State University logo

Mathematician to discuss computational models for studying algorithmic complexity

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 the 34th annual Lonseth Lecture.The lecture will take place at 5 p.m. on Friday, April 19, 2019, in the Willamette Room at OSU’s CH2M Hill Alumni Center.

In her talk, “Using abstract mathematical structures to study algorithmic complexity questions,” 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. Gehrke will introduce automata and show how finite monoids, certain very abstract algebraic structures, may be assigned as invariants of automata. Illustrating 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.

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 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. Her main contributions are in Stone duality, a theory which links algebraic and spatial mathematics in the realm of logic. More recently, Gehrke has been working on duality theoretic extensions of the profinite algebraic tools of automata theory and their application in complexity theory.

The Lonseth Lecture Series was established in 1985 to honor Arvid T. Lonseth, Professor Emeritus and former chair of OSU’s Mathematics Department. Lonseth was a superb and devoted scholar and teacher of mathematics. The lecture series is a continuing testimony to his strong interest and commitment to the mathematical education of students, especially undergraduates.

Read more on the 2019 Lonseth Lecture.

Print Friendly, PDF & Email

Comments are closed.