Is It Really Zero?

Middlebury College
Department of Computer Science Seminar

Is It Really Zero?

Chee K. Yap
Courant Institute, NYU

The Zero Problem asks whether a given numerical expression, such as , is equal to zero. In fact, there is a different Zero Problem for each clearly defined class of numerical expressions. (For example, the previous expression might be an instance of the class of radical expressions, which involve integers, the four arithmetic operations and square-roots.) The ability to decide zero can greatly simplify the programmer's task of achieving robust algorithms. It is tempting to think that if we can approximate each operation in the expression to sufficiently high precision, then we can surely discover the answer. A little thought shows the inadequacy of this approach.

In this talk, we show hope to achieve three goals:

• Show why Zero Problems are at the heart of some difficult computational problems in many fields, from computational geometry to transcendental number theory.
• Show how to solve the Zero Problem in the algebraic case.
• Give a demonstration of our Core Library, a software package in C++ language.

Chee Keng Yap is Professor of Computer Science at the Courant Institute of Mathematical Sciences, New York University. His research interests include computational geometry, algebraic and topological computation, visualization and algorithmic robotics. Since the early 90s, he has been interested in numerical non-robustness issues at the interface between numerical, geometric algebraic and topological computation. Yap was born in Singapore and educated in the Boys' Wing, Royal Military College in Malaysia. He received a double S.B. degree (Math and Comp.Sci) from M.I.T. in 1975, and a Ph.D. (Comp.Sci) from Yale in 1980. His book Fundamental Problems in Algorithmic Algebra (Oxford University Press, 2000) is often cited by researchers in robust computation (a preprint version is available from http://cs.nyu.edu/yap/bks/).

Friday, April 6, 2007
12:30 p.m. to 1:15 p.m.
McCardell Bicentennial Hall 538

Lunch will be provided at 12:15 p.m.

All are welcome to attend

This event is sponsored by the Computer Science Department.