text:
\section{Introduction}
\paragraph{Background.}
The most standard way of modeling distributed networks is to use graphs, where vertices and edges respectively correspond to computing entities (e.g., nodes or processes) and communication channels. The graphical structure of networks naturally motivates, both practically and theoretically, the study of graph algorithms, i.e., in-network solving of combinatorial graph problems for the own topology of the network.  In the last twenty years, research on distributed complexity theory has successfully investigated many fundamental graph problems such as independent set~\cite{ABI86,BEPS16}, dominating set~\cite{FR05,KMW16}, coloring~\cite{Linial92,BE13}, minimum spanning trees~\cite{GHS83,Elkin04,Elkin06,GKP93,PR99,LPPP05} shortest paths~\cite{LP13,LP15,Nanongkai14,HW12}, max-flow and min-cut~\cite{GK13,NS14,GKKLP15}.
The seminal textbook by Peleg~\cite{Peleg00} provides a good overview of those achievements.

A high-level perspective on distributed graph algorithms classifies problems into two categories according to their locality characteristics. Problems like minimum spanning trees, shortest paths or max-flow/min-cut mentioned above are classified as global problems because some node must (indirectly) communicate with a node $D$-hop away, where $D$ denotes the diameter of the network, which requires $\Omega(D)$ rounds. Since any problem can be solved within $O(D)$ rounds by a naive centralized approach if the communication bandwidth of each channel is unlimited, technical challenges on global problems appear only in the model of limited-bandwidth channels, the so-called CONGEST communication model where each channel has only $O(\log n)$-bit bandwidth. On the other hand, many local problems, like independent set, dominating set or coloring allow distributed (approximate) solutions within $o(D)$ rounds. Besides the limited bandwidth, a significant difficulty when designing distributed algorithms for local problems often consists in breaking the symmetry between nearby nodes.

\paragraph{Triangle finding.}
Triangle finding is an important counterpart of the perspective explained above. Since the distance-two information for a node $i$ is sufficient to find all triangles around~$i$, it is a purely local task. Aggregating at each node the set of its 2-hop neighbors, however, takes $\Theta(d_{\mathit{max}})$ rounds in the CONGEST model, where $d_{\mathit{max}}$ denotes the maximum degree of the nodes. In the case of dense graphs, such an approach gives linear round complexity. In this sense, despite being a local problem, the underlying difficulty of triangle finding is similar to the difficulty encountered when working with global problems in the CONGEST model, that is, the lack of communication bandwidth. These particularities make triangle finding a difficult problem to handle with current techniques. As summarized in Table~\ref{table:comparison}, recently some non-trivial upper bounds have been obtained by Dolev et al.~\cite{DLP12} and then improved by Censor-Hillel et al.~\cite{CKKLPS15}, but these upper bounds hold only in the much stronger CONGEST clique model (where at each round messages can even be sent between non-adjacent nodes) for which bandwidth management is significantly easier. No nontrivial upper bound is known in the standard CONGEST model.
As far as lower bounds are concerned, the locality of triangle finding rules out many standard approaches used to obtain lower bounds on the complexity of global problems  (e.g., the approaches from \cite{SHKKANPPW12,FHW12}). The only known lower bounds have been obtained recently by Drucker et al.~\cite{DKO14}, but hold only for the much weaker broadcast CONGEST model, where at each round the nodes can broadcast only a single common message to all other nodes, under a (reasonable) conjecture in communication complexity theory. No nontrivial lower bound is known for triangle finding in the standard CONGEST model.

Another, more practical, motivation for considering triangle finding
is that for several graph problems faster algorithms are known over triangle-free graphs (we refer to \cite{Hirvonen+14,Pettie+15} for some examples in the distributed setting). The ability to efficiently check if the network is triangle-free, and more generally detect which part of the network is triangle-free, is essential when considering such algorithms in practice.

\setlength{\extrarowheight}{1.5pt}
\begin{table*}[tb]
 \begin{center}
  \begin{tabular}{cccc}
  \Hline{1.5pt}
   Paper & Time Bound & Problem & Model \\ \Hline{1.5pt}
   \multirow{2}{*}{Dolev et al.~\cite{DLP12}} & $O(n^{1/3}(\log n)^{2/3})$& \multirow{2}{*}{Listing}&\multirow{2}{*}{CONGEST clique}\bigstrut\\
   &$O(d_{\mathit{max}}^{3}/n)$ && \\ \hline
   Censor-Hillel et al.~\cite{CKKLPS15} &

   $O(n^{0.1572})$ & Finding
   & CONGEST clique \bigstrut\\ \hline
   This paper (Theorem \ref{th:UB-finding}) & $O(n^{2/3}(\log n)^{2/3})$ & Finding & CONGEST \bigstrut\\ \hline
   This paper (Theorem \ref{th:UB-listing})& $O(n^{3/4}\log n)$ & Listing & CONGEST \bigstrut\\ \Hline{1.5pt}

   Drucker et al.~\cite{DKO14} &
   $\Omega\big(\frac{n}{e^{\sqrt{\log n}}\log n}\big)$ (conditional)
   & Finding & CONGEST broadcast \bigstrut\\ \hline
   Pandurangan et al.~\cite{Pandurangan+16}& $\Omega(\frac{n^{1/3}}{\log^3 n})$ & Listing & CONGEST clique \bigstrut\\ \hline
   This paper (Theorem \ref{thm:lowerBound})& $\Omega(\frac{n^{1/3}}{\log n})$ & Listing & CONGEST clique \bigstrut\\ \Hline{1.5pt}
  \end{tabular}

   \caption{Prior results on the round complexity of distributed triangle finding and listing and our new results, where $n$ denotes the number of nodes in the network.}
  \label{table:comparison}
 \end{center}
\end{table*}

\paragraph{Technical contribution.}
In this paper, in addition to triangle finding we also consider the triangle listing problem, which requires that each triangle of the network should be output by at least one node (we refer to Section \ref{sec:prelim} for the formal definition). The triangle listing problem can be seen as a special case of motif finding, which is a popular problem in the context of network data analysis. It is obvious that triangle finding is not harder than triangle listing, since finding reduces to listing.
In the literature mentioned above, triangle finding and triangle listing are not explicitly distinguished, but the algorithms by Dolev et al.~\cite{DLP12} are actually for the listing version, while the algorithms by Censor-Hillel et al.~\cite{CKKLPS15} are based on an algebraic approach and only support finding. The lower bound by Drucker et al.~\cite{DKO14} applies to triangle finding.

Our results are summarized in Table~\ref{table:comparison}. Our main contributions are a $O(n^{2/3}(\log n)^{2/3})$-round algorithm for triangle finding and a $O(n^{3/4}\log n)$-round algorithm for triangle listing, both in the CONGEST model. These two algorithms are the first algorithms with sublinear round complexity for triangle finding or listing applicable to the standard CONGEST model. The existence of sublinear-time algorithms shows, from an algorithmic perspective as well, that these two problems are indeed easier than global problems like diameter computation, which has a nearly linear-time lower bound in the CONGEST model~\cite{FHW12}. Interestingly, this result contrasts with the known relations between triangle finding and diameter computation in the centralized setting, in which the best known algorithms for both problems rely on matrix multiplication and have the same complexity.

We also show that there exist networks of $n$ nodes for which any triangle listing algorithm requires $\Omega(n^{1/3}/\log n)$ rounds in the CONGEST model. Actually we show a stronger result: any triangle listing algorithm requires $\Omega(n^{1/3}/\log n)$ rounds even in the CONGEST clique model. This lower bound slightly improves the $\Omega(n^{1/3}/\log^3 n)$-round lower bound for triangle listing in the CONGEST clique model obtained recently by Pandurangan et al.~\cite{Pandurangan+16}. Note that since the algorithm by Dolev et al.~\cite{DLP12} has round complexity $O(n^{1/3}(\log n)^{2/3})$, these lower bounds are tight up to possible polylogarithmic factors in the CONGEST clique model. These lower bounds also have the following interesting consequence. They shows that triangle listing is strictly harder than triangle finding in the CONGEST clique model since, as already mentioned, $(n^{0.1572})$-round algorithms for triangle finding have been shown by Censor-Hillel et al.~\cite{CKKLPS15}. Actually, since the algorithms in~\cite{CKKLPS15} also count the number of triangles, these lower bounds thus even show that triangle listing is harder than counting in this model.

Our lower bound is shown by a simple information-theoretic argument on random graphs. By similar arguments (see Proposition~\ref{cor} in Section~\ref{sec:LB}), we can also show a $\Omega(n/\log n)$-round lower bound for local listing algorithms, where each node~$i$ is required to output all the triangles containing~$i$. This corollary implies that any triangle listing algorithm with sublinear complexity inherently requires some counter-intuitive mechanism that enables a triangle~$t$ to be output by a node not contained in $t$. This is precisely how our $O(n^{3/4}\log n)$-round algorithm works.

\paragraph{Other related works.}
Distributed algorithms for triangle-freeness have recently also been considered in the setting of property testing \cite{Censor-Hillel+DISC16} (see also \cite{Fraigniaud+DISC16}). Note that in property testing the goal is to decide whether either the network is triangle-free or it contains a large number triangles. Since there is no need to consider the case where the network may have only a small number of triangles, this property testing version is significantly easier than the problems studied in the present paper.

Triangle finding is a fundamental problem in the field of centralized algorithms as well.
It has been known for a long time that this problem is not harder than Boolean matrix multiplication~\cite{Itai+SICOMP78}.
A few years ago Vassilevska Williams and Williams showed a converse reduction~\cite{Williams+FOCS10}: they proved that a subcubic-time algorithm for triangle finding can be used, in a combinatorial way, to construct a subcubic-time algorithm for Boolean matrix multiplication. This result, combined with recent developments \cite{Bansal+ToC12,Czumaj+SICOMP09,PatrascuSTOC10,Vassilevska+SICOMP13}, have put triangle finding as a central problem in the recent theory of fine-grained complexity.

\section{Preliminaries}\label{sec:prelim}
In this paper we consider undirected graphs. We will use $G = (V, E)$ to denote the graph considered, and write $n=|V|$ and $m=|E|$. In this section we present some of our notations, give details of our model and present some facts about hashing functions that will be used in Section \ref{sec:UB}.\vspace{-2mm}

\paragraph{Graph-theoretic notations.}
 For any vertex $i\in V$, we denote $\mathcal{N}(i)$ the set of neighbors of $i$. For any finite set $X$, we will use the notation $\mathcal{E}(X)$ to represent the set of unordered pairs of elements in~$X$, and use $\mathcal{T}(X)$ to represent the set of unordered triples of elements in~$X$. We will write $\mathcal{E}=\mathcal{E}(V)$ and $\mathcal{T}=\mathcal{T}(V)$.
Given a pair of vertices $\{j,k\}\in\mathcal{E}$, we write
\[
\multri{\{j,k\}}=
\Big|\left\{
l\in V\:|\:
\{j,l\}\in E \textrm{ and } \{k,l\}\in E
\right\}\Big|.
\]
Given $t = \{j,k,l\} \in \mathcal{T}$, and $e \in \mathcal{E}$, we will write
$e \in t$ when $e = \{j, k\}$, $e = \{j, l\}$, or $e = \{k, l\}$.  For any $R \subseteq \mathcal{T}$, we denote by $\mathcal{P}(R)\subseteq E$ the set of edges $e\in E$ such that $e\in t$  for some triple $t \in R$.

We define a triangle $t = \{j, k, l\}\in \mathcal{T}$ to be an unordered triple of vertices where any pair corresponds to an edge in $E$. Note that if $e$ is an edge of the graph, then $\multri{e}$ represents the number of triangles containing $e$. We write $T(G)$ the set of all triangles contained in graph $G$.

\vspace{-2mm}

