Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ODED SCHWARTZ:
All reports by Author Oded Schwartz:

TR06-119 | 13th September 2006
Noga Alon, Oded Schwartz, Asaf Shapira

An Elementary Construction of Constant-Degree Expanders

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

TR03-020 | 27th March 2003
Elad Hazan, Shmuel Safra, Oded Schwartz

On the Hardness of Approximating k-Dimensional Matching

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




ISSN 1433-8092 | Imprint