The FT-Mollification Method

January 11, 2011
Daniel Kane | Harvard University

We discuss a recent technique for dealing with k-independent families of random variables. The basic idea in showing that F is fooled by k-independence is to approximate by a smooth function F~ and note that the expectation of the Taylor polynomials are determined by k-independence. F~ can be obtained by convolving F with the Fourier transform of a compactly supported bump function. We discuss the development of this technique, leading up to the proof that limited independence fools degree 2 polynomial threshold functions.

Speaker Details

Daniel Kane is currently a graduate student in mathematics at Harvard University. Although his primary interests are in number theory and theoretical computer science, he is more generally interested in problem solving and has done work in a number of other fields including ergodic theory, combinatorial game theory, spherical designs, and combinatorics.