Title: The Art of Reduction

Name: Avi Wigderson

              Institute for Advanced Study, Princeton
Time: October 13th (Monday) 11:15-12:00
Location: Lecture Hall, FIT Building, Tsinghua University
Host Unit: ITCS, Tsinghua University


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

Research Interests: Complexity Theory, Parallel Computation, CombinatorITCS 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
  2008 Conant Prize
  2008 Guggenheim Fellowship
  2006 Fellow, Association for Computing Machinery
  1994 Donald E. Knuth Prize
  1994 Member, US National Academy of Sciences
  1990 Fellow, American Academy of Arts and Sciences
  1989 A.M. Turing Award
  1986-1989 Member, Academia Sinica
  1982-1983 Pan Wen-Yuan Research Award
  1977-1980 Doctor of Science, Honoris Causa, City University of Hong Kong


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每95 Chairman,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

CombinatorITCS 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.

Back