Department of Mathematics

Address: Mathematics 253-37 | Caltech | Pasadena, CA 91125
Telephone: (626) 395-4335 | Fax: (626) 585-1728
Math Home | People | Seminars | Courses | Undergraduate Info | Graduate Program | Positions
Project MATHEMATICS! | Caltech Home

Leonidas Alaoglu Memorial Lecture
in Mathematics
Thursday, May 15, 2014

4:00 p.m.  151 Sloan

Avi Wigderson
Institute for Advanced Studies, Princeton

The power of weakness and randomness
(when you are short on time)

Abstract: Man has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last thirty years has enriched this study considerably. I'll describe two main aspects of this research on randomness, demonstrating respectively its power and weakness for making algorithms faster. I will also address the rose of randomness in other computational settings, such as memory-bounded computation and probabillistic and zero-knowledge proofs.

No special background will be assumed.

Avi Wigderson did his undergraduate studies at the Technion in Haifa, Israel, graduating in 1980, graduate study at Princeton University. He received his Ph.D. in 1983 for work in computational complexity under Richard Lipton. After positions at UC Berkeley, the IBM Almaden Research Center in San Jose, California, and the MSRI, he joined the faculty of Hebrew University in 1986. In 1999 he also took a position at IAS, and in 2003 he gave up his Hebrew University position to take up full-time residence at the IAS. Wigderson received the Nevanlinna Prize in 1994 for his work on computational complexity. Along with Omer Reingold and Salil Vadhan he won the 2009 Gödel Prize for work on the zig-zag product of graphs, a method of combining smaller graphs to produce larger ones used in the construction of expander graphs. He was elected to the National Academy of Sciences in 2013.

dailybar.gif (67 bytes)

The Leonidas Alaoglu Memorial Lecture was established by friends and family of the late Leonidas Alaoglu in recognition of his great talents, distinguished contributions to mathematics, and long friendship with Caltech. The Institute is privileged to honor his memory with a lecture each year by an outstanding mathematician.

  | © California Institute of Technology | Questions?  scroomes @