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.

Biography of Prof. Avi Wigderson:

Born: September 9, 1956

Marital Status: Married, three children

Current Address: Institute for Advanced Study, Einstein Drive, Princeton, NJ 08540, USA.

Research Interests: Complexity Theory, Parallel Computation, Combinatorics and Graph Theory, Combinatorial Optimization Algorithms, Randomness and Cryptography, Distributed and Neural Networks.

Education

1983 — Ph.D in Computer Science, Princeton University, Department of Electrical Engineering and Computer Science.

Thesis: Studies in Combinatorial Complexity

Advisor: Prof. R.J. Lipton

1982 — M.A in Computer Science, Princeton University.

1981 — M.S.E in Computer Science, Princeton University.

1980 — B.Sc Summa cum laude in Computer Science, Technion -Israel Institute of Technology.

Honors

Conant Prize, 2008.

Gibbs lecture, San Diego, 2008.

ICM plenary lecture, Madrid, 2006.

The Yoram Ben-Porat Presidential Prize for outstanding Researcher

Nevanlinna Prize, 1994.

Invited speaker at the International Congress of Mathematicians , Zurich, Switzerland, 1994.

Invited speaker at the International Congress of Mathematicians , Kyoto, Japan 1990.

Bergman Fellowship, 1989.

Alon Fellowship, 1986–1989.

IBM Graduate Fellowship, Princeton University, 1982–1983.

President’s List of Excellence, The Technion, 1977–1980.

Employment

July, 1999–present Professor, School of Mathematics, Institute for Advanced Study, Princeton, NJ.

1991–July, 2003 Professor, Computer Science Institute, Hebrew University, Jerusalem.

1995–1996 Visiting Professor, Institute for Advanced Study, Princeton, and Department of Computer Science, Princeton University.

1993–95Chairman,ComputerScienceInstitute,HebrewUniversity,Jerusalem.

1990–92 Visiting Associate Professor, Department of Computer Science, Princeton University.

1987–92 Associate Professor (withtenure), Department of Computer Science, Hebrew University, Jerusalem.

1986–87 Senior Lecturer, Department of Computer Science, Hebrew University, Jerusalem.

1985–86 Fellow, Mathematical Sciences ResearchInstitute, Berkeley, California.

1984–85 Visiting Scientist, IBM Research, San Jose, California.

1983–84 Visiting Assistant Professor, Department of Computer Science, U.C. Berkeley, California.

Teaching