\paragraph{Communication Model.}
In the paper we mainly consider the CONGEST communication model. The graph
$G = (V, E)$ represents the topology of the network, executions proceed with round-based synchrony and each node can transfer one $O(\log n)$-bit message to each adjacent node per round. All links and nodes (corresponding to the edges and vertices of $G$, respectively) are reliable and suffers no faults. Each node has a distinct identifier from a domain $\Ii$. For simplicity we will assume
$\Ii=V = [0, n-1]$, but this assumption is not essential and easy to remove as long as $|\Ii| = \mathrm{poly}(n)$. It is also assumed that each node can access infinite sequence of local random bits, that is, the algorithm can be randomized. Initially, each node knows nothing about the topology of the network except the set of edges incident to itself and the value of $n$. All our upper bounds given in Section~\ref{sec:UB} hold for the CONGEST model.

The CONGEST clique model is a powerful variant of the CONGEST model. It allows an algorithm to transfer a $O(\log n)$-bit message per round between any two nodes not necessarily adjacent in~$G$ at each round. This means that in this model the communication topology is the complete graph on the $n$ nodes, and the graph~$G$ only takes the role of input instances to the algorithm. Except for the communication topology, all other features are common with the CONGEST model described in the above paragraph. The CONGEST clique model will be considered only in Section~\ref{sec:LB} when proving our lower bound (note that a lower bound for this model immediately holds for the CONGEST model as well).

\vspace{-2mm}

\paragraph{Triangle finding and listing in the CONGEST model.}
In the triangle finding problem, at least one node must output a triangle if $T(G)$ is not empty, or all the nodes must output ``not found'' otherwise. In the triangle listing problem, the goal is that for each triangle in $T(G)$ at least one node in $V$ outputs it.

Formally, we describe the output of an algorithm for triangle finding or listing by an $n$-tuple $T = (T_0, T_1, \dots, T_{n-1})$, where  $T_i \subseteq T(G)$ is the output by node $i$. The algorithm can be deterministic or randomized. In the latter case, note that the condition on the $T_i$'s implies that any triple output at a node should corresponds to a triangle of $G$, and thus the algorithm should be one-sided error. Note also that we do not require that the $T_i$'s are mutually disjoint. We often use notation $T$ as the union of~$T_i$  over all nodes if there is no ambiguity. We say that the algorithm solves the triangle finding problem if its output $T$ satisfies $T\cap T(G)\neq \emptyset$. We say that it solves the triangle listing problem if $T=T(G)$.  \vspace{-2mm}

\paragraph{Hash functions.}

Let $\mathcal{X}$  and $\mathcal{Y}$ be two finite sets.
For any integer $s\ge 1$, a family of hash functions $\Hh = \{h_1, h_2, \dots, h_p\}$, where each $h_i$ is a function from $\mathcal{X}$ to $\mathcal{Y}$, is called \emph{s-wise independent} if for any distinct
$x_1, x_2, \dots, x_s \in \mathcal{X}$ and any $y_1, y_2, \dots y_s
\in \mathcal{Y}$, a function $h$ sampled from
$\Hh$ uniformly at random satisfies $\Pr[\bigwedge_{1 \leq i \leq s} h(x_i)
= y_i] = 1 / |\mathcal{Y}|^s$.
We will use the following lemma, which follows almost immediately from the definition of $s$-wise independence.

