Rekha Thomas: Robert & Elaine Phelps Professor

Robert R. Phelps received his B.A. in Mathematics from the University of California at Los Angeles in 1954 and his Ph.D. from the University of Washington in 1958. After two years at the Institute for Advanced Study in Princeton, and two years on the faculty at the University of California at Berkeley, he joined the UW Mathematics Department in 1962. Phelps was a Visiting Professor at the University of Paris in 1969-70 and at University College London in 1977-78. He served as Chair of our department from 1978 to 1981. He retired in 1996 and was named Professor Emeritus.

Elaine F. Phelps received her B.A. in Slavic Languages and Literature from the University of California at Berkeley and her Ph.D. in Linguistics from the University of Washington. Her non-linguistic efforts were devoted to liberal political activism supporting secular humanism in general and abortion rights in particular.

Together they initiated the Robert R. and Elaine F. Phelps Endowed Fund in 1999. More recently, they supplemented the fund with an additional contribution in 2007, bringing it to the level of an endowed professorship. Rekha Thomas has been selected as the first Robert and Elaine Phelps Endowed Professor of Mathematics for a four-year term.

Rekha Thomas

Rekha Thomas began her research career as a Ph.D. student in the School of Operations Research at Cornell University. Operations Research is a branch of applied mathematics that emerged as a discipline around the 1940s, motivated by the optimization and scheduling requirements of the Second World War. The fathers of the field include some of the great minds of the time such as John von Neumann, Alan Tucker, George Dantzig, and John Nash, all of whom worked in many areas of mathematics. The main subjects of the field are optimization, probability, and statistics, and operations research methods have applications in many areas such as computer science, engineering, economics, biology, finance, manufacturing systems and health care. Thomas specialized in discrete optimization and wrote a thesis on algebraic methods in integer programming which was on the mathematical end of the optimization spectrum. She received her Ph.D. in 1994, got her first job in a math department, and has remained in mathematics ever since. She came to the University of Washington in 2000 after spending the first five years of her career at Texas A&M University.

A Gfan drawing of the Gröbner fan of the ideal generated by f := x5 + y3 + z2 -1, g := x2 + y2 + z -1 and h := x6 + y5 + z3 -1. The lexicographic Gröbner bases that could solve the system f = g = h = 0 (analogs of row-echelon forms for linear systems) correspond to cells hugging the sides of the triangle. They are usually very difficult or impossible to calculate directly. However, if any one cell is known, then a simple homotopy through the fan from that cell to the lex cells can be implemented fast. Gfan performs such tasks.

Thomas’s main research contributions are in discrete optimization and computational algebra. Until 2000 her main focus was on using algebraic methods to gain insight into the structure of integer programs, which are optimization problems where one needs to find non-negative integer solutions to linear systems of equations. We are very far from a complete understanding of integer programs even though very large ones are solved routinely in applications such as airline scheduling and portfolio management. The general integer program was studied intensely in the 1960s and 1970s using methods from linear algebra, number theory and linear programming, but then was deemed too hard without specialization to specific instances. However, theoretical results continued to surface pioneered by researchers in economics, computer science and mathematics such as Herb Scarf, Laci Lovász, Hendrik Lenstra, and Alexander Barvinok. Thomas’s thesis work made a connection between integer programming and methods from computational commutative algebra and algebraic geometry via the notion of a Gröbner basis. This connection has led to several structural results for the general integer program.

Gröbner bases drive many of the algorithms in commutative algebra and algebraic geometry today. These are special generating sets for a polynomial ideal that are to a polynomial equation system what a row echelon form is to a linear equation system. In particular, they solve polynomial systems. The idea of a Gröbner basis can be seen in Paul Gordan’s proof of Hilbert’s basis theorem in 1900 but was formalized only in the 1960s by Bruno Buchberger, working under Wolfgang Gröbner. Gröbner bases carry important invariants of the ideals they come from while facilitating a transformation of the ideal to a simpler (combinatorial) ideal where many of these invariants can be computed more easily. An ideal has only finitely many distinct Gröbner bases, and in many instances it is important to calculate one, several or all Gröbner bases of an ideal. As part of his Ph.D. work at the University of Aarhus done under Thomas’s supervision, Anders Jensen developed a software package called Gfan that can compute all Gröbner bases of an ideal (among other things). This is a major computational development in this area and one that was considered impossible ten years ago. Thomas’s contributions in computational algebra all stem from the theory of Gröbner bases in different guises.

Thomas is currently interested in problems that come from real algebraic geometry and semidefinite programming. The former is the study of real solutions to polynomial inequality systems, while the latter is a branch of optimization theory in the space of symmetric matrices. There is an intriguing connection between these two disparate fields via the fact that polynomial optimization can be approximated by semidefinite programs. Thomas is currently part of an NSF Focused Research Group to work in this area along with Bill Helton and Jiawang Nie at UC San Diego, Bernd Sturmfels at UC Berkeley, and Pablo Parrilo at MIT.