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

Avi Wigderson
Fri, Mar 8, 2013
Department of Mathematics, UBC
PIMS/UBC Distinguished Colloquium
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.