简介: |
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 Combinatorics and Graph Theory, Lower Bound Techniques, Data Structures, Algorithms, Probabilistic Algorithms, Circuit Complexity, Introduction to Complexity Theory, Randomness in Computation, The Probabilistic Method, Proof Techniques in Complexity Theory. |
