Home | Main Street Property Services, Inc.
Main Street Property Services, Inc. is a full-service retail real estate company, specializing in development, added value leasing, management, marketing and the revitalization of shopping centers and downtown shopping districts.
3000 Broadway is a mixed-use development featuring 1,480-8,320 Sq.Ft of retail space and 127 residential units in one of Oakland most desirable neighborhoods.
By focusing exclusively on retail, Main Street Property Services, Inc. provides clients with a competitive edge.
Main Street Property Services has been renovating, re-merchandising retail property since 1997.


Megamart Various Artists Is It…Dead?
Collaboration between Crash Rawk, Role Play, and Sub Pop. Comp directed by Dylan Kerbrat.
Homo-Eradicus - "The King's Bequest "
Hollywood Mike Miranda - "Grass on the Field"
Teen Cthulhu - "Brig. Song for a Dead Horse"
Bloodhag - "Kurt Vonnegut Jr. (1922-)"
Old Rawle - "Responsive Equipment"
Botch - "Hutton's Great Heat Engine"
Akimbo - "The Lotus Eaters"
Raft Of Dead Monkeys - "Wwiv"


Siamo specializzati Come Tirare Disconnect produttori e fornitori / fabbrica dalla Cina. Come Tirare Disconnect all'ingrosso con alta qualità a basso prezzo / a buon mercato, una delle Come Tirare Disconnect marchi leader in Cina, Timeplex Industrial Limited.
Wholesale Come Tirare Disconnect from China, Need to find cheap Come Tirare Disconnect as low price but leading manufacturers. Just find high-quality brands on Come Tirare Disconnect produce factory, You can also feedback about what you want, start saving and explore our Come Tirare Disconnect, We'll reply you in fastest.


text:
\section{Introduction}\label{sec:intro}

In coding theory, the problem of \em list-decoding \em is to return all
codewords that are close to some received word $z$; in \em algorithmic
list-decoding, \em the problem is to do so efficiently.  While there has been a
great deal of progress on algorithmic list-decoding in the past two
decades~\cite{GS-list-dec,PV05,GR06a,GW17,GX12,GX13,Kop15,GK14,HRW19,KRSW18},
most work has relied crucially on algebraic constructions, and thus it is interesting to develop combinatorial tools to construct efficiently list-decodable codes with good parameters.

In this work, we consider the question of list-decoding \em expander codes, \em introduced by Sipser and Spielman in \cite{SS96}.
We define expander codes formally in Section~\ref{sec:prelim}, but briefly, the expander code $\ensuremath{\mathcal{C}}(G, \ensuremath{\mathcal{C}}_0)$ is a linear code constructed from a $d$-regular bipartite expander graph $G$ and a linear inner code $\ensuremath{\mathcal{C}}_0 \subseteq {\mathbb F}_2^d$.  A codeword of $\ensuremath{\mathcal{C}}(G, \ensuremath{\mathcal{C}}_0)$ is a vector in ${\mathbb F}_2^{E(G)}$ which is a labeling of edges in $G$.  The constraints are that, for each vertex $v$ of $G$, the labels on the $d$ edges incident to $v$ form a codeword in $\ensuremath{\mathcal{C}}_0$.

Expander codes are notable for their very efficient unique
decoding algorithms~\cite{SS96, Z01,LMSS01,SR03,AS05,BZ02,BZ05,BZ06, RS06, HOW13}.
However, very little is known about the algorithmic list-decodability of expander codes, and it is an open problem to find a family of expander codes that admit fast linear-time list-decoding algorithms with good parameters.
Motivated by this open problem, our main contribution is a linear-time algorithm for list decoding expander codes \em from erasures. \em

\paragraph{Erasure list-decoding.} Erasure-list-decoding is a variant of list-decoding where the received word $z$ may have some symbols which are ``$\bot$'' (erasures), and the goal is to recover all codewords consistent with~$z$.  More formally, let $\ensuremath{\mathcal{C}} \subseteq {\mathbb F}_2^N$ be a binary code of length $N$.
For $z \in ({\mathbb F}_2 \cup \bot)^N$, define
\[\mathrm{List}_{\ensuremath{\mathcal{C}}}(z) := \left\{ c \in \ensuremath{\mathcal{C}} \,:\, c_i = z_i \text{ whenever } z_i \neq \bot \right\}. \]
We say that $\ensuremath{\mathcal{C}}$ is \em erasure-list-decodable \em from $e$ erasures with list size $L$ if for any $z \in ({\mathbb F}_2 \cup \{\bot\})^N$ with at most $e$ symbols equal to $\bot$, $|\mathrm{List}_{\ensuremath{\mathcal{C}}}(z)| \leq L$.

Erasure list-decoding has been studied before~\cite{Gur03,GI02,GI04a,GO06,DJX14,HW18,BDT18}, motivated both by standard list-decoding and as an interesting combinatorial and algorithmic question in its own right.
It is known that the erasure-list-decodability of a linear code is precisely captured by its generalized distances.  The \em $r$'th (relative)\footnote{Throughout this paper, we will work with the relative generalized distances (that is, measured as a fraction of coordinates).  We will omit the adjective ``relative'' to describe these quantities in the future.}  generalized  distance \em $\delta_r$ of a linear code $\ensuremath{\mathcal{C}} \subseteq {\mathbb F}_2^N$ is the minimum fraction of coordinates   which are not identically zero in an $r$-dimensional subspace of $\ensuremath{\mathcal{C}}$, that is,
\[ \delta_r = \frac{1}{N} \min_{V} \big|\inset{ i \,:\, \exists v\in V, v_i \neq 0 }\big|,\]
where the minimum is taken over all linear subspaces $V \subseteq \ensuremath{\mathcal{C}}$ of dimension $r$.
Thus, $\delta_1$ coincides with the traditional \em (relative) distance \em $\delta$ of the code, which for linear codes equals the minimum relative weight of any nonzero codeword.
The generalized distances of a linear code $\ensuremath{\mathcal{C}}$ characterize its erasure list-decodability:

\begin{lemma}[\cite{Gur03}]\label{lem:gd}
Let $\ensuremath{\mathcal{C}} \subseteq {\mathbb F}_2^N$ be a linear code. Then $\ensuremath{\mathcal{C}}$ is erasure-list-decodable from $e$ erasures with list size $L$ if and only if $\delta_r(\ensuremath{\mathcal{C}}) > e/N$, where $r = 1 + \lfloor \log_2(L) \rfloor$.
\end{lemma}

If $\ensuremath{\mathcal{C}}$ is linear, then it can be erasure list-decoded in polynomial time by solving a linear system.  Thus, the combinatorial result of Lemma~\ref{lem:gd} comes with a polynomial-time algorithm.

Our goal in this paper is twofold.  First,
we aim to develop algorithms to erasure list-decode expander codes beyond the minimum distance of the code with small list size.  Second, we aim to do so in linear time, faster than the straightforward algorithm described above.

\paragraph{Our Results.}
Our main result is a linear-time erasure list-decoding algorithm for expander codes beyond the (designed) minimum distance.
\begin{theorem}\label{thm:main}
Let $\ensuremath{\mathcal{C}}_0 \subseteq {\mathbb F}_2^d$ be a linear code with distance $\delta$ and $r$'th generalized distance $\delta_r$.  Let $G = (L \cup R,E)$ be the double cover
\footnote{The \em double cover \em of a graph $\tilde{G} = (\tilde{V},\tilde{E})$
is the bipartite graph $G = (L \cup R,E)$ defined as follows.  Let $L$ and $R$ be
two copies of $\tilde{V}$; there is an edge between $u \in L$ and $v \in R$ if and only if $(u,v) \in \tilde{E}$ (see Section \ref{sec:prelim}).}
 of a $d$-regular expander graph on $n$ vertices with expansion $\lambda = \max\{\lambda_2, |\lambda_n|\}$.
Let $\ensuremath{\mathcal{C}} = \ensuremath{\mathcal{C}}(G, \ensuremath{\mathcal{C}}_0)$ be the expander code that results.
Let $\varepsilon > 0$, and suppose that
$ \frac{\lambda}{d} \leq \frac{ \varepsilon^2 \delta^2 }{ 2^{r+4} }. $

Then there is an algorithm \textsc{ListDecode} which,
given a received word $z \in ({\mathbb F}_2 \cup \inset{ \bot })^E$ with at most
$(1 - \varepsilon)\delta \delta_rdn$
erasures,
 runs in time
$ n \cdot \mathrm{poly}\inparen{ \frac{ 2^r d }{ \varepsilon \delta} },$
and returns a matrix $L\in {\mathbb F}_2^{nd \times a}$ and a vector $\ell \in {\mathbb F}_2^{nd}$ so that
$ \mathcal{L} := \mathrm{List}_{\ensuremath{\mathcal{C}}}(z) = \inset{ Lx + \ell\,:\, x \in {\mathbb F}_2^a } $
where $a := \dim(\mathcal{L})$ satisfies
$ a \leq \frac{ 2^{2r+7} }{ \varepsilon^4 \delta^4 }.$
\end{theorem}

Because $\delta_r > \delta$ for any non-trivial linear code (any code of dimension $>1$), the radius that Theorem~\ref{thm:main} achieves is beyond the (designed) minimum distance of $\ensuremath{\mathcal{C}}$, which is approximately $\delta^2 d n$.  To the best of our knowledge, this is the first linear-time list-decoding algorithm for expander codes that achieves this with a non-trivial list size.

In light of Lemma~\ref{lem:gd}, the ultimate result we can hope for is
an algorithm that list-decodes up to $\delta_r(\ensuremath{\mathcal{C}})$ fraction of
erasures with list size $2^{r-1}$ for any $r \geq 1$. The quantity
$\delta(\ensuremath{\mathcal{C}}_0)  \cdot \delta_r(\ensuremath{\mathcal{C}}_0)$ in Theorem~\ref{thm:main} may
suggest it plays the role of a 'designed' $r$'th generalized distance,
especially since for $r=1$ it does (up to an $\epsilon$ term) coincide
with the expander designed distance. However, we cannot expect
$\delta(\ensuremath{\mathcal{C}}_0)  \cdot \delta_r(\ensuremath{\mathcal{C}}_0)$ to be a general lower bound
on the $r$'th generalized distance of an expander code,
which implies in particular that the list-size in Theorem~\ref{thm:main}
has to be larger than $2^{r}$. Indeed,
already in the special case of \em tensor codes \em (i.e., when the
graph $G$ is the complete bipartite graph that has perfect expansion),
the generalized distance has been shown \cite{WY93, Scha00} to be a
complicated quantity that can be lower than $\delta(\ensuremath{\mathcal{C}}_0)  \cdot
\delta_r(\ensuremath{\mathcal{C}}_0)$: in the general expander case, finding a reasonable
description of the worst-case behavior of generalized distances seems
quite challenging.

Note however that our results do imply a weak bound on the generalized distances of an expander code, namely that $\delta_r(\ensuremath{\mathcal{C}})$ is approximately at least $\delta(\ensuremath{\mathcal{C}}_0) \cdot \delta_{\Theta(\log r)}( \ensuremath{\mathcal{C}}_0)$. Moreover, for the special case of $r=2$,
we are able to show the following bound on the second generalized distance of an expander code.

\begin{lemma}\label{lem:delta2}
Let $\ensuremath{\mathcal{C}}_0 \subseteq {\mathbb F}_2^d$ be a linear code with distance $\delta$ and second generalized distance $\delta_2$, and
let $G = (L \cup R,E)$ be the double-cover of a $d$-regular expander graph with expansion $\lambda$.
Let $\epsilon>0$, and suppose that $\frac \lambda d \leq \frac{\delta_2 \delta^2 \epsilon^2} {16}$.
Then the expander code $\ensuremath{\mathcal{C}}(G, \ensuremath{\mathcal{C}}_0)$ has second generalized distance at least
$
(1-\epsilon)\cdot \delta \cdot \min\{\delta_2, 2\delta\} .
$
\end{lemma}

Note that under the mild assumption that $\delta_2 ( \ensuremath{\mathcal{C}}_0) \leq  2\delta( \ensuremath{\mathcal{C}}_0)$ (satisfied by any code that has two minimum-weight codewords with disjoint support),
 the above lemma gives a lower bound of approximately
 $\delta_2( \ensuremath{\mathcal{C}}_0) \delta ( \ensuremath{\mathcal{C}}_0)$ on the second generalized distance of expander codes.

Finally, note that while we do not know if the list size returned by our algorithm can be generally improved, our algorithm can still list-decode an expander code $\ensuremath{\mathcal{C}}$ from up to a $\delta_r(\ensuremath{\mathcal{C}})$ fraction of erasures with list size $2^{r-1}$ for some values of $r$: If $r'$ is such that $\delta_{r'}(\ensuremath{\mathcal{C}}) <\delta(\ensuremath{\mathcal{C}}_0) \delta_r(\ensuremath{\mathcal{C}}_0)$ for some $r = O(1)$, our algorithm will run in linear time and return a list of size $2^{r'-1}$ given a $\delta_{r'}(\ensuremath{\mathcal{C}})$ fraction of erasures.

\subsection{Technical Overview}\label{sec:overview}
In this section, we give a brief overview of our approach.  The basic idea is similar to the approach in \cite{HW18}; however, as we discuss more in Section~\ref{sec:related} below, in that work the goal was \em list-recovery, \em a generalization of list-decoding.  In this work we can do substantially better by restricting our attention to list-decoding, as well as by tightening the analysis of \cite{HW18}.

