Type of Talk: UTCS Distinguished Lecture Series

Speaker/Af

filiation: Avi Wigderson/Institute for Advanced Study

Date/Time: Frida

y, April 23, 2010, 1:00 p.m.

Location: ACES 2.302

Host: David

Zuckerman

Talk Title: Computational Capacity: The power and weakness o

f randomness, when you are short on time

Talk 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 st

udy considerably. I''ll describe two main aspects of this research on rando

mness, demonstrating respectively its power and weakness for making algori

thms efficient. Time permitting, I will address the role of randomness in

other computational settings, such as space bounded computation and probab

ilistic and zero-knowledge proofs.

Speaker Bio:

Avi Wigderson is

a Professor with the Institute of Advanced Study, School of Mathematics at
Princeton University. His main research interests are randomness and comp

utation, algorithms and optimization, complexity theory, circuit complex

ity, proof complexity, quantum computation and communication, and cyptog

raphy and distributed computation. He received the Nevanlinna prize in 199

4, and the Gödel Prize in 2009 for outstanding paper in theoretical compu

ter science. Professor Wigderson received his Ph.D. from Princeton Univers

ity.