\begin{lemma}\label{l:hashfunction}
Let $\Hh$ be any $3$-wise independent family of hash functions from $\mathcal{X}$ to $\mathcal{Y}$, and $h$ be a function sampled from
$\Hh$ uniformly at random. Let $H(y) = \{x'' \in \mathcal{X}\:|\:h(x'')=y\}$.
For any triple $(x,x',y)\in \mathcal{X}\times \mathcal{X}\times \mathcal{Y}$
we have
\[
\Pr\left[h(x)=h(x')=y \bigwedge
\Big|H(y)\Big| \leq 4\left(2 + \frac{|\mathcal{X}| - 2}{|\mathcal{Y}|}\right)\right] \geq \frac{3}{4|\mathcal{Y}|^2}.
\]
\end{lemma}

\begin{proof}
Let us write $Z=\{x''\in \mathcal{X}\:|\:h(x'')=y\}$. For any $a\in \mathcal{X}$, let $Z_{a}$ be the indicator random variable corresponding to the event $a \in Z$. By the 3-wise independence property of $h$, we have
\begin{align*}
\lefteqn{E\Big[|Z|\:|\:Z_x=Z_{x'}=1\Big]} \hspace{10mm} \\
&= 2+\sum_{a \in \mathcal{X} \setminus \{x, {x'}\}} E[Z_a\:|\:Z_x=Z_{x'}=1] \\
&= 2+\frac{|\mathcal{X}| - 2}{|\mathcal{Y}|}.
\end{align*}
By Markov's
inequality, we have
\begin{align*}
\Pr
\left[
|Z| > 4\left(2+\frac{|\mathcal{X}| - 2}{|\mathcal{Y}|}\right) \ \middle| \  Z_{x}=Z_{{x'}}=1
\right]
&\leq \frac{1}{4}.
\end{align*}
Since $\Pr[Z_x = Z_{x'} = 1] = 1/|\mathcal{Y}|^2$ holds, we obtain
\begin{align*}
\lefteqn{\Pr\left[Z_x = Z_{x'} = 1 \bigwedge |Z| \le 4\left(2+\frac{|\mathcal{X}| - 2}{|\mathcal{Y}|}\right)\right]} \hspace{10mm} \\
&= \Pr\left[|Z| \le 4\left(2+\frac{|\mathcal{X}| - 2}{|\mathcal{Y}|}\right) \middle| Z_x = Z_{x'} = 1 \right] \\
& \hspace{40mm} \times
\Pr[Z_x = Z_{x'} = 1] \\
&\ge
\frac{3}{4} \times \frac{1}{|\mathcal{Y}|^2},
\end{align*}
as claimed.
\end{proof}

Note that using the standard construction by Wegman and Carter \cite{WC81} we can encode $k$-wise independent hash functions using only $O(k\log |\mathcal{Y}|)$ bits.

\section{Upper Bounds}\label{sec:UB}
In this section we prove the following two theorems.
\begin{theorem}\label{th:UB-finding}
Let $\delta>0$ be any constant.
In the CONGEST model there exists a randomized algorithm for triangle finding with round complexity $O(n^{2/3}(\log n)^{2/3})$, where $n$ denotes the size of the network, and success probability at least $1-\delta$.
\end{theorem}
\begin{theorem}\label{th:UB-listing}
In the CONGEST model there exists a randomized algorithm for triangle listing with round complexity $O(n^{3/4}\log n)$ and success probability at least $1-1/n$, where $n$ denotes the size of the network.
\end{theorem}
Theorems \ref{th:UB-finding} and \ref{th:UB-listing} follow from three algorithms described in Propositions \ref{prop:tri-heavy-finding}--\ref{prop:tri-light} below, which rely on the following concept of heavy triangles. Let $\varepsilon$ be any real number such that $0\le \varepsilon\le 1$.  We say that a triangle $t \in T(G)$ is \emph{$\varepsilon$-heavy} if there exists an edge $e \in t$ such that
$\multri{e} \geq n^{\varepsilon}$. We define $\trih{\varepsilon} \subseteq T(G)$ as
the set of all $\varepsilon$-heavy triangles in $T(G)$. The first proposition is almost trivial, and
shows how to find an $\varepsilon$-heavy triangle by a straightforward sampling strategy:
\begin{proposition}\label{prop:tri-heavy-finding}
There exists a $O(n^{1-\varepsilon})$-round randomized algorithm $\Aa_1$  returning a set $T\subseteq T(G)$ such that, if $\trih{\varepsilon}\neq \emptyset$, then $T\cap\trih{\varepsilon}\ \neq \emptyset$ with probability $\Omega(1)$.
\end{proposition}
\begin{proof}
Algorithm $\Aa_1$ is as follows: First, each node $j\in V$ constructs a random set $S_j\subseteq\mathcal{N}(j)$ by including in $S_j$ each element of $\mathcal{N}(j)$ with probability $n^{-\varepsilon}$.  If $|S_j|> 4n^{1-\varepsilon}$, node $j$ then does not send anything to its neighbors. Otherwise (i.e., if $|S_j|\le 4n^{1-\varepsilon}$), node $j$ then sends $S_j$ to each neighbor $k\in\mathcal{N}(j)$, and each such neighbor~$k$ checks if there is a triangle containing $j$, $k$ and a third node in $S_j$, which can be done by computing locally the set $\mathcal{N}(k)\cap S_j$.

Observe that if $\trih{\varepsilon}\neq \emptyset$ then at least one $\varepsilon$-heavy triangle will be found with constant probability. Indeed, for each edge $\{j,k\}\in E$ such that $\multri{\{j,k\}}\ge n^\varepsilon$, with constant probability at least one node adjacent to both $j$ and~$k$ is included in $S_j$, and $S_j$ is small enough.
\end{proof}
The second proposition is about finding each $\varepsilon$-heavy triangle:
\begin{proposition}\label{prop:tri-heavy}
There exists a $O(n^{1-\varepsilon/2})$-round randomized algorithm $\Aa_2$ returning a set $T\subseteq T(G)$ such that, for any triangle $t\in \trih{\varepsilon}$, this set $T$ contains $t$ with probability $\Omega(1)$.
\end{proposition}
The third proposition is about finding each triangle that is not  $\varepsilon$-heavy:
\begin{proposition}\label{prop:tri-light}
There exists a $O(n^{1-\varepsilon}+n^{(1+\varepsilon)/2}\log n)$-round randomized algorithm $\Aa_3$ returning a set $T\subseteq T(G)$ such that, for any triangle $t\in T(G)\setminus\trih{\varepsilon}$, this set~$T$ contains $t$ with probability $\Omega(1)$.
\end{proposition}

Proposition \ref{prop:tri-heavy} and especially Proposition \ref{prop:tri-light} are the main technical contributions of this section. Their proofs are given in Subsections \ref{sub:heavy} and \ref{sub:light}, respectively.

We now explain how Theorems \ref{th:UB-finding} and \ref{th:UB-listing} immediately follow from these three propositions.
\begin{proof}[Proof of Theorem \ref{th:UB-finding}]
The triangle finding algorithm simply applies Algorithm $\Aa_1$ and then Algorithm $\Aa_3$.
From Propositions \ref{prop:tri-heavy-finding} and \ref{prop:tri-light} we know that a triangle will thus be found with at least constant probability (if $G$ contains a triangle). For any constant $\delta$ the success probability can be amplified to $1-\delta$ by repeating this process $c$ times for a large enough constant~$c$.

The round complexity of this algorithm is
$
O(n^{1-\varepsilon} + n^{1-\varepsilon} + \allowbreak n^{(1+\varepsilon)/2}\log n).
$
Choosing $\varepsilon$ such that $n^\varepsilon =\frac{n^{1/3}}{(\log n)^{2/3}}$ gives the claimed upper bound.
\end{proof}

\begin{proof}[Proof of Theorem \ref{th:UB-listing}]
The triangle listing algorithm repeats $\ceil{c \log n}$ times the following process (here $c$ is a large constant): apply Algorithm $\Aa_2$ and then Algorithm $\Aa_3$.

We now show that this algorithm lists all the triangles of $G$. Let $t$ be a triangle in $T(G)$. From Propositions \ref{prop:tri-heavy} and \ref{prop:tri-light} we know that $t$ is found with at least constant probability at each step. If~$c$ is large enough, repeating this process $\ceil{c\log n}$ times guarantees that $t$ is found with probability at least $1-1/n^4$. From the union bound, we can conclude that all triangles are found with probability at least $1-1/n$.

The round complexity of this algorithm is
$
O(((n^{1-\varepsilon/2} + n^{1-\varepsilon} \allowbreak + n^{(1+\varepsilon)/2}\log n)\log n).
$
Choosing~$\varepsilon$ such that $n^\varepsilon =\frac{n^{1/2}}{(\log n)^{2}}$ gives the claimed upper bound.
\end{proof}

\subsection{Listing all $\varepsilon$-heavy triangles: Proof of Proposition \ref{prop:tri-heavy}}\label{sub:heavy}
The goal of this subsection is to prove Proposition \ref{prop:tri-heavy}.

The main idea to find $\varepsilon$-heavy triangles is that each node $j$ will decide which information about $\mathcal{N}(j)$ it will send to each neighbor $a$ according to a hash function $h_a$ generated by $a$. More precisely, the function $h_a$ will be taken (by node $a$, and then distributed to all its neighbors) from a 3-wise independent family $\Hh$ of hash functions from~$V$ to $\{0,1,\ldots,\lfloor n^{\varepsilon/2}\rfloor-1\}$, and $j$ will send an edge $\{j,l\}$ to $a$ if $h_a(l)=0$. The complete algorithm, which is Algorithm $\Aa_2$ claimed in Proposition~\ref{prop:tri-heavy}, is described in Figure \ref{fig:algorithmheavylisting} and analyzed below.

\begin{figure*}[ht]
\begin{center}
\fbox{
\begin{minipage}{15 cm}
\begin{itemize}
\item[1.]
Each node $i\in V$ chooses a function $h_i\colon V\to\{0,1,\ldots,\lfloor n^{\varepsilon/2}\rfloor-1\}$ uniformly at random from a 3-wise independent family  $\Hh$ of hash functions, and sends $h_i$ to all the nodes
in $\mathcal{N}(i)$.
\item[2.]
Each node $j\in V$ locally computes, for each node $a\in \mathcal{N}(j)$, the set of edges
$E^j_a = \{\{j,l\}\in E \:|\: h_a(l) = 0\}$ and then sends $E^j_a$ to $a$ if $|E^j_a| \leq 8+\frac{4n}{\lfloor n^{\varepsilon/2}\rfloor}$.
\item[3.]For any node $i\in V$, let $F_i$ be the set of edges received by $i$ at the first step. Node $i$
outputs all triples $\{j, k, l\}$ satisfying $\{j,k\}, \{j, l\}, \{k, l\} \in F_i$.
\end{itemize}
\end{minipage}
}
\end{center}
\caption{Algorithm $\Aa_2$ finding any $\varepsilon$-heavy triangle in $O(n^{1 - \varepsilon/2})$ rounds.}
\label{fig:algorithmheavylisting}
\end{figure*}

We first prove the correctness of Algorithm $\Aa_2$.
Let $t = \{j, k, l\}$ be any $\varepsilon$-heavy triangle of~$G$. Let $\{j, k\}$ be the edge shared by at least $n^{\varepsilon}$ triangles and $A$ be the set of nodes such that $\{j, k, a\}$ forms a triangle for each $a \in A$. Consider the function $h_a\in\mathcal{H}$ chosen by node $a$. Applying Lemma~\ref{l:hashfunction} with $|\mathcal{X}|=n$ and $|\mathcal{Y}|=\lfloor n^{\varepsilon/2}\rfloor$,
we obtain the inequality
\[
\Pr\left[h_a(k)=h_a(l)=0  \bigwedge |E_a^j\cup E_a^k|\leq 8+\frac{4n}{\lfloor n^{\varepsilon/2}\rfloor}\right] \geq
\frac{3}{4n^{\varepsilon}}.
\]
This bound implies that with probability at least $\frac{3}{4n^{\varepsilon}}$ node $a$ receives $\{j,k\}$ from~$j$, $\{j,l\}$ from~$j$ and $\{k,l\}$ from~$k$ at Step 2, and thus
$T_a$ (i.e., the output of node $a$) includes $t$ with the same probability.
Since the events $t \not\in T_a$ are mutually independent
over all $a \in A$, we can bound the probability that no node in $A$ finds
$t$ as follows:
\[
\Pr\left[\bigcap_{a \in A} t \not\in T_a\right]
\leq \left(1 - \frac{3}{4n^{\varepsilon}}\right)^{|A|}
\leq \left(1 - \frac{3}{4n^{\varepsilon}}\right)^{n^{\varepsilon}}
\leq e^{-\Omega(1)}.
\]

The round complexity of Algorithm $\Aa_2$ is $O(n^{1-\varepsilon/2})$ since the hash function $h_i$ sent at Step 1 can be encoded using $O(\log n)$ bits, as explained in Section \ref{sec:prelim}.

This concludes the analysis of Algorithm $\Aa_2$ and the proof of Proposition~\ref{prop:tri-heavy}.
\subsection{Finding triangles that are not heavy: Proof of Proposition \ref{prop:tri-light}}\label{sub:light}
The goal of this subsection is to prove Proposition \ref{prop:tri-light}. We first give a brief description of the main ideas underlying our algorithm before giving the full description of Algorithm $\Aa_3$.

\paragraph{Key definition and outline of our approach.}
For any set $X\subseteq V$, define the set
\[
\Delta(\X)=\mathcal{E}(V)\setminus \bigcup_{x\in X}\mathcal{E}(\mathcal{N}(x)),
\]
which is the set of pairs of nodes that do not have a common neighbor in $X$. The following easy lemma shows how the set $\Delta(\X)$ is related to finding triangles which are not $\varepsilon$-heavy.
\begin{lemma}\label{lma:not-heavy-1}
Let $\varepsilon$ be any real number such that $0\le\varepsilon\le 1$.  Suppose that $X$ is a set obtained by including each node of $V$ into $X$ with probability $\frac{1}{9n^\varepsilon}$. Then, for any triangle $t\in T(G)\setminus\trih{\varepsilon}$, the three edges of $t$ are in $\Delta(\X)$ with probability at least $2/3$.
\end{lemma}
\begin{proof}
Let us consider any triangle $t\in T(G)\setminus\trih{\varepsilon}$. For each edge $e\in t$ we have $\multri{e}< n^\varepsilon$. From the union bound, we obtain the inequality
$
\Pr_X\left[
e\in
\bigcup_{x\in X}\mathcal{E}(\mathcal{N}(x))
\right]<
\frac{1}{9}.
$
Thus, again from the union bound, $t$ has its three edges in $\Delta(\X)$ with probability at least $2/3$.
\end{proof}
In view of Lemma~\ref{lma:not-heavy-1}, our strategy will be to take a set $X$ as in the lemma and then find the triangles with three edges in $\Delta(\X)$ using the following approach: Each node $i\in V$ sends to all its neighbors the set $\mathcal{N}(i)\cap X$, in $O(|X|)$ rounds. Then each node $k\in V$ constructs for each $j\in \mathcal{N}(k)$ the set containing all nodes $l\in \mathcal{N}(k)$ such that $\{j,l\}\in\Delta(\X)$, which can be done locally. Let us call this set $\mathcal{S}(j,k)$ for now -- later it will be called $\mathcal{S}_V^X(j,k)$. Node $k$ then sends $\mathcal{S}(j,k)$ to neighbor~$j$, who can report all triangles of the form $\{j,k,l\}$ with $\{j,l\}\in \Delta(\X)$.

This approach works, but its round complexity depends on the size of the sets $\mathcal{S}(j,k)$. The crucial point is that we can show from a combinatorial argument that with high probability (on the choice of~$X$) the average size of these sets is small. The main remaining issue is that, even if the average size is small, in general there exist pairs $(j,k)$ for which $\mathcal{S}(j,k)$ is large. We solve this issue by sending $\mathcal{S}(j,k)$ only when its size is close to the average and using a different strategy when its size exceeds the average. This latter strategy is based on a notion of ``good'' nodes. Roughly speaking, a node $j$ is good if it has only a small number of neighbors $k$ such that $\mathcal{S}(j,k)$ is large (see Definition~\ref{def} for the formal definition). The same combinatorial argument as above guarantees that most nodes are good (this is shown in Lemma \ref{lma:not-heavy-2} below).  Triangles containing at least one good node are fairly easy to deal with, and we can deal with triangle containing three bad nodes by applying the same approach recursively on the subgraph induced by the bad nodes. Our final algorithm will thus be recursive: it will keep a set $U\subseteq V$, with initially $U=V$, and successively search for triangles in the subgraph of $G$ induced by $U$, removing the good nodes from $U$ at each step, until $U=\emptyset$.

\paragraph{Further definitions and full description of Algorithm $\Aa_3$.}
For any set $U\subseteq V$ and
any nodes $j,k\in U$ such that $\{j,k\}\in E$, we define the set $\myS{j,k}\subseteq U$
as follows:
\begin{align*}
\myS{j,k}&=
\Big\{l\in U\:|\:  \{j,l\}\in \Delta(\X) \textrm { and } \{k,l\}\in E\Big\}.
\end{align*}
Note that this definition is asymmetric: we have $\myS{j,k}\neq \myS{k,j}$ in general.
Let $\m$ be any positive real number. For any node $j\in U$, we define the set
\[
\myT{j}=
\big\{
k\in U\:|\:
\{j,k\}\in E
\textrm{ and }
\left|
\myS{j,k}
\right|
>
\m
\big\}.
\]
Finally, we will use the following concept of good nodes.
\begin{definition}\label{def}
Let $U$ and $X$ be any subsets of $V$, and
$\m$ be any positive real number.
A node $j\in U$ is $\m$-good for $(U,X)$ if
$
\big|
\myT{j}
\big|
\le \m.
$
\end{definition}

The following crucial lemma shows an upper bound on the number of nodes which are not good, when $X$ is chosen as in Lemma~\ref{lma:not-heavy-1}.

\begin{lemma}\label{lma:not-heavy-2}
Let $\varepsilon$ be any real number such that $0\le\varepsilon\le 1$  and $X$ be a set chosen at random as in Lemma \ref{lma:not-heavy-1}.
Then, for any real number $\m\ge \sqrt{54n^{1+\varepsilon}\log n}$, the following statement holds with probability at least $1-1/n$:
\begin{equation} \label{eq1}
\parbox{75mm}{
For any set $U\subseteq V$ there are at most $|U|/2$ nodes in $U$  that are not $\m$-good for $(U,X)$. }
\end{equation}

\end{lemma}

\begin{proof}
Consider any pair $\{j,l\}\in\mathcal{E}$ such that
\[
\multri{\{j,l\}}\ge 27n^\varepsilon\log n.
\]
We have
\[
\Pr_X\left[
\{j,l\}\notin
\bigcup_{x\in X}\mathcal{E}(\mathcal{N}(x))
\right]\le
\left(1-\frac{1}{9n^\varepsilon}\right)^{27n^\varepsilon\log n}
\le
\frac{1}{n^3}.
\]
From the union bound we can thus conclude that with probability at least $1-1/n$ the following statement holds:
\begin{equation}\label{eq1b}
\multri{\{j,l\}}
<  27n^\varepsilon\log n
\textrm{
for any pair $\{j,l\}\in \Delta(\X)$.
}
\end{equation}

We now show that Statement (\ref{eq1b}) implies Statement (\ref{eq1}).
Let us consider the number of ordered triples $(j,k,l)\in U\times U\times U$ such that $\{j,l\}\in \Delta(\X)$, $\{j,k\}\in E$ and $\{k,l\}\in E$. If Statement~(\ref{eq1b}) holds then this number is at most $27|U|^2n^\varepsilon \log n$.
This number of triples can also be computed in another way: it is equal to
\[
\sum_{\begin{subarray}{c}(j,k)\in U\times U\\\textrm{s.t. } \{j,k\}\in E\end{subarray}}\left|\myS{j,k}\right|.
\]
Thus if Statement~(\ref{eq1b}) holds we obtain the inequality
\[
27|U|^2n^\varepsilon \log n\ge \sum_{\begin{subarray}{c}(j,k)\in U\times U\\\textrm{s.t. } \{j,k\}\in E\end{subarray}}\left|\myS{j,k}\right|
\ge \sum_{j\in U} \left|\myT{j}\right|\m,
\]
which implies that the number of nodes that are not $\m$-good for $(U,X)$ is at most
\[
27|U|^2n^\varepsilon \log n\times \frac{1}{\m^2}\le  \frac{27|U|n^{1+\varepsilon} \log n}{\m^2}.
\]
For any $\m\ge \sqrt{54n^{1+\varepsilon}\log n}$ we obtain the claimed upper bound.
\end{proof}

We now present an algorithm that lists all triangles of $G$ with three edges in $\Delta(\X)$. The algorithm is denoted $\Aa(X,\m)$ and described in Figure \ref{fig:algorithm}. We analyze it in the next proposition.

\begin{figure*}[ht]
\begin{center}
\fbox{
\begin{minipage}{15 cm}
\begin{itemize}
\item[1.]
Each node tells all its neighbors whether it is in $X$ or not.
\item[2.]
Each node $k\in V$ sends the set $\mathcal{N}(k)\cap X$ to all its neighbors.
\item[3.]
$U\gets V$.
\item[4.]
While $U\neq\emptyset$ do:
\begin{itemize}
\item[4.1]
Each node $k\in U$ sends the set $\myS{j,k}$ to each neighbor $j\in \mathcal{N}(k)\cap U$ for which $|\myS{j,k}|\le \m$. Each such neighbor $j$ then lists all triangles containing $j,k$ and a third node in $\myS{j,k}$, by locally computing the set $\myS{j,k}\cap \mathcal{N}(j)$.
\item[4.2]
Each node $k\in U$ decides whether itself is $\m$-good for $(U,X)$ or not.
Let $U'\subseteq U$ denote the set of nodes that are $\m$-good for $(U,X)$.
\item[4.3]
Each node $j\in U'$ of the network sends the set $\myT{j}$ to each neighbor $l\in\mathcal{N}(j)\cap U$. Each such neighbor $l$ then lists all triangles containing $j$, $l$ and a third node in $\myT{j}$, by locally computing the set $\myT{j}\cap\mathcal{N}(l)$.
\item[4.4]
$U\gets U\setminus U'$.
\item[4.5]
Each node tells all its neighbors whether it is in $U$ or not.
\end{itemize}
\end{itemize}
\end{minipage}
}
\end{center}
\caption{Algorithm $\Aa(X,\m)$ that lists all triangles in $G$ with three edges in $\Delta(\X)$. Here $X$ and~$\m$ are parameters of the algorithm: $X$ is a subset of nodes and $\m$ is a positive real number. The set~$X$ is given as follows: each node $i\in V$ knows whether $i\in X$ or not. The number $\m$ is given to each node.}\label{fig:algorithm}
\end{figure*}

\begin{proposition}\label{prop:tri-delta}
Assume that the set $X$ satisfies Statement (\ref{eq1}).
Then Algorithm $\Aa(X,\m)$ terminates after $O(\log n)$ iterations of the while loop, has overall round complexity $O(|X|+\m\log n)$, and its output $T\subseteq T(G)$ includes all the triangles of $G$ with three edges in $\Delta(\X)$.
\end{proposition}
\begin{proof}
Let us first show that Algorithm $\Aa(X,\m)$ terminates after $O(\log n)$ iterations of the while loop. The assumption on the set $X$ implies that
$
|U\setminus U'|\le |U|/2
$
at Step 4.2 of each iteration of the while loop.
Since we start with $|U| = n$, after at most $\log_2(n)+1$ iterations of the while loop the set $U$ becomes empty, at which point we exit the while loop.

We now analyze the overall round complexity of the algorithm by considering the complexity of each step.  Step~1 requires only one round. Note that after Step~1 each node $k$ can locally compute the set  $\mathcal{N}(k)\cap X$.
Step~2 can then be implemented using at most $|X|$ rounds, since $|\mathcal{N}(k)\cap X|\le |X|$. Step~4.1 can be implemented using at most $\m$ rounds.
Step~4.2 does not require any communication since the enough information has been obtained at~Step 4.1 to compute $\myT{k}$ locally. Step~4.3 only requires at most $\m$ rounds, since $|\myT{j}|\le \m$ for any $j\in U'$.
Finally, Step~4.5 obviously requires only one round. The overall round complexity is thus at most
\[
|X|+1+(\log_2(n)+1)(\m+\m+1)= O(|X|+\m\log n).
\]

We finally show that the algorithm lists all triangles of $G$ with three edges in $\Delta(\X)$.
First observe that for any set $U\subseteq V$, any triangle of $G$ with three nodes in $U$ and three edges in $\Delta(\X)$ satisfies at least one of the following three properties (where $U'\subseteq U$ denotes the set of nodes that are $\m$-good for $(U,X)$):
\begin{itemize}
\item[(a)]
it contains three distinct nodes $j,k,l\in U$ such that
$\left|\myS{j,k}
\right|
\le
\m$ and $l\in \myS{j,k}$;
\item[(b)]
it contains two distinct nodes $j,k\in U$ such that $j\in U'$ and $k \in\myT{j}$;\item[(c)]
all its three nodes are in $U\setminus U'$.
\end{itemize}
Indeed, if such a triangle does not satisfy Property~(a) then the inequality $|\myS{j,k}|>\m$ holds for any two nodes~$j$ and~$k$ of the triangle (which means that $k\in\myT{j}$). In that case it should satisfy either Property~(b) or Property~(c).

Algorithm $\Aa(X,\m)$ starts with $U=V$ and decreases the set $U$ until it is empty. Let us consider what happens at each execution of the while loop, with the current set $U$.
All triangles of type~(a) are found at Step 4.1 and all triangles of type~(b) are found at Step~4.3. The only remaining triangles are triangles of type~(c). They are considered at the next execution of the while loop, where $U$ is replaced by $U\setminus U'$.
\end{proof}

We are now ready to present Algorithm $\Aa_3$ and give the proof of Proposition \ref{prop:tri-light}.
\begin{proof}[Proof of Proposition \ref{prop:tri-light}]
Algorithm $\Aa_3$ is as follows. First each node selects itself with probability $\frac{1}{9n^{\varepsilon}}$. Then the nodes run Algorithm $\Aa(X,\m)$ with $X$ being the set of selected nodes (note that each node $i$ of the network knows whether $i\in X$ or not, as required) and $\m=\sqrt{54n^{1+\varepsilon}\log n}$, but stop as soon as the round complexity exceeds $c\times (n^{1-\varepsilon}+n^{(1+\varepsilon)/2}\log n)$ for some large enough constant~$c$.

By construction, the round complexity of  Algorithm $\Aa_3$ is
\[O(n^{1-\varepsilon}+n^{(1+\varepsilon)/2}\log n).\]

Let $t$ be any triangle in $T(G)\setminus\trih{\varepsilon}$, and let us show that Algorithm $\Aa_3$ finds $t$ with constant probability.
Note that the expectation of the value $|X|$ is $\frac{1}{9}n^{1-\varepsilon}$. By Chernoff bound, we know that the probability that $|X|> \frac{2}{9}n^{1-\varepsilon}$ is negligible.
Combining this observation with Lemmas~\ref{lma:not-heavy-1} and~\ref{lma:not-heavy-2}, we conclude (using the union bound) that with probability $\Omega(1)$ the following three conditions hold: $X$ has size at most $\frac{2}{9}n^{1-\varepsilon}$, $X$ satisfies Statement~(\ref{eq1}), and $t$ has its three edges in $\Delta(\X)$. From Proposition~\ref{prop:tri-delta} we know that in this case algorithm $\Aa(X,\m)$ stops within $O(n^{1-\varepsilon}+n^{(1+\varepsilon)/2}\log n)$ rounds and finds~$t$. By choosing the constant $c$ large enough we can thus guarantee that the output of Algorithm $\Aa_3$ contains the triangle $t$ with probability $\Omega(1)$.
\end{proof}

\section{Lower Bounds}\label{sec:LB}
This section proves the following lower-bound theorem.

\begin{theorem} \label{thm:lowerBound}
Let $\mathcal{A}$ be any triangle listing algorithm with error probability less than $1/32$. Then there exists a probability distribution on inputs such that the expected round complexity of $\mathcal{A}$ is~$\Omega(n^{1/3}/\log n)$.
\end{theorem}

In this section we will write $V=\{0,1,\ldots,n-1\}$.
Without loss of generality, the run of any algorithm $\mathcal{A}$ for triangle listing on any given instance $G = (V, E)$ can be described by two following steps:
\begin{enumerate}
\item
Each node $i$ locally constructs its initial state $\vecb{\rho}_i$ according to $G$. This state depends on the set of edges incident to $i$, but is independent of all other edges.
\item
Each node $i$ construct its output $\vecb{T}_i$ from $\vecb{\rho}_i$ and the transcript $\vecb{\pi}_i$ of the communication received it receives during the execution of the algorithm.
\end{enumerate}

To prove Theorem~\ref{thm:lowerBound}, we consider as input the random graph $G(n, 1/2)$, which is the graph on~$n$ nodes where each pair of nodes is independently taken as an edge with probability $1/2$. Since $\vecb{\rho}_i$, $\vecb{\pi}_i$, and $\vecb{T}_i$ depend only on the algorithm $\mathcal{A}$ (and its random bits if $\mathcal{A}$ is randomized) and the input $G$, we see all of them as random variables. For any pair $\{j,k\}\in \mathcal{E}$, let $\vecb{e}_{\{j,k\}}$ be the random variable with value 1 if $\{j,k\}$ is an edge, and value 0 otherwise. Let $\vecb{E}=(\vecb{e}_{\{0,1\}}, \vecb{e}_{\{0,2\}}, \dots, \vecb{e}_{\{n-2,n-1\}})$ be the concatenation of these $|\mathcal{E}|$ random variables. The proof idea is to bound the amount of information in $\vecb{\pi}_i$ necessary to construct $\vecb{T}_i$ locally. We write $\vecb{T}=(\vecb{T}_0,\vecb{T}_1,\ldots,\vecb{T}_{n-1})$ and use the notation $w(\vecb{T})$ to represent the node identifier $i$ such that $|T_i|$ is maximum (i.e., the index of the node that outputs the maximum number of triangles).

Our proof relies on the following graph-theoretic lemma, which is shown
in~\cite{Rivin02}.

\begin{lemma} \label{lma:triangleEdge}
If a graph $G$ contains $t$ triangles, then $G$ has at least
$\frac{\sqrt{2}}{3}t^{2/3}$ edges.
\end{lemma}

We first recall the definition of the entropy. For a random variable $\vecb{X}$ with domain $\mathcal{X}$ and probability distribution $p$, its entropy $H(\vecb{X})$ is defined as $H(\vecb{X}) = - \sum_{x \in \mathcal{X}} p(x)\log p(x)$. The conditional entropy can be defined similarly. For any random variables $\vecb{X}$ and $\vecb{Y}$ the mutual information of $\vecb{X}$ and $\vecb{Y}$ is defined as $I(\vecb{X}; \vecb{Y}) = H(\vecb{X})-H(\vecb{X}|\vecb{Y})$. We will use in our proofs the following standard results from information theory about the mutual information.
\begin{fact} \label{fact:mutualInfo}
For any random variables $\vecb{X}$, $\vecb{Y}$, and $\vecb{Z}$, the following three
properties hold:
\begin{itemize}
\item $I(\vecb{X}; \vecb{Y}) = I(\vecb{Y}; \vecb{X})$,
\item $I(\vecb{X}; \vecb{Y}) \leq H(\vecb{X})$ (and $I(\vecb{X}; \vecb{Y}) \leq H(\vecb{Y})$), and
\item $I(\vecb{X}; \vecb{Y}) \geq I(\vecb{X}; (\vecb{Y}, \vecb{Z})) -
I( \vecb{X}; \vecb{Z})$.
\end{itemize}
\end{fact}

\begin{fact}[Data Processing Inequality] \label{fact:DataProcessing}
For any three random variables $\vecb{X}, \vecb{Y}, \vecb{Z}$ such that $\vecb{X}$
and $\vecb{Z}$ are conditionally independent given $\vecb{Y}$, $I(\vecb{X}; \vecb{Y})
\geq I(\vecb{X}; \vecb{Z})$.
\end{fact}

The key technical ingredient of our proof is the following lemma
(the notation $\mathcal{P}$ is defined in Section \ref{sec:prelim}).
\begin{lemma} \label{lma:infoLowerBoundGeneral}
For any node $i$, the inequality $I(\vecb{E}; \vecb{T}_i) \geq E[|\mathcal{P}(\vecb{T}_i)|]$ holds.
\end{lemma}

The proof of Lemma \ref{lma:infoLowerBoundGeneral} is based on
an information-theoretic argument. The intuition is very simple:  since the information $\vecb{T}_i$ completely reveals the information on the edges forming triangles in $\vecb{T}_i$, it must contain all the information on $\mathcal{P}(\vecb{T}_i)$.

We will write $M = |\mathcal{E}| = \frac{n(n - 1)}{2}$ and $N = |\mathcal{T}| = \frac{n(n-1)(n-2)}{6}$.
\begin{proof}[Proof of Lemma~\ref{lma:infoLowerBoundGeneral}]
Since the random variables $\vecb{e}_{\{j,k\}}$ are independent of each other, we have
\begin{align*}
\lefteqn{I(\vecb{E}; \vecb{T}_i)} \\
&= H(\vecb{E}) - H(\vecb{E}|\vecb{T}_i) \\
&= H(\vecb{E}) - \sum_{\{j,k\} \in \mathcal{E}} H(\vecb{e}_{\{j,k\}} | \vecb{T}_i) \\
&= H(\vecb{E}) - \sum_{\{j,k\} \in \mathcal{E}} \sum_{R \subseteq \mathcal{T}}
H(\vecb{e}_{\{j,k\}} | \vecb{T}_i = R) \cdot \Pr[\vecb{T}_i = R] \\
&= M - \sum_{R \subseteq \mathcal{T}} \sum_{\{j,k\} \in \mathcal{E}}
H(\vecb{e}_{\{j,k\}} | \vecb{T}_i = R) \cdot \Pr[\vecb{T}_i = R]\\
&= M - \sum_{R \subseteq \mathcal{T}}\:\: \sum_{\{j,k\} \in\mathcal{E}\setminus\mathcal{P}(R)}
H(\vecb{e}_{\{j,k\}} | \vecb{T}_i = R) \cdot \Pr[\vecb{T}_i = R],
\end{align*}
where the last equality comes from the assumption that Algorithm $\mathcal{A}$ never outputs a triple that is not a triangle (thus $\Pr[\vecb{T}_i = R]\neq 0$ only if $R\subseteq T(G)$, and conditioned to this event we have $\vecb{e}_{\{j,k\}}=1$ with probability $1$ for any $\{j,k\}\in\mathcal{P}(R)$). Since $H(\vecb{e}_{\{j,k\}} | \vecb{T}_i = R) \leq 1$ always holds, we conclude that
\begin{align*}
I(\vecb{E}; \vecb{T}_i) &\geq M - \sum_{R \subseteq \mathcal{T}} (M - |\mathcal{P}(R)|) \cdot \Pr[\vecb{T}_i = R] \\
&\geq \sum_{R \subseteq \mathcal{T}} |\mathcal{P}(R)| \cdot \Pr[\vecb{T}_i = R]  = E[|\mathcal{P}(\vecb{T}_i)|],
\end{align*}
as claimed.
\end{proof}

Theorem \ref{thm:lowerBound} is proved by combining Lemma~\ref{lma:triangleEdge} and Lemma~\ref{lma:infoLowerBoundGeneral}. The intuition is again fairly simple: In expectation, an instance of $G(n, 1/2)$ contains $\Omega(n^3)$ triangles, and thus the average number of triangles output per node node is $\Omega(n^2)$. Thus node $w(\vecb{T})$ outputs at least $\Omega(n^2)$ triangles and, from Lemma~\ref{lma:triangleEdge}, we obtain $E[|\mathcal{P}(\ensuremath{\vecb{T}_{w(\vecb{T})}})|] = \Omega(n^{4/3})$. Lemma \ref{lma:infoLowerBoundGeneral} then gives the same lower bound for the mutual information between $\vecb{E}$ and $\ensuremath{\vecb{T}_{w(\vecb{T})}}$, which then gives the lower bound $\Omega(n^{4/3})$ on the amount of communication received by node $w(\vecb{T})$ during the execution of Algorithm $\Aa$. This implies the claimed $\Omega(n^{1/3}/\log n)$-round lower bound for triangle listing since $w(\vecb{T})$ can receive at most $O(n \log n)$ bits of information per round.

\begin{proof}[Proof of Theorem~\ref{thm:lowerBound}]
From Lemma~\ref{lma:infoLowerBoundGeneral}, we have
\[
I(\vecb{E}; \ensuremath{\vecb{T}_{w(\vecb{T})}}) \geq E[|P(\ensuremath{\vecb{T}_{w(\vecb{T})}})|].
\]
By Lemma~\ref{lma:triangleEdge}, for any $R\subseteq T(G)$ the inequality $|\mathcal{P}(R)| \geq \frac{\sqrt{2}}{3}|R|^{2/3}$ holds. We thus have
\begin{align*}
\lefteqn{I(\vecb{E}; \ensuremath{\vecb{T}_{w(\vecb{T})}}) \geq E[|\mathcal{P}(\ensuremath{\vecb{T}_{w(\vecb{T})}})|]} \hspace{5mm} \\
&= \sum_{R \subseteq \mathcal{T}} |P(R)| \cdot \Pr[\ensuremath{\vecb{T}_{w(\vecb{T})}} = R] \\
&\geq \sum_{R \subseteq \mathcal{T}, |R| \geq \frac{N}{16n}}
|\mathcal{P}(R)| \cdot \Pr[\ensuremath{\vecb{T}_{w(\vecb{T})}} = R]. \\
&\geq \sum_{R \subseteq \mathcal{T}, |R| \geq \frac{N}{16n}}
\frac{\sqrt{2}}{3}\left(\frac{N}{16n}\right)^{2/3} \cdot \Pr[\ensuremath{\vecb{T}_{w(\vecb{T})}} = R]\\
&\geq \frac{\sqrt{2}}{3}\left(\frac{N}{16n}\right)^{2/3} \cdot \Pr\left[|\ensuremath{\vecb{T}_{w(\vecb{T})}}| \geq \frac{N}{16n} \right].
\end{align*}
The expected number of triangles in $G(n,1/2)$ is $N/8$ and thus, since there cannot be more than~$N$ triangles, with probability at least $1/15$ the number of triangles exceeds $N/16$.
We conclude that the inequality $|\ensuremath{\vecb{T}_{w(\vecb{T})}}| \geq N/(16n)$ necessarily holds if the number of triangles is at least $N/16$ and Algorithm $\mathcal{A}$ correctly lists all the triangles of the graph, which occurs with overall probability probability at least $1/15 - 1/32$. Consequently
we obtain
\begin{equation}\label{eq0}
I(\vecb{E}; \ensuremath{\vecb{T}_{w(\vecb{T})}})\geq \frac{\sqrt{2}}{3}\left(\frac{N}{16n}\right)^{2/3} \cdot \left(\frac{1}{15}-\frac{1}{32}\right) =
\Omega(n^{4/3}).
\end{equation}

From Fact~\ref{fact:mutualInfo} we have
\begin{align}
H(\vecb{\pi}_{w(\vecb{T})})
&\geq I(\vecb{E}; \vecb{\pi}_{w(\vecb{T})})\nonumber \\
&\geq
I(\vecb{E}; (\vecb{\pi}_{w(\vecb{T})}, \vecb{\rho}_{w(\vecb{T})}))
- I(\vecb{E}; \vecb{\rho}_{w(\vecb{T})}) \nonumber \\
&\geq I(\vecb{E}; (\vecb{\pi}_{w(\vecb{T})}, \vecb{\rho}_{w(\vecb{T})}))
- H(\vecb{\rho}_{w(\vecb{T})}).\label{eq1c}
\end{align}
Since the initial knowledge of each node $i$ is only the set of edges incident to itself, the inequality \begin{equation}\label{eq2}
H(\vecb{\rho}_{i})\le \sum_{j\neq i} H(\vecb{e}_{i,j}) = n-1
\end{equation}
holds for each node $i\in V$.
Since the output $\vecb{T}_{w(\vecb{T})}$ is computed locally only from the transcript~$\vecb{\pi}_{w(\vecb{T})}$ and the initial state $\vecb{\rho}_{w(\vecb{T})}$, the random variables $\vecb{E}$ and $\vecb{T}_{w(\vecb{T})}$ are conditionally independent given $(\vecb{\rho}_{w(\vecb{T})}, \vecb{\pi}_{w(\vecb{T})})$. We can thus use Fact \ref{fact:DataProcessing} in Inequality (\ref{eq1c}), which combined with Inequalities (\ref{eq0}) and (\ref{eq2}) gives
\begin{align*}
H(\vecb{\pi}_{w(\vecb{T})})
&\geq I(\vecb{E}; \vecb{T}_{w(\vecb{T})}) - H(\vecb{\rho}_{w(\vecb{T})}) = \Omega(n^{4/3}).
\end{align*}
Since $H(\vecb{\pi}_i)$ lower bounds the average length of the transcript $\vecb{\pi}_i$, this implies that node ${w(\vecb{T})}$ receives messages of average total length $\Omega(n^{4/3})$ bits. Since node ${w(\vecb{T})}$ can receive only $O(n\log n)$ bits per round, we conclude that the expected round complexity of Algorithm $\mathcal{A}$ is $\Omega(n^{1/3} / \log n)$.
\end{proof}

The information-theoretic arguments of Lemma~\ref{lma:infoLowerBoundGeneral} can also be used to derive the following stronger lower bound mentioned in the introduction for local triangle listing, the setting where each node $i$ is required to output all the triangles containing $i$.
\begin{proposition}\label{cor}
Let $\mathcal{A}$ be any local triangle listing algorithm with error probability less than $1/32$. Then there exists a probability distribution on inputs such that the expected round complexity of $\mathcal{A}$ is $\Omega(n/\log n)$.
\end{proposition}
The proof of Proposition \ref{cor} is similar to the proof of Theorem \ref{thm:lowerBound} but does not even requires Lemma~\ref{lma:triangleEdge}: we can immediately obtain the stronger bound $E[|\mathcal{P}(\vecb{T}_i)|] = \Omega(n^{2})$ since for local triangle listing $\vecb{T}_i$ should include all the triangles containing $i$.

\begin{proof}[Proof of Proposition~\ref{cor}]
The proof is almost similar to the proof of Theorem~\ref{thm:lowerBound}, except that we can derive the stronger lower bound
\begin{equation}\label{eq4}
I(\vecb{E}; \vecb{T}_i) =
\Omega(n^{2})
\hspace{2mm}
\textrm{ for any $i\in V$},
\end{equation}
instead of the lower bound (\ref{eq0}). This new lower bound implies that $H(\vecb{\pi}_{w(\vecb{T})})=\Omega(n^2)$ and gives the claimed lower bound on the round complexity of the local triangle listing algorithm $\Aa$.

We now explain how to derive the lower bound (\ref{eq4}). From Lemma \ref{lma:infoLowerBoundGeneral} we get
\begin{align*}
\lefteqn{I(\vecb{E};\vecb{T}_i) \geq E[|\mathcal{P}( \vecb{T}_i)|]} \\
 &= \sum_{R \subseteq \mathcal{T}} |\mathcal{P}(R)| \cdot \Pr[ \vecb{T}_i = R] \\
&\geq \frac{M}{16}
\cdot \Pr\big[ \vecb{T}_i \textrm{ includes at least $M/6$ triangles containing $i$} \big],
\end{align*}
since the quantity $|\mathcal{P}(R)|$ is lower bounded by the number of triangles in $R$ containing node $i$. The expected number of triangles in $G(n,1/2)$ containing any fixed node is $M/8$ and thus, since there cannot be more than~$M$ such triangles, with probability at least $1/15$ the number of triangles containing node $i$ exceeds $M/16$.  Since in Algorithm $\mathcal{A}$ node $i$ correctly lists all the triangles containing~$i$ with probability at least $1-1/32$, we conclude that $\vecb{T}_i$ includes at least $M/6$ triangles including~$i$ with overall probability at least $1/15 - 1/32$. We thus obtain
\begin{align*}
I(\vecb{E};\vecb{T}_i)&\geq \frac{M}{16}
\cdot \left(\frac{1}{15}-\frac{1}{32}\right) =
\Omega(n^2),
\end{align*}
as claimed
\end{proof}

\section*{Acknowledgments}
  FLG was partially supported by MEXT KAKENHI (24106009) and JSPS KAKENHI (15H01677, 16H01705, 16H05853). TI was partially supported by JSPS KAKENHI (15H00852, 16H02878) and JST-SICORP Japan-Israel Bilateral Program "ICT for a resilient society".

redpajama_set_name: RedPajamaArXiv


text:
Population Replaced: Germans Have To Integrate With Migrants in Germany! Only 2 Kids out of 25 Are German in Nursery School! (Video)
A German mother has taken to Social Media to express her shock, fear and concern with a polarizing viral video which seems to have hit a chord as it received 2 million views. The mother of a 3-year-old boy, who ironically wears the liberal trademark pink hair, complains that her son cannot socialize with other kids in a public nursery, as only two out of 25 can speak German yet all foreigners can communicate with each other in their language. This situation is not unique either!
In a Facebook video post filmed on August 15, the mother, Leen Kroetsch, takes aim at German politicians for what she claims is a botched immigration policy which is forcing her 3-year-old, who has no immigrant background, to adjust to foreign and alien environment in the daycare center.
Kroetsch claims that out of 25 children, her son's group consists of only two without an immigrant background and who can speak German fluently, while the other 23 are unable to understand German at all. At the same time, all these other children, according to Kroetsch, can easily communicate with each other while speaking in their mother tongues, which her son obviously does not speak.
"My son must adapt to other children. This isn't integration, dear politicians, integration is a bit different," Kroetsch says.
She claims that her son's case is not an exception and is rather commonplace in Essen, the fourth largest city in North Rhine-Westphalia, Germany, noting that her friend's child is also one of only two in his class who do not have an immigrant background.
The woman also expressed outrage at the fact she had to win the right to send her boy to the daycare center in court, saying she almost lost her "existence" job as a result.
Kroetsch says she is concerned not only about the present situation and the well-being of her 3-year-old, but also about the future – in which she fears her son might become a foreigner in his own country.
"I'm scared, I'm scared for my son's future and I do not know what to expect next. My son and I feel here like foreigners. Was that intended?" she said, adding that she might be "forced to immigrate someday" herself.
The woman said that although her child was granted a place in a daycare center, she had to fight the center in court, while parents "of Muhammad, of Ali, and as they are all called" don't have to. Once again foreigners and migrants get VIP treatment whilst local have to fight and work for everything.
The video has upset people on social media and rightly so. While many echoed her concerns, saying "there is no big difference to Berlin" and praising the "courageous woman," others said, "nowadays, it's apparently not so bad to be Muslim."
While the video has been making the rounds on social media, as well as grabbing headlines in the German media, the official in charge of the institution, Petra Struck admitted that although it is true that only two out of 25 children were German citizens. Struck told Westdeutschen Allgemeinen Zeitung (WAZ) that around half of the students in the group can speak German, while some need more time to learn the language, as they have only been in the kindergarten for "several weeks." She noted that the group was a kind of emergency measure in order to give the children the opportunity to attend daycare. So they did not have to go to court for a place then?
Kroetsch argued that Struck was unaware of the situation "on the ground," saying that she was personally told by the administration that only seven children in her son's group have at least a basic knowledge of German.
"Mrs. Struck has never attempted to speak with me," the mother said.
In her video, she stressed that she is not blaming the children in the daycare or their parents. Kroetsch herself also deals with children with immigrant backgrounds in a boxing club.
She added, "does integration work like this? Who needs to integrate?" and that "when I decide to emigrate, I decide to accept a different language and culture". But clearly VIP migrants do not seem to care or understand that.
Watch video with subtitles:
Categories: AfD, African Migrants, Alternative Media, Anti-White, apologism, Asylum Seekers, Attack on Europe, Bavaria, Berlin, Bonn, Border Protection, Bremen, Changing the way we live, Colonization, Communism, consumers, cover-up, Culture Wars, diversity's dark side, Education, EU, Europe, European News, Facebook, fear, Foreign Affairs, Free Speech, Genocide, Geopolitics, Germany, Globalism, Hamburg, Illegal Immigration, Independence, IRC, Ireland, Islamic immigration, Liberalism, Lying Media, Marxism, mass immigration, Merkel, migrant invasion, Mohamed, Multiculturalism, Munich, Muslims, Northern Europe, Occupation Regimes, Open Borders, population replacement, Vierkirchen, Western Europe, White Genocide
Tags: Essen, Germany, Kindergarden, Leen Kroetsch, Muhammad, Nursery, Petra Struck, WAZ, Westdeutschen Allgemeinen Zeitung
« WHAT IF THEY HAD GUNS? Platoon of Well Organised African Invaders Land a Kalergi Boat on a Spanish Beach and Disappear
E.U. Brings Conflict To Europe! Does Ireland Side with EU Supremacists and Self Destruction or the Traditional European Nation States? »

redpajama_set_name: RedPajamaCommonCrawl


Santa Rosa, CA – September 12, 2017 – Defendants Christopher Miranda and Pamela Malfa each plead no contest earlier today in front of the Honorable Robert LaForge to multiple counts of grand theft that arose out of the operation of their business, West Coast Auto Craft, located in Windsor in CA.
Miranda and Malfa were each charged with grand theft, and Miranda was also charged with identity theft in a 57-count complaint. Miranda plead no contest to 13 counts of grand theft and one count of identity theft. Malfa pled no contest to 12 counts of grand theft. Miranda will be sentenced to state prison for a stipulated term of 15 years, 3 months. Malfa will be sentenced to 180 days county jail and will be thereafter placed on formal probation for a period of 5 years.
Miranda and Malfa owned and operated West Coast Auto Craft, an auto repair business specializing in the restoration and repair of classic cars. Over the course of several years Miranda and Malfa took hundreds of thousands of dollars from customers to restore cars. The work on the cars was consistently never finished. Miranda would continue to hold onto the cars, claiming they needed additional work, and then charge customers more money. During the investigation investigators discovered that in one instance Miranda changed the VIN on a customer's $90,000 Camero, and then sold it to an innocent buyer. At the time of the arrest, officers located over 30 classic cars in a field in Cloverdale that were entrusted to Miranda and Malfa to restore. The vehicles had little to no work done on them. Some of the cars were in worse condition than when brought in due to weather exposure and improper storage. Each of the cars has since been returned to its owner. Miranda and Malfa owe approximately $750,000 in restitution to their victims.
Malfa will be sentenced by Judge LaForge on November 14, and Miranda will be sentenced on November 21.
The case was prosecuted by Deputy District Attorney Emily Malfatti, and was investigated by District Attorney Investigator Lisa Chapman. The Bureau of Automotive Repair (BAR), Northern California Computer Crimes Task Force, and Windsor Police Department assisted in the investigation.


Hello again, readers. This second post for today is going to again deal with the screen layout literature that I previously spoke about in the first, but in a much different way. Using this literature as a basis, I have been tasked with reviewing two websites of my own choosing with the caveat being that one must be a website that I approve of while the other should be one that I do not. Naturally my satisfaction or lack thereof is to be based primarily on their layout and design.
The factors that helped me to choose my "thumbs up" website are the factors that are practically nonexistent in my "thumbs down" site. For those that read my previous blog post on the topic, you should already be familiar with these factors, but I explain them here again for the purpose of this assignment, which I am to write in a format resembling an academic paper while being allowed to present it on this blog. I have also cited literature that I did not discuss on the first post from earlier today, so there are fresh elements to keep things interesting.
I choose Edmodo as my website that I feel exhibits many of the features of good layout and design. I presented this same website in class as part of a show-and-tell of useful technology in which my fellow peers and I took turns introducing and explaining in detail some sort of technology that we felt our peers might not be aware of or, at the very least, not have a deep understanding of.
Edmodo, at its core, is a website designed to help teachers increase the efficiency of their classrooms. Teachers can create groups for each of the classes they teach and then invite their students to join these groups, and the service itself, without students ever having to give their personal email addresses to the teacher. This certainly eliminates any concerns over privacy issues that academic institutions might have, particularly at ones where students are not given a school email address. Once both teacher and students are signed up for Edmodo, the teacher can use the site to give students assignments, send reminders, create quizzes and tests, and much more. Students, in turn, can submit assignments via file upload, takes quizzes and tests, post questions for the teacher, etc. Teachers can also mark submitted work and assessments right on the site and have the results shown to their students immediately. It is this kind of functionality that contributes to the perceived usefulness of the website, which is now being utilized by thousands of teachers around the world (Davis, 1989).
Edmodo is also as simple or as complex as you wish to make it. The decision of which features to use is entirely up to the teacher and nothing will appear under the group for a given class unless the teacher specifically creates and posts it. Until that time, icons for creating things such as assessments, polls, and assignments sit up at the top of a class' group page, completely out of the way and undistracting as can be seen in Figure 1 below. It is this design choice that also gives Edmodo its perceived ease of use, as teachers can find the tools they want to use quickly, but are not distracted by unused elements taking up screen space (Davis, 1989).
If we need a reason to further delve into the aesthetic side of Edmodo, we can refer back to the work of Kurosu & Kashimura (1995), who discovered a high correlation between interface aesthetics and perceived usability. It was Altaboli & Lin (2011), however, who defined what makes a website aesthetically pleasing, citing the three elements of unity, balance, and sequence as necessary in a site's design in order for it to be considered so. Looking at Figure 2 below, Edmodo clearly exhibits these traits. It has uniformity across all pages in terms of fonts, colors, and even icon design, which utilizes an outline-type design with a great amount of empty space in the center and no color fill. Balance is achieved by the use of significant white space on the sides to keep the main elements of each page centered while also using a smaller amount between elements to keep them from blending together. Sequence is present as the page naturally flows from left to right and top to bottom as one would expect. Icons, as previously mentioned, are placed in locations that make sense without being distracting.
Because Edmodo follows a design style typical of many popular social networking sites such as Twitter and Facebook, it can be said that it has a high level of prototypicality. Everything is where we have come to expect certain items to be, with the features relating to the main site itself, such as the home button and search field, located in the upper left and continuing along the top, while navigational menus that are found once you are on a group page are located to the left. Even the icons for creating the various content items are set up much like the status update field of Facebook, located directly under the main site icons at the top and complete with tabs to change the type of content we are creating. This high level of prototypicality keeps users from wasting time getting their bearings on a page and allows them to begin adding or editing the content they are interested in immediately (Tuch, Presslaber, Stocklin, Opwis, & Bargas-Avila, 2012; Roth, Tuch, Mekler, Bargas-Avila, & Opwis, 2013). In my own usage, I have found that I can easily navigate to the group for the class I want upon logging in and from there immediately find the assignment submissions I wish to view or create the content that I need to send out to my students.
Overall, I believe this combination of perceived usability, perceived usefulness, and the aesthetic features that help to bolster these things are a driving force behind Edmodo's consistently growing number of users. The fact that Edmodo is also fully customizable so that teachers can tailor it to their needs while also being a completely free service simply increases the overall satisfaction that this site gives its user base from the very first time they sign on.
I chose Yahoo Japan as my "thumbs down" site as we had discussed it briefly in my class and the discussion we had about it was interesting so I wanted to bring that discussion here to my blog as well. Yahoo Japan seems to suffer from, quite simply, being a Japanese website. In fact, I, and many of my classmates, are convinced that a majority of Japanese websites are built on the premise of trying to fit as much content onto the screen as possible at any given time. Figure 3, which follows this paragraph, clearly demonstrates this apparent design choice. The American version of Yahoo is certainly not this cluttered.
The only saving grace of Yahoo Japan is in the fact that it uses white space on the sides to center content, much like Edmodo. Unfortunately, I cannot say anything positive aside from this in terms of aesthetics. The abundance of icons makes finding the content that I want akin to a word search. The small font size also greatly reduces the readability of the website and I am a younger man viewing the site on a Macbook Pro that has a high resolution Retina display. I can only imagine how horrible it must be for someone older viewing the site on a low resolution monitor. The content that the home page displays from the beginning is also seemingly random, with no clear sense behind why the many boxes are in the order in which they appear. At the very least, the search bar is where one would expect, but aside from this, Yahoo Japan has an incredibly low level of prototypicality.
If Yahoo Japan wants to turn things around, they may want to first mirror their American sibling, which has considerably less items in its navigational menus and employs much larger font sizes for headlines and other text. I think that even the U.S. site could use more white space between articles on its main page, but I understand that it is a news site and it wants to still keep at least 4 or 5 articles on the screen at any one time. It is still leaps and bounds above Yahoo Japan in terms of allowing me to find content that I am interested in and navigating back and forth between various pages on its site.
It would be easy to condemn the designers of Yahoo Japan if it were not for the fact that popular Japanese sites such as mixi are also cluttered messes. It makes me wonder what those that pursue web design as a career in Japan are taught inside the classrooms of their vocational schools. As someone who is well-versed in web design, I am sure that the answer might horrify me, but I would love to hear back from you and get your opinions on the matter, dear readers. Is this an actual phenomenon in Japanese design or am I just perceiving it as such because the two sites I mentioned just happen to be some of the most popular in Japan in recent history? I would also appreciate links to some well designed Japanese websites. While I do not believe all Japanese websites suffer from this problem, having actual evidence of such would be nice as my own web searches are seeing my inner web designer sink into depression.
Altaboli, A., & Lin, Y. (2011). Investigating effects of screen layout elements on interface and screen design aesthetics. Advances in Human-Computer Interaction, 2011(5), 1-10.
Davis, F. D. (1989). Perceived usefulness, perceived ease of use, and user acceptance of information technology. MIS Quarterly, 13, 319-340.
Roth, S. P., Tuch, A. N., Mekler, E. D., Bargas-Avila, J. A., & Opwis, K. (2013). Location matters, especially for non-salient features–An eye-tracking study on the effects of web object placement on different types of websites. International Journal of Human- Computer Studies, 71(3), 228-235.
Tuch, A. N., Presslaber, E. E., Stocklin, M., Opwis, K., & Bargas-Avila, J. A. (2012). The Role of Visual Complexity and Prototypicality Regarding First Impression of Websites: Working Towards Understanding Aesthetic Judgments. International Journal of Human- Computer Studies, 70, 794-811.


text:
Computer science Ph.D. student named finalist for international award honoring women in edge computing
Two leading organizations in edge computing - State of the Edge and Edge Computing World - announced 10 finalists for its inaugural Edge Woman of the Year award. Among the nominees was Tayebeh Bahreini, a computer science Ph.D. candidate in the Wayne State University College of Engineering.
The award was created to highlight the growing importance of the contributions and accomplishments of women in edge computing, a method that brings computation and data storage closer to the locations of devices and people producing and consuming information, lowering bandwidth and response times.
Bahreini and her fellow nominees were invited to attend the annual Edge Computing World event at the Computer History Museum from Dec. 9-12 in Silicon Valley.
Bahreini has made several important pioneering contributions in the area of resource management in edge computing systems, including the design of an efficient online iterative matching algorithm for placing multi-component services on edge servers. A paper on this research was published in the Proceedings of the Second ACM/IEEE Symposium on Edge Computing in 2017.
"Her design represents a big departure from the existing designs of service placement algorithms that mainly relied on complex techniques based on Markov models and imposed restrictions on the topology of the graphs characterizing both the applications and the physical resources," said Daniel Grosu, associate professor of computer science at Wayne State and Bahreini's Ph.D. advisor.
In addition to her design of the iterative matching placement algorithm, Tayebeh designed a novel envy-free auction mechanism for resource allocation in edge computing systems and an energy-aware resource manager for Vehicular Edge Computing systems.
Bahreini's proposed algorithms and mechanisms offer potential to enhance the capabilities of mobile devices and applications, and to reduce wasted energy and computational resources in organizations ranging from governments to private companies.
She received a Best Poster Award at the sixth biennial Michigan Celebration of Women in Computing (MICWIC) conference in 2017, and the 2019 National Center for Women & IT (NCWIT) Collegiate Award. Bahreini is also a past presenter at the CRA-Women Grad Cohort Workshop and the Grace Hopper Celebration of Women in Computing conference.
Results of Bahreini's research have been published in several international IEEE and ACM conferences and workshops, as well as top ranked journals such as IEEE Transactions on Parallel and Distributed Systems.
"She is very active in promoting the role of women in computer science," said Grosu.
Bahreini works in the Parallel and Distributed Computing Lab at Wayne State University directed by Grosu. She is the main developer on a major project in the lab focused on the design of a vehicular edge computing resource management system.


text:
ArticlesHealth
Mix of COVID-19 cluster-busting with vaccine push may bring a new normal faster
Combining so-called "backward tracing" with traditional forward tracing to help identify source events of COVID-19 outbreaks has been cited as a potential way of better tracking the disease, as seen in some Asian countries. Now that vaccines are emerging on the scene, how can this concept be used for more effective cluster-busting?
Régnier	on January 13, 2021
ArticlesDisinformation
What drives public trust? Broadening the traditional scope of science communication with TRESCA
The COVID-19 pandemic has accelerated the digitalisation of our daily lives and, by now, we are all a bit more dependent on technology than we had been before. But how can we trust all the scientific information that we receive through the media? How can we have a common understanding of what is reliable when we are being exposed to massive online information flows? Do we trust the same truths? What kind of people are more susceptible to trusting conspiracy theories? Using a novel approach based on social science, the new EU-funded project TRESCA tackles these, and other, research questions.
Régnier	on December 30, 2020
ArticlesEnvironment
The Oceans of Plastics – Plastisphere: A new term for the marine environment
Every minute, the equivalent of one garbage truck of plastic waste enters the oceans. Plastic pollution is so ubiquitous that scientists have coined a new term for the marine environment: the plastisphere.
The growing threat of internet addiction
Excessive and problematic internet use is increasingly recognised as a potential threat to public health.
ESMH Press Review – January 9, 2019
Here is the ESMH selection of science and tech news published in the last two weeks all around the web. Pick your favourite from the most popular topics in the mainstream media.
ArticlesArtificial Intelligence
Debate on "killer robots": the crucial role of human control
Advancement in military automation is raising concerns across the world, especially about the prospects of so-called "killer robots".
Antibiotics on farms: Europe starts to curb bad practices
Resistant infections kill an estimated 33 000 people in the European Union annually.
ESMH Press Review – December 12, 2018
Technology and elections : first event for journalists from all 28 EU member states Nov. 6-7, 2018
How technology could be used or misused in electoral campaign? This was the main topic debated during the two-day event in the European Parliament (EP), organised by the European Science-media Hub/ the Panel for the Future of Science and Technology (STOA) together with the Communication Directorate of the EP.
The ESMH kick-off event : Communicating Science via Social Media June 27, 2018
More than 50 representatives of the scientific community, European research organisations and journalists engaged into a stimulated debate on the challenges of communicating science via social media.


The main function of an air conditioning system is mainly to produce cool ventilation inside the building in which the heat is taken out from a certain location to give a chilled air effect. The main process is that the air circulation is drawn to the condenser containing refrigerant gas. The circulation process undergoes three stages wherein the evaporator carries secondary cooled refrigerant passing through to release ice-cold air into the area. Therefore, an air conditioning system can make the air indoors cold and release hot air outside. This is the main function of the refrigerant. The air conditioning system is composed of mechanical components which are the following: blower, chemical refrigerant, condenser, compressor and evaporator coil.
The most commonly used AC systems are the split system, fixed unit type, and duct-type. The ducted air conditioner type can be installed in any home whether it is old or new as long as there is enough ceiling space. The two components which comprise the ducted system are a compressor unit situated outside the building, and the indoor unit that is located inside the ceiling area. Air distribution passes through vents throughout the interior of the house. The air condition can be divided into two zones at the same time in different areas. One zone can give heated air in other locations such as the living room and the other make a cooled zone in the bedrooms.
The thermostat controls the compressor. The compressor acts as the "heart" as it pumps to let the refrigerant flow into the system and it draws in low-pressure and low-temperature. When the gas is compressed, the refrigerants' temperature and pressure are raised which automatically flows into the condenser coil. The most relevant task in maintaining good performance of an air conditioning system is to maintain clean air conditioner filters. Dirty filters will tend to block the normal air flow caused by clogged dirt thus reducing the system's efficiency. Air filters should be replaced regularly to avoid future problems.


Is it hard to stand out against the competition? With heavily regulated small group plans and rates, it is a challenge to leave an impression with a potential client. Making your market proposal UNIQUE with a one-of-a kind layout and structure is critical to branding your firm and leaving a lasting impression. Create your own look and feel and we will upload it into our system. Then each and every market proposal will have your custom branding to present a consistent message to your current clients and new prospects.
Either import a census from Excel or track your employee enrollments throughout the year directly within Salesforce. Census imports have a "search and replace" function so you won't have duplicate employee data entered. Our system allows for different elections for medical, dental and vision policies.
No more redundant data entry of plan design summaries. Master level users will enter or import the plan design specifications once and those fields will be locked from editing for all other administrators. This allows for consistent plan summary definitions and greatly reduces errors. Administrators will then have access to pull the set plan summaries into their market proposals and Benefits at a Glance employee workbook.
Significantly increase your dental and vision sales by automatically including these policies in EVERY market proposal. You no longer need to worry about sending out an RFP (Request for Proposal) for dental and vision. We have included our standard pricing on the most popular Delta Dental plans and VSP Vision plans in the market.
Do you tend to show new business prospects the same plans with each proposal? We saw the trend so we duplicated the process! Send each of these prospects a new business market proposal with a range of Bronze, Silver and Gold plans from each carrier. Simply click a button and this new business template will be created. Clean and clear with a nice range of options to start the conversation! PLUS, you will impress the client with being able to send them a market proposal within hours of the initial contact rather than a few days.


text:
Q: get facebook page public info I have a facebook app that tries to get a page's public info using the facebook graph api in php.
I got an app access token using this link https://graph.facebook.com/oauth/access_token?client_id={APP_ID}&client_secret={APP_SECRET}&grant_type=client_credentials but when I use that to get a page's info I get a "400 bad request" response.
I connect to this: https://graph.facebook.com/{PAGE_ID}?access_token={ACCESS_TOKEN_FROM_PREVIOUS_CODE}
If I use the access token from the "Graph Explorer" app, it works but that is probably a user access token.
If I use the token that facebook generates with the oauth link above or the access token composed of "{APP_ID}|{APP_SECRET}" as they suggest in the access tokens documentation page it doesn't work.
In the page api reference they say an app token should be enough to get a page's public info.

A: I just tried it with an App Access Token (App-ID|App-Secret), it works perfectly fine like this:
https://graph.facebook.com/bladauhu?access_token=App-ID|App-Secret

If your page is not public, it will only work with a User Access Token (from a User who is Admin of the page). May be the reason why it does not work. Take App-ID and App-Secret from any App and make sure the App is public too ("Status & Review" tab in the App settings - "Do you want to make this app and all its live features available to the general public?").

redpajama_set_name: RedPajamaStackExchange


text:
Famous Wrecks
Bankrupt Titanic collector is selling everything
In Famous Wrecks
By Dawn McCarty - Bloomberg
The story of the doomed luxury liner R.M.S. Titanic proved so alluring that divers were searching for the wreck seven decades after it sank to the bottom of the Atlantic Ocean.
Once it was found in 1985, fanfare over retrieved relics led to exhibits around the world and a blockbuster movie. But the company holding the rights to the ship and 5,500 artifacts has been mired in debt, placing the future of its collection in the hands of a bankruptcy court.
On Thursday, a judge weighed plans for auctioning the largest trove of Titanic memorabilia, which already is drawing the interest of U.S. hedge funds, Chinese investors, British museums and award-winning director James Cameron.
Among the items is the bell a crow's nest lookout rang to warn the bridge of an iceberg ahead; window grills from the first-class dining area; a passenger's three-diamond ring; and a suitcase full of clothes owned by William Henry Allen, an English toolmaker immigrating to America.
Titanic, once the biggest ocean liner ever built, sank almost two miles below the sea on its maiden voyage in 1912, killing more than 1,500 of its 2,200 passengers.
"It's just sad to see that great ship of dreams, and the pieces of it, bounced around like an orphaned child,'' said David Gallo, an oceanographer and former head of special projects at the Woods Hole Oceanographic Institution who co-led an expedition to the wreck in 2010.
At least three groups are vying for the artifacts from the current owner, Premier Exhibitions Inc. It's the successor to a company once owned by a wealthy Connecticut auto dealer, who bankrolled a French exhibition that retrieved artifacts from Titanic for the first time in 1987.
The wreck was discovered two years earlier by oceanographer Robert Ballard, who refused to remove anything from the site, which is 12,000 feet (3,700 meters) under water. Atlanta-based Premier organizes Titanic displays around the world, including at the Queen Mary hotel in Long Beach, California, the Luxor Hotel in Las Vegas, and the Guangdong Museum in China.
In recent years, the business was expanded to include exhibitions such as animatronic dinosaurs, human cadavers and bugs, along with sets and props from the Saturday Night Live TV show.
Titanic White Star Line wreck shipwreck Captain Edward Smith bankruptcy


- delete everything that is not MMAT, TXMT and TXTR.
- IMPORTANT, especially if it is a master mesh from which slaves draw their texture: go in the MMAT of the recolour file, find the modelName anc change it back to what it was in the mesh file. Otherwise the slaves will not recognise the recolour.
Plus in the MMAT, change the defaultMaterial value from 1 (true) to 0 (false).
- Echo has a tutorial here. Essentially, follow the tut to make a template which then you can recolour (by cloning) as described for CC plants above.
- Bienchen has posted some templates which make the recolourer's job a lot easier.
The above note on changing modelName in the MMAT applies here as well, if you want your recolour to be recognised by any seasons-friendly slave.
If the mesh already has recolours or you've made the first one, it's easier to clone an existing recolour so you'll only have to do all these once or not at all.
Any question, feel free to ask.
I'm trying to default the Easy Shade Bay Tree, and do some Seasons-friendly recolors, using a recolor of yours to clone mine from, but I'm wondering which boxes I need to keep ticked during the start process? Is it just the first four? I don't see anything about which boxes to leave checked or unchecked in Echo's tutorial!
It's been a while since I worked with plants but I believe you only tick the first four.
A note: Paladine/Simwardrobe has a season-changing urn which makes testing much easier.
I'll be glad to see more recolours!
That WILL make things much easier! Thank you!
I know I used a combination of selecting and deleting the green parts of EA snowy plant textures and copying the resulting snow-pieces over and over, hand-drawing, sharpening, strong HSV noise filtering, and soft airbrush painting.
I've put up some of the snowy textures I used here for you. I use GIMP so they are .XCF files, I hope you can use them. If not I can make some .PNGs.
Ahhh. So, I've extracted some texture files out of the game, and I'll try by snipping little pieces of green here and there.


She is starting to get her life together after being outed by the Kardashian clan.
Jordyn Woods appeared to be in high spirits on Tuesday when she stepped out in Calabasas for a coffee run. The 21-year-old showed off her incredible hourglass figure in a white crop top with a deep neckline and a pair of tight gray leggings, which she paired with comfy white sneakers while out and about in the Los Angeles neighborhood. She was spotted carrying a green beverage and appeared to be largely makeup-free while making her way back to the car. Jordyn wore eyeglasses and styled her long braids into a simple ponytail for her morning outing, according to The Daily Mail.
She just returned from a trip to the United Kingdom, where she attended several events to promote her new eyelash line with Eylure. She was accompanied by her mom, Elizabeth Woods, who recently shut down rumors that her family was behind new merchandise being sold that features Jordyn's face and a quote related to the cheating scandal involving herself and Khloe Kardashian's baby father, Tristan Thompson, as per Pop Culture.
She also shared photos of the merchandise featuring the quote "I don't need your situation," something that Jordyn said during her interview with Jada Pinkett Smith for the talk show Red Table Talk. She was referring to Khloe's turbulent relationship with the father of her baby daughter, True Thompson, who also publicly cheated on her last year, just days before she gave birth.
Jordyn had a falling out with the Kardashian-Jenner family when reports emerged that she was seen kissing NBA star Tristan at a house party back in February. She has been Kylie Jenner's closest friend since middle school, but the makeup mogul asked Jordyn to move out of her guest house following the scandal, and the two seemingly have not rekindled their friendship since.
However, Jordyn made headlines last week when she liked Kylie's Instagram photo, which also featured her beau Travis Scott. And despite the fact they're not best friends anymore, the reality TV star denied slashing the Jordyn Lip Kits' price after the scandal broke out, explaining the products had already been put on sale before the whole thing happened.
"That is just not my character. I would never do something like that and when I saw it, I was like, thrown back. Jordyn knows I didn't actually put it on sale," she told The New York Times.


text:
using System.Collections.Generic;
using System.Data.SqlClient;
using bv.common.Configuration;
using bv.model.BLToolkit;
using DevExpress.XtraReports.UI;
using eidss.model.Enums;
using EIDSS.Reports.BaseControls;
using EIDSS.Reports.BaseControls.Report;
using EIDSS.Reports.Document.Veterinary.LivestockInvestigation;
using EIDSS.Reports.Factory;
using EIDSS.Reports.Flexible;

namespace EIDSS.Reports.Document.Veterinary.AvianInvestigation
{
    public sealed partial class AvianInvestigationReport : BaseDocumentReport
    {
        private readonly FlexVetClinicalContainer m_ClinicalContainer;

        public AvianInvestigationReport()
        {
            InitializeComponent();
            int width = PageWidth - Margins.Left - Margins.Right;
            m_ClinicalContainer = new FlexVetClinicalContainer(DetailInvestigation, width, true);
        }

        public override void SetParameters
            (string lang, Dictionary<string, string> parameters, DbManagerProxy manager, DbManagerProxy archiveManager)
        {
            base.SetParameters(lang, parameters, manager, archiveManager);

            RebindAccessRigths();

            long caseId = (GetLongParameter(parameters, "@ObjID"));
            long diagnosisId = (GetLongParameter(parameters, "@DiagnosisID"));
            long includeMapInt;
            bool includeMap = TryGetLongParameter(parameters, "@IncludeMap", out includeMapInt) && includeMapInt ==1;

            VetObservationData observationData = LivestockInvestigationReport.GetVetCaseObservationData(manager, caseId);

            AvianCaseTableAdapter.Connection = (SqlConnection) manager.Connection;
            AvianCaseTableAdapter.Transaction = (SqlTransaction) manager.Transaction;
            AvianCaseTableAdapter.CommandTimeout = CommandTimeout;

            AvianInvestigationDataSet.EnforceConstraints = false;
            AvianCaseTableAdapter.Fill(AvianInvestigationDataSet.spRepVetAvianCase, caseId, lang);
            FillBarcode();

            ClinicalInvestigationSubreport.Visible = false;
            m_ClinicalContainer.SetObservations(observationData.SpeciesObservationIdList, diagnosisId);

            FlexFactory.CreateAvianEpiReport(EpiSubreport, observationData.FarmObservationId, diagnosisId);

            ((FlockReport) xrSubreportFlock.ReportSource).SetParameters(lang, caseId, manager, archiveManager);
            ((VaccinationReport)xrSubreportVaccination.ReportSource).SetParameters( lang, caseId, manager, archiveManager);
            ((RapidTestReport)xrSubreportRapidTest.ReportSource).SetParameters( lang, caseId, manager, archiveManager);
            ((DiagnosisReport)xrSubreportDiagnosis.ReportSource).SetParameters( lang, caseId, manager, archiveManager);
            ((SampleReport) xrSubreportSampleReport.ReportSource).SetParameters(lang, caseId, manager, archiveManager);

            DetailReportMap.Visible = BaseSettings.PrintMapInVetReports;
            if (includeMap)
            {
                MapPictureBox.Image = PrintMapHelper.GetPrintMap(AvianInvestigationDataSet.spRepVetAvianCase);
            }

            ReportRtlHelper.SetRTL(this);
            ReportRebinder.RebindDateAndFontForReport();
        }

        private void FillBarcode()
        {
            if (AvianInvestigationDataSet.spRepVetAvianCase.Count > 0)
            {
                var row = AvianInvestigationDataSet.spRepVetAvianCase[0];

                cellBarcode.Text = row.IsCaseIdentifierNull()
                    ? string.Empty
                    : m_BarCode.Code128(row.CaseIdentifier);
            }
        }

        private void RebindAccessRigths()
        {
            if (AccessRigthsRebinder.ForbiddenAccess(PersonalDataGroup.Human_Contact_Details))
            {
                xrTableCell25.DataBindings.Clear();
                xrTableCell25.DataBindings.Add(new XRBinding("Text", null, "spRepVetAvianCase.FarmAddressDenyRightsDetailed"));
            }
            if (AccessRigthsRebinder.ForbiddenAccess(PersonalDataGroup.Human_Contact_Settlement))
            {
                xrTableCell25.DataBindings.Clear();
                xrTableCell25.DataBindings.Add(new XRBinding("Text", null, "spRepVetAvianCase.FarmAddressDenyRightsSettlement"));
            }
        }
    }
}

redpajama_set_name: RedPajamaGithub


Savannah Food & Wine Festival focuses on giving back to the community by donating part of the profits from its events to local nonprofit organizations.
The weeklong Savannah Food & Wine Festival has announced the many nonprofit organizations to which part of the festival profits will be donated. The sought-out festival will return to Georgia for the week of Nov. 11 to 17, bringing top chefs, sommeliers, and culinary experts to the area.
One of the main events at the festival, the Grand Reserve Tasting, hopes to bring in a noticeable amount of profit, of which part will be donated to a local nonprofit organization, The 200 Club of The Coastal Empire. This high-profile event will offer wine bottles averaging more than $50 for those looking for the "ultimate in wine tasting," as well as host a silent auction of items such as one-of-a-kind wine lots, luxury travel, merchandise, and services, while guests can enjoy gourmet appetizers.
"The 200 Club of the Coastal Empire goals and objectives are honorable and clearly in line with Savannah's needs. The organization provides immediate financial assistance for surviving spouses and children of local law enforcement officers and firefighters who lose their lives in the line-of-duty while protecting their communities. We are very proud to be associated with the amazing work The 200 Club provides to our community," Michael T. Owens, president of the Savannah Food & Wine Festival, stated in a recent press release.
Special VIP guests at the Grand Reserve Tasting will include world-renowned sommeliers, winemakers, chefs, and authors such as Lydia and Rob Mondavi Jr., chef Chris Hastings, the Lee Brothers, chef Anthony Lamas, Master Sommeliers Robert Jones and Michael McNeill, and Iron Horse Vineyards.
According to Hugh Golden, chairman of the Grand Reserve Tasting Committee, the event is the must-attend event for wine enthusiasts. "If you appreciate good wine, the festival has a multitude of events you can attend — if you appreciate great wine, you won't find a better ticket available in the southeast region to taste extraordinary wine than the Grand Reserve."
With community being the focal point of this year's Savannah Food & Wine Festival, giving back and supporting local nonprofit organizations is of high priority to the festival organizers. Besides The 200 Club of the Coastal Empire, nonprofits that will benefit from festival include United Way of the Coastal Empire, Bethesda Academy, the West Broad Street YMCA, and Mom's Lemonade Stand.