Let $G=(L \cup R,E)$ be the double-cover of a $d$-regular expander graph, and let $\ensuremath{\mathcal{C}}_0 \subseteq {\mathbb F}_2^d$ be a linear code with distance $\delta$ and
$r$-th generalized distance $\delta_r$.
Since the inner code $\ensuremath{\mathcal{C}}_0$ is linear and has $r$'th generalized distance $\delta_r$, there is an $O(d^3)$-time algorithm to erasure list-decode $\ensuremath{\mathcal{C}}_0$ from up to $\delta_r d$ erasures.  Our first step will be to do this at every vertex $v \in L \cup R$ that we can, to produce a list $L_v$ at each such vertex.

In order to ``stitch together'' these lists, we define a notion of \em equivalence \em between edges, similar to the notion in \cite{HW18}.
Suppose that $(u,v)$ and $(w,v)$ are edges incident to a vertex $v$, so that there is some $b \in {\mathbb F}_2$ so that for any $c \in L_v$, $c_{(u,v)} = b + c_{(w,v)}$.  Then, even if we have not pinned down a symbol for $(u,v)$ or $(w,v)$,
we know that for any legitimate codeword $c \in \mathrm{List}_{\ensuremath{\mathcal{C}}}(z)$,
assigning a symbol for one of these edges implies an assignment for the other.
In this case, we say that $(u,v) \sim (w,v)$.  Because the lists $L_v$ are
actually affine subspaces, there are not many equivalence classes at each vertex
(and in particular substantially fewer equivalence classes than in the approach used in \cite{HW18}).

With these equivalence classes defined, we actually give two algorithms, \textsc{\LDS} and \textsc{ListDecode}.   As the name suggests, \textsc{\LDS} is a warm-up that has a worse dependence on $\epsilon, \delta$ and $r$, but is easier to understand.  We describe \textsc{\LDS} (given in Section \ref{sec:slow}, Figure~\ref{fig:alg1}) here first, and then describe the changes that need to be made to arrive at our final algorithm, \textsc{ListDecode} (given in Section \ref{sec:faster}, Figure~\ref{fig:alg2}).

The main idea of \textsc{\LDS} is to choose $s = \mathrm{poly}(2^{r}, 1/\epsilon, 1/\delta)$ large equivalence classes and generate a list of all $2^s$ possible labelings for these equivalence classes.  For each such labeling, we now hope to uniquely fill in the rest of the codeword, to arrive at a list of size $2^s$.
One might hope that labeling
these $s$ large equivalence classes would leave a fraction of unlabeled symbols
less than the designed distance of $\ensuremath{\mathcal{C}}$,
allowing us to immediately use the known linear-time erasure unique decoding algorithm
for the expander code.  Unfortunately, this is not in general the case.  However, we show that there are many vertices $v$ so that the number of unlabeled edges incident to $v$ is at most $\delta(\ensuremath{\mathcal{C}}_0)d$.  Thus, we may run the unique decoder for $\ensuremath{\mathcal{C}}_0$ (in time $O(d^3)$) at each such vertex to generate yet more labels.  It turns out that at this point, there \em are \em enough labels to run $\ensuremath{\mathcal{C}}$'s unique decoding algorithm and finish off the labeling.

Naively, the algorithm described above runs in time at least $2^s$, since we must loop over all $2^s$ possibilities.  This is exponential in $\varepsilon$ and $\delta$ and doubly-exponential in $r$.
The idea behind our final algorithm \textsc{ListDecode} is to take advantage of the linear structure of the lists $L_v$ to find a short description of all of the legitimate labelings.  We will show in Section~\ref{sec:faster} how to do this in time $n\cdot\mathrm{poly}( d 2^r / \varepsilon \delta )$ by leveraging the sparsity of $\ensuremath{\mathcal{C}}$'s parity-check matrix.

\subsection{Related Work}\label{sec:related}
\paragraph{Work on list-decoding expander codes.}
The work that is perhaps the most related to ours is \cite{HW18}, which seeks to \em list-recover \em expander codes in the presence of erasures in linear time.\footnote{We note that other works, such as \cite{GI04a}, have also had this goal, but to the best of our knowledge \cite{HW18} obtains the best known results, so we focus on that work here.}
List-recovery is a variant of list-decoding which applies to codes over a large alphabet $\Sigma$: instead of receiving as input a vector $z \in \{0,1\}^N$, the decoder receives a collection of lists, $S_1, \ldots, S_N \subseteq \Sigma$, and the goal is to return all codewords $c \in \Sigma^N$ so that $c_i \in S_i$ for all $i$.  In the setting of erasures,
some lists have size $|\Sigma|$, in which case we may as
well replace the whole list by a $\bot$ symbol.

List decoding from erasures is a special case of list-recovery with erasures,
where the $S_i$  that are not $\bot$  have size one.  However, existing list-recovery algorithms will not immediately work in our setting, as we consider binary codes: list-recovery is only possible for codes with large alphabets.

Our first observation is that the approach of \cite{HW18} for erasure list-recovery can be used to obtain an algorithm for erasure list-decoding in linear time, even for binary codes.  As described above, our first step is to erasure list-decode $\ensuremath{\mathcal{C}}_0$ at each vertex, leaving us with lists $L_v$ that need to be ``stitched together.''  The approach of \cite{HW18} does precisely this, although in their context the lists that they are stitching together come from list-recovering the inner code.

However, the results of \cite{HW18} about stitching together lists do not immediately yield anything meaningful for erasure list-decoding.  More precisely,
those results imply that an expander code $\ensuremath{\mathcal{C}}(G, \ensuremath{\mathcal{C}}_0)$ formed from a graph $G$ with expansion $\lambda$ and an inner code $\ensuremath{\mathcal{C}}_0$ with distance $\delta$ and $r$'th generalized distance $\delta_r$ is list-decodable from up to a $\delta \delta_r \inparen{ \frac{ \delta - \lambda/d }{6} }$ fraction of erasures in time $N \cdot \exp( \exp( \exp(r) ) )$.
In particular, the fraction of erasures that those results tolerate is smaller than the distance of the expander code, yielding only trivial results in this setting.

Thus, while we use the same ideas as \cite{HW18}, our analysis is different and significantly tighter.  This allows us to obtain a meaningful result in our setting, corresponding to the algorithm \textsc{\LDS}.  Moreover, as described above, we are able to take advantage of the additional linear structure in our setting to improve the dependence on $r$ in the running time.

To the best of our knowledge, there is no algorithmic work on list-decoding expander codes from errors (rather than erasures) in linear time with good parameters.
We note that \cite{MRRSW19} recently showed that there are expander codes which are \em combinatorially \em near-optimally list-decodable from errors, but this work is non-constructive and does not provide efficient list decoding algorithms.

\paragraph{Work on erasure list-decoding more generally.} It is known that, non-constructively, there are erasure-list-decodable codes of rate $\Omega(\varepsilon)$ which can list-decode up to a $1- \varepsilon$ fraction of erasures, with list sizes $O(\log(1/\varepsilon))$~\cite{Gur03}.  However, this proof is non-constructive and does not provide efficient algorithms, and it has been a major open question to achieve these results efficiently.  Recent progress has been made by \cite{BDT18}, who provided a construction (although no decoding algorithm) with parameters close to this for $\varepsilon$ which is polynomially small in $n$.

Our work is somewhat orthogonal to this line of work on erasure list-decoding
for several reasons.  First, that line of work is mostly concerned with low-rate
codes that are list-decodable from a large fraction of erasures (approaching
$1$), while expander codes tend to perform best at high rates.
Second, we are less concerned with the trade-off between rate and erasure tolerance and more concerned with efficiently erasure-list-decoding an arbitrary expander code as far beyond its (designed) distance as possible.
Finally, much of the line of work described above has focused on getting the list size down to $O(\log(1/\varepsilon))$, which is known to be impossible for linear codes, where the best list size possible is $\Omega(1/\varepsilon)$ \cite{Gur03}.
Since the expander codes we consider are linear, we do not focus on that goal in our work.

\paragraph{Organization.} In Section~\ref{sec:prelim}, we formally introduce the notation and definitions we will need. In Section \ref{sec:slow}, we introduce our preliminary algorithm \textsc{\LDS}, while in Section \ref{sec:faster} we describe the final algorithm that has better dependence on $\epsilon, \delta$ and $r$ in the running time. This proves our Main Theorem \ref{thm:main}.
We conclude in Section \ref{sec:delta2} with the proof of Lemma \ref{lem:delta2}, showing a bound on the second generalized distance of expander codes.

\section{Preliminaries}\label{sec:prelim}

\paragraph{Expander Graphs.}
Let $G = (L \cup R,E)$ be a bipartite graph.\footnote{In this paper we only consider undirected graphs.}
For a vertex $v \in L \cup R$, let $\Gamma(v)$ denote the set of vertices adjacent to $v$.
 For $S \subseteq L$ and $T \subseteq R$, let $E(S,T)$ denote the set of edges with endpoints in $S \cup T$, and for
$A \subseteq L \cup R$, let $E(A) := E(A \cap L, A \cap R)$.

Let $\tilde{G} = (\tilde{V},\tilde{E})$ be a (not necessarily bipartite) $d$-regular graph on $n$ vertices.
The \em expansion \em of $\tilde G$ is $ \lambda := \max\{ \lambda_2, |\lambda_n| \},$
where $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n$ are the eigenvalues of the adjacency matrix of $G$.
The  \em double-cover \em  of $\tilde{G}$
is the bipartite graph $G = (L \cup R,E)$ defined as follows.  Let $L$ and $R$ be
two copies of $\tilde{V}$; there is an edge between $u \in L$ and $v \in R$ if and only if $(u,v) \in \tilde{E}$.
If $\tilde{G}$ is an expander graph, then $G$ obeys the \em Expander Mixing Lemma: \em

\begin{theorem}[Expander Mixing Lemma, see \em e.g. \em \cite{HLW06}] \label{thm:eml}
Suppose that $G = (L \cup R,E)$ is the double cover of a $d$-regular expander graph on $n$ vertices with expansion $\lambda$.
Then for any $S \subseteq L$ and $T \subseteq R$,
$$\left|E(S,T)- \frac{d}{n}|S||T| \right| \leq \lambda \sqrt{ |S||T| }.$$
\end{theorem}

\paragraph{Expander Codes.}
Let $G = (L \cup R,E)$ be the double cover of a $d$-regular expander graph on $n$ vertices, as above.
Let $\ensuremath{\mathcal{C}}_0 \subseteq {\mathbb F}_2^d$ be a linear code, called the \em inner code. \em
Fix an order on the edges incident to each vertex of $G$, and let $\Gamma_i(v)$ denote the $i$'th neighbor of $v$.

The expander code $\ensuremath{\mathcal{C}} := \ensuremath{\mathcal{C}}(G, \ensuremath{\mathcal{C}}_0)$ is defined as the set of all labelings of the edges of $G$ that respect the inner code $\ensuremath{\mathcal{C}}_0$.  More precisely, we have the following definition.
\begin{definition}[Expander Code]
Let $\ensuremath{\mathcal{C}}_0 \subseteq {\mathbb F}_2^d$ be a linear code, and let $G = (L \cup R,E)$ be the double cover of a $d$-regular expander graph on $n$ vertices.
The expander code $\ensuremath{\mathcal{C}}(G,\ensuremath{\mathcal{C}}_0) \subseteq {\mathbb F}_2^E$ is a linear code of length $nd$, so that
for $c \in {\mathbb F}_2^{E}$,  $c \in \ensuremath{\mathcal{C}}$ if and only if, for all $v \in L \cup R$,
\[ \left(c_{(v,\Gamma_1(v))}, c_{(v, \Gamma_2(v))}, \ldots, c_{(v, \Gamma_d(v))} \right) \in \ensuremath{\mathcal{C}}_0. \]
\end{definition}

By counting constraints, it is not hard to see that if $\ensuremath{\mathcal{C}}_0 \subseteq {\mathbb F}_2^d$ is a linear code of rate $R$, then $\ensuremath{\mathcal{C}}(G, \ensuremath{\mathcal{C}}_0) \subseteq {\mathbb F}_2^{E}$ is a linear code of rate at least $2R - 1$.
Moreover, it is known that expander codes have good distance:
\begin{lemma}[\cite{SS96,Z01}]\label{lem:distance}
Let $\ensuremath{\mathcal{C}}_0 \subseteq {\mathbb F}_2^d$ be a linear code with distance $\delta$, and let $G = (L \cup R,E)$ be the double cover of a $d$-regular expander graph with expansion $\lambda$.
Then the expander code $\ensuremath{\mathcal{C}}(G, \ensuremath{\mathcal{C}}_0)$ has distance at least $\delta( \delta - \lambda/ d)$.
\end{lemma}

Moreover, $\ensuremath{\mathcal{C}}$ can be uniquely decoded up to this fraction of erasures in linear time.

\begin{lemma}\label{lem:uniquedec}
Let $\ensuremath{\mathcal{C}}_0 \subseteq {\mathbb F}_2^d$ be a linear code with distance $\delta$, and let $G = (L \cup R,E)$ be the double cover of a $d$-regular expander graph on $n$ vertices with expansion $\lambda$.
Let $\epsilon > 0$, and suppose that $\frac \lambda d < \frac \delta 2$.
Then there is an algorithm \textsc{UniqueDecode} which uniquely decodes the expander code $\ensuremath{\mathcal{C}}(G, \ensuremath{\mathcal{C}}_0)$ from up to $(1 - \epsilon)\delta(\delta - \lambda/d)$ erasures in time $n \cdot \mathrm{poly}(d)/\epsilon$.
\end{lemma}
The above lemma is by now folklore, but
for completeness, we include a proof in Appendix~\ref{app:uniquedec}.

\section{A preliminary algorithm}\label{sec:slow}

