24
$\begingroup$

I am looking for unbalanced expanders that are "good" and "space-efficient". Specifically, a bipartite left-regular graph $G=(A,B,E)$, $|A|=n$, $|B|=m$, with left degree $d$ is a $(k,\epsilon)$-expander if for any $S \subset A$ of size at most $k$, the number of distinct neighbors of $S$ in $B$ is at least $(1-\epsilon)d|S|$. It is known that the probabilistic method yields such a graph with $d=O(\log (n/k)/\epsilon)$ and $m=O(k \log(n/k)/\epsilon^2)$. However, one needs $O(n d)$ space to store such a graph. Also one also needs to access this storage when doing anything with the graph, which can cost as well. Ideally, one would like an explicit construction. However, as far as I know, known constructions achieve parameters that are still somewhat far from the above (at least provably so).

My question: are there any other constructions, possibly non-explicit, which achieve bounds "closer" to the ones above, yet use "significantly less" than $O(nd)$ space ?

I am looking for answers in any of these three categories: (a) theorems (b) conjectures (c) observations and "war-stories" such as "we did this and it kind of seemed to work (sort of)". I.e., "industrial" expanders are OK. I prefer (a) over (b) and (b) over (c), but beggars cannot be choosers :)

Here is an example of a construction of type (c). Take $d$ random linear hash functions $h_i: [n] \to [m]$ (mod $m$), and connect each vertex $i$ to $h_1(i) \ldots h_d(i)$. Me and my student did some experiments on it, and it seemed to work "fine". Are there any theorems or conjectures about this or related constructions ?

Thanks!

$\endgroup$
  • 2
    $\begingroup$ This is a great question, but there seem to be no answers! Is no-one using expanders other than as a magic wand to make proofs work? I thought some types of Ramanujan graphs were quite simple to construct. $\endgroup$ – András Salamon Sep 13 '10 at 9:55
  • 2
    $\begingroup$ Ramanujan graphs are indeed relatively easy to construct, but they are balanced, i.e., m=n. $\endgroup$ – Piotr Sep 20 '10 at 5:09
  • $\begingroup$ Have you looked at the Guruswami-Umans-Vadhan construction? I am wondering why it does not satisfy your requirement. $\endgroup$ – Zeyu Feb 21 '12 at 8:25
10
$\begingroup$

Eickmeyer and Grohe (2010) prove that your candidate construction can be made explicit: take $d$ somewhat linearly independent linear hash functions $h_1,\dots,h_d$ and connect left vertices $v$ with right vertices $h_1(v),\dots,h_d(v)$. Eickmeyer and Grohe show that this construction gives $(k,\epsilon)$-expanders with left degree $d=k(t-1)/(2\epsilon)$, whenever $t$ is an integer, the left vertex set has size $n=q^t$, the right vertex set has size $m=dq$, and $q>d$ is a prime power. The hash functions $h_1,\dots,h_d$ are chosen in such a way that any $t$ of them are linearly independent.

$\endgroup$
5
$\begingroup$

I thought that having a look at surveys/talks by Avi Wigderson may help with your question. Here are slides from a recent talk: Expander Tutorial, June 2010. Constructions start on page 40.

Regarding the space complexity, I think it can be helpful if you specify the operations you need to perform on the graph. If I am not mistaken, some constructions allow operation like computing neighborhood in logspace.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.