MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

The Unified Theory of Pseudorandomness

Biman Roy
Max-Planck-Institut für Informatik - D1
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Thursday, 28 August 2014
13:30
30 Minutes
E1 4
024
Saarbrücken

Abstract

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.

Contact

Natalia Klein
1000
--email hidden
passcode not visible
logged in users only

Natalia Klein, 08/11/2014 10:42
Natalia Klein, 08/08/2014 12:36 -- Created document.