Emmy Noether Lectures

2002 Lecturer: Lenore Blum

The classical (Turing) theory of computation has been extraordinarily successful in providing the foundations and framework for theoretical computer science. Yet its dependence on 0’s and 1’s is fundamentally inadequate for providing such a foundation for modern scientific computation where most algorithms – with origins in Newton, Euler, Gauss, et al. – are real number algorithms.

In 1989, Mike Shub, Steve Smale and I introduced a theory of computation and complexity over an arbitrary ring or field R. If R is Z² = {0,1}, the classical computer science theory is recovered. If R is the field of real numbers, Newton’s algorithm, the paradigm algorithm of numerical analysis, fits naturally into our model of computation.

Complexity classes P, NP and the fundamental question “Does P= NP?” can be formulated naturally over an arbitrary ring R. The answer to the fundamental question depends on the complexity of deciding feasibility of polynomial systems over R. When R is Z², this becomes the classical satisfiability problem of Cook-Karp-Levin. When R is the field of complex numbers, the answer depends on the complexity of Hilbert’s Nullstellensatz.

The notion of reduction between problems (e.g. between traveling salesman and satisfiability ) has been a powerful tool in classical complexity theory. But now, in addition, the transfer of complexity results from one domain to another becomes a real possibility. For example, we can ask: Suppose we can show P = NP over the complex numbers (using all the mathematics that is natural here). Then can we conclude that P=NP over another field such as the algebraic numbers or even over Z²? (Answer: Yes and essentially yes.)

In this talk, I will discuss these results and indicate how basic notions from numerical analysis such as condition, round off and approximation are being introduced into complexity theory, bringing together ideas germinating from the real calculus of Newton and the discrete computation of computer science.

Brief Biography

Lenore Blum received her Ph.D. in mathematics from the Massachusetts Institute of Technology in 1968 (the same year Princeton University first allowed women to enter their graduate program). She then went to the University of California at Berkeley as a Postdoctoral Fellow and Lecturer in Mathematics. In 1973 she joined the faculty of Mills College where in 1974 she founded the Mathematics and Computer Science Department (serving as its Head or co-Head for 13 years). In 1979 she was awarded the first Letts-Villard Chair at Mills.

An NSF Career Advancement Award in 1983 enabled Blum to embark on a longtime scientific collaboration with Mike Shub. She spent part of the next two years in New York as Visiting Professor at the CUNY Graduate Center and returned to New York in 1987 as Visiting Scientist at the IBM T.J. Watson Research Center.

In 1988 Blum joined the Theory Group of the newly formed International Computer Science Institute (ICSI) in Berkeley. From 1992 to 1996 she also served as Deputy Director of the Mathematical Sciences Research Institute (MSRI) in Berkeley.

Straddling the historic handover of Hong Kong from Britain to China on July 1, 1997, Blum’s two years, 1996-1998, at the City University of Hong Kong (CityU) were productive ones. While Visiting Professor of Mathematics and Computer Science at CityU, she completed her book, Complexity and Real Computation (Springer), with colleagues and co-authors Felipe Cucker, Mike Shub and Steve Smale.

In the fall of 1999, Blum joined the faculty of the School of Computer Science at Carnegie Mellon University where she is Distinguished Career Professor of Computer Science and co-Director of ALADDIN: A Center for ALgorithm, ADaption, Dissemination and INtegration (funded by the National Science Foundation).

Lenore Blum’s research, from her early work in model theory and differential fields (logic and algebra) to her more recent work with Shub and Smale in developing a theory of computation and complexity over the real numbers (mathematics and computer science), has focused on merging seemingly unrelated areas. In 1990 she was invited to talk on this latter work at the International Congress of Mathematicians in Kyoto. She has also given numerous invited talks at international conferences in the United States, Europe, China, Southeast Asia, the former Soviet Union, Latin America and Africa.

Blum is well known for her work in increasing the participation of girls and women in mathematics and scientific fields. She was instrumental in founding the Association for Women in Mathematics (serving as its third President from 1975 to 1978), the Math/Science Network and its Expanding Your Horizons conferences for high school girls (serving as co-Director from 1975 to 1981) and served as co-PI for the Mills Summer Mathematics Institute for undergraduate women. At Carnegie Mellon she has been faculty advisor to the Women@SCS.

Throughout her career, Blum has been an active member of the professional societies. She served on the Council and as Vice President of the American Mathematical Society (1990-92). After representing the AMS at the Pan African Congress of Mathematicians in Nairobi, (Summer 1991), she became committed to building links between the American and African mathematics communities. She served as Chair of the AAAS Mathematics Section for the years 1998-99.

In 1979 Blum was elected Fellow of the American Association for the Advancement of Science. In June 1999, on the 25th anniversary of the founding the Department of Mathematics and Computer Science at Mills College, she was awarded an honorary Doctor of Laws degree.

Biographies of Lenore Blum can be found in Notable Women of Mathematics (Charlene Morrow and Teri Perl), Women in Mathematics: The Addition of Difference (Claudia Henrion) and the delightful book Women and Numbers (Teri Perl) for grade school girls. Her history of the first 20 years of the AWM can be found on the AWM website: www.awm-math.org

Lenore is married to Manuel Blum and mother of Avrim Blum, both also MIT alumni and professors of Computer Science at Carnegie Mellon.