[Colloquium] Talk by Eli Ben-Sasson, Technion, on May 26, 2009

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, May 26, 2009
Time: 3:00 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:	Eli Ben-Sasson

From:		Technion

Website: 	 http://www.cs.technion.ac.il/~eli/

Title:     Affine Dispersers from Subspace Polynomials

Abstract:   An affine disperser over a field F for sources of  
dimension d is a  function f: F^n -> F that is nonconstant (i.e.,  
takes more than one value) on inputs coming from a d-dimensional  
affine subspace of F^n.

Affine dispersers have been considered in the context of deterministic  
extraction of randomness from structured sources of imperfect  
randomness, and in particular, generalize the notion of dispersers for  
bit-fixing sources. Previously, explicit constructions of affine  
dispersers were known for every d=\Omega(n), due to [Barak, Kindler,  
Shaltiel, Sudakov and Wigderson] and [Bourgain]. (The latter in fact  
gives stronger objects called affine extractors).

In this work we give the first explicit affine dispersers for  
sublinear dimension. Specifically, our dispersers work even when d>  
n^{4/5}.
The main novelty in our construction lies in the method of proof,  
which relies on elementary properties of subspace polynomials. In  
contrast, the previous works mentioned above relied on sum-product  
theorems for finite fields.

Time permitting we shall discuss recent work which shows that some of  
our constructions are in fact affine extractors, i.e., the output of f  
is almost uniformly distributed on F.

Joint work with Swastik Kopparty.

Refreshments will be served prior to the talk in RY 255.