text:
\section{Introduction}

We study a classic randomized protocol for information dissemination in networks, known as \emph{(randomized) rumor spreading}.
The protocol proceeds in a sequence of synchronous rounds.\footnote{There are also asynchronous versions of rumor spreading (see, e.g.,~\cite{Boyd2006}), but in this paper we focus on synchronous protocols.}
Initially, in round 0, an arbitrary node learns a piece of information,
the \emph{rumor}.
This rumor is then spread iteratively to other nodes:
In each round, every informed node (i.e., every node that learned the rumor in a previous round) chooses a random neighbor and sends the rumor to that neighbor.
This is the \Push{} version of the protocol.
The \Pull{} version is symmetric:
In each round, every uninformed node contacts a random neighbor, and if this neighbor knows the rumor it sends it to the uninformed node.
Finally, the \PPull{} algorithm is the combination of both:
In each round, every node chooses a random neighbor to send the rumor to, if the node knows the rumor, or to request the rumor from, otherwise.

These protocols were proposed almost thirty years ago, and have been the subject of extensive study, especially in the past decade.
The most studied question concerns the number of rounds that these protocols need to spread a rumor in various network topologies.
It has been shown that $O(\log n)$ rounds suffice with high probability (w.h.p.)  for several families for networks, from basic communication networks, such as complete graphs and hypercubes, to more complex structures, such as preferential attachment graphs modeling social networks (see the Related Work Section).

A main motivation for the study of rumor spreading is its application in algorithms for broadcasting in communication networks~\cite{Demers1987podc,Feige1990,Karp2000focs}.
Rumor spreading provides a scalable alternative to the flooding protocol (where each node sends the information to \emph{all} its neighbors in a round), and a simpler and more robust alternative to deterministic solutions.
The advantages of simplicity (each node makes a simple local decision in each round; no knowledge of the global topology is needed; no state is maintained), scalability (each node initiates just one connection per round), and robustness (the protocol tolerates random node/link failures without the use of error recovery mechanisms) make rumor spreading protocols particularly suited for today's distributed networks of massive-scale.
Such networks, e.g., peer-to-peer, mobile ad-hoc, or sensor networks, are highly dynamic, suffer from frequent link and node failures, or nodes have limited computational, communication, and energy resources.

Another motivation for the study of rumor spreading protocols is that they provide intuition on how information spreads in social networks~\cite{Chierichetti2009icalp}.
More generally, understanding these simple rumor spreading protocols may
lead to a better understanding of more realistic epidemic processes on social and other complex networks.

In this paper, our main focus is the connection between rumor spreading and graph expansion properties of networks.
Many of the topologies for which rumor spreading is known to be fast have high expansion.
Further, empirical studies indicate that social networks have good expansion properties as well~\cite{Eubank04nature,Leskovec08www}.

Several works have studied the relationship of rumor spreading with the \emph{conductance} of the network graph~\cite{Mosk-Aoyama2008,Chierichetti2010soda,Chierichetti2010stoc,Giakkoupis2011stacs}.
The conductance $\phi \in (0,1]$ is a standard expansion measure defined roughly as the minimum ratio of the edges leaving a set of nodes over the total number of edges incident to these nodes~(see Section~\ref{sec:preliminaries}).
The main result of the above works is an upper bound of $O(\log(n)/\phi)$ rounds for \PPull{} to inform all nodes w.h.p., for any $n$-node graph with conductance at least $\phi$.
This bound is tight, as there are graphs with diameter $\Omega(\log(n)/\phi)$~\cite{Chierichetti2010stoc}.

The above result has been used in the design of a recent breed of information dissemination protocols~\cite{Censor-Hillel2011soda,Censor-Hillel2012stoc,Haeupler2013soda}.
These protocols rely on the fact that \PPull{} spreads information fast in subgraphs of high conductance, and they combine \PPull{} with more sophisticated rules on how each node chooses the neighbor to contact in each round.
These new protocols achieve fast information spreading in a broader class of networks, and some achieve for all graphs time bounds that are close (within poly-logarithmic factors) to the network diameter, which is the natural lower bound for information dissemination in networks.

More recently, another standard measure of expansion, vertex expansion, has been studied in connection with rumor spreading.
The vertex expansion $\alpha \in (0,1]$ of a graph is, roughly, the minimum ratio of the neighbors that a set of nodes has (that are not in the set) over the size of the set.
In general, vertex expansion is incomparable to conductance, as there are graphs with high vertex expansion but low conductance,
and vice versa.
(For an account of the differences between the two measures see~\cite{GiakkoupisS2012soda}.)
The question of whether high vertex expansion implies fast rumor spreading (similarly to high conductance) was highlighted as an interesting open problem in~\cite{Chierichetti2010soda}.
This problem was studied in~\cite{Sauerwald2011soda,GiakkoupisS2012soda}, and their main result was an upper bound for \PPull{} of $O(\log^{2.5}(n)/\alpha)$ rounds w.h.p., for any graph with vertex expansion at least $\alpha$.
The precise bound is $O(\log n \cdot \log \Delta \cdot \sqrt{ \log (2 \Delta/ \delta)}/\alpha)$, where $\Delta$ and $\delta$ are the maximum and minimum node degrees, respectively.
Further, a lower bound of $\Omega(\log n \cdot \log(\Delta)/\alpha)$ was shown,  assuming $\Delta/\alpha\leq n^{1-\epsilon}$ for some constant $\epsilon > 0$.

\paragraph{Our Contribution.}

Our main result is the following upper bound for \PPull{} in terms of vertex expansion that matches the known lower bound.
\begin{theorem}
    \label{thm:ub-pushpull}
    Let $G=(V,E)$ be a graph with $|V| = n$, maximum degree at most $\Delta$, and vertex expansion at least $\alpha$.
    For any such graph $G$ and constant $\beta>0$, with probability $1-O(n^{-\beta})$ \PPull{} informs all nodes of $G$ in $O\big(\log n \cdot \log (\Delta)/\alpha\big)$ rounds.
\end{theorem}

This result, together with the $O(\log(n)/\phi)$ bound with conductance, resolve completely the natural question asked by Chierichetti, Lattanzi, and Panconesi~\cite{Chierichetti2009icalp,Chierichetti2010soda}, on the relationship between rumor spreading and the two most standard measures of graph expansion.

Our proof of Theorem~\ref{thm:ub-pushpull} can be summarized as follows.
Let $S$ be the set of informed nodes after a given round, and $\partial S$  be the boundary of $S$, i.e., the set of nodes from $V-S$ that have some neighbor in $S$.
The proof defines a new simple measure of the expansion of $S$, called boundary expansion.
If $S$ has low boundary expansion, then we prove that a constant fraction of the boundary $\partial S$ gets informed in an expected number of $O(\log\Delta)$ rounds; this is the core argument of the proof.
If, instead, $S$ has high boundary expansion, then we have that an expected number of $\Omega(|\partial S|)$ nodes from $V-(S\cup\partial S)$ are added to the boundary in a single round.
It follows that a simple potential function $\Psi(S)$ that counts 1 for each informed node and 1/2 for each node in the boundary, increases ``on average" per round by at least $\Omega(|\partial S|/\log\Delta) = \Omega(\alpha\Psi(S)/\log\Delta)$; this is the right increase rate we need to show the $O\big(\log n \cdot \log (\Delta)/\alpha\big)$ time bound.

The above proof borrows some ideas from the analysis in~\cite{GiakkoupisS2012soda}. In particular, both proofs study the growth of essentially the same potential function~$\Psi$.
However, the arguments they use are different.
Moreover, our proof provides a clear intuition for the result not conveyed by earlier proofs.

Some of the arguments in our proof may be of independent interest as tools for the analysis of rumor spreading.
We demonstrated this by reusing those arguments to show the following smaller results.
\begin{enumerate}
\item \label{res:dominatingset}
Our first result serves as a ``warm-up" for the main proof, as it uses a simpler version of the core argument of our analysis.
We show that if a rumor is initially known by a subset of nodes that is a dominating
set,
then $O(\log n)$ rounds of \PPull{} suffice w.h.p.\ to inform the other nodes.
(In fact we can use just \Pull{} instead of \PPull.)
This result is somewhat relevant to problems in viral marketing~\cite{Domingos2001kdd,Kempe2003kdd}:
It says that if we want to plant a rumor, or ad, in a (small) initial set of nodes in an arbitrary network, so that the remaining nodes get informed quickly by rumor spreading, then it suffices that the set we choose be a dominating set.\footnote{Note that the analysis of the more sophisticated information dissemination algorithm proposed in~\cite{Censor-Hillel2012stoc,Haeupler2013soda}, yields time bounds of $O(\log^3 n)$ and $O(\log^2 n)$, respectively, for this problem.}

\item \label{res:diametertwo}
Our next result uses (in an interesting way) the main argument from the proof of Result~1 above, to show that \PPull{} spreads a rumor in $O(\log n)$ rounds w.h.p.\ in any graph of diameter (at most) 2.
This result can be viewed as an extension to the classic result that rumor spreading takes $O(\log n)$ rounds in graphs of diameter~1, i.e., in complete graphs.
Note that unlike complete graphs, some graphs of diameter 2 have bad expansion.
Also the result does not hold for graphs of diameter~3.

\item \label{res:regular}
For regular graphs, a variant of our analysis yields an upper bound in terms of a new natural expansion measure, and this bound is strictly stronger than the $O(\log(n)/\phi)$ bound with conductance.
The new measure, denoted $\xi$, is defined as the minimum over all sets $S$ with $|S|\leq n/2$, of the product $\alpha(S)\cdot\phi(\partial S)$ of the vertex expansion of $S$ and the conductance of its boundary $\partial S$.
The bound we show is $O(\log(n)/\xi)$ w.h.p.\ for any regular graph.

\end{enumerate}
The proofs of Results~\ref{res:diametertwo} and~\ref{res:regular} can be found in the Appendix, in Sections~\ref{sec:dimeter-two} and~\ref{sec:regular}, respectively.

\paragraph{Related Work.}

The first works on rumor spreading provided a precise analysis of \Push{} on complete graphs~\cite{Frieze1985, Pittel1987}.
Time bounds of $O(\log n)$ rounds were later proved for hypercubes and random graphs~\cite{Feige1990}.
Other symmetric graphs similar to the hypercube in which rumor spreading takes $O(\log n + \diam)$ rounds were studied in~\cite{Elsasset2007stacs}.
A refined analysis for random graphs proving essentially the same time bound as for complete graphs was provided in~\cite{Fountoulakis2010infocom}, and extended to random regular graphs in~\cite{Fountoulakis2010random}.
The authors of~\cite{Chierichetti2009icalp} studied rumor spreading on preferential attachment graphs, which are used as models for social networks, and showed that \Push{} or \Pull{} need polynomially many rounds, whereas \PPull{} needs only $O(\log^2 n)$ rounds.
The last bound was subsequently improved to $\Theta(\log n)$~\cite{Doerr2011stoc}.
Another class of graphs used to model social networks was considered in~\cite{Fountoulakis2012soda}, and it was shown that \PPull{} needs just $\Theta(\log\log n)$ rounds to inform all but an $\epsilon$-fraction of nodes.

For general graphs, it was shown in~\cite{Mosk-Aoyama2008} a bound of $O(\log(n)/\Phi)$ for a version of \PPull{} with non-uniform probabilities for neighbor selection, where $\Phi$ is the conductance of the matrix of selection probabilities (which is different than the conductance $\phi$ of the graph).
This result does not extend to standard \PPull{}.
A comparable bound in terms of the mixing time of an appropriate random walk was shown in~\cite{Boyd2006}.
For \PPull{}, a polynomial bound in $\log(n)/\phi$ was shown in~\cite{Chierichetti2009icalp} via a connection to a spectral sparsification process.
An improved, almost tight bound was shown in~\cite{Chierichetti2010stoc}, and the tight $O(\log(n)/\phi)$ bound was shown in~\cite{Giakkoupis2011stacs}.
For \Push{} or \Pull{} this bound hold for regular graphs, but not for general graphs.

The bound for \PPull{} with conductance has been used in subsequent works~\cite{Censor-Hillel2010podc,Censor-Hillel2011soda,Censor-Hillel2012stoc,Haeupler2013soda}, mainly to argue that rumors spread fast in subgraphs of high conductance.
A refinement of conductance, called weak conductance, which is greater or equal to $\phi$ was introduced in~\cite{Censor-Hillel2010podc} and related to the time for \PPull{} to inform a certain fraction of nodes.
A gossip protocol for the problem in which every node has a rumor initially, and must receive the rumors of all other nodes was proposed in~\cite{Censor-Hillel2011soda}.
The protocol alternates rounds of \PPull{} with rounds of deterministic communication, and guarantees fast information spreading in all graphs with high weak conductance.
In~\cite{Censor-Hillel2012stoc,Haeupler2013soda} protocols for the same gossip problem were proposed that need only $O(\diam\cdot\polylog(n))$ or $O(\diam + \polylog(n))$ rounds.
One of these protocols is even deterministic~\cite{Haeupler2013soda}.
Hopefully, the results presented in the current paper will also help in the design of new protocol for information dissemination.

\section{Notation}
\label{sec:preliminaries}