For clarity of exposition, we begin the proof of our Main Theorem~\ref{thm:main} by proving the following weaker theorem.

\begin{theorem}\label{thm:slow}
Let $\ensuremath{\mathcal{C}}_0 \subseteq {\mathbb F}_2^d$ be a linear code with distance $\delta$ and $r$'th generalized distance $\delta_r$.  Let $G = (L \cup R,E)$ be the double cover
 of a $d$-regular expander graph on $n$ vertices with expansion $\lambda = \max\{\lambda_2, |\lambda_n|\}$.
Let $\ensuremath{\mathcal{C}} = \ensuremath{\mathcal{C}}(G, \ensuremath{\mathcal{C}}_0)$ be the expander code that results.
Let $\varepsilon > 0$, and suppose that
$ \frac{\lambda}{d} \leq \frac{ \varepsilon^2 \delta^2 }{ 2^{r+4} }. $
Let $s:=\frac{ 2^{2r+7}} {\epsilon^4 \delta^4}$.
Then there is an algorithm \textsc{\LDS} which erasure-list-decodes $\ensuremath{\mathcal{C}}$ from $( 1- \varepsilon)\delta \delta_r dn$  erasures
with list size at most $2^{s}$ in time $n \cdot \mathrm{poly}(d) \cdot \exp(s)$.
\end{theorem}

Theorem~\ref{thm:slow} still provides a linear-time algorithm (provided $d, r, \epsilon, \delta$ are all constant), but the dependence on $r$, $\varepsilon$, $\delta$ is not very good.  We will prove Theorem~\ref{thm:slow} in this section to illustrate the main ideas, and then in Section~\ref{sec:faster}, we will show how to adapt the algorithm to achieve the running times advertised in Theorem~\ref{thm:main}.

A formal description of our algorithm \textsc{\LDS} is given in Figure~\ref{fig:alg1}.
Roughly, the first step
is to list decode the inner codes to obtain an inner list $L_v$ at each vertex $v \in L \cup R$. The second and main step then is to label large equivalence classes by iterating over all possible assignments to representatives from these classes. In the third and final step
 we complete any such possible assignment, by first uniquely decoding at inner codes where sufficient number of edges are already labeled, followed by global unique decoding to recover the rest of the unlabeled edges. Below we elaborate on each of these steps.

In what follows, suppose that $z \in ({\mathbb F}_2 \cup \{\bot\})^{E}$ is a received word with at most $(1 - \varepsilon)\delta \delta_r dn$ symbols that are $\bot$, and let $\mathcal{L} = \mathrm{List}_{\ensuremath{\mathcal{C}}}(z)$ be the set of codewords of $\ensuremath{\mathcal{C}}$ that are consistent with $z$.

\subsection{List decoding inner codes}\label{subsec:list_dec_inn}

The first step is to list decode all inner codes with not too many erasures.
Specifically, let $B \subseteq L \cup R$ be the set of \em bad \em vertices $v$ so that $z$ has more than $\delta_r d$ erasures incident to $v$.
\begin{equation}\label{eq:defB}
 B = \left\{ v \in L \cup R \,:\, z_{(v,u)} = \bot \text{ for more than $\delta_r d$ vertices $u$} \right\}.
\end{equation}
Then by our assumption on the number of erasures in $z$,
\[ |B \cap L| \delta_r d \leq(1 - \varepsilon)  \delta \delta_r nd \]
and the same for $B \cap R$, which implies that
\begin{equation}\label{eq:Bsmall}
|B \cap L|,|B \cap R| \leq (1 - \varepsilon)\delta n.
\end{equation}

The first step of the algorithm will be to list-decode the inner code $\ensuremath{\mathcal{C}}_0$ at every vertex $v \not\in B$.
For all such $v$, let
\begin{equation}\label{eq:defLv}
 L_v := \mathrm{List}_{\ensuremath{\mathcal{C}}_0}\left(( z_{(v, \Gamma_1(v))}, z_{(v,\Gamma_2(v))}, \ldots, z_{(v, \Gamma_d(v))} )\right).
\end{equation}

Next we shall use the following notion of \em local equivalence relation \em  to assign labels to many of the edges.
To define this notion, note first that since $\ensuremath{\mathcal{C}}_0$ has $r$'th generalized distance $\delta_r$,
for any $v \notin B$, $L_v$ is an affine subspace of ${\mathbb F}_2^d$ of dimension $r_v \leq r-1$.
Let $G_v \in {\mathbb F}_2^{d \times r_v}$ and $b_v \in {\mathbb F}_2^d$ be such that
\[ L_v = \inset{ G_v x + b_v \,:\, x \in {\mathbb F}_2^{r_v} }. \]
Notice that each row of $G_v$ corresponds to an edge adjacent to $v$.

Next we define, for any vertex $v \notin B$, a \em local equivalence relation \em  $\sim_v$ at the vertex $v$.

\begin{definition}[Local equivalence relation]\label{def:local_equiv}
Suppose that $v \not\in B$.
For $(u,v), (w,v) \in E$, say that $(u,v) \sim_v (w,v)$ if the row of $G_v$ corresponding to $(u,v)$ is the same as the row of $G_v$ corresponding to $(w,v)$.
\end{definition}
Notice that Definition~\ref{def:local_equiv} depends on both $v$ and $z$; we suppress the dependence on $z$ in the notation.
We make the following observations.
\begin{observation}\label{obs:ABC}
Suppose that $v \not\in B$.
\ \begin{enumerate}
\item[(A)] If $(u,v) \sim_v (w,v)$, then for any $c
\in \mathcal{L}$, $c_{(u,v)}$ is determined by $c_{(w,v)}$.
\item[(B)] There are
at most $2^{r-1}$ local equivalence classes at $v$, because there are at most $2^{r-1}$ possible vectors in ${\mathbb F}_2^{r_v}$ that could appear as rows of the matrices $G_v$.
\end{enumerate}
\end{observation}

\subsection{Labeling large equivalence classes}\label{subsec:label_equiv}

The next step is to assign labels to large \em global \em equivalence classes, defined below.
For this, we first define a new edge set $E' \subseteq E$ by first throwing out all edges touching $B$, and then repeatedly throwing out  edges whose local equivalence classes are too small. Specifically, define $E'$ to be the output of the following Algorithm \textsc{FindHeavyEdges}, given in Figure \ref{algo:fhe}.

\begin{figure}
\centering
\fbox{
\begin{tabular}{cc}
\begin{minipage}{.9\textwidth}
\vspace{.3cm}
\textbf{Algorithm:} \textsc{FindHeavyEdges}

\textbf{Inputs:} A description of $G = (L \cup R,E)$ and $\ensuremath{\mathcal{C}}_0 \subseteq {\mathbb F}_2^d$, and the lists $L_v$ for $v \not\in B$.

\textbf{Output:} The set $E' \subseteq E$.

\bigskip

\textbf{Initialize:} $E' \gets E $.

\begin{enumerate}
\item Remove from $E'$ all edges incident to a vertex in $B$.
\item While true:\\ \\
 If there is some $(u,v) \in  E'$, so that
 $$\left|\left\{ (w,v) \in E' \,:\, (w,v) \sim_v (u,v) \right\}\right| \leq \frac{ \varepsilon^2 \delta^2  }{ 2^{r+3}} \cdot d,$$
remove $(u,v)$ and all edges $(w,v) \in E'$ so that  $(w,v) \sim_v (u,v)$ from $E' $.
	\item  Break and return the set $E'$.
\end{enumerate}
\end{minipage}
\vspace{.3cm}
&\hspace{.3cm}
\end{tabular}
}
\caption{\textsc{FindHeavyEdges} }
\label{algo:fhe}
\end{figure}

Next we define a \em global \em equivalence relation $\sim$ on the edges in $E'$ as follows.
\begin{definition}[Global equivalence relation]\label{def:global_equiv}
Suppose that $e, e' \in E'$. We say that $e \sim e'$ if there is a path $e=e_1, e_2, \ldots, e_t = e'$
so that $e_1, e_2, \ldots,e_t \in E'$, and for any pair of adjacent edges  $e_i = (u,v)$, $e_{i+1} = (v,w)$ on the path it holds that $(u,v) \sim_v (v,w)$.
\end{definition}

The following lemma shows that  $ E'$ is partitioned into a small number of large global equivalence classes. Consequently, one can assign labels to all edges in $ E'$ by iterating over all possible assignments for a small number of representatives from these classes.

\begin{lemma}\label{lem:equiv_1}
Any global equivalence class in $E'$ has size at least  $\frac{ \varepsilon^4 \delta^4  }{ 2^{2r+7}} dn$. In particular, $E'$ is partitioned into at most $s:=\frac{ 2^{2r+7}} {\epsilon^4 \delta^4}$ different equivalence classes.
\end{lemma}

\begin{proof}
Let $F$ be a global equivalence class in $E'$, and let $S\subseteq L$ and $T \subseteq R$ denote the left and right
vertices touching $F$, respectively.
By the definition of $E'$, any vertex $v \in  S \cup T$ is incident to at least $\frac{\varepsilon^2 \delta^2} {2^{r+3}} \cdot d$ edges in $F$.
Thus by the Expander Mixing Lemma (Theorem \ref{thm:eml}),
$$
\frac{\varepsilon^2 \delta^2} {2^{r+3}}d\sqrt{|S| |T| }
\leq \left|F\right|
\leq \frac{d}{n} |S| |T| + \lambda \sqrt{|S| |T| },
$$
and rearranging
\[ n \inparen{ \frac{\varepsilon^2 \delta^2} {2^{r+3}} - \frac{ \lambda }{d} } \leq \sqrt{ |S| |T|}.\]
This implies in turn that
$$|F| \geq  \frac{\varepsilon^2 \delta^2} {2^{r+3}} d \sqrt{|S| |T| } \geq \frac{\varepsilon^2 \delta^2} {2^{r+3}}  \left( \frac{\varepsilon^2 \delta^2} {2^{r+3}}  - \frac \lambda d\right) dn,$$
which gives the final claim
by our choice of $\frac \lambda d \leq \frac {\epsilon^2 \delta^2} {2^{r+4}}$.
 \end{proof}

Finally, by (A) in Observation~\ref{obs:ABC}, choosing a symbol on an edge determines all the symbols in that edge's equivalence class.  Thus, we will exhaust over all choices of symbols for the equivalence classes in $E'$; this leads to $2^s$ possibilities. Next we show that any such choice determines a unique codeword in $\ensuremath{\mathcal{C}}$.

\subsection{Completing the assignment}\label{subsec:complete}

To complete the assignment we first show that many of the vertices
have at least $(1-\delta)d$ incident edges in $E'$. For any such vertex, the inner codeword at this vertex is completely determined by the assignment to edges in $E'$, and so can be recovered by uniquely decoding locally at this vertex. We then recover the small number of remaining edges using global unique decoding. Specifically, let
\begin{equation}\label{eq:defB'}
 B' = \left\{ v \in L \cup R \,:\, (v,u) \notin E'  \text{ for more than $\delta d$ vertices $u$} \right\}.
\end{equation}
The next lemma bounds the size of $B'$, and the number of edges in $E(B')$.

