The power and weakness of randomness, when you are short on time
Duration: 1 hour 7 mins 49 secs
Share this media item:
Embed this media item:
Embed this media item:
About this item
| Description: |
Professor Avi Wigderson (Institute for Advanced Study Princeton)
Monday 28 March 2011, 17:00-18:00 Rothschild Lecture |
|---|
| Created: | 2011-03-30 15:12 | ||||
|---|---|---|---|---|---|
| Collection: |
Discrete Analysis
Rothschild Seminars |
||||
| Publisher: | Isaac Newton Institute | ||||
| Copyright: | Avi Wigderson | ||||
| Language: | eng (English) | ||||
| Keywords: | randomness; pseudorandomness; derandomization; P vs. NP; efficient computation; computational complexity; | ||||
| Credits: |
|
||||
| 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 efficient. Time permitting, I will address the role of randomness in other computational settings, such as space bounded computation and probabilistic and zero-knowledge proofs. |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 640x360 | 1.84 Mbits/sec | 940.87 MB | View | Download | |
| WebM | 640x360 | 1.42 Mbits/sec | 715.27 MB | View | Download | |
| Flash Video | 484x272 | 568.76 kbits/sec | 282.51 MB | View | Download | |
| iPod Video | 480x270 | 506.27 kbits/sec | 251.47 MB | View | Download | |
| MP3 | 44100 Hz | 125.02 kbits/sec | 61.90 MB | Listen | Download | |
| Auto * | (Allows browser to choose a format it supports) | |||||