Space efficient "industrial" unbalanced expanders

Question

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!

Answer 1

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.

Answer 2

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.