All reports by Author Oded Schwartz:

__
TR06-119
| 13th September 2006
__

Noga Alon, Oded Schwartz, Asaf Shapira#### An Elementary Construction of Constant-Degree Expanders

__
TR03-020
| 27th March 2003
__

Elad Hazan, Shmuel Safra, Oded Schwartz#### On the Hardness of Approximating k-Dimensional Matching

Noga Alon, Oded Schwartz, Asaf Shapira

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.

Elad Hazan, Shmuel Safra, Oded Schwartz

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 >>>