CS4HS slide show (15mb)
Photos by: Glenn Brookes
“An Outreach Program for HS CS teachers” (L. Blum, T.Cortina)
What we were doing in the 70’s
Professor Lenore Blum
Office: Gates 7105
Phone: (412) 268-8139
Fax: (412) 268-5576
Office: Gates 4113
Photos by: Darrell Sapp
“The Evolving Culture of Computing”
“Diversifying the Images of CS” (C. Frieze, E. Treat)
“From Bits to Bots” (GraceHopper 2002 Proposal )
Women@IT: Graduate Education, The Next Big Thing (GraceHopper 2004 Proposal)
Founding Director, Project Olympus.
In 1989, Steve Smale, Mike Shub and I introduced a theory of computation and complexity over an arbitrary ring or field R. In 1997, along with Felipe Cucker, we published a book, Complexity and Real Computation (Springer-Verlag). From our Introduction:
“The classical theory of computation had its origin in the work of logicians -- of Gödel, Turing, ... , among others -- in the 1930’s. The model of computation developed in the following decades, the Turing machine, has been extraordinarily successful in giving the foundations and framework for theoretical computer science.
“The point of view of this book is that the Turing model (we call it “classical”) with it's dependence on 0’s and 1’s, is fundamentally inadequate for giving such a foundation for modern scientific computation, where most of the algorithms - with origins in Newton, Euler, Gauss, et al. - are real number algorithms.”
Our approach applies to the analysis of algorithms over continuous domains as well as the discrete. The classical theory is recovered if we allow the ring R to be Z2 (the integers mod 2). But now R can also be the real or complex numbers, or any other field. The familiar complexity classes P, NP and fundamental question “does P = NP?” make sense over R and moreover, relate explicitly to fundamental problems in mathematics such as Hilbert’s Nullstellensatz. Thus, we are particularly interested in research concerning the complexity of algorithms that solve systems of polynomial equations.
Transfer Principles for Complexity Theory. A powerful tool of the classical theory is that of reduction: If problem A can be shown to be reducible to problem B, then techniques for solving B can be used to solve A. Classically, A and B are both discrete, i.e. defined over the same domain Z2. But now we have an additional powerful tool, namely that of transfer:
When there was essentially only one model of computation (i.e. over Z2 ), it didn't make sense to transfer complexity results from one domain to another. But now, transfer becomes a real possibility. 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 Z2? (Answer: Yes and essentially yes.)
I am particularly interested in such transfer results and problems that appear in the interface between the discrete and the continuous.
Generalized Algebraic Structures: A Model Theoretical
Ph.D. Thesis, MIT, (1968)
Towards a Mathematical Theory of Inductive Inference,
Information and Control, 125-155, (June 1975) (with M. Blum)
Differentially Closed Fields: A Model Theoretic Tour,
Contributions to Algebra: A Collection of Papers Dedicated to Ellis Kolchin,
(ed. Bass/Cassidy Kovacic), Academic Press, Inc., (Fall 1977)
A Simple Secure Pseudo-Random Number Generator,
SIAM Journal of Computing, Vol.15, No.2, 364-383, (May 1986)
(with M. Blum and M. Shub)
Evaluating Rational Functions : Infinite Precision is Finite Cost and
Tractable on Average
SIAM Journal of Computing, Vol. 15, No.2, 384-398, (May 1986) (with M. Shub)
Towards an Asymptotic Analysis of Karmarkar’s Algorithm,
Information Processing Letters, Vol. 23, No.4, 189-194, (Nov 1986)
A New Simple Homotopy Algorithm for Linear Programming I,
Journal of Complexity, Vol.4, No.2, 124-136, (June 1988)
On a Theory of Computation Over the Real Numbers; NP Completeness,
Recursive Functions and Universal Machines, Bulletin of the AMS,
Vol. 21, No.1, 1-46, (July 1989) (with M. Shub and
Lectures on Theory of Computation and Complexity Over the Reals (or an
Lectures in the Sciences of Complexity, Addison Wesley, 1-47, (1990)
The Gödel Incompleteness Theorem and Decidability Over a Ring,
Proceedings of the Smalefest, (1990) (with
A Theory of Computation and Complexity Over the Real Numbers,
Proceedings of the ICM-90, Springer-Verlag, (1991)
Algebraic Settings for the Problem “P=NP?”,
The Mathematics of Numerical Analysis, Volume 42, Lectures in Applied Mathematics,
pp. 125-144. AMS (1996) (with F. Cucker, M. Shub and
and Real Computation,
Springer-Verlag (1997) (with F. Cucker, M. Shub and
Julia, A Life in Mathematics, reviewed by Lenore Blum, the American
Vol. 105, No.10, pp. 964-972 (December 1998)
After attending public schools in New York City and junior and high school in Caracas, Venezuela, Lenore Blum enrolled in the Architecture Department at Carnegie Institute of Technology in Pittsburgh at the age of 16. During her sophomore year she changed her major to mathematics (her first love), taking electives in sculpture and design. Encouraged by Alan Perlis, Blum enrolled in his experimental computing class. Programs were written in TASS (Perlis' assembly language) on stacks of punch cards and run overnight on an IBM 650 (located in the basement of GSIA, the Graduate School of Industrial Administration). Unbeknownst to the students, Perlis' assignments often contained yet unsolved problems. The year was 1960. In 1961, she moved to Cambridge, Massachusetts and immersed herself in mathematics.
Blum received her Ph.D. in mathematics from M.I.T. in 1968 (the famous year Princeton University first allowed women to enter their graduate program ---and other amazing revolutionaryxeventsx!!!). She then went to UC 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
collaboration with Mike Shub.
She spent part of the next two years in
In 1988 Blum joined the Theory Group of the newly formed International Computer Science Institute
Straddling the historic handover of Hong Kong from
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. Along with Guy Blelloch, she is co-Director on the NSF-ITRxALADDIN Center for ALgorithm ADaptation Dissemination and INtegration. The primary goal of ALADDIN is to improve the process of incorporating powerful algorithms into application domains.
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 reported on this latter work at the International Congress of
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 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 and a member of the President's Diversity Advisory Council.
Blum has also been committed to increasing public understanding of
mathematics, prominent examples of which have been MSRI’s Fermat Fest and
“Conversations” between mathematics teachers and researchers. For the Y2K
meeting of the American Association for the
Advancement of Science (AAAS) in
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-1992). After
representing the AMS at the Pan African Congress of Mathematicians in
In 1979 Blum was elected Fellow of the AAAS. In June 1999, on the 25th
anniversary of the founding the Department of Mathematics and Computer Science
Biographies of Lenore Blum can be found in Notable Women of Mathematics, Women in Mathematics: The Addition of Difference, the Agnes Scott web site, the The MacTutor History of Mathematics archive, the delightful book Women and Numbers for grade school girls, and the new Career Ideas for kids who like math. For more information about Lenore and her family see Pittsburgh Post-Gazette article, Dad, mom join son to form a potent computer science team at CMU.
60th International Conference on Theoretical Computer Science, CityU Hong Kong.