[Lecture 4:1/3] Using Randomness in Computer Science

Name: [Lecture 4:1/3] Using Randomness in Computer Science
Uploaded: 2011-01-31T12:41:32+00:00
Duration: 1 h
Channel: Nicolas Schabanel
Description: Lecture @ MPRI Paris Master of Computer Science (Université Paris Diderot) by Nicolas Schabanel<br />Jan 12, 2011 - 16:15-19:15 - Guessing by sampling<br />• A lot of certificates puts Zero-P in BPP<br />• The presence of a lot of certificates allows linearity testing<br />• Random self-reduction allows linearity self-correcting

Nicolas Schabanel

Lecture @ MPRI Paris Master of Computer Science (Université Paris Diderot) by Nicolas Schabanel Jan 12, 2011 - 16:15-19:15 - Guessing by sampling • A lot of certificates puts Zero-P in BPP • The presence of a lot of certificates allows linearity testing • Random self-reduction allows linearity self-correcting

Catégorie

Recommandations