Avi Wigderson |
|
Avi Wigderson Professor at the School of Mathematics, Institute for Advanced Study. He obtained his B.Sc. in Computer Science from the Technion in 1980, and his Ph.D. from Princeton in 1983. He was a member of the faculty at the Hebrew University in Jerusalem from 1986-2003, and is currently a member of the Mathematics Faculty at the Institute for Advanced Study at Princeton. His research interests lie principally in Complexity Theory, Algorithms, Randomness, and Cryptography. His awards include the Yoram Ben-Porat Presidential Prize for Outstanding Researcher, and the Nevanlinna Prize (2004).
|
|
|
The Art of Reduction: Abstract |
|
Everyone is familiar with NP-completeness, and the basic idea that appropriate reductions can tie together seemingly unrelated computational problems. The last couple of decades have seen an incredible growth and sophistication in utilizing reductions and completeness. These tie together seemingly unrelated computational notions, models and even whole subareas of computer science. I will survey such results, and their general and diverse consequences.
|
|
|
|
