[Colloquium] Talk by Lenore Blum on Monday, May 12, 2003

[Margery Ishmael]

------------------------------------------------------------------------

DEPARTMENT OF COMPUTER SCIENCE
& TOYOTA TECHNOLOGICAL INSTITUTE

Monday, May 12, 2003 at 2:30 pm in Ryerson 251

------------------------------------------------------------------------

Speaker: Lenore Blum

From: Carnegie Mellon University

Title: "Computing over the Reals: Where Turing Meets Newton"

Abstract:

The classical (Turing) theory of computation has been extraordinarily 
successful in providing the foundations and framework for theoretical 
computer science. Yet it?s 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_2 = {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_2, 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 discrete 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 
between domains (discrete and continuous) becomes a real possibility.

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. Speaker's Homepage: http://www-2.cs.cmu.edu/~lblum/

*The talk will be followed by refreshments in Ryerson 255*

Hosts: Stephen Smale & Partha Niyogi