2009-2010 Seminars

An affine disperser over F_2^n for sources of dimension d is a function f: F_2^n --> F_2 such that for any affine subspace S in F_2^n of dimension at least d, we have {f(s) : s in S} = F_2 . Affine dispersers have been considered in the context of...

I will talk about a recent work describing a deterministic polynomial time algorithm for blackbox identity testing for depth three circuits with bounded top fanin over the field of rational numbers. This resolves a question posed by Klivans and...