Improved small-set expansion from higher eigenvalues

Details Improved small-set expansion from higher eigenvalues Improved small-set expansion from higher eigenvalues

2012-04-20

arxiv.org/abs/1204.4688v1

Computer Science

Data Structures and Algorithms

Scientific paper

Consider an irreducible reversible Markov chain on state space $V$, with $|V| = n$ and invariant distribution $\pi$. Let $0 = \lambda_1 \leq \lambda_2 \leq ...\lambda_n \leq 2$ be the eigenvalues of its Laplacian operator. We give a simple spectral condition under which there exists a unit vector $f \in L^2(V,\pi)$ with $\|f\|_1^2 \leq \delta$ and $\la f, Lf \ra \leq \eps$. (Using a standard Cheeger inequality, this implies the existence of a set $S \subseteq V$ with measure at most $O(\delta)$ and expansion at most $O(\sqrt{\eps})$.) As a consequence we show that for any $k \in [n]$ and small $\alpha > 0$, there is always a set $S \subseteq V$ with measure at most $O(k^{-1+\alpha})$ and expansion at most $\sqrt{\lambda_k \log_k n}... O(\alpha^{-1/2})$. This essentially resolves a question of Arora, Barak, and Steurer, who obtained the same result with $O(k^{-1/100})$ in place of $O(k^{-1+\alpha})$.

Affiliated with

Also associated with

No associations

Rating

Improved small-set expansion from higher eigenvalues does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved small-set expansion from higher eigenvalues, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved small-set expansion from higher eigenvalues will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-6136