PIMS/UBC Distinguished Colloquium: Avi Wigderson (IAS Princeton)
Topic
Speakers
Details
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 role of randomness in other computational settings, such as space bounded computation and probabilistic and zero-knowledge proofs.
Additional Information
Avi Wigderson, IAS Princeton
Avi Wigderson is a widely recognized authority in theoretical computer science. His main research area is computational complexity theory. This field studies the power and limits of efficient computation and is motivated by such fundamental scientific problems as: Does P=NP? Can every efficient process be efficiently reversed? Can randomness enhance efficient computation? Can quantum mechanics enhance efficient computation? He has received, among other awards, both the Nevanlinna Prize and the Gödel Prize.