דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
אלי בן-ששון (מדעי המחשב, הטכניון)
event date icon
יום רביעי, 13.05.2009, 15:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
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.

Joint work with Swastik Kopparty.