\begin{lemma}\label{lem:equiv_2}
The following hold:
\begin{enumerate}
\item $|B' \cap L|, |B' \cap R| \leq \left(1-\frac \epsilon 2 \right) \delta n$.
\item $|E(B')| \leq \left(1-\frac \epsilon 4\right) \left(\delta - \frac \lambda d\right)\delta nd$.
\end{enumerate}
\end{lemma}

\begin{proof}
For the first item, let $B_1 \subseteq (L \cup R)\setminus B$ be the subset of vertices $ v \notin  B$ so that more than $\left(1- \frac \epsilon 2 \right) \delta d$ edges incident to $v$ are removed on Step 1 of \textsc{FindHeavyEdges}, and let $B_2 \subseteq (L \cup R)\setminus B$ be the subset of vertices $ v \notin B$ so that more than $\frac \epsilon 2 \delta d$ edges incident to $v$ are removed on Step 2 of \textsc{FindHeavyEdges}.
Note that $B' \subseteq   B \cup B_1 \cup B_2$,
so it suffices to show that $|(B \cup B_1 \cup B_2) \cap L| \leq \left(1-\frac \epsilon 2 \right) \delta n$, and similarly for $R$.
By (\ref{eq:Bsmall}), $|B \cap L|, |B \cap R| \leq (1-\epsilon) \delta n$. Claims \ref{clm:remove_step_1} and \ref{clm:remove_step_2} below show that
each of  the sets $B_1, B_2$ has size at most $\frac \epsilon 4 \delta n$ which gives the desired conclusion.

For the second item, note that by the first item and the Expander Mixing Lemma,
\begin{align*}
\left|E(B')\right| & \leq \frac{d}{n} \left( \delta n \left(1 - \frac \varepsilon 2\right) \right)^2 + \lambda \delta n \left(1 - \frac \varepsilon 2\right) \\
&\leq  \left(1 - \frac \varepsilon 2\right)\left( \delta + \frac \lambda d \right)\delta nd \\
& \leq\left(1-\frac \epsilon 4\right) \left(\delta - \frac \lambda d\right)\delta nd,
\end{align*}
where the last inequality follows by our choice of  $\frac{\lambda} {d} \leq \frac{ \epsilon \delta} {8}$.
\end{proof}

\begin{claim}\label{clm:remove_step_1}
$|B_1| \leq \frac \epsilon 4 \delta n.$
\end{claim}

\begin{proof}
By the description of \textsc{FindHeavyEdges},
$B_1$ is the set of all vertices $v \in (L \cup R) \setminus B$ that are incident to more than $\left(1- \frac \epsilon 2 \right) \delta d$ vertices of $B$.
Thus by the Expander Mixing Lemma,
\begin{align*}
|B_1\cap L|  \left(1- \frac \epsilon 2 \right) \delta  d&\leq \left|E(B_1\cap L, B\cap R)\right| \\
&\leq \frac{d}{n} |B_1\cap L||B\cap R| + \lambda \sqrt{ |B_1\cap L||B\cap R| } \\
&\leq \frac{d}{n} |B_1\cap L| n\delta(1 - \varepsilon) + \lambda \sqrt{ |B_1\cap L| n\delta (1 - \varepsilon) },
\end{align*}
where the last inequality follows by (\ref{eq:Bsmall}).

Rearranging, we have
$$
\sqrt{|B_1\cap L|} \leq \frac{ \lambda \sqrt{ n \delta (1 - \varepsilon) } }{ d\delta \varepsilon/2 },
$$
and
$$
|B_1 \cap L| \leq 4n \inparen{ \frac{\lambda}{d} }^2 \cdot \frac{ 1 }{\delta \varepsilon^2 } \leq  \frac{\epsilon } {8} \delta n,
$$
where the last inequality follows by our choice of $\frac \lambda d \leq \frac{\varepsilon^{3/2} \delta} {8}$.
As the same holds for $B_1\cap R$, we conclude that $B_1$ has size at most $\frac{\epsilon} {4} \delta n$.
\end{proof}

\begin{claim}\label{clm:remove_step_2}
$|B_2| \leq \frac \epsilon 4 \delta n.$
\end{claim}

\begin{proof}
Since there are at most $2^{r-1}$ local equivalence classes at each vertex $v$, the algorithm \textsc{FindHeavyEdges} performs at most
 $2n \cdot 2^{r-1}$ iterations at Step 2. At each such iteration, at most $\frac{\epsilon^2 \delta^2 } {2^{r+3}}\cdot d$ edges are removed, and so the total number of edges removed at Step 2 of  \textsc{FindHeavyEdges} is  $2n \cdot 2^{r-1} \cdot \frac{\epsilon^2 \delta^2 } {2^{r+3}}\cdot d = \frac{\epsilon^2 \delta^2 } {8}\cdot d n$. Finally, by averaging this implies that there are at most $\frac \epsilon 4 \delta n$ vertices $v$ so that more than $
 \frac \epsilon 2 \delta d$ edges incident to $v$ are removed at this step.
\end{proof}

Next observe that for any vertex $v \not\in B'$, the choices for symbols on $E'$ uniquely determine the codeword of $\ensuremath{\mathcal{C}}_0$ that belongs at the vertex $v$.  This is because $\ensuremath{\mathcal{C}}_0$ has distance $\delta$, and at least $(1 - \delta)d$ edges incident to $v$ have been labeled. Note that since $\ensuremath{\mathcal{C}}_0$ is a linear code of length $d$, this unique codeword can be found in time $O(d^3)$ by solving a system of linear equations.
Once this is done, the only edges that do not have labels are those in $E(B')$. By Item (2) of Lemma \ref{lem:equiv_2}, there are at most $\left(1-\frac \epsilon 4\right) \left(\delta - \frac \lambda d\right)\delta nd$ such edges.
By Lemma \ref{lem:uniquedec}, these edges can be recovered using global unique decoding in time $n \cdot \mathrm{poly}(d) /\epsilon$.  In this way, we can recover the entire list $\mathcal{L}$.

\bigskip

The algorithm described above is given as
\textsc{\LDS} in Figure~\ref{fig:alg1}.  This algorithm runs in time $n \cdot \mathrm{poly}(d) \cdot \exp(s)$,
which proves
Theorem~\ref{thm:slow}.  We will show how to speed it up in Section~\ref{sec:faster}, where we will conclude the proof of Theorem~\ref{thm:main}.

\begin{figure}
\centering
\fbox{
\begin{tabular}{cc}
\begin{minipage}[c][]{.9\textwidth}
\vspace{.3cm}
\textbf{Algorithm:} \textsc{\LDS}

\textbf{Inputs:} A description of $G = (L \cup R,E)$ and $\ensuremath{\mathcal{C}}_0 \subseteq {\mathbb F}_2^d$, and $z \in ({\mathbb F}_2 \cup \{\bot\})^E$.

\textbf{Output:} The list $\mathcal{L} = \mathrm{List}_{\ensuremath{\mathcal{C}}}(z)$.

\bigskip

\textbf{Initialize:} $\mathcal{L} = \emptyset$.

\begin{enumerate}
	\item Let $B \subseteq L \cup R$ be as  in \eqref{eq:defB}.
	For each $v \not\in B$, run $\ensuremath{\mathcal{C}}_0$'s erasure list-decoding algorithm to obtain the lists $L_v$ as in \eqref{eq:defLv}.  For each $v$, this entails finding the kernel of a sub-matrix of $G_v$, which can be done in time $O(d^3)$.  Thus, the time for this step is $n \cdot \mathrm{poly}(d)$.
		\item Run the algorithm \textsc{FindHeavyEdges} given in Figure \ref{algo:fhe} to find the set $E'$, find the partition of $E'$ into $s$ global equivalence classes, and
choose representative edges $e^{(1)}, \ldots, e^{(s)}$ from each of the equivalence classes. This can be done in time $O(nd)$ using Breadth-First-Search.
	\item For each $y^{(advice)} \in {\mathbb F}_2^{\{e^{(1)}, \ldots, e^{(s)}\}}$:
	\begin{enumerate}
	\item For each $i \in [s]$, and for each $e \sim e^{(i)}$, define $y_e$ to be the value uniquely determined by $y^{(advice)}_{e^{(i)}}$, as given in Item (A) of Observation~\ref{obs:ABC}.  This can be done in time $O(nd)$, again by Breadth-First-Search.

	\item Let $B' \subseteq L \cup R$ be as in \eqref{eq:defB'}.  For each $v \not\in B'$, find the unique $y|_{\inset{v}\times\Gamma(v)}$ so that $y_{(v,u)}$ is consistent with existing assignments to $y$, or determine that no such $y$ exists.  As above, this can be done in time $n \cdot \mathrm{poly}(d)$.  If no such $y$ exists for some $v$, continue to the next choice of $y^{(advice)}$.

	\item Use the linear-time erasure unique decoding algorithm \textsc{UniqueDecode} from Lemma \ref{lem:uniquedec} to find a unique $y \in {\mathbb F}_2^E$ that agrees with all the choices of $y$ made so far, or determine that none exists.  If it exists, add $y$ to $\mathcal{L}$. By Lemma \ref{lem:uniquedec}, this can be done in time $n \cdot \mathrm{poly}(d)/\epsilon$.
\end{enumerate}
\item Return $\mathcal{L}$.
\end{enumerate}
\vspace{.3cm}
\end{minipage}
& \hspace{.3cm}
\end{tabular}
}
\caption{\textsc{\LDS}: Returns $\mathrm{List}_{\ensuremath{\mathcal{C}}}(z)$ in time $O_{r,\delta, \varepsilon}(n)$.  However, the dependence on $r, \delta, \epsilon$ is not good, and is improved in \textsc{ListDecode}, given in Figure~\ref{fig:alg2}. }
\label{fig:alg1}
\end{figure}

\vspace{.5cm}

\section{Final algorithm}\label{sec:faster}
The algorithm \textsc{\LDS} runs in
time $O_{r, \delta,\epsilon}(n \cdot \mathrm{poly}(d))$, but the constant inside the $O_{r,\delta, \varepsilon}(\cdot)$ is exponential in $\mathrm{poly}\left(\frac{2^r} {\epsilon \delta} \right)$, since there are $s =  \mathrm{poly}\left(\frac{2^r} {\epsilon \delta} \right)$ equivalence classes, and we exhaust over all $2^s$ possible assignments to representatives from these classes.
In this section, we will show how to do significantly better and obtain a running time that depends polynomially on $2^r,  1/\delta, 1/\epsilon$, finishing the proof of Theorem~\ref{thm:main}.
The basic idea is as follows.
Instead of exhausting over all possible ways to assign values to the edges $e^{(1)}, \ldots, e^{(s)}$, we will set up and solve a linear system to find a description of the ways to assign these values that will lead to legitimate codewords. Specifically, we prove the following lemma.

\begin{lemma}\label{alg:findcands}
There is an algorithm \textsc{\FC} which, given the state of \textsc{\LDS} at the end of Step 2, runs in time $n \cdot \mathrm{poly}(d,s)$ and returns
$A \in {\mathbb F}_2^{nd \times s}$,
$b \in {\mathbb F}_2^{nd}$,
$\hat A \in {\mathbb F}_2^{s \times a}$,
and $\hat b \in {\mathbb F}_2^{s}$ so that
\[ \mathrm{List}_{\ensuremath{\mathcal{C}}}(z) = \left\{ Ax + b \,:\, x= \hat A\hat x + \hat b\text{ for some $\hat x \in {\mathbb F}_2^{a}$ } \right\}, \]
where $a := \dim(\mathrm{List}_{\ensuremath{\mathcal{C}}}(z))$ satisfies $a \leq s$.
\end{lemma}

The above lemma immediately implies Theorem \ref{thm:main}:
We first run Steps 1 and 2 in \textsc{\LDS} in order to find the set $E'$ and its partition into equivalence classes.  As before, this takes time $n \cdot \mathrm{poly}(d)$.  Next, we run \textsc{\FC} in order to find a linear-algebraic description of the list $\mathcal{L}$, which we return.  This second step takes time $n \cdot \mathrm{poly}(s,d)$, for a total running time of $n \cdot \mathrm{poly}(s,d)$.  Plugging in our definition of $s$ proves Theorem~\ref{thm:main}. The formal description of the final algorithm \textsc{ListDecode} is given in Figure \ref{fig:alg2}.
 The rest of this section is devoted to the proof of Lemma \ref{alg:findcands}.

First, note that every value $y_e$ determined by \textsc{\LDS} is some affine function of the labels on $e^{(1)}, \ldots, e^{(s)}$.  That is, there is some matrix $A \in {\mathbb F}_2^{dn \times s}$ and some vector $b \in {\mathbb F}_2^{dn}$ so that the list generated by \textsc{\LDS} is
\[ \inset{ Ax+ b \,:\, x \in {\mathbb F}_2^s }, \]
where $x := y^{(advice)}$.
Our goal in \textsc{\FC} will thus be to find this $A$ and $b$ efficiently, as well as to find a description of the $x$'s so that $Ax + b$ is actually a codeword in $\ensuremath{\mathcal{C}}$.
An overview of the algorithm \textsc{\FC} is given in Figure~\ref{fig:findcands}, and the steps are described below.

\subsection{Finding $A$ and $b$}
The first step of the algorithm will be to find $A$ and $b$.
To find this efficiently, we will mirror the decoding algorithm in \textsc{\LDS}, except we will do it while keeping the choices of $y^{(advice)}$ as variables.
As we will see below, this can be done in time $n \cdot \mathrm{poly}(s,d)$.
For this, we shall find a series $\left(A^{(t)},b^{(t)}\right)$ for $t=0,1, \ldots, T$, where $(A,b)=\left(A^{(T)},b^{(T)}\right)$ as follows.

\paragraph{Finding $A^{(0)}$ and $b^{(0)}$.}
First, let $E_0 :=E'$, and let $A^{(0)} \in {\mathbb F}_2^{E_0 \times s}$ and $b^{(0)} \in {\mathbb F}_2^{E_0}$ such that
\[ (A^{(0)} x + b^{(0)})_e =  y_{e} ,
 \]
where $x := y^{(advice)}$, and
$y_e$ is as in Step (3a) in Algorithm \textsc{\LDS}.
Note that $A^{(0)}$ has rows which are $1$-sparse, and that $A^{(0)}, b^{(0)}$
can be created in time $O(nd)$ given the matrices $G_v$ and vectors $b_v$.  Further note that, for any $c \in \ensuremath{\mathcal{C}}$, $c|_{E_0} = A^{(0)} c|_{\{e^{(1)}, \ldots, e^{(s)}\}} + b^{(0)}$.

\paragraph{Finding $A^{(1)}$ and $b^{(1)}$.}
Recalling $B'$ from \eqref{eq:defB'}, let $E_1:= \left(E \setminus E(B')\right) \cup E_0$.  Note that for each $e \in E_1 \setminus E_0$, the label on $e$ can be determined in an affine way from the labels on edges in $E_0$.  More precisely, there is some vector $f^{(e)} \in {\mathbb F}_2^{E_0}$ of weight at most $d$ and some $h^{(e)} \in {\mathbb F}_2$ so that for any $c \in \mathcal{C}$,
$$
c_e = (f^{(e)})^T \cdot c|_{E_0} + h^{(e)},
$$
and moreover $f^{(e)}$ and $h^{(e)}$ can
be found in time $\mathrm{poly}(d)$ by inverting a submatrix of one of the matrices $G_v$.

Let $F \in {\mathbb F}_2^{(E_1\setminus E_0) \times E_0}$ be the matrix with the $f^{(e)}$ as rows, let $h\in {\mathbb F}_2^{E_1 \setminus E_0 }$ be the vector with entries $h^{(e)}$, and let
\[ A^{(1)} := \begin{bmatrix} \\ A^{(0)} \\ \\ \hline \\ F A^{(0)}\\  \\ \end{bmatrix} \qquad \text{and} \qquad b^{(1)} := \begin{pmatrix} | \\ b^{(0)} \\ | \\ \hline  | \\ F  b^{(0)} +h \\ | \\\end{pmatrix}. \]
Note that $A^{(1)}, b^{(1)}$ can be created in time $n\cdot \mathrm{poly}(d) \cdot s$ given $A^{(0)}$, $b^{(0)}$, $F$, and $h$.
Further note that for any $c \in \ensuremath{\mathcal{C}}$, $c|_{E_1} = A^{(1)} c|_{\{e^{(1)}, \ldots, e^{(s)}\}} + b^{(1)}$.

\paragraph{Finding $A^{(t)}$ and $b^{(t)}$ for $t=2, \ldots, T$.}
At this point, by the analysis above (following from Lemma \ref{lem:equiv_2}), we know that there are at most $\left(1 - \frac \epsilon 4\right)\left(\delta - \frac \lambda d\right) \delta nd$ edges which are not in $E_1$.   If we had labels for the edges in $E_1$,
then by Lemma~\ref{lem:uniquedec} we can use the algorithm \textsc{UniqueDecode} to recover the rest.

The algorithm \textsc{UniqueDecode} is given in Appendix~\ref{app:uniquedec} in Figure~\ref{fig:uniquedec}.
The basic idea is to iteratively decode $\ensuremath{\mathcal{C}}_0$ at vertices in $L$, then $R$, then $L$, and so on, to arrive at a unique assignment for all of the edges.
In order to do this with matrices, we will continue as above, creating $A^{(t)}, b^{(t)}$ from $A^{(t-1)},b^{(t-1)}$ for larger $t$ just as we did for $t=1$.  Note that the sets $E_t$ in \textsc{UniqueDecode} play the same role that they do here; $E_t$ represents the set of edges for which a label can be assigned in step $t$.

More precisely,
suppose that at step $t-1$, \textsc{UniqueDecode} has assigned labels to $E_{t-1}$, and
suppose that we have $A^{(t-1)} \in {\mathbb F}_2^{E_{t-1} \times s}$ and $b^{(t-1)} \in {\mathbb F}_2^{E_{t-1}}$ so that
for any $c \in \ensuremath{\mathcal{C}}$,
$$
c|_{E_{t-1}} = A^{(t-1)} c|_{\{e^{(1)}, \ldots, e^{(s)}\}} + b^{(t-1)}.
$$
At the next step, \textsc{UniqueDecode} would have assigned labels to edges in $E_{t} \setminus E_{t-1}$.  We note that the total amount of time
(over all iterations)
to determine the edges in $E_{t}\setminus E_{t-1}$ is the same as in \textsc{UniqueDecode}, which, with the right bookkeeping, is $n \cdot \mathrm{poly}(d)/\epsilon$.

Then as above, for every $e \in E_t \setminus E_{t-1}$, there is some vector $f^{(e)} \in {\mathbb F}_2^{E_{t-1}}$ of weight at most $d$, and some $h^{(e)} \in {\mathbb F}_2$ so that  for any $c \in \ensuremath{\mathcal{C}}$,
$$
c_e = (f^{(e)})^T \cdot c|_{E_{t-1}} + h^{(e)},
$$
and moreover, these vectors can be found in time $\mathrm{poly}(d)$.
Then, as above, let $F \in {\mathbb F}_2^{(E_{t}\setminus E_{t-1}) \times E_{t-1}}$ be the matrix with the $f^{(e)}$ as rows, let $h\in {\mathbb F}_2^{E_t \setminus E_{t-1}}$ be the vector with entries $h^{(e)}$, and  let
\[ A^{(t)} := \begin{bmatrix} \\ A^{(t-1)} \\ \\ \hline \\ F A^{(t-1)}\\  \\ \end{bmatrix} \qquad \text{and} \qquad b^{(t)} := \begin{pmatrix} | \\ b^{(t-1)} \\ | \\ \hline  | \\ Fb^{(t-1)} + h \\ | \\\end{pmatrix}. \]
As above, $A^{(t)}, b^{(t)}$ can be created in time $|E_t \setminus E_{t-1}| \cdot \mathrm{poly}(d) \cdot s$, and
for any $c \in \ensuremath{\mathcal{C}}$, $$c|_{E_t} = A^{(t)} c|_{\{e^{(1)}, \ldots, e^{(s)}\}} + b^{(t)}.$$

We continue this way until $E_T = E$, which happens eventually by Lemma~\ref{lem:uniquedec}.
Then, the amount of work that has been done to compute $A := A^{(T)}$ and $b:= b^{(T)}$ is
\[  n\cdot \mathrm{poly}(d) \cdot s + \sum_{t=2}^{T} |E_t \setminus E_{t-1} | \cdot \mathrm{poly}(d) \cdot s = n \cdot \mathrm{poly}(d,s), \]
as claimed.

\subsection{Finding $\hat A$ and $\hat b$}

Once we have found $A$ and $B$, our goal is to find the set of $x \in {\mathbb F}_2^s$ so that
\begin{equation}\label{eq:wantH}
HAx + Hb= 0,
\end{equation}
where $H \in {\mathbb F}_2^{2nd(1 - R) \times nd}$ is the parity-check matrix for $\ensuremath{\mathcal{C}}$.

First, notice that given the parity-check matrix for $\ensuremath{\mathcal{C}}_0$, $H_0 \in {\mathbb F}_2^{d(1 - R) \times d}$, and a description of $G$, we can access any entry of $H$ in time $O(1)$: for each vertex $v$, there is a parity check for each row of $H_0$ on the edges incident to $v$.
Next, notice that we can compute $HA$ in time $O(nd^2s)$:  each row of $H$ has at most $d$ nonzeros, so for each of the $O(nd)$ rows of $H$, we take time $O(ds)$ to compute the corresponding row of $HA$.  Similarly we can compute $Hb$ in time $O(nd^2)$.

Our goal then is to find the space of $x$'s which lead to legitimate codewords, which is
\[ \mathcal{W} = \left\{ x \in {\mathbb F}_2^s \,:\, HAx = Hb\right\}. \]
To find a description of $\mathcal{W}$, we first find a basis for the row space of $HA$, which we can do in time $O(nd s^3)$: we iterate through the $O(nd)$ rows of $HA$, and check (in time $O(s^3)$) to see if they are linearly independent from the rows we have already found.  If so, we add the new row to our basis and continue.  Suppose that $t \leq s$ is the dimension of the row space of $HA$, and let $j_1, \ldots, j_t \leq 2nd(1 - R)$ be the indices of the rows in the basis; let $J \in {\mathbb F}_2^{t \times s}$ be the submatrix of $HA$ with these rows.

Let $\hat A \in {\mathbb F}_2^{s \times (s-t)}$ be a matrix so that the columns of $\hat
A$ span $\ensuremath{\operatorname{Ker}}(J) = \ensuremath{\operatorname{Ker}}(HA)$.  Note that we can compute such an $\hat A$ in time $\mathrm{poly}(s)$ given $J$.  Next suppose there is some $\hat b \in {\mathbb F}_2^s$ so that
\begin{equation}\label{eq:wantb}
H A \hat b = Hb.
\end{equation}
 Then
the space we are after is
\[ \mathcal{W} = \inset{\hat A\hat x + \hat b \,:\, \hat x \in {\mathbb F}_2^{s-t}}. \]

If there is no such $\hat b$, then $\mathcal{L} = \emptyset$ and we should return $\bot$.
If such a $\hat b$ exists, we may compute it by finding a solution to the system
\begin{equation}\label{eq:tosolve}
J \hat b = \left(H b\right)_{j_1, \ldots, j_t}
\end{equation}
 which can be done in time $\mathrm{poly}(s)$.  Indeed,
suppose that there is some $\hat b$ satisfying \eqref{eq:wantb}.  Then $\hat b$ satisfies \eqref{eq:tosolve}, and for any $b'$ which also satisfies \eqref{eq:tosolve}, $b' \in \hat b + \ensuremath{\operatorname{Ker}}(J) = \hat b+ \ensuremath{\operatorname{Ker}}(HA)$, and hence $b'$ satisfies \eqref{eq:wantb} as well.
 Then we check to see if this $\hat b$ satisfies $HA\hat b = H b$, which can be done in time $O(nds)$.
If so, we return $A,b$ and $\hat A, \hat b$.  If not (or if no $\hat b$ satisfying \eqref{eq:tosolve} exists), then we return $\bot$.

\begin{figure}
\centering
\fbox{
\begin{tabular}{cc}
\begin{minipage}[c][]{.9\textwidth}
\vspace{.3cm}
\textbf{Algorithm:} \textsc{\FC}

\textbf{Inputs:} The state of \textsc{\LDS} after step 2.

\textbf{Output:} $A \in {\mathbb F}_2^{nd \times s}, b \in {\mathbb F}_2^{nd}, \hat A \in {\mathbb F}_2^{s \times a}, \hat b \in {\mathbb F}_2^s$ so that
\[ \mathcal{L} = \inset{ Ax + b \,:\, x = \hat A\hat x + \hat b \text{ for some } \hat x \in {\mathbb F}_2^{a} }\]
or returns $\bot$ if such things do not exist.

\begin{enumerate}
\item Form $A^{(1)}, b^{(1)},$ and find $E_1$ as described in the text in time $n \cdot \mathrm{poly}(d,s)$.
Let $P_0 \subseteq R, P_1 \subseteq L$ be the sets of vertices incident to an edge in $E \setminus E_1$.
\item For $t = 2,3, \ldots$:
\begin{enumerate}
\item If $P_{t-1} = \emptyset$, break.
	\item Initialize  $P_t \gets \emptyset$ and $E_t \gets E_{t-1}$.
	\item For each vertex $v \in P_{t-1}$ so that $|(\inset{v} \times \Gamma(v)) \cap E_{t-1}| > (1 - \delta)d$:
	\begin{enumerate}
	\item[$\circ$] Remove $v$ from $P_{t-1}$.
	\item[$\circ$] For any $(v,u) \notin E_{t-1}$, add  $(v,u)$ to $E_t$.
	\end{enumerate}
	\item For each vertex $v \in P_{t-1}$, for any $(v,u) \notin E_{t-1}$, add $u$ to $P_t$.

	\em By Lemma \ref{lem:uniquedec}, the total time (over all iterations) for the above steps is $n \cdot \mathrm{poly}(d)/\epsilon$. \em
	\item Find $A^{(t)}$ and $b^{(t)}$ given $A^{(t-1)}, b^{(t-1)}$ so that for all $c \in \mathcal{C}$,
\[ c|_{E_t} = A^{(t)} c|_{e^{(1)}, \ldots, e^{(s)}} + b^{(t)}. \]
This can be done in time $|E_t \setminus E_{t-1}| \cdot \mathrm{poly}(s,d)$ as described in the text.

\end{enumerate}
\item Let $A = A^{(t)}$ and $b= b^{(t)}$.
\item Compute $HA$ and $Hb$, which can be done in time $O(nd^2s)$.
Let $t \leq s$ be the dimension of the row space of $HA$, and
find $j_1, \ldots, j_t$ so that the rows of $HA$ indexed by $j_1, \ldots, j_t$ form a basis for the row space of $HA$.  This can be done in time $O(nds^3)$.  Let $J \in {\mathbb F}_2^{t \times s}$ be the submatrix of $HA$ with these rows.
\item Find $\hat A \in {\mathbb F}_2^{s \times (s-t)}$ whose columns are a basis for the kernel of $J$, and find $\hat b \in {\mathbb F}_2^s$ so that $J\hat b = (Hb)|_{j_1, \ldots, j_t}$.  This can be done in time $\mathrm{poly}(s)$.
\item If $HA\hat b \neq Hb$, return $\bot$.  In this case, $\mathcal{L} = \emptyset$.
\item Otherwise, return $A, b, \hat A, \hat b$.
\end{enumerate}
\end{minipage}
\vspace{.3cm}
&\hspace{.3cm}
\end{tabular}
}
\caption{\textsc{\FC}: prunes the list of advice strings $y^{(advice)}$ in \textsc{\LDS} to a space $\mathcal{L} = \inset{ Lx + \ell \,:\, x \in {\mathbb F}_2^{a} }$ and returns this description.}\label{fig:findcands}
\end{figure}

\begin{figure}
\centering
\fbox{
\begin{tabular}{cc}
\begin{minipage}[c][]{.9\textwidth}
\vspace{.3cm}
\textbf{Algorithm:} \textsc{ListDecode}

\textbf{Inputs:} A description of $G = (L \cup R,E)$ and $\ensuremath{\mathcal{C}}_0 \subseteq {\mathbb F}_2^d$, and $z \in ({\mathbb F}_2 \cup \{\bot\})^E$.

\textbf{Output:} A matrix $L \in {\mathbb F}_2^{nd \times a}$ and a vector $\ell \in {\mathbb F}_2^{nd}$ so that
 \[ \mathrm{List}_{\ensuremath{\mathcal{C}}}(z) = \inset{ L x + \ell \,:\, x \in {\mathbb F}_2^{a} } \]
for some integer $a$ (which does not depend on $n$),
or else $\bot$ if $\mathrm{List}_{\ensuremath{\mathcal{C}}}(z)$ is empty.

\begin{enumerate}
	\item Run Steps 1 and 2 from \textsc{\LDS} (Figure~\ref{fig:alg1}).
	\item Run \textsc{\FC} (Figure~\ref{fig:findcands}).
	\item If \textsc{\FC} returns $\bot$, return $\bot$.
	\item Otherwise, \textsc{\FC} returns $A, b, \hat A, \hat B$.
	\item Compute $L = A  \hat A$ and $\ell = A\hat b +b$.
	\item Return $L, \ell$.
\end{enumerate}
\vspace{.3cm}
\end{minipage}
& \hspace{.3cm}
\end{tabular}
}
\caption{\textsc{ListDecode}: Returns a description of $\mathrm{List}_{\ensuremath{\mathcal{C}}}(z)$ in time $n \cdot \mathrm{poly}(d,2^r, 1/\delta, 1/\varepsilon)$.}
\label{fig:alg2}
\end{figure}

\section{Second generalized distance of expander codes}\label{sec:delta2}

In this section we prove Lemma~\ref{lem:delta2}, restated below.

\restatethm{Lemma \ref{lem:delta2}}{restated}{
Let $\ensuremath{\mathcal{C}}_0 \subseteq {\mathbb F}_2^d$ be a linear code with distance $\delta$ and second generalized distance $\delta_2$, and
let $G = (L \cup R,E)$ be the double-cover of a $d$-regular expander graph with expansion $\lambda$.
Let $\epsilon>0$, and suppose that $\frac \lambda d \leq \frac{\delta_2 \delta^2 \epsilon^2} {16}$.
Then the expander code $\ensuremath{\mathcal{C}}(G, \ensuremath{\mathcal{C}}_0)$ has second generalized distance at least
$
(1-\epsilon)\cdot \delta \cdot \min\{\delta_2, 2\delta\} .
$
}

We first note the following simple claim which provides an equivalent definition of generalized distance. For a vector $x \in {\mathbb F}_2^N$, let $\mathrm{Supp}(x):=\{i \in [n] \mid x_i \neq 0\}$.

\begin{claim}\label{clm:general_dist_equiv}
Let $C \subseteq {\mathbb F}_2^N$ be a linear code.
The $r$'th generalized distance of $C$ is  $$\frac{1} {N} \min_{c_1, c_2,\ldots,c_r}\left| \mathrm{Supp}(c_1) \cup \mathrm{Supp}(c_2) \cup \cdots \cup \mathrm{Supp}(c_r) \right|,$$ where the minimum is taken over all $r$-tuples $c_1, c_2, \ldots, c_r$ of linearly independent codewords in $C$.
\end{claim}

We proceed to the proof of Lemma \ref{lem:delta2}.
Let $c,c'$ be two distinct  non-zero codewords in $\ensuremath{\mathcal{C}}(G, \ensuremath{\mathcal{C}}_0)$. Let $F:=\mathrm{Supp}(c)$ and $F':=\mathrm{Supp}(c')$, by Claim \ref{clm:general_dist_equiv} it suffices to show that
 $$|F \cup F'| \geq (1-\epsilon) \cdot \delta \cdot \min\{\delta_2, 2\delta\}  dn.$$ Let  $W$ denote the subset of vertices $v\in L \cup R$ which satisfy that $c|_{\Gamma(v)}, c'|_{\Gamma(v)}$ are two distinct non-zero  codewords in $\ensuremath{\mathcal{C}}_0$. Let $\epsilon_0:=\frac{\delta^{2} \epsilon} {8}$.
 Below we divide into cases.

 \paragraph{Case 1: $|F \cap F'| \leq \epsilon_0 d n$.}

In this case,
\begin{align*}
 |F \cup F'| & = |F| + |F'| - |F \cap F'| \\
& \geq \left(2\delta(\delta -\lambda/d) - \epsilon_0 \right) dn \\
& \geq (1-\epsilon)2\delta^2 dn,
\end{align*}
where the first inequality follows  since by Lemma \ref{lem:distance}, the code
$\ensuremath{\mathcal{C}}(G, \ensuremath{\mathcal{C}}_0)$
has relative distance at least $\delta(\delta -\lambda/d)$, and the second inequality follows by choice of $\frac{\lambda} {d} \leq \frac{\delta \epsilon} {2}$ and $\epsilon_0 \leq \delta^2 \epsilon$.

\paragraph{Case 2: $|W| \geq  \epsilon_0^2 n$.} Without loss of generality, we may assume that $|W \cap L| \geq |W \cap R|$, so $|W \cap L| \geq \frac{\epsilon_0^2} {2} n$. We apply the expander mixing lemma with $S_1 :=W \cap L$, and $T_1 \subseteq R$ the set of all right vertices  that are incident to an edge from $F \cup F'$.

Recall that for any vertex $v \in S_1 $ it holds that $c|_{\Gamma(v)}, c'|_{\Gamma(v)}$ are two distinct non-zero codewords in $\ensuremath{\mathcal{C}}_0$, and so
$$\big|\mathrm{Supp}\left(c|_{\Gamma(v)}\right) \cup \mathrm{Supp}\left( c'|_{\Gamma(v)}\right)\big| \geq \delta_2 \cdot d.$$ Therefore, any vertex $v \in S_1 $ is incident to at least $\delta_2 d$ edges in $F \cup F'$, and so  $|E(S_1 ,T_1)| \geq \delta_2 d|S_1 |$.

By the expander mixing lemma, the above implies in turn that
$$\delta_2 d|S_1 | \leq |E(S_1 ,T_1)| \leq  \frac{d} {n} |S_1 ||T_1| +\lambda \sqrt{|S_1 ||T_1|},$$
and rearranging gives
$$|T_1| \geq \left( \delta_2 - \frac{\lambda} {d} \sqrt{\frac {|T_1|} {|S_1 |} } \right)  n \geq \left(\delta_2 - \frac{\lambda} {d}
 \cdot \frac {2} {\epsilon_0} \right) \cdot n ,$$
where the second inequality follows by assumption that $|S_1 | \geq \frac{\epsilon_0^2 } {2}n$.

Finally, note that any vertex $v\in T_1$ has at least $\delta d$ incident edges in $F \cup F'$, and so
$$|F \cup F'| \geq \delta d |T_1| \geq  \delta \left(\delta_2 - \frac{\lambda} {d}  \cdot \frac {2} {\epsilon_0}\right)  d n \geq \delta \delta_2 (1-\epsilon)d n,$$
where the last inequality follows by choice of $\frac \lambda d \leq  \frac{\delta_2 \delta^2 \epsilon^2} {16} = \frac{\delta_2   \epsilon_0 \epsilon} {2}$.

\paragraph{Case 3: $|F\cap F'| \geq \epsilon_0 d n$ and $|W| \leq  \epsilon_0^2 n$.}
Under these assumptions, Claims \ref{clm:delta2_intersect} and \ref{clm:delta2_diff} below show that  both the intersection
 $F\cap F'$ and the symmetric difference $F \triangle F'$ are of size at least $(1-\epsilon)\delta^2 dn$. This implies in turn that
 $$|F \cup F'| = |F \cap F'| + |F \triangle F'| \geq (1-\epsilon) 2 \delta^2dn.$$

\begin{claim}\label{clm:delta2_intersect}
$|F \cap F'| \geq (1-\epsilon)\delta^2dn$.
\end{claim}

\begin{proof}
We apply the expander mixing lemma with $S_2 $ ($T_2$, resp.) being the set of all vertices $v \in L \setminus W$ ($v \in R \setminus W$, resp.) that are incident to an edge from $F \cap F'$.
Without loss of generality we may assume that $|S_2 | \geq |T_2|$.

Next observe that since $\ensuremath{\mathcal{C}}_0$ has relative distance at least $\delta$, any vertex $v \in S_2$ is incident to at least $\delta d$ edges in $F \cup F'$. We claim that these edges are in fact contained in $F \cap F'$; Otherwise, $v$ is incident to some edge from $F \cap F'$ and another edge from $F \triangle F'$ which means that $c|_{\Gamma(v)}, c'|_{\Gamma(v)}$ are two distinct non-zero codewords in $\ensuremath{\mathcal{C}}_0$, contradicting the assumption that $v \notin W$. We conclude that any vertex $v \in S_2 $ has at least $\delta d$ incident edges that are incident to either $T_2$ or $W$.

Consequently, we have that
$$|E(S_2 ,T_2)| \geq \delta d |S_2 | -d |W|  =   \left(\delta- \frac{|W|} {|S_2 |}\right) d|S_2 | \geq  \left(\delta  - \frac{\epsilon_0} {1-\epsilon_0}\right)d|S_2 | ,$$
where the last inequality uses the assumptions that  $|W| \leq \epsilon_0^2 n$ and $|F\cap F'| \geq \epsilon_0 d n$, implying in turn that
$$|S_2 | \geq \frac{|F \cap F'|} {d} -|W| \geq \epsilon_0 (1- \epsilon_0) n .$$
On the other hand, by the expander mixing lemma we have that
$$
 |E(S_2 ,T_2)| \leq \frac{d} {n} |S_2 ||T_2| +\lambda \sqrt{|S_2 ||T_2|},
$$

Combining the above, rearranging,  and recalling our assumption that $|S_2 | \geq |T_2|$, gives
$$|T_2| \geq \left(\delta - \frac{ \epsilon_0} {1-\epsilon_0} -\frac {\lambda} {d} \right ) n.$$
Finally, similarly to the above, we conclude that
$$|F \cap F'| \geq \left(\delta  - \frac{\epsilon_0} {1-\epsilon_0}\right)d|T_2| \geq\left(\delta - \frac{ \epsilon_0} {1-\epsilon_0} -\frac {\lambda} {d} \right )^2 dn \geq \delta^2\left(1-  \varepsilon \right)dn,$$
where the last inequality follows by choice of $\epsilon_0 \leq \frac{\delta\epsilon} {8}$ and $\frac{\lambda} {d} \leq \frac{\delta \epsilon} {4}$.
\end{proof}

\begin{claim}\label{clm:delta2_diff}
$|F \triangle F'| \geq (1-\epsilon)\delta^2dn$.
\end{claim}

\begin{proof}
 Similarly to the previous claim, we apply the expander mixing lemma with $S_3$ ($T_3$, resp.) being the set of all vertices $v \in L \setminus W$ ($v \in R \setminus W$, resp.) that are incident to an edge from $F \triangle F'$, and we may assume that  $|S_3| \geq |T_3|$.

 Once more we observe that  any vertex $v \in S_3$ is incident to at least $\delta d$ edges in $F \triangle F'$, and we conclude that any vertex $v \in S_3$ has at least $\delta d$ incident edges that are incident to either $T_3$ or $W$.
Consequently, as before we have that
$$|E(S_3,T_3)| \geq    \left(\delta- \frac{|W|} {|S_3 |}\right) d|S_3 | \geq  \left(\delta  - \frac{\epsilon_0^2} {\delta\left(\delta - \frac \lambda d\right)-\epsilon_0^2}\right)d|S_3 | ,$$
where the last inequality uses the assumption that  $|W| \leq \epsilon_0^2 n$, and the fact that $|F \triangle F'| \geq \delta \left(\delta -\frac \lambda d\right)dn$ (since $F \triangle F'$ is the support of the non-zero codeword $c+c' \in \ensuremath{\mathcal{C}}(G,\ensuremath{\mathcal{C}}_0)$), implying in turn that
$$|S_3| \geq \frac{|F \cap F'|} {d} -|W| \geq \delta\left(\delta - \frac \lambda d\right) n - \epsilon_0^2 n .$$

On the other hand, by the expander mixing lemma we have that
$$
 |E(S_3 ,T_3)| \leq \frac{d} {n} |S_3 ||T_3| +\lambda \sqrt{|S_3 ||T_3|},
$$
and combining with the above, rearranging, and recalling our assumption that $|S_3 | \geq |T_3|$, this gives
$$|T_3| \geq \left(\delta - \frac{\epsilon_0^2} {\delta\left(\delta -\frac \lambda d\right)-\epsilon_0^2}-\frac {\lambda} {d} \right ) n.$$
Finally, similarly to the above, we conclude that
$$|F \cap F'| \geq \left(\delta  -\frac{\epsilon_0^2} {\delta\left(\delta -\frac \lambda d\right)-\epsilon_0^2}\right)d|T_3| \geq\left(\delta - \frac{\epsilon_0^2} {\delta(\delta - \lambda/d)-\epsilon_0^2} -\frac {\lambda} {d} \right )^2 dn \geq \delta^2\left(1-  \varepsilon \right)dn,$$
where the last inequality follows by choice of $\epsilon_0^2 \leq \frac{\delta^{3}\epsilon} {8}$ and $\frac{\lambda} {d} \leq \frac{\delta \epsilon} {4}$.
\end{proof}

\section*{Acknowledgements}
Most of this work was done while the authors were participating in the Summer Cluster on Error-correcting Codes and High-dimensional Expansion at the Simons Institute for the Theory of Computing at UC Berkeley.
We thank the Simons Institute for the hospitality.

\bibliographystyle{alpha}

redpajama_set_name: RedPajamaArXiv


text:
Frank Gardiner – bushranger
Escaped, Gaols, Twisted History
Frank Gardiner, born in 1830 Scotland and shipped out to Australia as a child with his parents, made an illustrious career out of horse thievery and highway robbery. On 15 June 1862, Gardiner along with Ben Hall, John Gilbert and associates held up a gold escort travelling from Forbes to Bathurst. They stole over £14,000 worth of gold and bank notes – Australia's biggest gold robbery. In February 1864, New South Wales police traced Gardiner to his hideout in Queensland. He was arrested and sentenced to 32 years of hard labour in July. Ten years later, Governor Hercules Robinson granted him mercy and released him, subject to exile. Gardiner lived in Hong Kong and Francisco before dying in Colorado in 1903. "Colonial rule was constantly challenged by bushrangers – it was a major threat to the central administration," says Dr Hamish Maxwell-Stewart from the University of Tasmania. "They were turning the tables on the convict state."
https://twistedhistory.net.au/wp-content/uploads/2016/08/image-24.jpg 458 321 Limelight https://twistedhistory.net.au/wp-content/uploads/2018/10/Twisted-Logo-Tranparent-no-shadow.png Limelight2018-08-06 01:00:092018-08-10 01:00:23Frank Gardiner – bushranger
Japanese Bombing of Mossman – Queensland
In WWII, the first real attack of the Japanese on an Australian base occurred with the bombing of Darwin on 19 February 1942. That attack was the first of about 90 attacks that occurred at various places in and around Australia during the war. Shortly after this initial attack, the northwest coastal towns of Broome and Wyndham also came under fire, followed by Derby a few weeks later. It is less well known that the town of Mossman, near Cairns, was also bombed. On the night of 31 July 1942, Sub Lieutenant Mizukura dropped eight bombs, thinking that the lights he saw were Cairns. In fact it was Mossman, and while the other seven bombs have never been recovered, one fell on a sugar cane farm near Saltwater, Mossman. It caused a crater that measured 7 metres wide and a metre deep, and sent flying shrapnel through the window of the nearby farmhouse. Farmer Felice Zullo's two and a half year old daughter was wounded in the head from shrapnel which entered the house, although she was in her cot at the time.
The child grew up to become Mrs Carmel Emmi, and on 31 July 1991, Mrs Emmi unveiled a plaque on a memorial stone commemorating the attack and her survival. The memorial stone is situated on Bamboo Creek Road, after the turnoff to Whyanbeel.
https://twistedhistory.net.au/wp-content/uploads/2016/06/image-103.jpg 869 1368 Limelight https://twistedhistory.net.au/wp-content/uploads/2018/10/Twisted-Logo-Tranparent-no-shadow.png Limelight2018-07-31 18:00:172018-07-22 01:44:24Japanese Bombing of Mossman – Queensland
'Yowie' of Southeast Queensland
On this day …….. 25th of July 1851
From the mid 1800s, writings about strange ape-like creatures in Australia abounded. One of these was a diary entry from the Connondale region of southeast Queendland, written on the 25th of July 1851, which stated:
"They are short, stout and of very muscular appearance. They are covered in thick black hair…Their hair and beards are long…They are completely naked…the stench of their body is unbearable…great hunters of the forests and jungles…They come and go without being seen. They can hide in the undergrowth in such a manner that one can be touched or struck without their person being visible. I am to wonder if these are the same people…who take people away when they dare enter the forests and jungles…the women made grunt-like expression during contact…the child hung to its mother on the breast in the manner of an ape. These were the Woningityan/Won-ingee-tyan – the shadow men creatures of the jungles and forests…"
https://twistedhistory.net.au/wp-content/uploads/2016/06/image-91.jpg 225 300 Limelight https://twistedhistory.net.au/wp-content/uploads/2018/10/Twisted-Logo-Tranparent-no-shadow.png Limelight2018-07-25 18:00:192018-07-22 00:47:38'Yowie' of Southeast Queensland
Blind mans honour
Asylums, Twisted History
A blind man in a Brisbane Asylum never missed an inmates funeral in the 30 years he was there between 1890 and 1920. He took his stand 200 yards from the morgue and when the hearse passed he, fell in behind for the mile walk to the cemetery. After listening to the service, he made his way back to his room. He attended more than 3500 funerals.
https://twistedhistory.net.au/wp-content/uploads/2016/07/image-128.jpg 326 451 Limelight https://twistedhistory.net.au/wp-content/uploads/2018/10/Twisted-Logo-Tranparent-no-shadow.png Limelight2018-07-19 20:56:302018-07-22 20:56:47Blind mans honour
Man Found with Tongue Frozen to Pipe
William Cunningham of Paddington, Brisbane was found with his tongue frozen against a pipe at the Mountain Milk Company's freezing works at Dayboro, Queensland, on the 18th of July 1936. The 20 year old was released from the pipe after water was poured on his tongue.
https://twistedhistory.net.au/wp-content/uploads/2016/06/image-80.jpg 503 670 Limelight https://twistedhistory.net.au/wp-content/uploads/2018/10/Twisted-Logo-Tranparent-no-shadow.png Limelight2018-07-18 21:08:552018-07-22 21:09:08Man Found with Tongue Frozen to Pipe
Two Meter Crocodile
On this day …….. 26th of June 2001
On this day in 2001 an unexpected speed bump on the road to the Cairns Airport in Queensland gave a taxi driver and his passenger a fright when it turned out to be a two meter crocodile laying in the sun.
https://twistedhistory.net.au/wp-content/uploads/2016/05/image-247.jpg 366 650 Limelight https://twistedhistory.net.au/wp-content/uploads/2018/10/Twisted-Logo-Tranparent-no-shadow.png Limelight2018-06-26 18:17:282018-06-26 18:17:28Two Meter Crocodile
Blacktrackers on the Hunt for Ned Kelly
The blacktrackers brought from Queensland to find Ned Kelly and his Gang left Benalla, North East Victoria on this day in 1880 after being withdrawn from the hunt. The Queensland government considered they were not being given a fair chance. The operation had not been encouraged by officers in the Victorian Police (like Commissioner Standish), who thought it would be rather bad form if the outlaw could be captured by savages and not by European policeman.
https://twistedhistory.net.au/wp-content/uploads/2016/05/image-240.jpg 696 1157 Limelight https://twistedhistory.net.au/wp-content/uploads/2018/10/Twisted-Logo-Tranparent-no-shadow.png Limelight2018-06-24 18:00:282018-06-23 16:56:08Blacktrackers on the Hunt for Ned Kelly
Death of the Oldest Known Animal in Captivity
On this day …….. 23rd of June 2006
"Harriet" was a Giant Galapagos tortoise, at least 176 years old, which resided at Steve Irwin's Australia Zoo near Beerwah, Queensland, Australia. Believed for one hundred years to have been a male, she was the world's oldest living chelonian in captivity. A chelonian is a reptile with a shell or bony plates. The giant tortoise was taken from the Galapagos Islands by naturalist Charles Darwin in 1835 as a personal pet during his five-year voyage on the HMS Beagle. On that voyage was a young naval officer, John Clements Wickham. After studying Harriet whilst formulating his theory of evolution, Darwin handed the tortoise on to Wickham when the latter sailed for Brisbane to take up a post as police magistrate. Over the years, the tortoise was carefully tended, and in 1958, was moved to naturalist David Fleay's wildlife park on the Gold Coast. She was moved to Australia Zoo on the Sunshine Coast in 1987 where she enjoyed celebrity status until her death on 23 June 2006.
https://twistedhistory.net.au/wp-content/uploads/2016/05/image-238.jpg 552 800 Limelight https://twistedhistory.net.au/wp-content/uploads/2018/10/Twisted-Logo-Tranparent-no-shadow.png Limelight2018-06-23 15:18:122018-06-23 15:18:12Death of the Oldest Known Animal in Captivity
Entangled Bulls
On this day in 1906, two cows owned by Mr F. Dolan of Logan River district in Queensland were found with their horns entangled as a result of fighting. They had apparently been that way for some time. They were freed by a hand saw cutting the horns. Neither animal was injured, although they were both very weak.
https://twistedhistory.net.au/wp-content/uploads/2016/05/image-233.jpg 279 351 Limelight https://twistedhistory.net.au/wp-content/uploads/2018/10/Twisted-Logo-Tranparent-no-shadow.png Limelight2018-06-20 18:00:502018-06-20 03:26:17Entangled Bulls
TWO FISH ONE HOOK
While fishing on the Balonne River in Queensland on this day in 1925, a lucky fisherman managed to catch two fish with the one hook. At first a 3kg cod took the bait, the fish was in turn swallowed by an 18kg cod. Both fish were successfully landed.
https://twistedhistory.net.au/wp-content/uploads/2016/05/image-231.jpg 525 800 Limelight https://twistedhistory.net.au/wp-content/uploads/2018/10/Twisted-Logo-Tranparent-no-shadow.png Limelight2018-06-18 18:00:282018-06-17 00:07:50TWO FISH ONE HOOK
Australian Mass Shootings
Murder, Twisted History
A list of Australia's mass shootings
Shipwreck of the Batavia in – 1628 (Western Australia) 110 Dutch
Cape Grim massacre – 10 February 1828 (Tasmania) – 30 Indigenous Australians
Convincing Ground – 1833 Portland (Victoria) – 200 Indigenous Australians
Pinjarra – 28 October 1834, Pinjarra (Western Australia ) – 40 Indigenous Australians
Waterloo Creek – 1838 (New South Wales) – 70 Indigenous Australians
Myall Creek – 10 June 1838 (New South Wales) – 30 Indigenous Australians
Murdering Gully – 1839, Camperdown (Victoria) – 40 Indigenous Australians
Campaspe Plains – June 1839 (Central Victoria) – 40 Indigenous Australians
Gippsland massacres – 1840-1850 (Victoria) – 1000 Indigenous Australians
Cullin-La-Ringo – 17 October 1861 (Central Queensland) – 19 Indigenous Australians
Flying Foam – 1868 Flying Foam (Western Aust)150 – Indigenous Australians
Palmer massacre – 1878 Palmer River (Queensland) – 150 Chine against each other
Ching family murders – 16 November 1911 Mackay (Queensland) – 6
Broken Hill – 1 January 1915 Broken Hill (New South Wales) – 4 shooting spree
Mowla Bluff massacre – 1916 Kimberley (Western Aust) – 400 Indigenous Australians
Forrest River massacre – 1926 Kimberley (Western Aust) – 11 Indigenous Australians
Coniston massacre – 1928 (Northern Territory) – 170 Indigenous Australians
Hope Forest massacre – 6 September 1971 (Sth Aust) – 10 Rampage killing
Campsie murders – 24 September 1981 (New South Wales) – 5 Rampage killing
Wahroonga murders – 1 June 1984 (New South Wales) – 5 Rampage killing
Milperra – 2 Sept 1984 (New South Wales) – 7 Shootout between two rival gangs
Top End Shootings – 1987 (Northern Territory) – 5 Spree killing
Hoddle Street massacre – 1987 Clifton Hill (Victoria) – 7 Spree shooting
Canley Vale murders – 1987 (New South Wales) – 5 Rampage killing
Queen Street massacre – 1987 Melbourne (Victoria) – 8 Spree shooting
Oenpelli shootings – 1988 (Northern Territory) – 6 Rampage killing
Surry Hills shootings – 1990 (New South Wales) – 5 Spree shooting
Strathfield massacre – 1991 (New South Wales) – 7 Spree shooting
Central Coast massacre – 1992 Terrigal (New South Wales) 6 – Spree shooting
Cangai siege – 1993 (New South Wales) – 5 Rampage killing
Hillcrest Murders – 1996 Hillcrest (Queensland) – 6 Rampage killing
Port Arthur massacre – 1996 (Tasmania) – 35 Spree shooting
Monash University Shooting – 2002 Melbourne (Victoria) – 2 Shooting spree
Hectorville siege – 2011 (South Australia) – 3 Shooting
Hunt family murder – 2014 Lockhart (New South Wales) – 5 Shooting spree
Logan shooting – 2014 Logan (Victoria) – 3 Shooting spree
Photo from 1997, piles of guns in Australia are moved after a landmark law that resulted from a mass shooting. Now, Australians are saying the US could learn their lesson.
https://twistedhistory.net.au/wp-content/uploads/2016/06/image-137.jpg 700 700 Limelight https://twistedhistory.net.au/wp-content/uploads/2018/10/Twisted-Logo-Tranparent-no-shadow.png Limelight2018-06-16 18:00:422018-06-14 13:55:08Australian Mass Shootings
AUSTRALIA'S TOP 10 DEADLIEST FLOODS
Between 1852 and 2011, at least 951 people were killed by floods, another 1326 were injured, and the cost of damage reached an estimated $4.76 billion dollars.
1. June 1852 – Gundagai, NSW
89 deaths, entire settlement of 250 people destroyed
There's little doubt that the 2010/2011 Queensland floods were Australia's most devastating in terms of damage to infrastructure and cost, but the worst loss of life happened in June 1852 when massive flooding on the Murrumbidgee River swept away most of the town of Gundagai, leaving just three houses standing. Eighty-nine people were killed, more than third of the population. The town was later rebuilt on higher ground.
2. Dec 2010 – Jan 2011 – Brisbane and SE QLD
35 confirmed deaths, $2.38 billion in damage
With more than 200,000 people affected state-wide, the economic damage from this flood was estimated at $2.38 billion. Beginning with rains in September and then culminating with Category 1 Cyclone Tasha crossing the Far North Queensland coast on 24 December 2011, this was probably the most notorious flood in Australian history. In Brisbane, the river peaked at 4.46m on 13 January, flooding more than 28,000 homes and leaving 100,000 without power. Cyclone Yasi, which hit 3 Feburary, caused further damage to already sodden towns.
3. Dec 27, 1916 – Clermont and Peak Downs, QLD
65 deaths, 10 homes destroyed, 50 buildings damaged and 10,000 livestock killed
A cyclone swept the coast along the Whitsunday Passage, bringing heavy rainfall to Clermont, Sapphire and Peak Downs. This usually flood-savvy town forgot to counter for the runoff from nearby catchments and creeks and the debris it carried with it at crushing speeds. The torrent smashed through houses and caused widespread damage. The lower part of Clermont was submerged, so the town was rebuilt on higher ground.
4. Nov 29, 1934 – Melbourne, VIC
36 deaths, 6000 homeless and 400+ buildings damaged
In late November 140mm of rain fell in Melbourne over a 48-hour period. To the east of Melbourne, in South Gippsland, 350mm fell over the same two-day period. The downpour resulted in landslides, evacuations and many submerged roads. Eighteen people drowned, with a further 18 killed by collapsing buildings and other dangers. More than 400 buildings were damaged in Melbourne and 6000 people were left homeless.
5. Feb 15, 1893 – Ipswich, QLD
35 deaths, 300 people injured and two bridges destroyed
Often referred to as the Black February Flood, the extreme weather conditions and heavy rain were brought about by tropical Cyclone Bundinyong. The Crohamhurst weather station recorded 914mm of rain in a 24-hour period and another gauge recorded almost 889mm of rainfall in Brisbane's water catchments. Both the Victoria Bridge and the Indooroopilly railway bridge collapsed, with 35 people killed and 300 injured.
6. Feb 1927 – Brisbane, Cairns, Townsville, QLD
47 deaths, 16 homes destroyed, an estimated £300,000 in damages
A tropical cyclone hit north of Cairns, causing major rainfall through Queensland, reaching as far as Toowoomba. The torrential rain, which fell from 9-17 February, led to the deaths of 47 people, damaged roads, railways, bridges and buildings – and completely destroyed 16 houses. There was also widespread loss of livestock. The estimated costs reported at the time were in the region of £300,000.
7. Apr 1929 – Northern Tasmania
22 deaths, 1000 homes damaged, 25 bridges destroyed
The area of Northern Tasmania is prone to heavy rainfall over short periods and up to 500mm of rain fell over three days. The floodwater carved a path across the region, destroying everything in its path, including vehicles, buildings and railroad tracks. It inflicted huge stock losses, the evacuation of 3500 people, while damaging 35 bridges and 1000 homes.
8. Feb 1955 – Hunter Valley, NSW
24 deaths, 59 homes destroyed, 5200 homes flooded and 40,000+ people evacuated
The majority of deaths were around Singleton and Maitland, but most other river systems in the state were also in flood. These floods in the Hunter Valley have become symbolic in the Australian psyche of the dramatic nature of flood damage and rescue. About 15,000 people were evacuated from around these two towns, with more than 40,000 people being evacuated from a total of 40 towns. Five of the lives lost were due to electrocution during rescue operations.
9. Jan – Apr 1974 – Brisbane, QLD
14 deaths, 300 injured, 56 homes destroyed, an estimated $68 million in damages
After a particularly wet year in 1973, Brisbane was inundated with water when tropical cyclone Wanda hit the north of the city on 25 January 1974. By 29 January the Brisbane area had recorded 900mm of rain, with 314mm of rain falling in a 24-hour period. In the coming months the torrential rain swept down the east coast, causing floods in parts of NSW and Tasmania. The floods killed 14 people and injured 300 more, as well as destroying 56 homes and damaging 6000 others. In all, an estimated $68 million worth of damages occurred.
10. Aug 1986 – Hawkesbury and Georges River Flood, NSW
6 dead, 10,000 homes damaged, an estimated $35M in damages.
With the rainfall reaching 327.6mm in 24 hours, this day has been dubbed Sydney's wettest day ever. The torrential rain created chaos, with flooded roads prompting many motorists to abandon their cars. Bus services were severely disrupted in the city and trains were halted due to flooded tunnels.
https://twistedhistory.net.au/wp-content/uploads/2016/06/image-8.jpg 617 990 Limelight https://twistedhistory.net.au/wp-content/uploads/2018/10/Twisted-Logo-Tranparent-no-shadow.png Limelight2018-06-06 18:00:322018-06-01 00:38:47AUSTRALIA'S TOP 10 DEADLIEST FLOODS

redpajama_set_name: RedPajamaCommonCrawl


text:
This website uses cookies to ensure you get the best experience on our website. Privacy Policy.
Creative campaigns
Site migrations
LinkedIn training
WeThrive
Generated leads at conversion rates of 5.26% and 3.12%
WeThrive provide employee engagement solutions for businesses. The aim was to use digital to increase awareness of the brand to HR professionals and generate leads, which could then be followed up and converted into customers.
wethrive.net
Real-time bidding & AI
In order to fulfil the objectives we used two paid channels in combination with each other. We know that LinkedIn can be effective for reaching a specific B2B audience, so first we set up and ran a brand awareness campaign targeting HR decision-makers, getting the brand name in front of them and piquing their interest enough to drive them to the website to find out more. LinkedIn has a relatively high cost-per-click compared to other channels, however we could be highly targeted, which was important for this fairly niche product. The targeting was also geographically focussed around key business areas and specified length of experience within HR, to include HR Managers, Directors and Regional Managers.
The second part of the strategy was to use AdRoll's real-time bidding and AI capabilities to run a retargeting campaign. People who had already visited the WeThrive website were served a display ad as they browsed elsewhere, inviting them to sign up for a free webinar. We were also able to specifically retarget those who had been to the sign up page but not signed up, increasing the chances of them converting into leads.
It was interesting to see that those who had come to the site after seeing a LinkedIn ad engaged with the website more when they got there and were more likely to sign up when retargeted, showing the effectiveness of using the two channels together.
Project stats
LinkedIn was primarily aimed at generating brand awareness but also generated webinar sign ups at a 5.26% conversion rate, further justifying the spend.
AdRoll generated a greater number of sign ups, at a conversion rate of 3.12%.
As a benchmark, Hubspot expects a rate of 1.5 – 3% to convert a website visitor into a contact for B2B paid media campaigns.
Related paid media work
Dont Buy Her Flowers
KIMS Hospital
Cooden Medical Group
Posturite
Tapi Carpets & Floors
Contact the team to find out more
hello@foxbear.co.uk
I'm interested in *Branding and DesignCreative MarketingPaid mediaWebsite optimisationPR
I understand Fox&Bear will securely hold my data.
Contact us to find out out how
we can help grow your business.
Unit A, Level 8 South,
New England House,
New England Street,
Brighton BN1 4GH
Get in touch using the following channels:
© 2022 Fox&Bear Ltd. All rights reserved. Company registration number: 08472905.
Registered office: The Old Bank, 257 New Church Road, Hove, East Sussex, United Kingdom, BN3 4EL. Privacy Policy


Wander Indiana Courtesy of Indiana Dunes…and Me!
Congratulations Terri DeWulf!! YOU are the winner of the trip!!!
I am SO excited to share my latest giveaway with you all! I just love giving things to my friends and what better to share than a weekend trip with dinner, lodging and entertainment! I am excited for YOU!
Recently my family and I had the pleasure of visiting The Indiana Dunes area near Chesterton, Indiana. It was a dream trip. No shopping, no tourist traps, just fun in the sun and playing on the beautiful beaches of Lake Michigan. Read more about our trip, and where YOU can go too HERE.
In partnership with the Indiana Dunes Visitors Center I am giving the following 'Family Getaway' package to one lucky reader! Entering will be simple with several ways to get your name in the hat! Please read my POST about our trip so you can see all of the pictures I took….This is where YOU will be going too ????
*One night stay for you and your family at The Inn at Aberdeen in Valparaiso, one of the best B&B's I have ever stayed in,also has a fantastic breakfast in the morning! AND it's included!
*1 $50 gift card for dinner at Lucrezia Cafe in Chesterton, really good food, great atmosphere!
*4 passes to TalTree Arboreum and Gardens-home of the COOLEST train garden EVER!!
5 minutes after we got there…..
After a fun day at the beach we got all dressed up for dinner out!
Trains. Too cool, this picture doesn't do it justice!
Leave a comment below, you must do this for every entry separately. Do any one or all of these daily for more entries, it's up to you! Please make sure this trip is possible in your future before you enter and please leave a contact email address in your comments so I can find you. You will have 24 hours to respond or I will have to chose someone else ????
Giveaway runs Tuesday July 10-Sunday July 15th at 9 pm EST!!
*Visit one of the websites listed (using the links in their names) and tell me one fact you got from their website. I will check too, so be original! Each comment is an entry.
Each tweet with link for it is an entry.
*Follow Indiana Dunes, Inn at Aberdeen, TalTree Arboreum or Lucrezia on Facebook, tell them Basilmomma sent you ???? Leave an individual, separate comment for each page you liked. Each 'like' is an entry. Visit one or all, it's up to you!
*Bonus: if you share this on your Facebook wall, and tag me, I will give you a bonus entry! Make sure to tag Basilmomma so I see it ????
Bottom line-each separate comment is an entry. I have just given a variety of ways to win in case you do not use social media, I want it to be fair ????
That's it! Do any or all of these for a chance to win! Best of luck to you!
All of these opinions are my own. I was not paid to give this away but I did receive a comparable package to enjoy with my family (since you can see us there in the pictures ????
Heather! This is so cool!!! We take the commuter train from Chesterton into Chicago all the time and every time we go we say we want to come back to enjoy the dunes and the town and the inns - this is awesome!!! Pictures of your trip look GREAT!!!
Wow...would love to get to the Arboretum with my camera in hand and my son with his camera. We always love a great nature walk.
From the Dunes website...Without fire, there could be no prairie at Indiana Dunes National Lakeshore. Non-prairie plant species would crowd out native prairie grasses. These rare grasslands are maintained through periodic controlled burns.
At the Inn at Aberdeen you can design your own gift package that includes room, dinner and activities like golf!
I learned that part of the train garden is set in limestone. It's so beautiful!
I would love to win a trip here! I live in Indiana and have been to Michigan but not the Dunes. I learned they have an annual Blueberry Social on July 11th and I would love to go to that.
I like Indiana Dunes on FB.
I liked Inn at Aberdeen on FB.
I liked TalTree Arboreum on FB.
I liked Lucrezia on FB.
I "liked" Indiana Dunes on facebook.
I "liked" the Inn at Aberdeen on facebook.
I "liked" Lucrezia on facebook.
Lucrezia has one of the most unique drinks I've ever heard of, the Shroomtini "Vodka, splash of spicy pickled juice, garnished with spicy pickled mushrooms"! Although I wouldn't like it, since I don't like mushrooms! Dee dno1@columbia.edu p.s. I tweeted (@asiansplenda) and did 2 FB posts (tagged you).
I love that the Inn at Aberdeen was featured in Midwest Living - one of my favorite resources for finding great midwest places to visit!
I learned Native Plant Garden has a new addition that is the Monarch Waystation that showcases plants that play a vital role in the lifecycle of a butterfly!
I learned that Taltree existed. I HAD NO IDEA, and my parents live just two exits down on I-94! Can't wait to visit!
I liked Taltree on Facebook!
Liked @Taltreehort on Twitter. And OMG, it's Thomas Month. Seriously, how did I not know this was there?!?!?
I liked the Inn at Aberdeen on Facebook.
I like Taltree on Facebook.
I like Lucrezia on Facebook!
Love the pictures! We have always wanted to explore that area, but have not had the chance. Thanks for sharing!


•	1 1/2 a cup of flour.
•	3/4 a cup of butter.
•	3/4 a cup of castor sugar.
•	Scrub butter or ghee until it becomes soft.
•	Add sugar and stir the mix well with a wooden spoon until it becomes white and fragile like cream.
•	Sift flour with the yeast and then add the used dried ingredients (as sweetened fruit, (walnut- almond), condiments…).
•	Add vanilla to the egg and shake well.
•	Add egg then flour gradually to the mix that includes butter and sugar and flip well until you get somehow a dry dough.
•	Leave the dough dried a little to make it easy to laminate it, then add the orange peel on it and mix well.
•	Laminate the dough with a thickness of 1/2 a cm and then cut it into different shapes and then put it in the baking tray.
•	Paint the surface of biscuit with egg yolk and then insert it in a medium heat oven for 10- 15 minutes.
•	Leave it to cool and then serve it in a glass plate.


Health Education Student Growth Goals- we got it!
Foundations of Health Education- National Health Education Content Standards, CDCs Health Education Curriculum Analysis Tool and a quick-guide from Kentucky Department of Education on the Youth Risk Behavior Survey.
Those of you teaching in Kentucky have heard PGES, Program Review, Student Growth Goals multiple times in different settings. Even if you are obsessed with student achievement & assessment (like I am), the terms may make you groan, roll your eyes or have a stomach ache. It is not because you don't believe in clear criteria for accountability for yourself or your students. I'm assuming the groaning and resistance is due to the fact you haven't received enough information or effective specific (to health education) profressional development within these new systems.
Well, last week- ten passionate middle and high school health education teachers from around Kentucky participated in a 2-day Standards and Assessment in the Classroom workshop in Eddyville, KY. The evaluations are among the strongest I've ever received during a teacher training. I have facilitated this workshop to thousands of health educators and elementary teachers incorporating health into their classrooms over a dozen years, however, the timing of this for these ten teachers was perfect. Half of the participants responded on their evaluation that they wanted a third day or more time for the training. I was shocked! Amazed! Proud! These teachers wanted more time spent on a grading discussion...How do we go from scoring student work using rubrics on a number scale to giving grades on a report card? What is the research behind effective grading these days? We used to offer this workshop as a 3 day, however, I don't think I would have had anyone sign up! So, we made it a two day, having to cut our ou learning styles and the in-depth grading discussion that's always incredibly philosophical & rich.
KDE and I successfully took these ten teachers through a process to build their skills in the effective practices of health education, the National Health Education Standards (NHES), the rubrics in health education (that align to each of the 8 NHES), effectively teaching the skill standards depending on the grade level span you teach (for example, what are the steps to effectively teach accessing information K-2, 3-5, middle and high school?), scoring student work samples from a health education classroom, building an instructional unit, developing pre-assessments per skill within your course to develop student growth goals and finally, feeling comfortable & confident writing student growth goals from pre-assessments given at the beginning of your health education course. PHEW! A semester long course in two days. I worked the participants hard. They resisted at times, celebrated and shared exemplary assessments. They laughed, participated and many have followed up with emails of appreciation. Thank YOU teachers for your hard work... our Kentucky youth will be healthier people as a result of your hard work last week.