[Colloquium] REMINDER: Eli Ben-Sasson Talk Today

[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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20090526/10f02f26/attachment.htm