Theory Day March 2, 2009 - Amir ShpilkaExplicit construction of a small epsilon-net for linear threshold functions Abstract: We give explicit constructions of epsilon nets for linear threshold functions on the binary cube and on the unit sphere. The size of the constructed nets is polynomial in the dimension and 1/epsilon. To the best of our knowledge no such constructions were previously known. Our results match, up to the exponent of the polynomial, the bounds that are achieved by probabilistic arguments. Our work is motivated by questions of constructing interesting geometric objects, known to exist via probabilistic arguments. We will discuss some of this motivation. This is joint work with Yuval Rabani |