We generalize the construction of Gabber and Galil
to essentially every unimodular matrix in $SL_2(\Z)$. It is shown that
every parabolic
or hyperbolic fractional linear transformation explicitly
defines an expander of bounded degree
and constant expansion. Thus all but a vanishingly small fraction
of unimodular matrices define expanders.

more >>>

We give a polynomial time approximation scheme (PTAS) for dense
instances of the NEAREST CODEWORD problem.

more >>>

We suggest a candidate one-way function using combinatorial
constructs such as expander graphs. These graphs are used to
determine a sequence of small overlapping subsets of input bits,
to which a hard-wired random predicate is applied.
Thus, the function is extremely easy to evaluate:
all that is needed ... more >>>