Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:The Unified Theory of Pseudorandomness
Speaker:Biman Roy
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 28 August 2014
Duration:30 Minutes
Building:E1 4
Pseudorandomness is the main approach of addressing, to what extent randomness is really necessary some of the main areas in computer science like algorithm design, cryptography, coding theory, network design and interactive proofs. Pseudorandomness is the theory of efficiently generating objects that "look random" to certain classes of algorithms, despite being constructed with little or no randomness. Due to their fundamental nature and wide applicability, pseudorandom objects like list decoding, randomness extractors, expander graphs, and pseudorandom generators have been the center of a large body of research. Until recently, these areas of research were largely distinct. While it was common to use one of them as a tool to construct another (e.g., expander graphs were used to construct error-correcting codes), researchers have recently discovered that these objects are almost the same when interpreted appropriately. In the talk we will see the connections between all of these objects,  how they can all be cast within a single "list-decoding framework" that brings out both their similarities and differences.
Name(s):Natalia Klein
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Natalia Klein, 08/11/2014 10:42 AM
  • Natalia Klein, 08/08/2014 12:36 PM -- Created document.