Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > EXPANSION:
Reports tagged with expansion:
TR00-020 | 27th March 2000
Oded Goldreich, Dana Ron

#### On Testing Expansion in Bounded-Degree Graphs

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

TR05-112 | 12th September 2005
Eran Ofek

#### On the expansion of the giant component in percolated $(n,d,\lambda)$ graphs

Revisions: 1

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

TR18-078 | 23rd April 2018
Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra

#### Small Set Expansion in The Johnson Graph

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

ISSN 1433-8092 | Imprint