Oded Goldreich, Dana Ron

We consider testing graph expansion in the bounded-degree graph model.

Specifically, we refer to algorithms for testing whether the graph

has a second eigenvalue bounded above by a given threshold

or is far from any graph with such (or related) property.

We present a natural algorithm aimed ... more >>>

Eran Ofek

Let $d \geq d_0$ be a sufficiently large constant. A $(n,d,c

\sqrt{d})$ graph $G$ is a $d$ regular graph over $n$ vertices whose

second largest eigenvalue (in absolute value) is at most $c

\sqrt{d}$. For any $0 < p < 1, ~G_p$ is the graph induced by

retaining each edge ...
more >>>

Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra

This paper studies expansion properties of the (generalized) Johnson Graph. For natural numbers

t < l < k, the nodes of the graph are sets of size l in a universe of size k. Two sets are connected if

their intersection is of size t. The Johnson graph arises often ...
more >>>