PIMS/UBC Distinguished Colloquium: Avi Wigderson (IAS Princeton)

  • Date: 03/08/2013
  • Time: 15:00

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. 


University of British Columbia


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


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.


Watch this lecture on Mathtube.org


Lecture begins at 3:00 pm in MATX 1100, preceded by a reception in MATH 125 at 2:30 pm