We describe a short and easy to analyze construction of constant-degree expanders. The construction relies on the replacement-product, which we analyze using an elementary combinatorial argument. The construction applies the replacement product (only twice!) to turn the Cayley expanders of \cite{AR}, whose degree is polylog n, into constant degree expanders. more >>>

We study bounded degree graph problems, mainly the problem of k-Dimensional Matching \emph{(k-DM)}, namely, the problem of finding a maximal matching in a k-partite k-uniform balanced hyper-graph. We prove that k-DM cannot be efficiently approximated to within a factor of $ O(\frac{k}{ \ln k}) $ unless $P = NP$. This ... more >>>