Explicit Construction of a Small $\epsilon$-Net for Linear Threshold Functions
Yuval Rabani, Amir Shpilka · SIAM Journal on Computing · 2010
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 n and in $\frac{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. As a corollary we also construct subsets of the binary cube that have size polynomial in n and a covering radius of $\frac{n}{2}-c\sqrt{n\log n}$ for any constant c. This improves upon the well-known construction of dual BCH codes that guarantee only a covering radius of $\frac{n}{2}-c\sqrt{n}$.