2009-2010 Seminars

Sep
15
2009

Computer Science/Discrete Mathematics Seminar II

Affine Dispersers from Subspace Polynomials
10:30am|S-101

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...

Sep
14
2009

Computer Science/Discrete Mathematics Seminar I

Blackbox Polynomial Identity Testing for Depth 3 Circuits
11:15am|S-101

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...