Dr. Shmuel Winograd is a pioneer in the field of computational complexity – a branch of theoretical computer science concerned with the work necessary to do a given computation. In his research on the lower bounds of the time required to do a computation, he has achieved a number of outstanding results. Most notably, Dr. Winograd has formulated and proved several theorems giving the minimum amount of work required for performing addition and multiplication, regardless of how the numbers are represented. Also, his finding that multiplication can be done faster than addition if the appropriate number representation is chosen, have upset several widely held views to the contrary.
Because his results apply to any kind of logical device or arithmetic unit design using a non-redundant number scheme, they provide a fundamental limit to the performance of any adder against which a particular design can be evaluated.
Along with these achievements, Dr. Winograd has established lower bounds on how many arithmetic operations are required for evaluating polynomials, for finding roots of functions, and for performing certain matrix calculations. In some cases, these results have led to improved algorithms, in others; they have shown that existing algorithms cannot be improved.
Dr. Winograd’s work has given enormous support to the idea that rigorous mathematical analysis can permit the discovery of lower bounds for the number of steps necessary in wide classes of computations, thus providing a scientific basis for the search for better algorithms for such computations.
Dr. Winograd was born 4 January 1936 in Tel Aviv, Israel. He received his BS and MS degrees in Electrical Engineering in 1959 from the Massachusetts Institute of Technology, and his PhD in Mathematics from New York University in 1968. He worked at MIT as a research assistant from 1959 to 1961 when he joined IBM as a research staff member. He became director of the Mathematical Sciences Department at the Thomas J. Watson Research Center in Yorktown Heights, N.Y., in 1970. Two years later, he was named IBM Fellow, the company’s highest recognition for technical accomplishments, having already received an IBM Corporate Outstanding Contributions Award in 1968 for his work on the minimum time for arithmetic operations.
He served as Mackay Lecturer at the University of California at Berkeley in 1967–1968, and as Professor of Computer Science at Technion in Israel, where he is a permanent visiting professor.
Dr. Winograd was elected to Sigma Xi, and Tau Beta Pi, and is a Fellow of the IEEE. His hobbies include bridge, backpacking, and bicycling. He lives with his wife, Elaine, and their two children, Daniel and Sharon, in Scarsdale, New York.
