We give an explicit construction of $\eps$-net for the family
of linear threshold functions. More formally, for every $\eps >0$
we give an explicit construction of a set $S \subset \{-1,+1\}^n$ of size $poly(n,1/\eps)$,
such that for any linear threshold function $f: \{-1,+1\}^n \to \{-1,+1\}$ if
$\Pr[f(x)=1] > \eps$ then there exists $x \in S$
with $f(x)=1$. To the best of our knowledge no
such construction was previously known. Our result matches, up to
a polynomial factor in the size of S, the parameters achieved by
a random set.

As a consequence of our techniques we also get the following
result: we give an explicit construction of a set $S \subset \{-1,+1\}^n$
of polynomial size such that for every $x \in \{-1,+1\}^n$ there exists
$s \in S$ with $H(x,s) < n/2 - \sqrt{n \log n}$, where
$H$ is the Hamming distance. This improves on the well known
construction of dual BCH codes that only guarantee covering radius
of $n/2 - \sqrt{n}$.

The construction uses tools such as $k$-wise independent
distributions, random walks on expander graphs and families of
perfect hash functions.

This is a joint work with Yuval Rabani