Shmuel Winograd

Shmuel Winograd
Tel Aviv, Israel


Shmuel Winograd was born on January 4th, 1936 in Tel Aviv, Israel. He received BS and MS degrees in Electrical Engineering in 1959 from MIT, and a PhD in Mathematics from New York University in 1968. He joined IBM as a research staff member in 1961 and was named IBM Fellow, the company's highest recognition for technical accomplishments in 1972.

He's a pioneer in the field of computational complexity, a branch of theoretical computer science concerned with the work necessary to do a given computation. He developed and proved several theorems giving the minimum amount of work to perform addition and multiplication, regardless of the representation of the numbers. He also discovered that multiplication can be done faster than addition if the numbers are represented correctly, a shocking breakthrough. He also established lower bounds on how many arithmetic operations are required for polynomial evaluations, finding roots of functions, and performing certain matrix calculations. These led to improved algorithms or proved that existing algorithms cannot be improved.

Further Reading