Throughout the paper we assume that graph $G = (V,E)$ is connected, and $n=|V|$.
For a node $v\in V$, we denote by $N(v)$ the set of $v$'s neighbors in $G$, and $\deg(v) = |N(u)|$ is the degree of $v$.
By $\Delta$ and $\delta$ we denote the maximum and minimum node degrees of $G$.
For a set of nodes $S\subseteq V$, we denote by $\partial S$ the \emph{boundary} of $S$, that is, the set of neighbors of $S$ that are not in $S$; formally, $\partial S = \{ v \in V - S \colon N(v)\cap S\neq \emptyset\}$.
We will write $S^+$ to denote the set $S\cup \partial S$.
Set $S$ is a \emph{dominating set} of $G$ iff each node $v\in V$ either belongs to $S$ or has a neighbor from $S$, i.e., $S^{+} = V$.
The vertex expansion of a non-empty set $S\subseteq V$ is
$
    \alpha(S) = {|\partial S|}/{|S|},
$
and the vertex expansion of $G$ is
\[
    \alpha(G) = \min_{S\subset V,\ 0<|S|\leq n/2} \alpha(S).
\]
The volume of $S$ is $\vol(S) = \sum_{v\in S}\deg(v)$.
By $E(S,V-S)$ we denote the set of edges with one endpoint from $S$ and the other from $V-S$.
The conductance of a non-empty set $S\subseteq V$ is
$
    \phi(S) = {|E(S,V-S)|}/{\vol(S)},
$
and the conductance of $G$ is
\[
    \phi(G) = \min_{S\subset V,\ 0<\vol(S)\leq \vol(V)/2} \phi(S).
\]
We have $0< \phi(G),\alpha(G) \leq 1$, and $(\delta/\Delta)\cdot \phi(G) \leq \alpha(G)\leq \Delta\cdot\phi(G)$~\cite{GiakkoupisS2012soda}.

\section{Warm-up: Rumors Spread Fast from a Dominating Set}

We show the following result in this section.
\begin{theorem}
    \label{thm:dominating-set}
    Let $S\subseteq V$ be a dominating set of $G=(V,E)$, i.e., $S^+:= S\cup\partial S = V$.
    Suppose that all nodes $u\in S$ know of a rumor initially.
    Then \Pull{} informs all remaining nodes  in $O(\log n)$ rounds, with probability $1-O(n^{-\beta})$ for any constant $\beta>0$.
\end{theorem}

We start with an overview of the proof.
From a standard lemma on the symmetry between \Push{} and \Pull{} (Lemma~\ref{lem:symmetry}), it follows that to bound the time for \Pull{} to spread a rumor from $S$ to a given node $u\notin S$, it suffices to bound instead the time for \Push{} to spread a rumor from $u$ to \emph{some} node in $S$.
We  bound the latter time as follows (Lemma~\ref{lem:push-to-S}).
Let $I_t^u$ be the set of informed nodes after $t$ rounds of \Push{}, when the rumor starts from $u$.
We consider the earliest round $\tau$ for which the expected growth of $I_t^u$ in the next round $\tau + 1$ is smaller than by a constant factor $\epsilon>0$, i.e., $\Exp[|I_{\tau+1}^u-I_\tau^u| \mid I_\tau^u] < \epsilon\cdot |I_\tau^u|$.
We argue that $\tau = O(\log n)$ w.h.p.\ (Claim~\ref{clm:tau}), which is intuitively clear, as up to round $\tau$ the number of informed nodes increased by a constant factor in expectation per round.
Next we bound the harmonic mean of the degrees of nodes in $I_\tau^u$, precisely, we show that $\sum_{v\in I_t^u} \deg(v)^{-1} = \Omega(1)$.
If $I_\tau^u\cap S =\emptyset$ then each node from $I_\tau^u$ has some neighbor in $S$, and from the above bound on the degrees it follows that the probability  in one round that some nodes from $I_\tau^u$ pushes the rumor to a neighbor in $S$ is $\Omega(1)$.
Thus, within $O(\log n)$ rounds after round $\tau$ the rumor has reached some node in $S$ w.h.p.

Next we give the detailed proof.
\begin{lemma}
    \label{lem:symmetry}
    Let $T_{push}(V_1,V_2)$, for $V_1,V_2\subseteq V$, be the number of rounds for \Push{} until a rumor that is initially known to all nodes $u\in V_1$ (and only them) spreads to at least one node $v\in V_2$; let also $T_{pull}(V_1,V_2)$ be defined similarly.
    Then, for any  $V_1,V_2\subseteq V$, the random variables $T_{push}(V_1,V_2)$ and $T_{pull}(V_2,V_1)$ have the same distribution.
\end{lemma}

The proof of Lemma~\ref{lem:symmetry} is essentially the same as that of~\cite[Lemma~3]{Chierichetti2010stoc}, and is therefore omitted.

Next we state our main lemma.
\begin{lemma}
    \label{lem:push-to-S}
    Let $S$ be a dominating set of $G=(V,E)$, and let $u\in V-S$.
    Using \Push, a rumor originated at $u$ spreads to at least one node $v\in S$ in $O(\log n)$ rounds, with probability $1-O(n^{-\beta})$ for any constant $\beta > 0$.
\end{lemma}

The proof of Lemma~\ref{lem:push-to-S} is given in Section~\ref{sec:push-to-S}.

From the two lemmata above, Theorem~\ref{thm:dominating-set} follows easily:
From Lemma~\ref{lem:push-to-S} we obtain that a rumor originated at a given $u\in V-S$ spreads to at least one $v\in S$ after $O(\log n)$ rounds of \Push, with probability $1-O(n^{-\beta-1})$.
Lemma~\ref{lem:symmetry} then implies that a rumor known to all $v\in S$ reaches $u$ after $O(\log n)$ rounds of \Pull, with the same probability, $1-O(n^{-\beta-1})$.
Applying now the union bound over all $u\in V-S$ yields the claim.

\subsection{Proof of Lemma~\ref{lem:push-to-S}}

\label{sec:push-to-S}

Let $I_t^u$ be the set of informed nodes after $t$ rounds of \Push{}, when the rumor starts from node $u\in V-S$.
Let $\tau$ be the earliest round such that the expected increase of $I_t^u$ in the next round is smaller than $\epsilon\cdot|I_t^u|$, i.e.,
\[
    \tau
    =
    \min\{t \colon \Exp[|I_{t+1}^u| \mid I_t^u] < (1+\epsilon)\cdot |I_t^u|\},
\]
for some positive constant $\epsilon <  1$.
\begin{claim}
    \label{clm:tau}
    With probability $1-n^{-\beta}$ we have $\tau = O(\log n)$.
\end{claim}

The proof of Claim~\ref{clm:tau} is by standard probabilistic arguments, and can be found in the Appendix.

The next claim bounds the harmonic mean of the degrees of nodes $v\in I_\tau^u$.
\begin{claim}
    \label{clm:degrees}
    If $\Exp[|I_{t+1}^u| \mid I_t^u] < (1+\epsilon)\cdot |I_t^u|$ then
    $\sum_{v\in I_t^u} \deg(v)^{-1} \geq 1-\sqrt\epsilon$.\footnote{An equivalent statement for $\sum_{v\in I_t^u} \deg(v)^{-1} \geq 1-\sqrt\epsilon$ is that the harmonic mean of $\deg(v)$, over all $v\in I_t^u$, is at most $|I_t^u|/(1-\sqrt\epsilon)$.}
\end{claim}
\begin{proof}
The proof is by contradiction.
Fix the set $I_t^u$, and let $k=|I_t^u|$.
For $i=1,\ldots, k$, let $u_i$ denote the $i$-th node from $I_t^u$, and let $d_i = \deg(u_i)$.
We will assume that $\sum_{i=1}^k d_i^{-1} < 1-\sqrt\epsilon$ and prove that  $\Exp[|I_{t+1}^u|] \geq (1+\epsilon)\cdot k$.

We count the number of uninformed node that in round $t+1$ receive exactly one copy of the rumor.
This is clearly a lower bound on the number of nodes that get informed in round $t+1$.
Let $d'_i = |N(u_i)\cap I_t^u|$ be the number of neighbors that $u_i$ has in $I_t^u$.
The probability that in round $t+1$ node $u_i$ pushes the rumor to some uninformed node is then $1-d'_i/d_i$.
And if this happens, the probability that the recipient node  does not receive the rumor from any other node in the same round is at least
\[
    \prod_{j\neq i}{(1 - 1/d_j)}
    \geq
    1 - \sum_{j\neq i}(1/d_j)
    \geq
    1 - (1-\sqrt\epsilon)
    =
    \sqrt\epsilon.
\]
Thus the probability that $u_i$ sends the rumor to an uninformed node that does not receive another copy of the rumor is at least $(1-d'_i/d_i)\cdot \sqrt\epsilon$.
Hence, the expected number of uninformed nodes that receive exactly one rumor copy in round $t+1$ is at least $\sum_{i=1}^k\big((1-d'_i/d_i)\cdot \sqrt\epsilon\big)$.
And since
\begin{align*}
    \sum_{i=1}^k(1-d'_i/d_i)
    &=
    k - \sum_{i=1}^k(d'_i/d_i)
    \\&
    \geq
    k - \sum_{i=1}^k (k/d_i)
    \geq
    k - k(1-\sqrt\epsilon)
    =
    k\sqrt\epsilon,
\end{align*}
we obtain a lower bound of $k\sqrt\epsilon\cdot \sqrt\epsilon = k \epsilon$ on the expected number of uninformed nodes that receive exactly one copy of the rumor in round $t+1$.
Hence, the same lower bound holds for the total number on nodes informed in the round, and we conclude that $\Exp[|I_{t+1}^u|] \geq (1+\epsilon)\cdot k$.
\end{proof}

Using Claim~\ref{clm:degrees} it is easy to show an $O(\log n)$ bound w.h.p.\ on the number of additional rounds after round $\tau$, until the rumor spreads to at least one node from $S$.
Suppose that $I_\tau^u = U$ for some set $U\subseteq V-S$.
(If $U\nsubseteq V-S$ then some node from $S$ is already informed.)
Each node $v\in U$ has at least one neighbor in the dominating set $S$, and thus the probability that none of these nodes pushes the rumor to a neighbor in $S$ in a given round $t > \tau$, is upper bounded by
\[
    \prod_{v\in U}\left(1 - \deg(v)^{-1}\right)
    \leq
    e^{-\sum_{v\in U}\deg(v)^{-1}}
    \leq
    e^{-1+\sqrt\epsilon},
\]
by Claim~\ref{clm:degrees}.
This probability bound holds for each round $t>\tau$ independently of the outcome of previous rounds.
It follows that $\ell := (\beta\cdot \ln n)/(1-\sqrt\epsilon) = O(\log n)$ additional rounds after round $\tau$ suffice to spread the rumor to a node in $S$ with probability $1 - (e^{-1+\sqrt\epsilon})^\ell = 1 - n^{-\beta}$.
Combining this with Claim~\ref{clm:tau}, which bounds $\tau$ by $O(\log n)$  with probability $1 - n^{-\beta}$, and applying the union bound gives that the rumor spreads from $u$ to at least one $v\in S$ in $O(\log n)$ rounds with probability $1 - 2n^{-\beta}$.
This completes the proof of Lemma~\ref{lem:push-to-S}.

Another application of the above argument is described in Section~\ref{sec:dimeter-two} of the Appendix.

\section{Bound with Vertex Expansion}
\label{sec:ub-vexpansion}

In this section we prove our main result, Theorem~\ref{thm:ub-pushpull}.

We start with an overview of the proof.
Let $I_t$ denote the set of informed nodes after the first $t$ rounds.
We study the growth of the quantity
$\Psi_t := |I_t| + |\partial I_t|/2 = (|I_t| + |I_t^+|)/2$.
You can think of $\Psi_t$ as a potential function:
each informed node has as a potential of 1, each uninformed node with an informed neighbor has potential 1/2, and the remaining uninformed nodes have potential zero; $\Psi_t$ is then the total potential after round $t$.
We have $1 < \Psi_t \leq n$.
To prove the theorem, we show (as outlined below) that the expected number of rounds needed to double $\Psi_t$  is bounded by $O(\log(\Delta)/\alpha)$, as long as $|I_t| \leq n/2$.
It follows that $O(\log n \cdot \log(\Delta)/\alpha)$ rounds suffice w.h.p.\ to inform $n/2  + 1$ nodes, and by a symmetry argument,  $O(\log n \cdot \log(\Delta)/\alpha)$ additional rounds suffice to inform all remaining nodes w.h.p.

For $\Psi_t$ to double in  $O(\log(\Delta)/\alpha)$ rounds, it suffices that it increases by $\Omega(|\partial I_t|/\log\Delta)$ ``on average" per round, as $|\partial I_t|\geq \alpha\cdot |I_t|$ and thus $|\partial I_t| = \Omega(\alpha\Phi_t)$.
Such an increase can be achieved either by informing $\Omega(|\partial I_t|/\log\Delta)$ nodes from $\partial I_t$, or by informing fewer nodes which however have a total number of $\Omega(|\partial I_t|/\log\Delta)$ neighbors in $\partial(I_t^+)$.
Along this intuition, we distinguish the following two cases, in terms of a simple expansion measure we define for $I_t$, called boundary expansion (Definition~\ref{def:bexpansion}).

The first case is when the boundary expansion of $I_t$ is low (upper-bounded by a constant $\epsilon_h < 1$).
This is the more challenging case, and is the core of our analysis.
Our main lemma in this case is Lemma~\ref{lem:growthIt}, which establishes that a constant fraction of the boundary $\partial I_t$ gets informed in an expected number of $O(\log\Delta)$ rounds.
The proof builds upon and extends the ideas used in the proof of Theorem~\ref{thm:dominating-set}.
We note that in the setting of Theorem~\ref{thm:dominating-set}, the boundary expansion of the set $S$ of informed nodes is zero.

The second case is when the boundary expansion of $I_t$ is high (lower-bounded by a constant $\epsilon_h > 0$).
Then from our definition of boundary expansion it follows that the expected number of nodes from $\partial(I_t^+)$ that have an informed neighbor after the next round is $\Omega(|\partial I_t|)$, i.e., $\Exp[|I_{t+1}^+ - I_{t}^+| \mid I_t] = \Omega(|\partial I_t|)$.
Our main lemma in this case is Lemma~\ref{lem:growthItplus}, which turns the above lower bound on the expected per round growth of $I_{t}^+$ into an upper bound on the expected number of rounds until $I_{t}^+$ grows by some quantity $b$, which depends on the degrees of nodes in $\partial I_t$.

Finally we bound the expected time needed to double $\Psi_t$, in Claim~\ref{clm:psi-double}, by combine the results of the two cases above and using an inductive argument.

The rest of this section is structured as follows.
We define the measure of boundary expansion in Section~\ref{sec:bexpansion}.
In Section~\ref{sec:It} we prove Lemma~\ref{lem:growthIt}, which lower-bounds the growth of $I_t$ when boundary expansion is low.
In Section~\ref{sec:It} we prove Lemma~\ref{lem:growthItplus}, which lower-bounds the growth of $I_t^+$ when boundary expansion is high.
And in Section~\ref{sec:proof-main} we put the pieces together to prove Theorem~\ref{thm:ub-pushpull}.

\subsection{Boundary Expansion}
\label{sec:bexpansion}

\begin{definition}
\label{def:bexpansion}
Let $S\subset V$ be a non-empty set of nodes.
Let $U$ be a random subset of $\partial S$ such that each node $u\in \partial S$ belongs to $U$ with probability  $1/\deg(u)$ independently of the other nodes.
The \emph{boundary expansion $h(S)$ of $S$} is the ratio of the expected number of nodes $v\in \partial(S^+)$ that have some neighbor in $U$, over the size of $\partial S$, i.e.,
\[
    h(S) = \Exp\left[|\{v\in \partial(S^+) \colon N(v)\cap U\neq \emptyset \}|\right]/|\partial S|.
\]
\end{definition}

It follows that
\begin{equation}
    \label{eq:hofS}
    h(S) =
    \frac1{|\partial S|}
    \sum_{v\in \partial(S^+)}
    \bigg(1-\prod_{u\in N(v)\cap\partial S} \left(1-\deg(u)^{-1}\right)\bigg).
\end{equation}
We have $0\leq h(S) < 1$.
The lower bound of 0 is matched iff $S^+ = V$; and
the upper bound holds because the expected number of nodes from $\partial(S^+)$ that have some neighbor in $U$ is upper-bounded by the expected number of the edges between $U$ and $\partial(S^+)$, which is
\[
    \sum_{u\in\partial S} \frac{|N(u)-S^+|}{\deg(u)}
    \leq
    \sum_{u\in\partial S} \frac{\deg(u)-1}{\deg(u)}
    <
    |\partial S|,
\]
and thus $h(S) < 1$.
We note that it is possible to have $h(S)\leq \epsilon_h < 1$, for some constant $\epsilon_h$, even if each node $u\in \partial S$ has $\deg(u)-1$ neighbors in $\partial(S^+)$, if the nodes $u\in \partial S$ have sufficiently many \emph{common} neighbors in $\partial(S^+)$.

We observe that if $I_t=S$, then $h(S)\cdot |\partial S|$ is a lower bound on the expected number of new nodes that have an informed neighbor after round $t+1$, i.e.,
\begin{equation}
    \label{eq:pull-bexpansion}
    \Exp[|I_{t+1}^+ - I_{t}^+| \mid I_t = S]
    \geq
    h(S)\cdot |\partial S|.
\end{equation}
This follows because each node $u\in \partial I_t$ pulls the rumor from $I_t$ in round $t+1$ with probability at least $1/\deg(u)$.

In Section~\ref{sec:Itplus} we will need the following refined definition, which describes the boundary expansion of $S$ contributed by a given subset $T$ of $\partial S$.
\begin{definition}
\label{def:bexpansion2}
Let $S\subset V$ and $T\subseteq \partial S$.
Let $U_T$ be a random subset of $T$ such that each node $u\in T$ belongs to $U_T$ with probability  $1/\deg(u)$ independently of the other nodes.
The \emph{boundary expansion of $S$ due to $T$} is
\[
    h_T(S) = \Exp\left[|\{v\in \partial(S^+) \colon N(v)\cap U_T\neq \emptyset \}|\right]/|\partial S|.
\]
\end{definition}

For $T=\partial S$, the above definition is identical to Definition~\ref{def:bexpansion}, i.e., $h_{\partial S}(S) = h(S)$.

\subsection{The Case of Low Boundary Expansion: Analysis of the Growth of
\texorpdfstring{$\boldsymbol{I_t}$}{It}}
\label{sec:It}

In this section we prove the following result, which is the core lemma of our analysis.
\begin{lemma}
    \label{lem:growthIt}
    Suppose that $I_t = S$ for some set $S \subset V$ with boundary expansion
    $h(S)\leq\epsilon_h$, where $0\leq \epsilon_h < 1$ is an arbitrary constant.
    There is a constant $\epsilon = \epsilon(\epsilon_h) > 0$ such that the expected number of rounds until $\epsilon\cdot |\partial S|$ nodes from $\partial S$ get informed is $O(\log\Delta)$.
\end{lemma}

We start with an overview of the proof.
Similarly to the proof of Theorem~\ref{thm:dominating-set}, to bound the time needed for a given node $u\in\partial S$ to get informed, we bound instead the time needed for a rumor originated at $u$ to spread to some node from $S$ (Lemma~\ref{lem:ppsymmetry}).
Establishing this bound, however, is more difficult in the current setting than in the setting of Theorem~\ref{thm:dominating-set}.
Recall that in the proof of Theorem~\ref{thm:dominating-set}, to bound the time until a rumor originated at $u\in\partial S$ reaches $S$, we first bound the time until the set $I_t^u$ of informed nodes stops doubling (Claim~\ref{clm:tau}), and then bound the harmonic mean of the degrees of nodes in $I_t^u$ at that time (Claim~\ref{clm:degrees});
the bound on the degrees implies that if $I_t^u\cap S=\emptyset$, then with large probability some node from $I_t^u$ will send the rumor to a neighbor in $S$.
This last statement depends critically on the assumption that $S$ is a dominating set, and thus every node from $I_t^u$ has a neighbor in $S$.
This in not true, however, in the current setting, hence the above degree bound does not guarantee with large enough probability that some node from $I_t^u$ will send the rumor to $S$.

To tackle this problem we consider a ``restricted" rumor spreading process, on an induced subgraph of $G$.
We identify a set of nodes \emph{participating} in rumor spreading (Definition~\ref{def:participating}), such that, intuitively, each participating node has at least some constant probability to contact or be contacted by another participating node in a round.
Only nodes from  $S^+$ or $\partial(S^+)$ can be participating.
Participating nodes from $S^+$ are \emph{active}, i.e., they initiate a connection to a random neighbor in each round, while participating nodes from $\partial(S^+)$ are \emph{passive}, i.e., they \emph{accept} connections from active neighbors but do not \emph{initiate} connections to random neighbors.
Using the assumption that $S$ has low boundary expansion we show that at least some constant fraction of $\partial S$ is participating (Claim~\ref{clm:active-fraction}).
For each active node $u\in \partial S$ then, we show that an expected number of $O(\log\Delta)$ rounds suffices for a rumor originated at $u$ to spread to some node in $S$ (Lemma~\ref{lem:ppull-to-S}).
The proof of this result is now similar to that for Theorem~\ref{thm:dominating-set}, although it is crucial that we use \PPull{} rather than just \Push.

An novelty of the argument above is that it exploits the fact that in \PPull{} each edge $uv$ is chosen with probability roughly $\deg(u)^{-1} + \deg(v)^{-1}$, which is more powerful that treating push and pull operations separately.

The rest of this section is structured as follows.
In Section~\ref{sec:participating} we describe the set of participating nodes.
In Section~\ref{sec:rumor-active} we bound the time until a rumor originating from an active node reaches $S$.
And in Section~\ref{sec:finish-mainlemma} we put the pieces together to obtain Lemma~\ref{lem:growthIt}.

\subsubsection{Participating Nodes}
\label{sec:participating}

Below we give the definition of participating, active, and passive nodes, followed by some intuitive explanation.
\begin{definition}
\label{def:participating}
    The set $P$ of \emph{participating} nodes is the largest subset of $V$
    with the property that for every node $u\in P$ and for $A = P \cap S^+$,
    \begin{align}
        \label{eq:active}
        \frac{|N(u)\cap P|}{\deg(u)} + \sum_{v\in N(u)\cap A}\deg(v)^{-1}
        &\geq
        \epsilon_p,
        && \text{if $u\in A$;}
        \\
        \label{eq:passive}
        \sum_{v\in N(u)\cap A}\deg(v)^{-1}
        &\geq
        \epsilon_p,
        && \text{if $u\in P-A$,}
    \end{align}
    where $0 < \epsilon_p < (1-\epsilon_h)/3$ is a constant.\footnote{We will see later that $P$ is unique, although this is not essential for the analysis.}
    Set $A$ is the set of \emph{active} nodes, and $P - A$ is the set of \emph{passive} nodes.
\end{definition}

Note that all participating nodes belong to $S^+\cup \partial(S^+)$; the ones in $S^+$ are active, and those in $\partial(S^+)$ are passive.

Intuitively, $P$ is defined such that each participating node has at least a constant probability to contact or be contacted by another participating node in a round.
The term $|N(u)\cap P|/\deg(u)$ in Equation~\eqref{eq:active} is the probability that active node $u$ chooses a participating neighbor in a round.
In Equation~\eqref{eq:passive} we do not have this term because, as mentioned earlier, passive nodes do not initiate connections.
The sum that is common in both equations adds the probabilities of the events that $u$ is chosen by $v$, for all active neighbors $v$ of $u$.
If this sum is small (bounded by a constant), then it is of the same order as the probability that $u$ is chosen by at least one of its active neighbors, which is $1-\prod_{v\in N(u)\cap A}(1-\deg(v)^{-1})$.
(We elaborate later.)

The set $P$ can be generated by a simple procedure, which recursively removes from $V$ all nodes that do not satisfy~\eqref{eq:active} or~\eqref{eq:passive}.
Formally, we start with set $P_0 = V$.
In the $i$-th step of the procedure we obtain set $P_i$ by removing from $P_{i-1}$ all nodes $u\in A_{i-1} := P_{i-1}\cap S^+$ for which
$|N(u)\cap P_{i-1}|/\deg(u) + \sum_{v\in N(u)\cap A_{i-1}}\deg(v)^{-1}
<
\epsilon_p$, and all nodes $u\in P_{i-1} - A_{i-1}$ for which
$\sum_{v\in N(u)\cap A_{i-1}}\deg(v)^{-1} < \epsilon_p$.
Clearly, the procedure finishes after at most $n$ steps.
Let $P^\ast = P_i$ for the last step $i$.
We argue now that $P^\ast = P$ (this also proves that $P$ is unique).
From the maximality of $P$ it follows that $|P^\ast| \leq |P|$.
Thus, it suffice to show that $P \subseteq P^\ast$:
Suppose, for contradiction, that $P \nsubseteq P^\ast$, and consider the first round $i$ for which $P \nsubseteq P_{i}$.
Then, we have that $P \subseteq P_{i-1}$, and $A \subseteq A_{i-1}$, and some node $v\in P$ is removed from $P_{i-1}$ in step $i$.
If $v\in A \subseteq A_{i-1}$ then it follows from~\eqref{eq:active} that
$|N(u)\cap P_{i-1}|/\deg(u) + \sum_{v\in N(u)\cap A_{i-1}}\deg(v)^{-1}
\geq \epsilon_p$, which contradicts the assumption that $v$ is removed in step $i$.
Similarly, if $v\in P - A$, then it follows from~\eqref{eq:passive} that
$\sum_{v\in N(u)\cap A_{i-1}}\deg(v)^{-1} \geq \epsilon_p$, which again contradicts the removal of  $v$.
Thus, our assumption that  $P \nsubseteq P^\ast$ is false.

In the above procedure, if we use as a starting set $P_0$ a subset of $V$, instead of $P_0=V$, then the resulting set of participating nodes is a subset of  $P$.
We will use this observation in the proof of the claim below.

The next claim says that at least a constant fraction of the nodes
$u\in\partial S$ is participating.
\begin{claim}
    \label{clm:active-fraction}
    $|\partial S\cap P|
    \geq
    \left(1 - \frac{\epsilon_h}{(1-\epsilon_p)(1-2\epsilon_p)}\right)\cdot|\partial S|$.\footnote{From our assumption in Definition~\ref{def:participating} that $\epsilon_p < (1-\epsilon_h)/3$, it follows that $1 - \frac{\epsilon_h}{(1-\epsilon_p)(1-2\epsilon_p)}>0$.}
\end{claim}

\begin{proof}
The proof is based on a potential function argument.
We consider the procedure described above for generating $P$, but  use a smaller starting set $P_0$ as described later.
We observed earlier that such a modification yields a set of participating nodes that is a subset of $P$, thus it can only strengthen our lower bound.
The reason for this modification is that it makes the potential function we will use non-increasing.
We denote by $\Phi_i$ the potential after step $i$ of the procedure.
This potential is non-negative and is defined later.
We will show that the potential $\Phi_0$ before the first step is $\Phi_0\leq \frac{\epsilon_h}{1-\epsilon_p}\cdot |\partial S|$.
Further, we will show that for each node $u\in A_{i-1}$ that is removed from $P_{i-1}$ in step $i$, the potential decreases by at least $1-2\epsilon_p$, and the removal of a node $u\notin A_{i-1}$ decreases the potential by zero or more.
Since the potential function is non-negative, it follows that the total number of nodes $u\in S^+$ removed in all steps is at most $\Phi_0/(1-2\epsilon_p)$.
Thus, the same bound holds for the number of nodes $u\in \partial S$ removed, i.e., $|\partial S| - |\partial S\cap P|\leq \Phi_0/(1-2\epsilon_p)$.
Rearranging and using that $\Phi_0\leq \frac{\epsilon_h}{1-\epsilon_p}\cdot |\partial S|$ yields $|\partial S\cap P| \geq \big(1 - \frac{\epsilon_h}{(1-\epsilon_p)(1-2\epsilon_p)}\big)\cdot|\partial S|$.

Next we fill in the pieces omitted from the above description.
We start with the definition of the potential function.
Intuitively, the potential $\Phi_{i}$ after round $i$ measures the probability ``wasted'' in connections between participating and non-participating nodes.
Its first component, $\Phi_{i,1}$, is the sum over all $u\in A_i$ of the probability that $u$ chooses a neighbor $v\notin P_i$; the second component, $\Phi_{i,2}$, is the sum over all $u\in S^+-A_i$ of the probability that $u$ would choose a neighbor $v\in P_i$ if $u$ were active.
We give two equivalent expressions for each of $\Phi_{i,1}, \Phi_{i,2}$, to be used later on.
\begin{align*}
    \Phi_{i,1}
    &=
    \sum_{u\in A_i} \sum_{v\in N(u) - P_i} \deg(u)^{-1}
    =
    \sum_{u \notin P_i} \sum_{v\in N(u)\cap A_i} \deg(v)^{-1};
    \\
    \Phi_{i,2}
    &=
    \sum_{u\in S^+ - A_i} \sum_{v\in N(u)\cap P_i} \mspace{-18mu}\deg(u)^{-1}
    =
    \sum_{u \in P_i} \sum_{v\in N(u)\cap (S^+ - A_i)} \mspace{-42mu}\deg(v)^{-1}.
\end{align*}
Then, $\Phi_i = \Phi_{i,1} + \Phi_{i,2}$.

The new starting set $P_0$ we use consists of all $u\in S^+$, plus those $u\in \partial(S^+)$ for which
\begin{equation}
    \label{eq:P0}
    \sum_{v\in N(u)\cap \partial S}\deg(v)^{-1} \geq 2 \epsilon_p.
\end{equation}
The above condition is similar to~\eqref{eq:passive}, but the threshold is twice that in~\eqref{eq:passive}.

We can now prove that
\begin{equation}
    \label{eq:Psi0}
    \Phi_0\leq \frac{\epsilon_h}{1-\epsilon_p}\cdot |\partial S|
\end{equation}
The proof can be found in the Appendix.

It remains to show that for each node $u\in A_{i-1}$ that is removed in step $i$, the potential decreases by at least $1-2\epsilon_p$, and for each node $u\in P_{i-1} - A_{i-1}$ removed the potential does not increase.
W.l.o.g., we assume that only one node  $u\in P_{i-1}$ is removed in step $i$.
(If $k>1$ nodes should be removed we just break step $i$ into $k$ sub-steps.)

First, we consider the case in which a node $u\in P_{i-1}-A_{i-1}$ is removed in step $i$.
Then $P_i = P_{i-1} - \{u\}$ and $A_i = A_{i-1}$.
From the second expressions for $\Phi_{i,1}$ and  $\Phi_{i,2}$ we obtain
\begin{align*}
    \Phi_{i,1} - \Phi_{i-1,1}
    &=
    \sum_{v\in N(u)\cap A_i} \deg(v)^{-1}
    =:\phi_{inc},
    \\
    \Phi_{i,2} - \Phi_{i-1,2}
    &=
    - \sum_{v\in N(u)\cap (S^+ - A_{i-1})} \deg(v)^{-1}
    =: - \phi_{dcr}.
\end{align*}
Since $A_i = A_{i-1}$, we have that
$\phi_{inc} + \phi_{dcr} = \sum_{v\in N(u)\cap S^+} \deg(v)^{-1} \geq 2\epsilon_p$, from~\eqref{eq:P0}.
Further, since $u$ is removed in round $i$ it satisfies the condition $\sum_{v\in N(u)\cap A_{i-1}}\deg(v)^{-1} < \epsilon_p$, which yields $\phi_{inc} < \epsilon_p$.
From these two inequalities on $\phi_{inc}$ and $\phi_{dcr}$, it follows $\phi_{inc} < \epsilon_p < \phi_{dcr}$, and thus,
$\Phi_i - \Phi_{i-1} = \phi_{inc} - \phi_{dcr} < 0$.

Next, we consider the case in which a node $u\in A_{i-1}$ is removed.
Then $P_i = P_{i-1} - \{u\}$ and $A_i = A_{i-1}  - \{u\}$, and
\begin{align*}
    \Phi_{i,1} - \Phi_{i-1,1}
    &=
    -\underbrace{\sum_{v\in N(u) - P_{i-1}} \mspace{-5mu}\deg(u)^{-1}}_{\phi_1}
    +
    \underbrace{\sum_{v\in N(u)\cap A_i} \mspace{-5mu}\deg(v)^{-1}}_{\phi_2}
    \\&
    =
    -\phi_1 + \phi_2
    ,
    \\
    \Phi_{i,2} - \Phi_{i-1,2}
    &=
    \underbrace{\sum_{v\in N(u)\cap P_i} \mspace{-10mu}\deg(u)^{-1}}_{\phi_3}
    -
    \sum_{v\in N(u)\cap (S^+ - A_{i-1})} \mspace{-35mu}\deg(v)^{-1}
    \leq
    \phi_3
    .
\end{align*}
In the expression for $\phi_2$ we  can replace $A_i$ by $A_{i-1}$, as $u\notin N(u)$ and thus $N(u)\cap A_i = N(u)\cap A_{i-1}$.
Similarly, in the expression for $\phi_3$ we  can replace $P_i$ by $P_{i-1}$.
It follows that $\phi_1 + \phi_3 = \sum_{v\in N(u)} \deg(u)^{-1} = 1$, and also $\phi_2 + \phi_3 < \epsilon_p$ because otherwise $u$ would not be removed in round $i$.
Thus,
\begin{align*}
    \Phi_i - \Phi_{i-1}
    &=
    (\Phi_{i,1} - \Phi_{i-1,1}) + (\Phi_{i,2} - \Phi_{i-1,2})
    \\&
    \leq
    -\phi_1 + \phi_2 + \phi_3
    \leq
    -\phi_1 + 2\phi_2 + \phi_3
    \\&
    =
    -(\phi_1 +\phi_3) + 2(\phi_2 + \phi_3)
    < -1 + 2\epsilon_p
    .
\end{align*}
This completes the proof of Claim~\ref{clm:active-fraction}.
\end{proof}

\subsubsection{Spreading a Rumor from an Active Node}
\label{sec:rumor-active}

In this section we prove the following lemma, which bounds the expected time until a rumor originated at some active node $u\in \partial S$ reaches $S$.
\begin{lemma}
    \label{lem:ppull-to-S}
    Let $u\in \partial S \cap P$.
    Using \PPull, a rumor originated at $u$ spreads to at least one node $v\in S$ in an expected number of  $O(\log \Delta)$ rounds.
\end{lemma}

This result is similar to Lemma~\ref{lem:push-to-S}, but holds only for {active} nodes rather than all $u\in \partial S$, and assumes \PPull{} rather than \Push.

The proof analyzes the spread of $u$'s rumor on the subgraph induced by the set $P$ of participating nodes.
We assume that each active node (from the set $A = P\cap S^+$) chooses a random neighbor in each round, and contacts that neighbor if it is participating.
Passive nodes (from $P - A = P\cap \partial(S^+)$) do not choose neighbors; they communicate only with the active nodes that choose them in each round.

Let $I_t^u$ denote the set of informed nodes after $t$ rounds.
Similarly to the proof of Lemma~\ref{lem:push-to-S}, we define
\[
    \tau
    =
    \min\{t \colon \Exp[|I_{t+1}^u| \mid I_t^u] < (1+\varepsilon)\cdot |I_t^u| \ \vee\  |I_t^u| \geq \Delta^2 \},
\]
where $0 < \varepsilon < \epsilon_p/2$ is a constant.
The condition $|I_t^u| \geq \Delta^2$ is added because we want to show a bound of $O(\log\Delta)$, instead of $O(\log n)$ as in Lemma~\ref{lem:push-to-S}.
The square in $\Delta$ is to ensure that if at least $\Delta^2$ nodes are informed then at least $O(\Delta)$ of them are active. (We elaborate later.)
The next result is an analogue of Claim~\ref{clm:tau}.
\begin{claim}
    \label{clm:pptau}
    $\Exp[\tau] = O(\log \Delta)$.
\end{claim}

\begin{proof}
The proof is along the same lines as the proof of Claim~\ref{clm:tau}.
The main difference is that we use a new argument to lower-bound the probability that $|I_{t}^u|$ grows by a constant factor in a given round $t\leq \tau$, as the argument used in  Claim~\ref{clm:tau} for \Push{} does not extend to \PPull.

Let $X_t$, for $t\geq1$, be the 0/1 random variable that is 1 iff either
$|I_{t}^u| \geq (1+\varepsilon/3)\cdot|I_{t-1}^u|$ or $t \geq \tau$.
Further, let
\[
    \tau' = \min\bigg\{i \colon \sum_{t=1}^i X_t\geq 2\log_{1+\varepsilon/3}\Delta\bigg\}.
\]
We have
\[
    \Exp[\tau]\leq \Exp[\tau'],
\]
because: For any k, if $\tau > k$, then $|I_{k}^u| \geq (1+\varepsilon/3)^{\sum_{t=1}^k X_t}$ and $|I_t^u| < \Delta^2 $, and thus,
\[
    \sum_{t=1}^k X_t
    \leq
    \log_{1+\varepsilon/3} (|I_{k}^u|)
    < \log_{1+\varepsilon/3} (\Delta^2)
    =2\log_{1+\varepsilon/3}\Delta,
\]
which implies $\tau' > k$.
Hence, for any $k$, we have that $\tau > k$ implies $\tau' > k$, and thus $\Exp[\tau] \leq \Exp[\tau']$.

Next we establish a lower-bound on the probability that $X_t = 1$, which holds independently of the past.
We fix the outcome of the first $t-1$ rounds, and show that
\[
    \Pr(X_t = 1) \geq  1-e^{-\varepsilon^2/18}.
\]
Suppose that $\tau > t-1$.
(Otherwise, $X_t = 1$ and the inequality above  holds trivially.)
We have
\begin{align*}
    \Pr(X_t = 0)
    &=
    \Pr(|I_{t}^u| < (1+\varepsilon/3)\cdot|I_{t-1}^u|  \ \wedge\  t < \tau)
    \\&
    \leq
    \Pr(|I_{t}^u| < (1+\varepsilon/3)\cdot|I_{t-1}^u|).
\end{align*}
Also, from $\tau$'s definition and the assumption that $\tau > t-1$ it follows that
$\Exp[|I_{t}^u|] \geq (1+\varepsilon)\cdot|I_{t-1}^u|$.
If we could express $|I_{t}^u|$ as a sum of independent 0/1 random variables, then we could bound $\Pr(|I_{t}^u| < (1+\varepsilon/3)\cdot|I_{t-1}^u|)$ using the above lower bound on $\Exp[|I_{t}^u|]$ and Chernoff bounds.
We have $|I_{t}^u|=\sum_{v\in V} Y_v$, where $Y_v$ is the indicator variable of the event that $v\in I_{t}^u$.
But the random variables $Y_v$ are not independent: if two nodes $v,v'\notin I_{t-1}$ have a common neighbor $w\in I_{t-1}$, then the events that $w$ pushes the rumor to $v$ or to $v'$ in round $t$ are correlated.
However, the random variables $Y_u$ are \emph{negatively associated}~\cite{Dubhashi2009book}.
This follows from~\cite[Example 4.5]{Dubhashi2009book}.\footnote{The example cited refers to a general balls and bins model.
In our case: bins are the nodes; for each informed node $u$ we place a ball to a random neighbor of $u$; and for each uninformed node $v$ we place a ball to $v$ iff a randomly chosen neighbor of $v$ is informed. The example then shows that the number of balls in the bins are negatively associated.}
Negative association allows us to use standard Chernoff bounds,
thus we have
\begin{align*}
    \Pr(|I_{t}^u| < (1+\varepsilon/3)&\cdot|I_{t-1}^u|)
    \leq
    \Pr\!\left(|I_{t}^u| < (1+\varepsilon/3)\cdot\frac{\Exp[|I_{t}^u|]}{1+\varepsilon} \right)
    \\&
    \leq
    \Pr(|I_{t}^u| < (1-\varepsilon/3)\cdot\Exp[|I_{t}^u|])
    \\&
    \leq
    e^{-(\varepsilon/3)^2\cdot \Exp[|I_{t}^u|/2}
    \leq
    e^{-(\varepsilon/3)^2\cdot (1+\varepsilon) \cdot|I_{t-1}^u|/2}
    \\&
    \leq
    e^{-\varepsilon^2/18}.
\end{align*}
Combing the above gives $\Pr(X_t = 1) = 1 - \Pr(X_t = 0) \geq 1 - e^{-\varepsilon^2/18}$.

It follows that for any $t$, $\Pr(X_t= 1 \mid X_1\ldots X_{t-1})\geq 1-e^{-\varepsilon^2/18}$.
Thus, in the 0/1 sequence $X_1,X_2,\ldots,$ the distance between the $i$-th `1' and the $(i+1)$-th `1' is stochastically dominated by a geometric random variable with expectation $1/(1-e^{-\varepsilon^2/18})$.
From the linearity of expectation then it follows that $\Exp[\tau'] \leq (2\log_{1+\varepsilon/3}\Delta)/(1 - e^{-\varepsilon^2/18})=O(\log\Delta)$.
This completes the proof of Claim~\ref{clm:pptau}.
\end{proof}

The next result is an analogue of Claim~\ref{clm:degrees}.
It bounds the harmonic mean of the degrees of \emph{active} nodes informed in the first $\tau$ rounds.
\begin{claim}
    \label{clm:ppdegrees}
    If $\Exp[|I_{t+1}^u| \mid I_t^u] < (1+\varepsilon)\cdot |I_t^u|$
    or $|I_t^u| \geq \Delta^2$, then
    $\sum_{v\in I_t^u\cap S^+} \deg(v)^{-1} \geq  \zeta := (\epsilon_p - 2\varepsilon)/3$.
\end{claim}

\begin{proof}
First we show that $|I_t^u| \geq \Delta^2$ implies $\sum_{v\in I_t^u\cap S^+} \deg(v)^{-1} \geq \zeta$; this is the easier part.
Each informed node $w\in \partial (S^+)$ has at least one informed neighbor $v\in \partial S$, the one that pushed the rumor to $w$.
Further each node $v\in \partial S$ has at most $\deg(v) - 1\leq \Delta-1$ neighbors in $\partial (S^+)$ (and at least one in $S$).
It follows that if $|I_t^u| \geq \Delta^2$, then at least $\Delta$ of the nodes in $I_t^u$ belong to $S^+$, i.e., $|I_t^u\cap S^+|\geq\Delta$, because otherwise, we have $|I_t^u| \leq  |I_t^u \cap S^+| + |I_t^u\cap S^+|\cdot (\Delta-1) < \Delta^2$.
From this it follows that $\sum_{v\in I_t^u\cap S^+} \deg(v)^{-1}\geq |I_t^u\cap S^+|\cdot \Delta^{-1}\geq \Delta\cdot \Delta^{-1} = 1 > \zeta$.

It remains to show that $\Exp[|I_{t+1}^u| \mid I_t^u] < (1+\varepsilon)\cdot |I_t^u|$ implies $\sum_{v\in I_t^u\cap S^+} \deg(v)^{-1} \geq \zeta$.
We assume that $\sum_{v\in I_t^u\cap S^+} \deg(v)^{-1} < \zeta$, and will show that $\Exp[|I_{t+1}^u| \mid I_t^u] \geq (1+\varepsilon)\cdot |I_t^u|$.

The proof builds upon the ideas used to prove Claim~\ref{clm:degrees}.
Similarly to Claim~\ref{clm:degrees}, we count the number of uninformed nodes to which exactly one copy of the rumor is \emph{pushed} in round $t+1$ (these nodes may also receive a second copy via pull).
In addition, we also count the number of uninformed nodes that \emph{pull} the rumor in this round.
The sum of those two numbers is then a lower-bound on twice the total number of nodes informed in round $t+1$.
We lower-bound the expectation of this sum using the definition of active and passive nodes (Definition~\ref{def:participating}).

Fix $I_t^u$.
For each informed active node $v\in I_t^u\cap S^+$, let $\beta(v) = |N(v) \cap (P-I_t^u)|/ \deg(v)$ be the fraction of $v$'s neighbors that are participating and uninformed.
Then the probability that $v$ pushes the rumor to such a neighbor and no other nodes pushes the rumor to the same neighbor is lower-bounded by
\begin{align*}
    \beta(v)\cdot\!\!\! \prod_{v'\in I_t^u \cap S^+}\mspace{-15mu}
    \left(1 - \deg(v')^{-1}\right)
    &\geq
    \beta(v)\cdot \left(1 - \sum_{v'\in I_t^u \cap S^+} \mspace{-15mu} \deg(v')^{-1}\right)
    \\&
    \geq
    \beta(v)\cdot (1-\zeta).
\end{align*}
Further, for each informed node $v\in I^u_t$, let $\gamma(v) = \sum_{v'\in N(v)\cap (A - I_t^u)}\deg(v')^{-1}$ be the expected number of uninformed active nodes that pull the rumor from $v$.
It follows that the expected total number of nodes that get informed in round $t+1$ is
\begin{equation}
    \label{eq:expI-beta-gamma}
    \Exp\left[|I_{t+1}^u| - |I_{t}^u|\right]
    \geq
    \frac12\sum_{v\in I_t^u\cap S^+} \beta(v)\cdot (1-\zeta)
    +
    \frac12\sum_{v\in I_t^u} \gamma(v).
\end{equation}

Next we bound each of the above sums of $\beta(v)$ and $\gamma(v)$ using Definition~\ref{def:participating}.
For each informed active node $v\in I_t^u\cap S^+$ we apply~\eqref{eq:active}: we have
\[
    \frac{|N(v)\cap P|}{\deg(v)}
    =
    \frac{|N(v)\cap I_t^u|}{\deg(v)} +  \beta(v)
    \leq
    \frac{|I_t^u|}{\deg(v)} + \beta(v),
\]
and
\begin{align*}
    \sum_{v'\in N(v)\cap A}\deg(v')^{-1}
    &=
    \sum_{v'\in N(v)\cap (A\cap I_t^u)}\deg(v')^{-1} +  \gamma(v)
    \\&
    \leq
    \sum_{v'\in A\cap I_t^u}\deg(v')^{-1} +  \gamma(v)
    <
    \zeta +  \gamma(v).
\end{align*}
From~\eqref{eq:active} then it follows
\[
    |I_t^u|/\deg(v) + \beta(v) + \zeta +  \gamma(v) \geq \epsilon_p.
\]
Summing now over all $v\in I_t^u\cap S^+$ and rearranging yields
\begin{align*}
    \sum_{v\in I_t^u\cap S^+} (\beta(v) + \gamma(v))
    &\geq
    |I_t^u\cap S^+|\cdot (\epsilon_p-\zeta) - \sum_{v\in I_t^u\cap S^+}\frac{|I_t^u|}{\deg(v)}
    \\&
    \geq
    |I_t^u\cap S^+|\cdot (\epsilon_p-\zeta) - |I_t^u|\cdot \zeta.
\end{align*}
Next, for each informed passive node $v\in I_t^u - S^+$, we obtain similarly using~\eqref{eq:passive} that $\zeta +  \gamma(v) \geq \epsilon_p$, and summing over all such $v$ gives
\[
    \sum_{v\in I_t^u- S^+} \gamma(v)
    \geq
    |I_t^u- S^+|\cdot (\epsilon_p-\zeta).
\]
Adding the last two inequalities above yields
\begin{align*}
    \sum_{v\in I_t^u\cap S^+} \beta(v) + \sum_{v\in I_t^u}\gamma(v)
    &\geq
    |I_t^u|\cdot (\epsilon_p-\zeta) - |I_t^u|\cdot \zeta
    \\&
    =
    |I_t^u|\cdot (\epsilon_p-2\zeta).
\end{align*}
From this and~\eqref{eq:expI-beta-gamma} it follows
\[
    \Exp[|I_{t+1}^u| - |I_{t}^u|]
    \geq
    ((\zeta-1)/2)\cdot |I_t^u|\cdot (\epsilon_p-2\zeta)
    \geq
    \varepsilon\cdot |I_t^u|,
\]
where for the last inequality we used that $\zeta = (\epsilon_p - 2\varepsilon)/3$.
This completes the proof of Claim~\ref{clm:ppdegrees}.
\end{proof}

Using Claim~\ref{clm:ppdegrees} it is easy to show an $O(1)$ bound on the expected number of additional rounds after round $\tau$, until some node in $S$ gets informed.
Fix $I_\tau^u$ and suppose that $I_\tau^u\cap S=\emptyset$ (otherwise some node from $S$ is already informed).
Then $I_\tau^u\cap S^+ = I_\tau^u\cap \partial S$, and Claim~\ref{clm:ppdegrees} gives $\sum_{v\in I_t^u\cap \partial S} \deg(v)^{-1} \geq \zeta$.
Since each node $v\in I_t^u\cap \partial S$ has at least one neighbor in $S$, the probability that none of these nodes pushes the rumor to a neighbor in $S$ in a given round $t > \tau$, is at most
\[
    \prod_{v\in I_t^u\cap \partial S}\left(1 - \deg(v)^{-1}\right)
    \leq
     e^{-\sum_{v\in I_t^u\cap \partial S}\deg(v)^{-1}}
    \leq
    e^{-\zeta}.
\]
It follows that the expected number of rounds until some of the nodes $v\in I_\tau^u\cap \partial S$ pushes the rumor to a node in $S$ is upper bounded by $1/(1 - e^{-\zeta}) = O(1)$.
Combining this with Claim~\ref{clm:pptau}, which says $\Exp[\tau] = O(\log\Delta)$, proves Lemma~\ref{lem:ppull-to-S}.

\subsubsection{Finishing the Proof of Lemma~\ref{lem:growthIt}}
\label{sec:finish-mainlemma}

We will use the next standard lemma, which is the analogue of Lemma~\ref{lem:symmetry} for \PPull{}.
Versions of this result can be found, e.g.,
in~\cite{Chierichetti2010stoc,GiakkoupisS2012soda,Censor-Hillel2012stoc}.
\begin{lemma}
    \label{lem:ppsymmetry}
    Let $T(V_1,V_2)$, for $V_1,V_2\subseteq V$, be the number of rounds for \PPull{} until a rumor that is initially known to all nodes $u\in V_1$ (and only them) spreads to at least one node $v\in V_2$.
    Then, for any  $V_1,V_2\subseteq V$, random variables $T(V_1,V_2)$ and $T(V_2,V_1)$ have the same distribution.
\end{lemma}

From this lemma and Lemma~\ref{lem:ppull-to-S}, it follows that the rumor spreads from $S$ to a given node $u\in \partial S \cap P$ in an expected number of at most $\ell = O(\log\Delta)$ rounds.
Markov's Inequality then gives that in $2\ell$ rounds $u$ is informed with probability at least 1/2, and from the linearity of expectation, in $2\ell$ rounds at least 1/2 of the nodes from $\partial S \cap P$ are informed in expectation.
Using Markov's again we obtain that in $2\ell$ rounds more than $3/4$ of the nodes from $\partial S \cap P$ are still uninformed with probability at most $(1/2)/(3/4)=2/3$.
Thus, 1/4 of the nodes from $\partial S \cap P$ are informed in an expected number of most $2\ell/(1/3) = 6\ell$ steps.
From this and Claim~\ref{clm:active-fraction}, that says $|\partial S \cap P| = \Theta(|\partial S|)$, we obtain Lemma~\ref{lem:growthIt}.

\subsection{The Case of High Boundary Expansion: Analysis of the  Growth of \texorpdfstring{$\boldsymbol{I_t^+}$}{It plus}}
\label{sec:Itplus}

In this section we prove the following result.
\begin{lemma}
    \label{lem:growthItplus}
    Suppose that $I_t = S$ for some set $S \subset V$ with boundary expansion $h(S)\geq\epsilon_h$, where $ \epsilon_h > 0$ is an arbitrary constant.
    There is a positive integer $b = b(S) \leq |\partial S|/\alpha$ such that the expected number of rounds until $b$ nodes from $\partial(S^+)$ have some informed neighbor is  $O\left((b/|\partial S|)\cdot \log\Delta \right)$.
\end{lemma}

Observe that the expected number of nodes from $\partial(S^+)$ that have some informed neighbor after round $t+1$ is at least $h(S)\cdot |\partial S| = \Omega(|\partial S|)$ (from Equation~\eqref{eq:pull-bexpansion} in Section~\ref{def:bexpansion}).
To prove Lemma~\ref{lem:growthItplus} we need to bound also the variance of the number of those nodes.
Intuitively, the variance will be larger when the degrees of nodes in $\partial S$ are larger, and then larger values for $b$ are needed for the lemma to hold.
We note that the condition  $b \leq |\partial S|/\alpha$ is  to ensure that the time bound is at most $O(\log(\Delta)/\alpha)$, as this is necessary for the intended use of the lemma (in the proof of Claim~\ref{clm:psi-double}).

We give now an overview of the proof of Lemma~\ref{lem:growthItplus}.
We distinguish three cases.

The first case is when the larger contribution to the boundary expansion of $S$ is from nodes $u\in \partial S$ of degree $\deg(u) \leq c\cdot|\partial S|$, for some constant $c$.
Formally, we have  $h_{\{u\in \partial S \colon \deg (u)\leq c\cdot|\partial S| \}}(S)\geq \epsilon_h/3$ (see Definition~\ref{def:bexpansion2}).
Using the second moment method, we show that after one round of \Pull{}, we have with probability $p=\Omega(1)$ that $b = \Omega(|\partial S|)$ nodes from $\partial(S^+)$ have some informed neighbor.
It follows that $b$ nodes from $\partial(S^+)$ have some informed neighbor after an expected number of $1/p = O(1)$ rounds.

The next case is when the larger contribution to $h(S)$ comes from nodes $u\in \partial S$ of degree between $c\cdot|\partial S|$ and $|S|$.
We argue that for some $k$ from this range of degrees, the number of nodes $u\in \partial S$ with degree $k\leq \deg(u)\leq 2k$ and $\Theta(k)$ neighbors in $\partial(S^+)$ is at least $\Omega(|\partial S|/l)$, where $l = \log\frac{2\min\{|S|,\Delta\}}{\max\{c|\partial S|,\delta\}}$.
Then the probability of informing at least one such $u$ in a round of \Pull{} is $p = \Omega (|\partial S|/(kl))$.
Hence, at least $b = \Theta(k)$ nodes from $\partial(S^+)$ have some informed neighbor after an expected number of $1/p = O(bl/|\partial S|)$ rounds.

The last case is when the largest contribution to $h(S)$ is from nodes $u\in \partial S$ of degree $\deg(u) \geq d^\ast$, where $ d^\ast =\max\{|S|,c|\partial S|\}$.
We argue that $\Omega(|\partial S|)$ nodes $u\in \partial S$ have $\Omega(d^\ast)$ neighbors in $\partial(S^+)$.
As the degree of those nodes $u$ may be very large, we rely on push transmissions to inform them.
Since the degree of any node from $S$ is at most $|S^+|-1$, we argue that in one round of \Push{}, at least one of those $u$ is informed with probability $p = \Omega (|\partial S|/|S^+|)$.
Hence, at least $b = \Theta(d^\ast) = \Theta(|S^+|)$ nodes from $\partial(S^+)$ have some informed neighbor after an expected number of $1/p = O(b/|\partial S|)$ rounds.

The results we prove in the first and last cases are stronger than the statement of Lemma~\ref{lem:growthItplus}, as the time bounds shown are $O(b/|\partial S|)$ rather than $O((b/|\partial S|)\cdot \log\Delta)$.
For the second case the time bound is $O((b/|\partial S|)\cdot l)$, and $l$ can be as large as $\Theta(\log\Delta)$; there are examples for which  this bound cannot be improved to $O(b/|\partial S|)$.

The complete proof of Lemma~\ref{lem:growthItplus} is in the Appendix.

\subsection{Proof of Theorem~\ref{thm:ub-pushpull}}

\label{sec:proof-main}

We combine Lemmata~\ref{lem:growthIt} and~\ref{lem:growthItplus} to show that the expected number of rounds needed to double
$
    \Psi_t = |I_t| + |\partial I_t|/2
$
or increase $|I_t|$ above $n/2$ (whichever occurs first) is bounded by $O(\log(\Delta)/\alpha)$.
\begin{claim}
    \label{clm:psi-double}
    Let
    $
        T_t
        =
        \min\{i\colon  \Psi_{t+i} \geq 2\Psi_{t} \,\vee\, |I_{t+i}| > n/2\}.
    $
    Then
    $
        \Exp[T_t \mid I_t]
        \leq
        s\cdot \log(\Delta)/\alpha,
    $
    for some constant $s>0$.
\end{claim}

\begin{proof}
The proof is by an  inductive argument.
It relies on the following direct corollary of Lemmata~\ref{lem:growthIt} and~\ref{lem:growthItplus} (its proof is in the Appendix).
We write $I_i^S$ and $\Psi_i^S$ to denote respectively $I_{t+i}$ and $\Psi_{t+i}$
given that $I_t = S$.
\begin{corollary}
    \label{cor:growthPsi}
    For any non-empty set $S\subset V$, there is a  positive integer $b_S \leq |\partial S|/\alpha$ such that for
    \[
        \tau_S = \min\{i\colon  \Psi_{i}^S \geq \Psi_{0}^S + b_S\}
    \]
    we have
    $\Exp[\tau_S] \leq  c\cdot(b_S/|\partial S|)\cdot\log\Delta$, for some constant $c>0$.
\end{corollary}

Let
\[
    T(S,k)
    =
    \min\{i\colon  \Psi_{i}^S \geq k \,\vee\, |I_{i}^S| > n/2\}.
\]
Note that the quantity $T_t$ we are interested in can be expresses as  $T_t = T(I_t,2\Psi_t)$.
We will prove that if $|S|\leq n/2$ and $\Psi_0^S < k\leq 2\Psi_0^S$, then
\begin{equation}
    \label{eq:expTsk}
    \Exp[T(S,k)]
    \leq
    c\cdot
    \frac{4k - 3\Psi_0^S}{\alpha k}\cdot \log\Delta,
\end{equation}
where $c$ is the constant of Corollary~\ref{cor:growthPsi}.
Setting $k = 2\Psi_0^S$ yields
$\Exp[T(S,2\Psi_0^S)] \leq 5c \log(\Delta) / (2\alpha)$,
which is equivalent to  the desired inequality
$ \Exp[T_t \mid I_t = S] \leq s \log(\Delta)/\alpha$,
for $s = 5c/2$.

It remains to show~\eqref{eq:expTsk}.
The proof is by induction on $k - \Psi_0^S$.
We distinguish two cases.

\smallskip
\textbf{Case 1: $k \leq \Psi_0^S +  b_S$}.
This is the base case of the induction.
Since $k \leq \Psi_0^S +  b_S$ we have $T(S,k)\leq T(S,\Psi_0^S +  b_S) \leq \tau_S$. Also,  from Corollary~\ref{cor:growthPsi} we have $\Exp[\tau_s] \leq c\cdot(b_S/|\partial S|)\cdot\log\Delta \leq c\cdot(1/\alpha)\cdot\log\Delta$, as $b_S \leq |\partial S|/\alpha$.
Combining these two results yields
$$\Exp[T(S,k)] \leq  c\cdot(1/\alpha)\cdot \log \Delta.$$
Hence, to prove~\eqref{eq:expTsk} it suffices to show that $\frac{4k - 3\Psi_0^S}{ k}\geq1$: we have
$
    \frac{4k - 3\Psi_0^S}{ k}
    =
    4 - 3\Psi_0^S/{k}
    \geq
    1,
$
because $k > \Psi_0^S$.

\smallskip
\textbf{Case 2: $k > \Psi_0^S + b_S$}.
Let $S' = (I_{t+\tau_S}\mid (I_t = S))$.
We have $T(S,k) = T(S, \Psi_0^S + b_S) + T(S',k) = \tau_S + T(S',k)$.
Taking the expectation gives
\[
    \Exp[T(S,k)] = \Exp[\tau_S] + \Exp[T(S',k)].
\]
From Corollary~\ref{cor:growthPsi}, we have
\[
    \Exp[\tau_S] \leq c\cdot\frac{b_S}{|\partial S|}\cdot\log\Delta
\]
To bound $\Exp[T(S',k)] = \Exp[T(I_{t+\tau_S},k)\mid I_t = S]$, we observe that $\Psi_0^{S'} = (\Psi_{t+\tau_S} \mid(I_t = S)) \geq \Psi_0^{S} + b_S$.
Further, from the induction hypothesis, Inequality~\eqref{eq:expTsk} holds if we replace $S$ by $S'$ as  $k - \Psi_0^{S'} < k - \Psi_0^{S}$.
It follows
\[
    \Exp[T(S',k)]
    \leq
    c\cdot
    \frac{4k - 3(\Psi_0^S+b_S)}{\alpha k}\cdot \log\Delta.
\]
Combining the three inequalities above yields
\[
    \Exp[T(S,k)]
    \leq
    c\cdot
    \left(\frac{b_S}{|\partial S|}
    +\frac{4k - 3\Psi_0^S}{\alpha k}
    -\frac{3b_S}{\alpha k}\right)
    \cdot \log\Delta.
\]
Thus to prove~\eqref{eq:expTsk} it suffices to show that $\frac{b_S}{|\partial S|} - \frac{3b_S}{\alpha k}\leq 0$, or equivalently, that $k \leq 3 |\partial S|/\alpha$:
We use the assumption of~\eqref{eq:expTsk} that $k\leq 2\Psi_0^S$, and the fact that $|S|\leq |\partial S|/\alpha$ which follows from the definition of $\alpha$.
We have
\begin{align*}
    k
    \leq
    2\Psi_0^S
    =
    2(|S| + |\partial S|/2)
    &\leq
    2(|\partial S|/\alpha + |\partial S|/2)
    \\&
    =
    (2+\alpha)|\partial S|/{\alpha}
    \leq
    3|\partial S|/{\alpha}.
\end{align*}
This completes the proof of~\eqref{eq:expTsk}, and the proof of Claim~\ref{clm:psi-double}.
\end{proof}

Let $y = 2s \log(\Delta)/\alpha$.
From Claim~\ref{clm:psi-double} we have
$
    \Exp[T_t \mid I_t]
    \leq
    y/2,
$
and Markov's Inequality yields
$
    \Pr\left(T_t \leq y \mid I_t \right)
    \geq
    1/2.
$

We partition time into intervals of $y$ rounds, and count the number of intervals in which $\Psi_t$ doubles or $|I_t|$ exceeds $n/2$.
Formally, let $X_i$, for $i\geq 1$, be the 0/1 random variable that is 1 iff  $T_{(i-1) y} \leq y$.
From  inequality $\Pr\left(T_t \leq y \mid I_t \right) \geq 1/2$ above it follows that $\Pr(X_i = 1 \mid X_1\ldots X_{i-1}) \geq 1/2$.
Hence, $\sum _{j\leq i} X_j$ stochastically dominates the sum  of $i$ {independent} Bernoulli trials with expectation 1/2.
From Chernoff bounds then we obtain for $i^\ast = 2(\beta + 3) \log n$ that
\begin{align*}
    \Pr\bigg(\sum _{j \leq i^\ast} X_j  < \log n \bigg)
    \leq
    e^{-2(i^\ast/2 - \log n)^2/i^\ast}
    <
    n^{-\beta - 1}.
\end{align*}
This implies that $i^\ast y$ rounds suffice to inform $n/2 + 1$ nodes with probability at least $1-n^{-\beta - 1}$:
If $|I_{i^\ast y}| \leq n/2$ then fewer than $\log n$ among the $X_1\ldots X_{i^\ast}$ are 1, because $|I_{i^\ast y}| \leq n/2$ implies $\Psi_{i^\ast y} \geq 2^{\sum _{j \leq i^\ast} X_j}$, and $\Psi_t< n$ if $|I_t| < n$.
Hence, $\Pr(|I_{i^\ast y}| \leq n/2) \leq \Pr(\sum _{j \leq i^\ast} X_j  < \log n) < n^{-\beta - 1}$.

Once a set $V_1\subseteq V$ of size $|V_1|\geq n/2+1$ has been informed, any given node $u\notin V_1$ gets informed within $i^\ast y$ additional rounds with probability at least $1-n^{-\beta - 1}$:
From Lemma~\ref{lem:ppsymmetry}, the probability that $u$ learns the rumor from $V_1$ within $i^\ast y$ rounds, is the same as the probability that some node from $V_1$ learns a rumor originated at $u$ within $i^\ast y$ rounds.
And the latter probability is at least equal to the probability that $n/2+1$ nodes learn $u$'s rumor within $i^\ast y$ rounds, because then at least one of these nodes belongs to $V_1$, as $|V_1| > n/2$.

From the above and the union bound, all nodes get informed in at most $2i^\ast y = O(\log n\cdot \log(\Delta) / \alpha)$ rounds with probability at least $1-n^{-\beta}$.

\subsection*{Acknowledgements}

I would like to thank Keren Censor-Hillel and Thomas Sauerwald for helpful discussions on the motivation for this work.

redpajama_set_name: RedPajamaArXiv


You in a general sense settled when you took in your video has so minor scenes you are first-since everlastingly YouTube video and you other than accomplish add up to base. Obtaining saw is direct especially with YouTube; regardless, you have to pass on a great deal of views. With a wide grouping of motion pictures being downloaded and present well ordered, you should make results about it. With making an amazing film you regularly begin. It could be stacked with essential and moreover obliging data, or conceivably it is the thing truly, or a champion among the most outlandish issue which would undeniably ever strike any individual. Whichever it can't abstain from being, it will emphatically verifiably be tending to have the watcher's inclination. Anchoring the best stunning film isn't adequate. You require an interesting once-over; and moreover recall target catchphrases. This moves for picking your titles other than. It is to raise the visitors' enthusiasm to win your short article is seen by them.
You may in any case assume that it is difficult to affect the views you to will emphatically call for; however starting at now, possibly you are executing these things by the book all clearly. This is adequately not. A disaster area fundamentally more set out to ensure accomplishment is taken by the road to pervasiveness. One point you should put in head is that, YouTube is simply among the on the web sorting out on the web. You will without a doubt uncovers such an extensive proportion of online web based life organize out-there to use to get essentially more scenes to youtube views. Face book is among various most sweltering social correspondence objectives around. You will be able to just post relationship of one's narratives in your record, your partners' profile; for the most part the client is family you have truly not furthermore met, of untouchables. You make a note or can even lead it to them. There are without uncertainty awesome arrangements of procedures for getting sights that are YouTube – from your own specific Face book account that is to an extraordinary degree. Where beloveds may get to your motion pictures with just a tick away you could moreover impact your very own particular fan to page.
One more people gather on the web arranging advancing these days is Twitter, which has truly been named because the inescapable predetermination of advancement. Proper here, your supporters could on a very basic level tail you despite your free youtube views. This is the way in which you will get YouTube scenes – tweet the privilege expects to get seen. Help could correspondingly begin with your own unique YouTube mates. You ought to just watch their film, and circuit amigos. You UI and also can in addition think about your own specific movie to get their consideration.


text:
Johanna Leia Net Worth: Who is Johanna Leia, Drake's Girlfriend?
By Mark Adams Last updated Jun 29, 2022
Johanna Leia, whose real name is Johanna Edelburg and who was born on February 19, 1981, is a well-known American model, TV personality, social media influencer, brand ambassador, and business owner from Los Angeles, California. Johanna is well-known all over the country because she is the mother of the basketball player Amari Bailey from Sierra Canyon.
Let me tell you that Amari is famous for being on the 2019 USA Basketball Men's Junior National Team. He is also well-known for being on the USA U16 National Team, which won the gold medal in Belém, Brazil. If we talk about his mother, Johanna, on the other hand, she is a well-known fashion model and TV personality.
$9 and $10 million (approx)
Source of Wealth: Model, TV Personality, Social Media Influencer
Johanna Leia Early Life
Johanna Leia's parents brought her into the world on February 19, 1981, in Los Angeles, California, United States. She is a beautiful American model. Her real name, according to the sources, is Johanna Edelburg.
Based on the date Johanna was born, she is 40 years old (as of 2021). Every year on February 19, Johanna cuts her birthday cake. Leia believes in the Christian faith. Sources say that Johanna Leia got her degree from a well-known college in LA.
Ava Max Net Worth: How Much Does Ava Max Earn a Year?
After that, she turned her attention to her career as a model. Let me tell you that she got serious about her modeling career when she was in college. Johanna is a well-known model and TV personality right now.
Johanna Leia Career
At the time, Johanna Leia got her first job as a fashion model. Some people say that for a long time, she worked as a freelance model. She then got a contract with a few well-known fashion agencies to be a model.
Taylor Lautner Net Worth: Career, His Life, His Total Income and More
Reports say that Johanna Leia has also used Ford Models and Wilhelmina Models. She has also been a model for several well-known fashion brands. Johanna now works as a model for IconSwim and other swimwear companies.
Johanna Leia's Net worth
Let me tell you that Johanna also uses her social media accounts to promote different fashion items. Sources say that she made a good living from her modeling job. Johanna Leia is thought to be worth between $9 and $10 million (approx).
Who is Johanna Leia, Drake's girlfriend?
Leia is a model and used to be on the reality show "Bringing Up Ballers" on Lifetime. Sports Keeda says that Leia used to work for both Ford and Wilhelmina Models.
A post shared by Johanna Leia (@johannaleia)
Amari Bailey, a basketball player at Sierra Canyon High School, lives with his mother, who is 40 years old. She has Amari with her ex, Aaron Bailey, who used to play wide receiver in the NFL.
Aaron played for the Indianapolis Colts in the NFL for five years. Leia and Aaron also have a daughter named Savy.
Who is Johanna Leia's Son?
Amari is a shooting guard for Sierra Canyon High School. He is 6 feet 4 inches tall. Amari is the No. 3 player in the country overall and the No. 1 combo guard.
Amari also helped USA Basketball win the 2019 FIBA Americas U16 Championship in Brazil, where they won the gold medal.
The 17-year-old plays with Bronny James, who is the son of NBA star LeBron James. In 2019, Bronny became a member of Sierra Canyon.
ESPN says that Amari has already decided to go to UCLA, even though he and Bronny are both in their last year of high school.
Who is Drake's Girlfriend Johanna Leia?
Drake and Leia were seen at the Sierra Canyon basketball game, and then they were seen at an exotic private dinner. This seemed to be the next step in their relationship. Drake made the most of the fact that the LA Dodgers were out of town on July 8 by renting Dodgers Stadium for a private dinner with Leia.
A person who was at the meeting tells The Sun that the two were having dinner at a fancy table set up on the third baseline. The source told The Sun, "The two were seen out to dinner just after 11 p.m. on Thursday."
Taylor Swift Net Worth: Will Taylor Swift Be a Billionaire?
Except for a well-dressed butler, they were the only ones on the baseball field. Large white flower arrangements were placed on the table and on the butler's stand to match the big white table where the couple was sitting.
Drake's appearance definitely wowed the beautiful model, who was even wearing a Dodgers jersey with her name on it. The source also told The Sun that the pair had "two waiting black SUVs parked right outside the stadium" for a quick and private exit.
What Does Johanna Leia Do for a Living?
Johanna Leia is a well-known American model, TV personality, social media influencer, model ambassador, and business owner from Los Angeles, California. She was born on February 19, 1981.
Does Johanna Leia Have a Child?
Johanna has a son named Amari Bailey and a daughter named Savvy, according to her social media profiles (daughter). The latest news says that Aaron Bailey is the father of Johanna Leia's child. Sources say that Aaron Bailey is a professional football player who used to play for the Indianapolis Colts.
Why Did Drake Break Up With Johanna Leia?
Drake's relationship with Johanna started after it was said that he was the reason why Naomi Sharon broke up with musician Jamie Sun after 8 years together. People said that the rapper flew the two to Los Angeles so that Naomi could work on his album. Jamie, on the other hand, said that Drake hooked up with his girlfriend while they were recording.
Johanna Leia is an American model, TV personality, social media influencer, brand ambassador, and business owner from Los Angeles, California.
Johanna Leia is worth between $9 and $10 million (approx) in 2022.
Ben Shapiro Net Worth: How Much Did He Invest in Real Estate?
Del Vecchio Net Worth: How Much Money Did He Have When He Died?
Who is Stephanie Hsu? Her Personal Life, Net Worth and More
Who is Alba Baptista? Net Worth, Age and Career
How Much Net Worth Has Adam Rich at the Time of His Death?
Let's Take a Tour of Captain Marvel Brie Larson's Lifestyle
When Will the Manga Series Tokyo Revengers Season 2 Be…
Netflix' s Women at War Movie Ending Explained
Did the Show Pier Get Renewed for Season 3?
When Will "How I Met Your Father" Season 2 Be…

redpajama_set_name: RedPajamaCommonCrawl


text:
MayMay 18, 1912
Born on May 18#36
Born in 1912#6
First Name Perry#1
Born in Canonsburg, PA#1
Singer Born in Pennsylvania#25
Prominent singer in the 1930s and '40s whose best known songs included "Don't Let the Stars get in Your Eyes" and "Catch a Falling Star," the latter of which became the first ever certified gold single on March 14, 1958. He was also a television personality who hosted his own weekly TV show.
In his early teens, his main ambitions were to become the best barber in his city, and by the age of 14, he was running his own barber shop.
Those close to him said he was the same person on stage as he was off stage.
He got married to Roselle Beline on July 31, 1933 and they had three children together.
He was influenced by Bing Crosby's style.
Perry Como Clips
Perry Como Popularity
Perry Como Is A Member Of
First Name Perry
Perry Como Fans Also Viewed
Laverne Andrews
More May 18 Birthdays
Caroline Gregory
Armon Warren
May 18 Birthdays
More Taurus


text:
Get up-to-date information about BER here.
Get information today. Fly from 31 October 2020.
Information about BER in brief about costs, financing and architectural art.
Press Releases and Archive
Here you will find all press releases of Flughafen Berlin Brandenburg GmbH.
Sign up here to subscribe to the airport company's press releases and traffic reports.
Our press kit for the company and the airport can be downloaded here.
This is where you can access the monthly traffic statistics.
Here you can find photos and videos regarding Berlin's airports and Flughafen Berlin Brandenburg GmbH.
Here you can order or download all FBB publications free of charge.
Photography and filming requests
For photography and filming requests please fill out this form.
We are happy to help with your research and inquiries.
The Master Plan offers the airlines, the regional economy and all other partners and service providers a clear orientation regarding the development of the airport location. The site will be developed further in several steps and more terminal capacity will be added. In addition, airside developments such as taxiways, aprons or operational buildings are planned during all extension phases to meet operational requirements.
First extensions
The new Terminal 3 is built
Further terminal expansion
As part of the first construction stage, Terminal T2 will be built directly in front of the existing North Pier. T2 is designed to handle 6 million passengers and will be used as a processor. It provides all of the various functions, ranging from check-in, baggage check-in and reclaim to security screening and service facilities, right through to retail and restaurants. The aircraft are embarked from the North Pier, which Terminal T2 is connected to via two bridges.
Terminal 1 was opened with a capacity of approximately 25 million passengers but, in subsequent years, will be used at its maximum capacity of approximately 27 million passengers. In addition, the old Schönefeld site – then Terminal 5 – will provide capacity of between 8 and 10 million passengers per year.
Overall, a total of up to 43 million passengers will be able to fly to and from Berlin each year from BER.
The new Terminal 3 can be built opposite Terminal 1 by the end of the 2020s. It will be used to concentrate commercial air traffic between the runways and at BER's railway station and replace Terminal 5. Capacity will be geared towards demand. Overall, the T3 site has a total capacity of up to 15 million passengers, which will make it possible to handle up to 48 million passengers annually.
As a counterpart to Terminal 3, Terminal 4 with its capacity of 6 million passengers per year can be built to the south.
Terminal 1 can also be extended to the west by another pier and satellite. The focus of this expansion step is on waiting rooms with aircraft positions close to the building, which passengers can easily access via bridges, and additional non-aviation areas.
Once all terminal expansions are complete, BER will be able to handle up to 55 million passengers per year.


text:
Q: Table alias not recognized in subquery Access I have created a query to find the previous row with matching ID criteria. In the WHERE statement, my table alias "t1" is not being recognized as an alias and when running the query I am prompted to enter parameter value for T1. From my understanding subqueries MUST have a table alias. How do I make the "enter parameter value" prompt go away? My SQL code is below.
SELECT t.NUM, t.ID, tprev.Date_ AS previous_date, tprev.Measurement AS previous_measurement
FROM Table1 AS t LEFT JOIN Table1 AS tprev ON (tprev.Date_ < t.Date_) AND (tprev.id = t.id)
WHERE not exists
        (select 1
        from Table1 AS t1
        where
            t1 = t.ID
            and t1.Date_ < t.Date_
            and t1.Date_ > tprev.Date_);

A: You have a table alias, but no column.  Presumably you intend:
where not exists (select 1
                  from Table1 AS t1
                  where t1.ID = t.ID and
--------------------------^ this part
                        t1.Date_ < t.Date_ and
                        t1.Date_ > tprev.Date_
                 );

redpajama_set_name: RedPajamaStackExchange


text:
Ndeng est un village du Cameroun situé dans le département du Boumba-et-Ngoko et la région de l'Est, à proximité de la frontière avec la République centrafricaine. Il fait partie de la commune de Gari-Gombo.

Population
En 1964, le village comptait 137 habitants, principalement des Yangéré.

Lors du recensement de 2005, on y dénombrait  personnes.

Notes et références

Annexes

Bibliographie
 Dictionnaire des villages de Boumba-Ngoko, ORSTOM, , juin 1966, 34 p.,

Liens externes
 Gari-Gombo, sur le site Communes et villes unies du Cameroun (CVUC)
 Plan communal de développement de Gari-Gombo, PNDP, juillet 2012, 117 p.

Village dans la région de l'Est (Cameroun)

redpajama_set_name: RedPajamaWikipedia


text:
CDS Volunteers Go to Springfield, Complete Joplin Response
Photo by Lorna Grow
CDS volunteer Pearl Miller reads with a child in Joplin, Missouri, following severe tornadoes
A new response site for Children's Disaster Services (CDS) is Springfield, Mass., which was hit by a tornado on June 2. A team of five CDS volunteers began work there late last week in response to a call from the American Red Cross.
In Springfield, the CDS team is working in the Mass Mutual shelter–a multi purpose arena and convention center. "The center is working well," reports CDS associate director Judy Bezon.
The Springfield Tornado has just been "declared," Bezon says, "which means the President has identified it as a major disaster area, which in turn makes federal resources available to those whose homes have been destroyed." She expects FEMA to open eight Disaster Recovery Centers (DRCs) where people come to apply for aid. "We have had preliminary talks with the FEMA Voluntary Agency Liaisons about setting up child care centers in some of their DRCs," she adds.
Meanwhile, CDS volunteers are completing a project to care for children of families living in shelters in Joplin, Mo. Previously this spring, CDS also served in Tuscaloosa, Ala., after tornado destruction there in April.
The last CDS volunteers will leave Joplin today. A total of 28 CDS volunteers have worked there since the tornado. The response has lasted well past the standard time limit of two weeks for CDS volunteers, so new volunteers have been rotated in while others left after completing their two weeks. "The last few days, CDS volunteers who lived locally drove in to help us–they couldn't stay an entire week," Bezon reports. "The Red Cross Case Workers worked hard to find places for the last people in the shelter to live. Generally we leave a few days before the shelter closes, as numbers of children are dwindling."
Bezon herself worked in Joplin up until last week as part of a Critical Response Childcare team that was deployed because of the high number of fatalities. That specially trained team was "very very needed in the shelters," she says. Some of the children in the Joplin shelters required intensive caregiving.
CDS volunteer Rosemary Brandenberg engages a child in water play after severe tornadoes in Joplin, Missouri.
The CDS volunteers in Joplin handled an especially stressful situation very well, Bezon says gratefully. "It was a hardship because the volunteers were living in the shelters, and the work was so difficult. The sheer number of children and the behavioral needs were very intense."
The destruction in the area of Joplin hit by the tornado is "just unbelievable," in Bezon's words. The path of the tornado was a mile wide and six miles long, and passed through low and middle income areas. "Everything in its path was completely flattened," she says. "It looks barren in every way."
One reason the shelters in Joplin had been needed for longer than usual was that damaged homes continued to be condemned and demolished, forcing families to find other places to live when all available housing and hotels were already full, Bezon explains. Many residents "doubled up" by sharing their homes with friends. The people left in the shelters were those without the connections or the money to find other places to live.
In other disaster relief news, Brethren Disaster Ministries has just learned that it will receive a grant for $52,500 from the Community Foundation of Middle Tennessee for the rebuilding work in the Nashville area.
The Church of the Brethren's Emergency Disaster Fund (EDF) has given $5,000 to Brethren Disaster Ministries for assessment and project development following the 2011 spring storms in the US. The money will help BDM staff gather information, attend meetings, and travel to disaster sites.
An EDF grant of $4,000 has been given to aid the community of Union Victoria CPR in Guatemala, following wind damage to a suspension bridge used for transporting coffee beans to market.
Tagged BDM, CDS
Conference Officers Review How Special Response Decisions Will Be MadeNewsline for June 16, 2011


Is there a New Yorker who does not yearn occasionally to escape the city and its grinding annoyances? Jeff Mehler and his wife, Mary Russell, know well the impulse to flee and, unlike most of us, acted on it. After more than two decades in New York City, they left in 1995 in search of a simpler life in the bucolic hills of eastern Connecticut. Theirs is a cautionary tale for those seeking the alleged placidity of the country. Emphasis on the alleged.
Mr. Mehler, a financial planner, and Ms. Russell, a school administrator, found their dream home high on a hill overlooking the Connecticut River in the tiny village of Deep River, near Old Lyme. The lower level has an indoor pool and a spacious office for Mr. Mehler. The back wall on both levels faces east, with a panoramic view of the river and the lush hills beyond. It was everything that their old apartment on the Upper East Side was not: open, spacious, imbued with the outdoors.
But the pastoral perfection did not last long. They discovered termites in the basement in the summer of 1996. Exterminators came twice, placing pesticide in the ground and drilling holes through the basement's concrete floor to attack the pests in the soil below the house.
Winter came, and Mr. Mehler and Ms. Russell found that they were using hundreds of gallons of heating oil each month. By February, the cause and awful scope of the problem became clear: the exterminators had punctured a pipe beneath the basement floor that returned unused oil from the furnace to the oil tank, allowing between 800 and 1,800 gallons of heating oil to seep into the ground.
The pool was unusable, so foul were the oil vapors. So was Mr. Mehler's home office. Worse, the oil had leaked down the hill into three adjoining properties and into the bedrock beneath the house. While the oil can be pulled from the soil, there is no technology for removing it from bedrock.
Mr. Mehler and Ms. Russell said they began getting rashes, headaches and other ailments. They discovered late last year that the exterminators, ignoring state regulations and the manufacturer's own warnings, had placed insecticide under the house near the well that contains their drinking water. Tests have shown no trace of the pesticide in the water, but they fear a connection between their symptoms and the oil and pesticide in the ground.
To its credit, the exterminating company, Terminix International, took responsibility for the mess. The company has been actively involved in the cleanup, although the quality of the effort is in dispute. When it became clear that the oil had reached the bedrock -- rendering the house unsalable -- Terminix offered to buy it.
The company says it offered more than the house's market value; several appraisals produced an average estimate of $456,000. But Mr. Mehler says the company balked at paying for all the damage it had caused. ''We can't get back the three years that we lost, the stress we've been under, the fear that we'll be financially ruined,'' he said.
After negotiations broke down, Terminix invoked a clause of its service contract with Mr. Mehler and Ms. Russell requiring all disputes to be resolved by arbitration. The clause, increasingly common in consumer contracts, was on the back of the form Mr. Mehler and Ms. Russell had signed. They say they never even saw it.
Afraid they would not be compensated adequately for their losses if they accepted arbitration, Ms. Russell and Mr. Mehler hired a lawyer, filed a suit in Federal District Court and spent thousands of dollars fighting for the right to air their grievances before a jury. Recent court decisions have generally upheld such agreements, known as mandatory arbitration clauses. But Mr. Mehler and Ms. Russell won a preliminary round in court on Sept. 28, with a judge ruling that the case could be heard in Federal court. Terminix says it will appeal.
But Mr. Mehler and Ms. Russell want desperately to go to trial, where they hope to be awarded more than $1 million. They have also begun to reconsider the virtues of a large house in the unspoiled countryside.
Mr. Mehler said his wife has begun looking at newspaper ads for Manhattan apartments.


text:
Automotive jobs in Brookfield Wisconsin
Join Our Team in Brookfield.
Join Our Winning Team
We have a dedicated and motivated team here at Hall Volkswagen, and we are looking for more people who can bring that to our business. We need people who have excellent customer service skills, and people who are prepared to handle a new challenge everyday. If you consider yourself to be a passionate, creative, and reliable person then you may be the perfect fit for our team.
We are currently looking for:
Lot Attendant
Courtesy Driver
Service Department Valet
Body Shop Technician
Mazda Technician
VW Technician
You will get to work in a great environment with competitive benefits. All you have to do is fill out the form below. We will take a look at your information, and if we think you will make a good fit, then we will be in touch with you soon. We thank you for considering Hall Volkswagen during your search for employment.
Online Employment Application
Position You Are Applying For* Product Specialist Lot Attendant Automotive Sales Courtesy Driver Service Department Valet Body Shop Technician Automotive Technician Mazda Technician VW Technician
Desired Location(s)*
Desired Salary*
Date Available*
Day Time Phone
Education Type Some H.S. H.S. Grad Some College College Grad
Areas Studied
Degree Earned
Start Date January February March April May June July August September October November December 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1990 1989 1988 1987 1986 1985 1984 1983 1982 1981 1980 1979 1978 1977 1976 1975 1974 1973 1972 1971 1970 1969 1968 1967 1966 1965 1964 1963 1962 1961 1960 1959 1958 1957 1956 1955 1954 1953 1952 1951 1950 1949 1948 1947 1946 1945 1944 1943 1942
End Date January February March April May June July August September October November December 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1990 1989 1988 1987 1986 1985 1984 1983 1982 1981 1980 1979 1978 1977 1976 1975 1974 1973 1972 1971 1970 1969 1968 1967 1966 1965 1964 1963 1962 1961 1960 1959 1958 1957 1956 1955 1954 1953 1952 1951 1950 1949 1948 1947 1946 1945 1944 1943 1942
Employer Name
Supervisor Phone
Job Start Date January February March April May June July August September October November December 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1990 1989 1988 1987 1986 1985 1984 1983 1982 1981 1980 1979 1978 1977 1976 1975 1974 1973 1972 1971 1970 1969 1968 1967 1966 1965 1964 1963 1962 1961 1960 1959 1958 1957 1956 1955 1954 1953 1952 1951 1950 1949 1948 1947 1946 1945 1944 1943 1942
Job End Date January February March April May June July August September October November December 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1990 1989 1988 1987 1986 1985 1984 1983 1982 1981 1980 1979 1978 1977 1976 1975 1974 1973 1972 1971 1970 1969 1968 1967 1966 1965 1964 1963 1962 1961 1960 1959 1958 1957 1956 1955 1954 1953 1952 1951 1950 1949 1948 1947 1946 1945 1944 1943 1942
Any additional information about yourself or skills that may apply
Attach Resume Optional
Enter 4 digit code
Refresh Code
By submitting this form you will be submitting an application for employment at Hall Volkswagen. We appreciate your interest in the positions mentioned above and will contact you shortly.
The information contained in this web site is provided as a service to the Internet community, and does not constitute legal advice. We try to provide quality information, but we make no claims, promises or guarantees about the accuracy, completeness, or adequacy of the information contained in or linked to this web site and its associated sites and we make no claim that any of the free forms contained in this web site are appropriate for your particular needs.
Please speak with our trade advisor for more information.
Email Parts


Children of all ages (and their parents and grandparents) enjoy hearing holiday stories, singing holiday songs, learning holiday traditions, and, of course, tasting holiday foods. Join the Kol Hadash community for children-friendly Jewish celebrations held throughout the year. Parents, grandparents and guests are always welcome! All holiday celebrations are free, except where indicated.
Our whole school—students, teachers, and families—come together to celebrate major Jewish holidays as well as to enjoy special programs on Jewish culture.
A wonderful way for families to celebrate together in a relaxed and child-friendly atmosphere. Intended for families with children ages 5-12 (and parents/grandparents), but younger children are very welcome — we have a high noise tolerance! Childcare is available during the 10:30 am Adult Morning Service; families can then join us for lunch during our extensive oneg and stay for the Family Service.
A fun way to sing, dance and play our way into the Jewish New Year! Intended for families with children ages 0-5 (and parents/grandparents).
A opportunity to reflect on the Jewish New Year together. Intended for families with children ages 5-12 (and parents/grandparents), but younger children are very welcome — we have a high noise tolerance! Childcare is available during the 10:30 am Adult Morning Service. If you need lunch suggestions for your children, we can provide a list of quick and easy local eateries so you can join us again at 1:00 for the Family Service.
At Kol Hadash our celebration begins outdoors, where we gather in and around our sukkah, sharing stories, singing songs and passing the lulav (bundle of 3 varieties of tree branches) and etrog (citron fruit). Then we move the festivities indoors, with a potluck dinner.
A wonderful celebration of the cycling of the seasons, our connections to the natural world, and a delicious variety of foods. Intended for all ages.
A grand time dressing in costume, playing games, eating delicious hamantaschen (holiday pastries) while celebrating the triumph of good over evil in the biblical tale of Queen Esther. Nominal cost for carnival tickets. Intended for all ages.
See seven different Jewish holidays come alive for your children with stories, songs, and activities led by Rabbi Adam Chalom and Education Director Dawn Friedman. Storytimes are intended for children ages 0-2 (older children welcome) and are held at different local bookstores and other convenient neighborhood locations. All programs are free of charge. Full schedule. For more information on any of these upcoming events, please visit jBaby Chicago, or contact our administrator, Jeremy Owens, at info@KolHadash.com, or 847/383-5184.
All programs are free of charge. Storytimes are sponsored by JBaby Chicago. RSVP for storytime on JUF's website. For more information, contact our administrator, Jeremy Owens, at info@KolHadash.com, or 847/383-5184.


It manufactures a wide range of clamping products ranging from stainless steel cable ties to bands to buckles to marking & identification systems offering a one stop solution to all your clamping requirements.
Copyright © 2008 sannguyenco.com. All rights reserved.


crushing machine plant pdf – Grinding Mill China. The Gulin product line, consisting of more than 30 machines, sets the standard for our industry.
crushing foodstuff machine pdf maize crusher machines manual pdf . manual corn choppers in south africa | Gulin Machinery.
Discover your crusher and grinder machine at ... PDF Center Vibrating Screen. ... Guidance for Industry U S Food and Drug Administration Home … · PDF .
You created this PDF from an application that is not licensed to print to novaPDF printer ... to further improve the designs of small scale stone crushing machines.