\section{Introduction and Main Results}

The Constraint Satisfaction Problem (CSP) over a relational structure $\relstr{A}$ in a finite language, denoted by $\CSP(\relstr{A})$, is the problem of deciding whether or not a given primitive positive (pp-) sentence in the language of $\relstr{A}$ holds in $\relstr{A}$.
An alternative, combinatorial definition of the CSP is also popular in the literature: $\CSP(\relstr{A})$ is the problem of deciding whether a given relational structure in the same language as $\relstr{A}$ maps homomorphically into $\relstr{A}$.

For CSPs over certain structures, including all finite ones, a computational complexity classification has been conjectured, separating NP-hard problems from polynomial-time solvable ones. In the following, we shall state and discuss this conjecture, and subsequently present an improvement thereof which follows from our results. In order to keep the presentation compact, we postpone most definitions to Section~\ref{sect:notation}, and refer also to the monograph~\cite{Bodirsky-HDR} as well as to the shorter~\cite{Pin15}. As a reference for standard notions from model theory, we point to the textbook~\cite{Hodges}.

All structures in the present article are implicitly assumed to be finite or countable.

\subsection{The tractability conjecture}
The CSP over a structure with finite domain is clearly contained in the class $\mathrm{NP}$. Some well-known $\mathrm{NP}$-complete problems, such as variants of 3-SAT or 3-COLORING, can be formulated as CSPs over suitable finite structures, as well as some problems solvable in polynomial time, such us 2-SAT, HORN-SAT, or systems of linear equations over finite fields. In fact, it has been conjectured~\cite{FederVardi} that CSPs over finite structures enjoy a dichotomy in the sense that every such CSP is either $\mathrm{NP}$-complete, or tractable, i.e., solvable in polynomial time. A large amount of attention has been brought to confirming or refuting this conjecture, resulting in considerable progress; see~\cite{Barto-survey} for a recent brief introduction and survey. In particular, a precise borderline between $\mathrm{NP}$-complete and tractable CSPs has been delineated~\cite{JBK} and is now referred to as the \emph{tractability conjecture} or also the \emph{algebraic dichotomy conjecture}, since most of the equivalent formulations are algebraic.

When we allow the domain of $\relstr{A}$ to be infinite, the situation changes drastically: every computational decision problem is polynomial-time equivalent to $\CSP(\relstr{A})$ for some $\relstr{A}$~\cite{BodirskyGrohe}! A reasonable assumption on $\relstr{A}$ which sends the CSP back to the class $\mathrm{NP}$ and still allows to cover many interesting computational problems which cannot be modeled as the CSP of a finite structure,
is that $\relstr{A}$ is a reduct of a finitely bounded homogeneous structure. Substantial results for such CSPs include the full complexity classification of the CSPs over the reducts of $(\mathbb{Q};<)$ in \cite{tcsps-journal} (classifying the complexity of problems previously called temporal constraint satisfaction problems), the reducts of the random graph (generalizing Schaefer's theorem for Boolean CSPs to what can be called the propositional logic for graphs), and the reducts of the binary branching $C$-relation~\cite{Phylo-Complexity} (classifying the complexity of problems known as phylogeny CSPs). The methods here include the algebraic methods from the finite, but in addition tools from model theory and Ramsey theory~\cite{BP-reductsRamsey}. Moreover, topological considerations have played a significant role in the development of the theory~\cite{Topo-Birk}, and indeed seem inevitable in a sense, although paradoxically it was believed or at least hoped that they would  ultimately turn out inutile in a general complexity classification. On the other hand, due to the fact that the investigation of infinite domain CSPs is more recent, and the additional technical complications which are to be expected when passing from the finite to the infinite,
the purely algebraic theory as known in the finite is still quite undeveloped in the infinite; the present work can be seen as the first purely algebraic result for such CSPs.

A generalization of the finite domain tractability conjecture has been formulated by Manuel Bodirsky and the second author.
To state it, we first recall several basic facts.
When $\relstr{B}$ has a primitive positive (pp-)interpretation without parameters in $\relstr{A}$, then $\CSP(\relstr{B})$ reduces to $\CSP(\relstr{A})$. When $\relstr{A}$ is an $\omega$-categorical core, then this statement is even true for pp-interpretations with parameters. By~\cite{Cores-journal}, every $\omega$-categorical structure, in particular every reduct of a finitely bounded homogeneous structure, is homomorphically equivalent to an $\omega$-categorical core, which is unique up to isomorphism. Moreover,  the CSPs over any two structures which are homomorphically equivalent are equal, and so passing from an $\omega$-categorical structure to its core does not result in any loss of information concerning the CSP.

These facts imply that the CSP over an $\omega$-categorical structure is $\mathrm{NP}$-hard whenever its core pp-interprets with parameters some structure whose CSP is NP-hard, such as
\[
\mathbb{K}_3 = (\{1,2,3\}; \neq)\]
 whose CSP is the 3-coloring problem, or
\[
\mathbb{L} = (\{0,1\}; R_{000}, R_{001}, R_{011}, R_{111}), \  R_{abc} = \{0,1\}^3 \setminus \{(a,b,c)\}
\]
whose CSP is the 3-SAT problem, or
\[
\mathbb{M} = (\{0,1\}; \{(0,0,1),(0,1,0),(1,0,0)\})
\]
whose CSP is the positive 1-in-3-SAT problem. In fact, these three structures not only pp-interpret each other, they pp-interpret all finite structures. The infinite domain tractability conjecture postulates, as does the corresponding conjecture for finite structures, that pp-interpreting all finite structures with parameters in the core is the only source of hardness for CSPs over reducts of finitely bounded homogeneous structures.

\begin{conjecture}[Bodirsky + Pinsker\; 2011; cf.~\cite{BPP-projective-homomorphisms}]\label{conj:dicho}
Let $\relstr{B}$ be a reduct of a finitely bounded  homogeneous structure and let $\relstr{A}$ be the core of $\relstr{B}$. Then
\begin{itemize}
\item $\relstr{A}$ pp-interprets all finite structures with parameters (and thus $\CSP(\relstr{B})$ is NP-complete), or
\item $\CSP(\relstr{B})$ is solvable in polynomial time.
\end{itemize}
\end{conjecture}

In the present article, we show that the failure of the first condition of this conjecture is witnessed by a certain algebraic fact that could, similarly to what is the hope in the finite setting, potentially be exploited for proving tractability of the CSP. We now make the notion of an algebraic witness more precise.

\subsection{The algebraic approach}

The algebraic approach to finite domain CSPs is based on the fact that pp-interpretability strength of a finite structure $\relstr{A}$ is determined by its set of compatible operations, the so called \emph{polymorphism clone} of $\relstr{A}$, denoted by $\Pol(\relstr{A})$. Namely, by classical universal algebraic results,
a finite structure $\relstr{A}$ pp-interprets a finite structure $\relstr{B}$ if and only if there exists a clone homomorphism from $\Pol(\relstr{A})$ to $\Pol(\relstr{B})$, that is, a mapping which preserves arities and \emph{identities} (universally quantified equations). This fact implies that the complexity of $\CSP(\relstr{A})$ only depends on the identities satisfied by operations in $\Pol(\relstr{A})$
and leads to an algebraic reformulation of the first item of Conjecture~\ref{conj:dicho} for finite structures.
The following notation is used: the \emph{stabilizer} of $\Pol(\relstr{A})$ by finitely many constants $c_1,\ldots,c_n$ is denoted $\Pol(\relstr{A},c_1,\ldots,c_n)$; its elements are those polymorphisms of $\relstr{A}$ which preserve all unary relations $\{c_i\}$. The clones $\Pol(\relstr{L})$, $\Pol(\relstr{M})$, as well as $\Pol(\relstr{K},0,1,2)$ are trivial, i.e., they contain only projections. Let us denote the clone of projections on a $2$-element set by $\clone{P}$. The clone of projections on any other set of at least $2$ elements is isomorphic to $\clone{P}$.

\begin{theorem}[\cite{Geiger,BoKaKoRo,Bir-On-the-structure}, cf.~\cite{Bodirsky-HDR}] \label{thm:finite-birk}
The following are equivalent for a finite relational structure $\relstr{A}$ with domain $A = \{c_1, \dots, c_n\}$.
\begin{itemize}
\item $\relstr{A}$ pp-interprets all finite structures with parameters.
\item There exists a clone homomorphism from $\Pol(\relstr{A},c_1,\ldots,c_n)$ to $\clone{P}$.
\end{itemize}
\end{theorem}

For the second, algebraic statement of Theorem~\ref{thm:finite-birk} numerous equivalent algebraic criteria have been obtained within the setting of finite structures~\cite{T77,HM88,JBK,MM08,Sig10,Cyclic}, making in particular the failure of the condition more easily verifiable: this failure is then usually witnessed by the satisfaction of particular identities in $\Pol(\relstr{A},c_1,\ldots,c_n)$ which cannot be satisfied in $\clone{P}$.

Some of the above-mentioned facts about finite domain CSPs have analogues for $\omega$-categorical structures. The complexity of $\CSP(\relstr{A})$ still only depends on the polymorphism clone $\Pol(\relstr{A})$ \cite{BodirskyNesetrilJLC}, and there is an analogue of Theorem~\ref{thm:finite-birk}, which however takes into consideration the natural topological structure of $\Pol(\relstr{A})$.

\begin{theorem}[\cite{Topo-Birk}]\label{thm:int}
The following are equivalent for an $\omega$-categorical structure $\relstr{A}$.
\begin{itemize}
\item $\relstr{A}$ pp-interprets all finite structures with parameters.
\item There exists a \emph{continuous} clone homomorphism from $\Pol(\relstr{A},$ $c_1,\ldots,c_n)$ to $\clone{P}$, for some $c_1,\ldots,c_n\in A$.
\end{itemize}
\end{theorem}

More generally, the complexity of $\CSP(\relstr{A})$ for $\omega$-categorical structures provably only depends on the structure of $\Pol(\relstr{A})$ as a topological clone~\cite{Topo-Birk}. A natural, yet unresolved problem when comparing the finite with the $\omega$-categorical setting then
is whether the topological structure of the polymorphism clone is really essential in the infinite, or whether the abstract algebraic structure, i.e., the identities that hold in $\Pol(\relstr{A})$, is sufficient to determine the complexity of the CSP.

\subsection{The result}
We show that the borderline proposed in Conjecture~\ref{conj:dicho} \emph{is} purely algebraic. In particular, if the conjecture is true, then the complexity of CSPs over structures concerned by the conjecture only depends on the identities which hold in the polymorphism clone of their core, rather than the additional topological structure thereof. Moreover, the borderline is characterized by a single
 simple identity generalizing that of~\cite{Sig10}. We show the following.

\begin{theorem}\label{thm:main}
The following are equivalent for an $\omega$-categorical core structure $\relstr{A}$.
\begin{itemize}
\item[(i)] There exists no continuous clone homomorphism $\Pol(\relstr{A},c_1,\ldots,$ $c_n) \rightarrow\clone{P}$, for any $c_1,\ldots,c_n\in\relstr{A}$.
\item[(ii)] There exists no clone homomorphism $\Pol(\relstr{A},c_1,\ldots,c_n)\rightarrow\clone{P}$, for any $c_1,\ldots,c_n\in\relstr{A}$.
\item[(iii)] $\Pol(\relstr{A})$ contains a pseudo-Siggers operation, i.e., a 6-ary operation $s$ such that
\[
\alpha s(x,y,x,z,y,z) \approx \beta s(y,x,z,x,z,y)
\]
for some unary operations $\alpha, \beta \in \Pol(\relstr{A})$.
\end{itemize}
\end{theorem}

Consequently, the missing piece for proving Conjecture~\ref{conj:dicho} can now be stated in purely algebraic terms.

\begin{conjecture} \label{conj:newdicho}
Let $\relstr{A}$ be the core of a reduct of a finitely bounded  homogeneous structure.
If $\Pol(\relstr{A})$ contains a pseudo-Siggers operation, then $\CSP(\relstr{A})$ is solvable in polynomial time.
\end{conjecture}

In a proposed strategy~\cite{Pin15} for solving Conjecture~\ref{conj:dicho}, the first step asked to prove that for an $\omega$-categorical structure $\relstr{A}$, the existence of a clone homomorphism $\Pol(\relstr{A})\rightarrow\clone{P}$ implies the existence of a continuous such homomorphism (cf.~\cite{BPP-projective-homomorphisms}). If this was true, then the failure of the first item of Conjecture~\ref{conj:dicho} would have an algebraic witness, i.e., a non-trivial identity holding in some polymorphism clone $\Pol(\relstr{A},c_1,\ldots,c_n)$. The idea is to then, roughly speaking, ``lift" the algorithm for finite structures whose polymorphism clone satisfies this identity (assuming the finite tractability conjecture is true) via Ramsey theory to show that $\CSP(\relstr{A})$ is tractable.

While we do not answer this question, Theorem~\ref{thm:main} gives an answer for the variant which is actually relevant for the CSP: for an $\omega$-categorical core structure $\relstr A$, the existence of a clone homomorphism $\Pol(\relstr{A})\rightarrow\clone{P}$ implies the existence of a continuous clone homomorphism from \emph{some stabilizer} of $\Pol(\relstr{A})$ to $\clone{P}$. Taking into account the existence of non-continuous clone homomorphisms $\Pol(\relstr{A})\rightarrow\clone{P}$~\cite{BPP-projective-homomorphisms}, for an $\omega$-categorical $\relstr{A}$, as well as the recent discovery of $\omega$-categorical structures $\relstr{A}, \relstr{A}'$ whose polymorphism clones are isomorphic algebraically, but not topologically~\cite{BEKP},
it might very well turn out that the answer to the original question is negative, but, as we would then see a posteriori, irrelevant for CSPs.

Let us also remark that Theorem~\ref{thm:main} is, by the fact that every $\omega$-categorical structure has a unique $\omega$-categorical core, a statement about all $\omega$-categorical structures, rather than only the structures concerned by Conjecture~\ref{conj:dicho}. Theorem~\ref{thm:main} is therefore remarkable in that non-trivial statements about the class of all $\omega$-categorical structures, other than the fundamental theorem of Ryll-Nardzewski, Engeler, and Svenonius characterizing them,  are practically non-existent.

\subsection{Outline and proof strategy}

The strategy for proving Theorem~\ref{thm:main} is similar to the finite analogue of Theorem~\ref{thm:main} proved in~\cite{Sig10} (see also~\cite{KMM14}).
Siggers's reasoning is based on a ``loop lemma'' from Bulatov's paper~\cite{B05} that refines the dichotomy theorem for finite undirected graphs~\cite{HellNesetril}.

After providing definitions and notation in Section~\ref{sect:notation}, we start our proof in Section~\ref{sect:loop} with a generalization of the loop lemma, the \emph{pseudoloop lemma}, using some of the ideas from~\cite{B05}. Instead of finite graphs we work with infinite objects which we call graph-group-systems, and which can be imagined as an infinite permutation group acting on an infinite fuzzy graph, which is a finite graph modulo the action. Theorem~\ref{thm:main} is then derived from the pseudoloop lemma in Section~\ref{sect:main} using a standard universal algebra technique adapted to the $\omega$-categorical setting via a compactness argument.

Section~\ref{sect:disc} at the end of the article contains further discussion of our results in the light of other recent results, in particular from the wonderland of reflections~\cite{wonderland}, as well as inspiration for future work.

\section{Definitions and Notation}\label{sect:notation}

Relational structures are denoted by blackboard bold letters, such as $\relstr{A}$, and their domain by the same letter in the plain font, such as $A$.
By a \emph{graph} we mean a relational structure with a single symmetric binary relation.

\subsection{The range of the infinite CSP conjecture}
A relational structure $\relstr{B}$ is \emph{homogeneous} if every isomorphism between finite induced substructures extends to an automorphism of the entire structure $\relstr{B}$. In that case, $\relstr{B}$ is uniquely determined, up to isomorphism, by its \emph{age}, i.e., the class of its finite induced substructures up to isomorphism. $\relstr{B}$ is \emph{finitely bounded} if its signature is finite and its age is given by a finite set $\forb{F}$ of forbidden finite substructures, i.e., the age consists precisely of those finite structures in its signature which do not embed any member of $\forb{F}$. A \emph{reduct} of a structure $\relstr{B}$ is a structure $\relstr{A}$ on the same domain which is first-order definable without parameters in $\relstr{B}$. Reducts $\relstr{A}$ of finitely bounded homogeneous structures are \emph{$\omega$-categorical}, i.e., the up to isomorphism unique countable model of their first-order theory. Equivalently, their automorphism groups are \emph{oligomorphic}: they have finitely many orbits in their action on $n$-tuples over $\relstr{A}$, for every finite $n\geq 1$.

\subsection{ pp-formulas and interpretations} A formula is \emph{primitive positive}, in short \emph{pp}, if it contains only equalities, existential quantifiers, conjunctions, and atomic formulas -- in our case, relational symbols. A pp-formula \emph{with parameters} can contain, in addition, elements of the domain.

A \emph{pp-interpretation} is a first-order interpretation in the sense of model theory where all the involved formulas are primitive positive:
a structure $\relstr{A}$ \emph{pp-interprets} $\relstr{B}$ if there exists a partial mapping $f$ from a finite power $A^n$ to $B$ such that
the domain of $f$, the $f$-preimage of the equality relation and the $f$-preimage of every relation in $\relstr{B}$ is pp-definable in $\relstr{A}$. In particular, $\relstr{A}$ pp-interprets its substructures induced by pp-definable subsets and also its quotients modulo a pp-definable equivalence relation.

\subsection{Cores} An $\omega$-categorical structure $\relstr{A}$ is a \emph{core}, also called \emph{model-complete core}, if all of its endomorphisms are elementary self-embeddings, i.e., preserve all first-order formulas over the structure. This is the case if and only if its automorphism group is dense in its endomorphism monoid with respect to the pointwise convergence topology on functions on $A$; cf.~Section~\ref{sect:top} for a description of the latter. Two structures $\relstr{A}, \relstr{B}$ are \emph{homomorphically equivalent} if there exist homomorphisms from $\relstr{A}$ into $\relstr{B}$ and vice-versa.

\subsection{Clones}
A \emph{function clone} $\clone{C}$ is a set of finitary operations on a fixed set $C$ which contains all projections and which is closed under composition.
A \emph{polymorphism} of  a relational structure $\relstr{A}$ is a finitary operation $f(x_1,\ldots,x_n)$ on $A$  which \emph{preserves} all relations $R$ of $\relstr{A}$: this means that for all $\tuple{r}_1,\ldots,\tuple{r}_n\in R$ we have that $f(\tuple{r}_1,\ldots,\tuple{r}_n)$, calculated componentwise, is again in $R$. The \emph{polymorphism clone} of $\relstr{A}$, denoted by $\Pol(\relstr{A})$, consists of all polymorphisms of $\relstr{A}$, and is always a function clone. Its unary operations are precisely the endomorphisms of $\relstr{A}$, and its invertible unary operations are precisely the automorphisms of $\relstr{A}$.

A \emph{clone homomorphism} is a mapping from one function clone to another which preserves arities, composition, and which sends every projection of its domain to the corresponding projection of its co-domain. Clone homomorphisms preserve all identities which hold in a function clone, as defined in the introduction.

\subsection{Topology}\label{sect:top}

Function clones carry a natural topology, the topology of \emph{pointwise convergence}, for which a subbasis is given by sets of functions which agree on a fixed finite tuple; the functions of a fixed arity in a function clone form a clopen set. Equivalently, the domain of a function clone is taken to be discrete, and the $n$-ary functions in the clone equipped with the product topology, for every $n\geq 1$; the whole clone is then the sum space of the spaces of $n$-ary functions.

We always understand continuity of clone homomorphisms with respect to this topology.

The function clones which are closed in the topology of pointwise convergence are precisely the polymorphism clones of relational structures.

\subsection{Core clones and oligomorphicity}

We say that a closed function clone is a \emph{core}
if  it is the polymorphism clone of a core.

A function clone $\clone{C}$ is \emph{oligomorphic} if and only if  the permutation group $\clgr{\clone{C}}$ of unary invertible elements of $\clone{C}$ is oligomorphic. When $\clone{C}$ is closed, then this is the case if and only if it is the polymorphism clone of an $\omega$-categorical structure, in which case $\clgr{\clone{C}}$ consists of the automorphisms of that structure.

Note that when $\clone{C}$ is a core, then the set of its unary operations is the closure of $\clgr{\clone{C}}$.

\subsection{Pseudo-Siggers operations} A 6-ary operation $s$ in a function clone $\clone{C}$ is a \emph{pseudo-Siggers operation} if there exist unary $\alpha, \beta \in \clone{C}$
such that $\alpha s(x,y,x,z,y,z) \approx \beta s(y,x,z,x,z,y)$ holds  (where $\approx$ means that equality holds for all values for the variables in $C$). We then also say that $s$ \emph{satisfies} the pseudo-Siggers identity.

\section{The Pseudoloop Lemma}\label{sect:loop}

The following definition is a generalization of finite graphs to the $\omega$-categorical which is suitable for our purposes.

\begin{definition}\label{defn:gg}
A \emph{graph-group-system}, in short \emph{gg-system}, is a pair $(\relstr{G},\group{G})$, where $\group{G}$ is a permutation group on a set $G$, and $\relstr{G}=(G;R)$ an (undirected) graph which is invariant under $\group{G}$. We also write $(R,\group{G})$ for the same gg-system.

The system is called \emph{oligomorphic} if $\group{G}$ is; in that case, $\relstr{G}$ is $\omega$-categorical, since its automorphism group contains $\group{G}$ and hence is oligomorphic.

The system \emph{pp-interprets (pp-defines)} a structure $\relstr{B}$ if $\relstr{G}$ together with the orbits of $\group{G}$ on finite tuples does.

A \emph{pseudoloop} of a gg-system $(\relstr{G},\group{G})$ is an edge of $\relstr{G}$ of the form $(a,\alpha(a))$, where $\alpha\in\group{G}$.
\end{definition}

Note that $R$, as well as any relation that is first-order definable from a gg-system $(\relstr{G},\group{G})$, is invariant under the natural action of $\group{G}$ on tuples. In particular, such relations are unions of orbits of the action of $\group{G}$ on tuples, and
when $\group{G}$ is oligomorphic, then there are only finite many first-order definable relations of any fixed arity.

We are now ready to state our pseudoloop lemma for gg-systems.

\begin{lemma}[The pseudoloop lemma]\label{lem:loop}
Let $(\relstr{G},\group{G})$ be an oligomorphic gg-system, where $\relstr{G}$ has a subgraph isomorphic to $\relstr{K}_3$. Then either it {pp}-interprets $\relstr{K}_3$ with parameters, or it contains a pseudoloop.
\end{lemma}

For the proof of Lemma~\ref{lem:loop}, we need the following auxiliary definitions.

\begin{definition}
Let $(\relstr{G},\group{G})$ be a gg-system. The \emph{support} of $(\relstr{G},\group{G})$ are those elements of its domain which are contained in an edge.

For $a_1,\ldots,a_n \in G$, we denote by $O(a_1,\ldots,a_n)$ the orbit of the tuple $(a_1,\ldots,a_n)$ under $\group{G}$.
\end{definition}

The support of a gg-system $(\relstr{G},\group{G})$ is a union of $\group{G}$-orbits by the remark below Definition~\ref{defn:gg}. This justifies the following definition.

\begin{definition}
A pseudoloop-free gg-system $(\relstr{G},\group{G})$ containing a $\relstr{K}_3$ is \emph{minimal} if it does not pp-define a symmetric relation $R'$ on $G$ such that $(R',\group{G})$ is a pseudoloop-free gg-system containing a $\relstr{K}_3$ whose support consists of fewer orbits.
\end{definition}

We can now prove the pseudoloop lemma.

\begin{proof}[Proof of Lemma~\ref{lem:loop}]
Assuming that a gg-system $(\relstr{G},\group{G})$, where $\relstr{G} = (G;R)$, has no pseudoloop, we show that it {pp}-interprets $\relstr{K}_3$ with parameters. \bigskip

\noindent \textit{Step 0}: If $(\relstr{G},\group{G})$ is not minimal, then we can replace it by a minimal gg-system. We thus henceforth assume that it is minimal.\bigskip

\noindent \textit{Step 1}: $R$ pp-defines a symmetric binary relation $R'$ with the property that every edge of $R'$ is contained in a $\relstr{K}_3$, i.e.,  every element of $R'$ is contained in an induced  subgraph of $(G;R')$ isomorphic to $\relstr{K}_3$, and which still shares our assumptions on $R$:
$$
R'(x,y):\leftrightarrow \exists z\; R(x,y)\wedge R(x,z)\wedge R(y,z).
$$
Hence, replacing $R$ by $R'$, we henceforth assume that every edge of $R$ is contained in a $\relstr{K}_3$.\bigskip

\noindent
In the following, for $n\geq 1$ we say that $x,y\in G$ are \emph{$n$-diamond-connected}, denoted by $x\sim_n y$, if there exist $a_1$, $b_1$, $c_1$, $d_1$, $\ldots$, $a_n$, $b_n$, $c_n$, $d_n\in G$ such that, for every $1\leq i\leq n$, both $a_i,b_i,c_i$ and $b_i,c_i,d_i$ induce $\relstr{K}_3$,
$x=a_1$, $d_1=a_2$, $d_2=a_3$, \dots, $d_{n-1} = a_{n}$, and $d_n=y$. They are \emph{diamond-connected}, denoted by $x\sim y$, if they are $n$-diamond-connected for some $n\geq 1$.

Observe that $\sim_n$  is a pp-definable relation from $R$ (since our definition is in fact a pp-definition). Also recall that there are only finitely many binary relations first-order definable from $R$, and note that if $x,y$ are $n$-diamond-connected, then they are $m$-diamond-connected for all $m\geq n$. Therefore, there exists an $n\geq 1$ such that $x,y$ are diamond-connected if and only if they are $n$-diamond connected. In particular, the relation $x\sim y$ is pp-definable in $\relstr{G}$. Note also that it is an equivalence relation on the support of $R$: it is clearly transitive and symmetric, and it is reflexive since on the support every vertex is contained in a $\relstr{K}_3$, by Step~1.\bigskip

\noindent \textit{Step 2}: We claim that if $x, y\in G$ are $n$-diamond-connected for some $n \geq 1$, then $\neg R(x,y')$ for all $y'\in O(y)$. Otherwise, pick a counterexample $x,y,y'$ with minimal $n\geq 1$.

Suppose first that $n$ is odd and set $k := \frac{n-1}{2}$. Let $a$ be the $a_{k+1}$ from the chain of diamonds witnessing $x\sim_n y$.
Consider the following pp-definition over $(\relstr{G},\group{G})$:
$$
S(w):\leftrightarrow \exists u,v\;(u\in O(a)\wedge u\sim_{k} v\wedge R(v,w))\; ;
$$
in case that $k=0$ we replace $\sim_k$ by the equality relation. Then clearly $S(b_n)$ and $S(c_n)$. But we also have $S(y)$, since $S(y')$ holds by virtue of $a\sim_k x$ and $R(x,y')$ and since $y$ is in the same orbit as $y'$.
Hence, since $d_n=y$, we have $S(d_n)$ and so $S$ contains a $\relstr{K}_3$.
By the minimality of $(\relstr{G},\group{G})$ (see Step~0), it contains $x$, for otherwise we could intersect $R$ with $S^2$ and obtain a relation whose support consists of a smaller number of orbits. Let $u, v\in G$ as in the definition of $S$ witness that $S(x)$ holds. Then $u\sim _{k} v$, but also $u\sim_{k} x'$ for some $x'\in O(x)$, as $a \sim_k x$, $u \in O(a)$, and $\sim_k$ is invariant under $\group{G}$. Therefore, $v\sim_{n-1} x'$, which together with  $R(v,x)$ contradicts the minimality of $n$ when $n\geq 3$; when $n=1$, this means that we have discovered a pseudoloop of $(\relstr{G},\group{G})$, again a contradiction.

Suppose now that $n$ is even and denote $k = \frac{n}{2}-1$; the argument is similar.
Let $b,c$ be the $b_{k+1}, c_{k+1}$ from the chain of diamonds witnessing $x\sim_n y$.
Consider the following pp-definition:
\begin{align*}
S(w):\leftrightarrow \exists & u_b,u_c,u,v\;((u_b,u_c)\in O(b,c)\wedge \\
  & R(u,u_c)\wedge R(u,u_b)\wedge u\sim_{k} v\wedge R(v,w))\; .
\end{align*}
Then as in the odd case, $S(b_n), S(c_n), S(d_n)$, and so the set defined by $S$ contains a $\relstr{K}_3$.
By the minimality of $(\relstr{G},\group{G})$, it contains $x$; let $u_b,u_c,u,v\in G$ as in the definition of $S$ witness this. Then $u\sim _{k} v$, but also
 $u\sim _{k+1} x'$ for some $x'\in O(y)$. Hence, $v\sim_{n-1} x'$ and $R(v,x)$ contradict the minimality of $n$.\bigskip

 \noindent \textit{Step 3}: Defining
 $$
 R'(x,y):\leftrightarrow \exists x', y'\; (x\sim x'\wedge y\sim y'\wedge R(x',y'))
 $$
 we obtain a relation $R'\supseteq R$ which does not contain a pseudoloop. Indeed,
if $R'(x,y)$ is witnessed by $x',y'$ and $x$ and $y$ are in the same orbit, then
$x \sim y''$ for some $y'' \in O(y')$ since $y\in O(x)$ and since $\sim$ is invariant under $\group{G}$. Thus $x' \sim y''$ and $R(x',y')$, a contradiction with Step~2.
Moreover, every edge in $R'$ is contained in a $\relstr{K}_3$: if $z'$ is so that $\{x',y',z'\}$ induce a $\relstr{K}_3$ in $R$,
then $\{x,y,z'\}$ induce a $\relstr{K}_3$ in $R'$, for $z'\sim z'$ and $x\sim x'$ imply $R'(x,z')$, and similarly we infer $R'(y,z')$.

Therefore, we may replace $R$ by $R'$. If this replacement changes the equivalence $\sim$, we repeat Step 3.
Since the relation $R$ gets bigger after each step and $\group{G}$ is oligomorphic, this process stabilizes after finitely many steps.
\bigskip

\noindent \textit{Step 4}:
Now $R$ is in fact a relation between equivalence classes of $\sim$ and the naturally defined quotient gg-system $(\relstr{G}^q,\group{G}^q)$ on $G^q = G/\sim$ contains neither pseudoloops (by Step~3), nor \emph{diamonds}, that is, there do not exist distinct $a,b,c,d \in G^q$ such that $\{a,b,c\}$ and $\{b,c,d\}$ both induce a $\relstr{K}_3$.
Moreover, every edge of $\relstr{G}^q$ is still contained in a $\relstr{K}_3$.
We replace the gg-system $(\relstr{G},\group{G})$ by $(\relstr{G}^q,\group{G}^q)$.

If this new gg-system was not minimal, we could repeat the whole proof starting from Step 0. In each reiteration, Step 0 decreases the number of orbits in the support, while no other step increases it, so this process will terminate after a finite number of steps, and we will end up with a minimal gg-system after Step~4 eventually. The first author insists to remark that this process is in fact unnecessary, as the gg-system is already minimal after the first round of Steps~0 to~4: if after factoring it did pp-define a relation whose support consists of less $\group{G}^q$-orbits,
then the syntactically same pp-definition would show that the original gg-system was not minimal.

\bigskip

\noindent
Whichever solution we prefer, summarizing we end up with a gg-system $(\relstr{G},\group{G})$ which is minimal, pseudoloop-free, and diamond-free; still, every edge of $\relstr{G}$ is contained in a $\relstr{K}_3$.
\bigskip

\noindent \textit{Step 5}: For $k\geq 1$, we denote the $k$-th power of $\relstr{K}_3$ by $\relstr{T}_k$.
By Lemma~\ref{lem:Tk_bound} shown below, there exists an $m\geq 1$ such that, for any $k \geq m$, $\relstr{G}$ has no induced subgraph isomorphic to $\relstr{T}_k$.\bigskip

\noindent \textit{Step 6}: Recall that $\relstr{G}$ contains $\relstr{T}_1 = \relstr{K}_3$. By Step 5, there exists a maximal $k\geq 1$ such that $\relstr{G}$ contains an induced subgraph isomorphic to $\relstr{T}_k$.
Let $k$ be that number and let $a_1, \dots, a_l$, where $l = |T_k| = 3^{k}$, denote the vertices of such an induced subgraph.
We show that $\relstr{G}$ pp-defines the set $A = \{a_1, \dots, a_l\}$ with parameters $a_1,\ldots,a_l$.

By~\cite{BodirskyNesetrilJLC}, this is the case if each $l$-ary operation $f$ in $\Pol(\relstr{G},a_1, \dots, a_l)$ preserves $A$. So, suppose that such a function $f$ does not preserve $A$.
Now, $f$ is a homomorphism $\relstr{G}^l \rightarrow \relstr{G}$ and its restriction to $A$ is a homomorphism $f'$ from $\relstr{T}_k$ to the diamond-free graph $\relstr{G}$ whose image, which contains $A$ because $f$ stabilizes each $a_i$, is strictly larger than $|T_k|$. \cite[Claim 3, Subsection 3.2]{B05} shows that the image of $f'$ induces a graph isomorphic to $\relstr{T}_m$ for some $m > k$, a contradiction.\bigskip

\noindent \textit{Step 7}: Step 6 implies that $\relstr{G}$ pp-interprets $\relstr{T}_k$ with parameters. But $\relstr{K}_3$ can be pp-interpreted in $\relstr{T}_k$ with parameters by the final sentence of~\cite{B05}.
\end{proof}

\begin{lemma}\label{lem:Tk_bound}
Let $(\relstr{G},\group{G})$ be an oligomorphic gg-system containing a $\relstr{K}_3$ and having no pseudoloops, and assume the system is minimal.
Then $\relstr{G}$ has no induced subgraph isomorphic to $\relstr{T}_k$ for any $k\geq 1$ where $|T_k|=3^{k}$  exceeds the number of orbits of $\group{G}$.\bigskip
\end{lemma}
\begin{proof}
Suppose there exists a counterexample $(\relstr{G},\group{G})$, where $\relstr{G}=(G;R)$.
We may assume without loss of generality that every edge of $\relstr{G}$ is contained in a $\relstr{K}_3$ by keeping only those which are, as in Step~1 of the proof of Lemma~\ref{lem:loop}.
Under those assumptions, we pp-define in $(\relstr{G},\group{G})$ a symmetric relation $R'\supsetneq R$ without pseudoloops in which every edge is still contained in a $\relstr{K}_3$, and such that the support of $(R',\group{G})$ equals the support of $(R,\group{G})$. Repeating this process, by oligomorphicity we must after finitely many steps arrive at a gg-system $(R',\group{G})$ which is not minimal. Hence, $(\relstr{G},\group{G})$ was not minimal in the first place, a contradiction.

Fix a copy of $\relstr{T}_k$ in $\relstr{G}$, the elements of which we denote by tuples in $\{1,2,3\}^k$. So, two vertices in $\{1,2,3\}^k$ are adjacent if and only if they differ in every coordinate.
From the cardinality assumption, we can pick two elements $\tuple{a},\tuple{a}'$ of the copy that belong to the same orbit $A$. Let $\tuple{b},\tuple{c}$ in the copy be so that $\{\tuple{a},\tuple{b},\tuple{c}\}$ induce a $\relstr{K}_3$, and let $B,C$ be their orbits. Since $(\relstr{G},\group{G})$ has no pseudoloops, the three orbits $A,B,C$ are distinct. Without loss of generality, assume $\tuple{a}=1^k$ (i.e., the $k$ tuple all of whose entries equal $1$), $\tuple{b}=2^k$, and $\tuple{c}=3^k$.

 Define a relation
\begin{align*}
	S(u,v):\leftrightarrow \exists & a'',b'',c'', n_A,n_B,n_C \; \\
	&(R(u,n_A)\wedge R(v,n_A)\wedge R(n_A,a'')\wedge a''\in A\; \wedge\\
	& R(u,n_B)\wedge R(v,n_B)\wedge R(n_B,b'')\wedge b''\in B\; \wedge\\
	& R(u,n_C)\wedge R(v,n_C)\wedge R(n_C,c'')\wedge c''\in C)\; .
\end{align*}
In words, $u,v$ have common neighbors adjacent to elements in $A, B,$ and $C$.

The relation $S$ is obviously symmetric. It is also reflexive on the support of $(\relstr{G},\group{G})$: every element of the support is a neighbor of a neighbor of an element in $A$, and similarly in $B$ and $C$, by the minimality of $(\relstr{G},\group{G})$; otherwise, we could restrict $R$ to neighbors of neighbors of $A$, a set which contains $A\cup B\cup C$; we would therefore obtain a smaller support gg-system containing a $\relstr{K}_3$, namely the one induced by $\{\tuple{a},\tuple{b},\tuple{c}\}$.

Observe that whenever $S(u,v)$ holds, then every element of the support of  $(\relstr{G},\group{G})$ is adjacent to a common neighbor of $O(u)$ and $O(v)$: this follows as above from the minimality of $(\relstr{G},\group{G})$ since the elements of  $A\cup B \cup C$ are adjacent to a common neighbor of $O(u)$ and $O(v)$.

Set
$$
Q(u,v):\leftrightarrow \exists s\; (R(u,s)\wedge S(s,v))\; \wedge\; \exists t\; (S(u,t)\wedge R(t,v))\; .
$$
Then $Q\supseteq R$: since $S$ is reflexive on the support of $(\relstr{G},\group{G})$, setting $s=v$ and $t=u$ in the above definition shows that $R(u,v)$ implies $Q(u,v)$. Moreover, $Q$ is symmetric by definition. Let $R'$ consist of those edges of $Q$ which are contained in a $\relstr{K}_3$ with respect to $Q$. We still have that $R'\supseteq R$.

We now show that $(Q,\group{G})$, and thus $(R',\group{G})$, has no pseudoloop. To this end, it suffices to show that whenever $R(u,v)$ holds, then we cannot have $S(u,v')$ for any $v'\in O(v)$. Suppose to the contrary that there exist such elements.
The $R$-edge $(u,v)$ is contained in a $\relstr{K}_3$, induced by $\{u,v,w\}$, for some $w\in G$.
As observed above, each vertex, in particular the vertex $w$, is adjacent to a common neighbor of $O(u)$ and $O(v')=O(v)$.
Therefore, there exists a common neighbor $z$ of $O(u)$, $O(v)$ and $O(w)$.
The set of neighbors of $O(z)$ contains $O(u), O(v)$, and $O(w)$; it is a proper subset of $G$ since $(\relstr{G},\group{G})$ has no pseudoloops; it is pp-definable in $(\relstr{G},\group{G})$; and finally, it contains a $\relstr{K}_3$, contradicting the minimality of $(\relstr{G},\group{G})$.

Using for the first time the copy of $\relstr{T}_k$ in $\relstr{G}$, we now show that $R$ is properly contained in $R'$ by showing that $\tuple{a}'$, the second element of the copy of $\relstr{T}_k$ in the orbit $A$ of $\tuple{a}$, is related to $\tuple{b}$ and $\tuple{c}$ via $R'$. Note that this is sufficient since in $\relstr{T}_k$, no two distinct elements are related to both $\tuple{b}$ and $\tuple{c}$.
We show only $R'(\tuple{a}',\tuple{b})$, the second claim is analogous.
Reordering the tuples when necessary, we may assume that $a'_i\neq 2$ for all $1\leq i\leq j$, and $a'_i= 2$ for all $j<i\leq k$. Since $\tuple{a}'\neq \tuple{b}$, we have $j\geq 1$.
Observe that whenever $\tuple{u}, \tuple{v} \in \{1,2,3\}^k$ are of the form $(x,\ldots,x,2,\ldots,2)$ and $(x,\ldots,x,3,\ldots,3)$, respectively, where the number of occurences of $x$ equals $j$, then $S(\tuple{u},\tuple{v})$: this is witnessed by their common neighbor $(y_1,\ldots,y_j,1,\ldots,1)$, where $y_i\notin\{a'_i,x\}$ for all $1\leq i\leq j$, which is $R$-related to $\tuple{a}'\in A$; their common neighbor $(z,\ldots,z,1,\ldots,1)$, starting with $j$ occurrences of $z\notin\{2,x\}$, which is $R$-related to $\tuple{b}\in B$; and their common neighbor $(w,\ldots,w,1,\ldots,1)$, starting with $j$ occurrences of $w\notin\{3,x\}$, which is $R$-related to $\tuple{c}\in C$. But now we see that $Q(a',b)$ holds: setting $\tuple{t} = (a_1',\ldots,a_j',3,\ldots,3)$,
we have $S(\tuple{a}',\tuple{t})$ and $R(\tuple{t},\tuple{b})$; on the other hand, setting $\tuple{s}:=(2,\ldots,2,3,\ldots,3)$, with $j$ occurrences of $2$, we have $R(\tuple{a}',\tuple{s})$ and $S(\tuple{s},\tuple{b})$. We can then conclude that $R'(\tuple{a}',\tuple{b})$ holds, since any two elements of $\{1,2,3\}^k$, in particular $\tuple{a}'$ and $\tuple{b}$, have a common neighbor with respect to $R$, and hence also with respect to $Q$, showing that the $Q$-edge $(\tuple{a}',\tuple{b})$ is contained in a $\relstr{K}_3$ with respect to $Q$.

\end{proof}

\section{Proof of the main result} \label{sect:main}

In order to derive Theorem~\ref{thm:main}, we will produce pseudo-Siggers operations locally using the pseudoloop lemma, and then derive a global pseudo-Siggers operation via a compactness argument.

\begin{definition}
We say that a function clone $\clone{C}$ has \emph{local pseudo-Siggers operations} if for every finite $A\subseteq C$ there exists a $6$-ary $s\in\clone{C}$ and unary $\alpha, \beta \in\clone{C}$ satisfying
\[
\alpha s(x,y,x,z,y,z) = \beta s(y,x,z,x,z,y)
\]
for all $x,y,z \in A$.
\end{definition}

\begin{lemma}\label{lem:localglobal}
Let $\clone{C}$ be a closed oligomorphic function clone. If it has local pseudo-Siggers operations, then it has a pseudo-Siggers operation.
\end{lemma}
\begin{proof}
Let $A_0\subseteq A_1\subseteq\cdots$ be a sequence of finite subsets of $C$ whose union equals $C$, and pick for every $i\in \omega$ a $6$-ary operation $s_i\in\clone{C}$ witnessing the definition of local pseudo-Siggers operations on $A_i$, i.e., there exist unary $\alpha_i,\beta_i\in\clone{C}$ such that $\alpha_i s_i(x,y,x,z,y,z) = \beta_i s_i(y,x,z,x,z,y)$ for all $x,y,z\in A_i$.
 Note that if  $s_i$ is such a witness for $A_i$, then so is $\gamma s_i$, for all $\gamma\in\clgr{\clone{C}}$. Hence, because $\clgr{\clone{C}}$ is oligomorphic,  we may thin out the sequence in such a way that $s_j$ agrees with $s_i$ on $A_i$, for all $j>i\geq 0$. We briefly describe this standard compactness argument for the convenience of the reader: there exists a smallest $j_0\geq 0$ such that for infinitely many $k\geq j_0$ there exists $\gamma_k\in\clgr{\clone{C}}$ such that $\gamma_k s_k$ agrees with $s_{j_0}$ on $A_0$, by oligomorphicity. Replace $s_0$ by $s_{j_0}$, all $s_k$ as above by $\gamma_k s_k$, and remove all other $s_{k'}$ where $k'\geq 0$ from the sequence. Next repeat this process picking $j_1\geq 1$ for $A_1$, and so on. This completes the argument.

Since the elements of the sequence $(s_i)_{i\in\omega}$ agree on every fixed $A_i$ eventually, and since $\clone{C}$ is closed, they converge to a function $s\in \clone{C}$. The function $s$, restricted to any $A_i$, witnesses local pseudo-Siggers operations on $A_i$, i.e., there exist unary $\alpha_i,\beta_i\in\clone{C}$ such that $\alpha_i s(x,y,x,z,y,z) = \beta_i s(y,x,z,x,z,y)$ for all $x,y,z\in A_i$. By a similar compactness argument as above, there exist
unary functions $\alpha,\beta\in\clone{C}$ such that $\alpha s(x,y,x,z,y,z) = \beta s(y,x,z,x,z,y)$ for all $x,y,z\in C$.
\end{proof}

We now consider gg-systems where the group $\clgr{\clone{C}}$ of a closed oligomorphic function clone $\clone{C}$ acts on finite powers of its domain.

\begin{lemma}\label{lem:1}
Let $\clone{C}$ be a closed oligomorphic function clone. Suppose that every gg-system $(\relstr{G},\group{G})$ where
\begin{itemize}
\item $\relstr{G}=(C^k;R)$ for some $k\geq 1$,
\item $\group{G}$ corresponds to the componentwise action of $\clgr{\clone{C}}$ on $C^k$,
\item $\relstr{G}$ contains $\relstr{K}_3$, and
\item $R\subseteq C^{2k}$ is invariant under $\clone{C}$
\end{itemize}
has a pseudoloop. Then $\clone{C}$ has a pseudo-Siggers operation.
\end{lemma}
\begin{proof}
We show that $\clone{C}$ has local pseudo-Siggers operations and apply Lemma~\ref{lem:localglobal}. Let $A\subseteq C$ be finite, and pick $k\geq 1$ and $\tuple{a}^x,\tuple{a}^y,\tuple{a}^z\in A^k$ such that the rows of the $(k\times 3)$-matrix $(\tuple{a}^x,\tuple{a}^y,\tuple{a}^z)$ form an enumeration of $A^3$. Let $R$ be the binary relation on $C^k$ where tuples $\tuple{b},\tuple{c}\in C^k$ are related via $R$ if there exists a $6$-ary $s\in \clone{C}$ such that $\tuple{b}=s(\tuple{a}^x,\tuple{a}^y,\tuple{a}^x,\tuple{a}^z,\tuple{a}^y,\tuple{a}^z)$ and $\tuple{c}=s(\tuple{a}^y,\tuple{a}^x,\tuple{a}^z,\tuple{a}^x,\tuple{a}^z,\tuple{a}^y)$.
In other words, it is the $\clone{C}$-invariant  subset of $(2k)$-tuples generated by the six vectors obtained by concatenating $\tuple{a}^u$ and $\tuple{a}^v$, where $u,v\in\{x,y,z\}$ are distinct. The latter description reveals that $R$ is a symmetric relation on $C^k$ invariant under $\clone{C}$ and containing $\relstr{K}_3$, therefore the gg-system $(R,\group{G})$, where $\group{G}$ is the componentwise action of $\clgr{\clone{C}}$ on $C^k$,  has a pseudoloop $(\tuple{b},\tuple{c})$. That means that there exists a $6$-ary $s\in \clone{C}$ and $\alpha \in\clgr{\clone{C}}$ such that $s(\tuple{a}^x,\tuple{a}^y,\tuple{a}^x,\tuple{a}^z,\tuple{a}^y,\tuple{a}^z)=\alpha s(\tuple{a}^y,\tuple{a}^x,\tuple{a}^z,\tuple{a}^x,\tuple{a}^z,\tuple{a}^y)$, proving the claim.
\end{proof}

\begin{corollary}\label{cor:K3-Siggers}
Let $\relstr{A}$ be an $\omega$-categorical core. Then either it pp-interprets $\relstr{K}_3$ with parameters, or $\Pol(\relstr{A})$ has a pseudo-Siggers operation.
\end{corollary}
\begin{proof}
We apply Lemma~\ref{lem:1} to the clone $\clone{C}:=\Pol(\relstr{A})$; then $\clgr{\clone{C}}$ consists precisely of the automorphisms of $\relstr{A}$.
If the assumptions of this lemma are satisfied, then $\clone{C}$ has a pseudo-Siggers operation.
Otherwise, there exists a pseudoloop-free gg-system $((C^k;R),\group{G})$ satisfying the four conditions. By Lemma~\ref{lem:loop}, this gg-system pp-interprets $\relstr{K}_3$ with parameters.  Since $R$ is invariant under $\clone{C}$, it is pp-definable from $\relstr{A}$ by~\cite{BodirskyNesetrilJLC}. Moreover, since $\relstr{A}$ is a core, the orbits of $\group{G}$ are pp-definable from $\relstr{A}$ as well by~\cite{Bodirsky-HDR}. It follows that $\relstr{A}$ pp-interprets $\relstr{K}_3$ with parameters, as required.
\end{proof}

We are now ready to prove Theorem~\ref{thm:main}.

\begin{proof}[Proof of Theorem~\ref{thm:main}]
We first prove that (iii) implies (ii).
Take $\alpha,\beta,s \in \Pol(\relstr{A})$ satisfying the pseudo-Siggers identity. We claim that every stabilizer $\Pol(\relstr{A},c_1,\dots, c_n)$ has a pseudo-Siggers operation. To see that, consider the endomorphisms $\gamma,\delta$ of $\relstr{A}$ defined by $\gamma(x)=s(x,\dots,x)$, $\delta(x) = \alpha\gamma(x)$ ($=\beta\gamma(x)$ by the pseudo-Siggers identity). Because $\relstr{A}$ is a core, its automorphisms are dense in endomorphisms, thus there exist automorphisms $\epsilon, \theta$ of $\relstr{A}$ such that $\epsilon(c_i) = \gamma(c_i)$ and $\theta(c_i) = \delta(c_i)$ for every $i$. But then $\theta^{-1}\alpha\epsilon$, $\theta^{-1}\beta\epsilon$ and $\epsilon^{-1}s$ are contained in $\Pol(\relstr{A},c_1, \dots, c_n)$ and satisfy
\[
(\theta^{-1}\alpha\epsilon)(\epsilon^{-1}s)(x,y,x,z,y,z) \approx (\theta^{-1}\beta\epsilon)(\epsilon^{-1}s)(y,x,z,x,z,y).
\]

The implication from (ii) to (i) is trivial.

Finally, assume that no stabilizer of $\Pol(\relstr{A})$ has a continuous homomorphism to $\clone{P}$. Then no such stabilizer has a continuous clone homomorphism to $\Pol(\relstr{K}_3)$ since it is well-known that the latter clone has a continuous homomorphism to $\clone{P}$.
By Theorem~\ref{thm:int}, $\relstr{A}$ does not pp-interpret $\relstr{K}_3$ with parameters. Corollary~\ref{cor:K3-Siggers} then tells us that $\Pol(\relstr{A})$ has a pseudo-Siggers operation.
\end{proof}

\section{Discussion}\label{sect:disc}

Our main theorem can be used as a tool for proving hardness: If an $\omega$-categorical core structure $\relstr{A}$ does not have a pseudo-Siggers polymorphism, then $\relstr{A}$ interprets all finite structures with parameters by the combination of Theorem~\ref{thm:main} and Theorem~\ref{thm:int}, and therefore $\CSP(\relstr{A})$ is $\mathrm{NP}$-hard. The pseudoloop lemma itself can be regarded as a hardness result as well:

\begin{corollary}
Let $\relstr{A}$ be an $\omega$-categorical core structure.
If $\relstr{A}$ pp-defines with parameters a pseudoloop-free graph containing a $\relstr{K}_3$, then $\CSP(\relstr{A})$ is $\mathrm{NP}$-hard.
\end{corollary}

Recall that a digraph is \emph{smooth} if each vertex has an incoming and an outgoing edge, and a digraph has \emph{algebraic length 1} if it contains a closed walk with one more forward edges than backward edges.
The finite loop lemma for graphs~\cite{HellNesetril,B05} has been generalized to finite smooth digraphs with algebraic length $1$ in~\cite{BartoKozikNiven,Cyclic}. We conjecture that the pseudoloop lemma can be generalized to such digraphs as well.

\begin{conjecture}~\label{conj:loop}
Let $\group{G}$ be an oligomorphic permutation group on $G$ and let $\relstr{G}$ be a countable smooth digraph of algebraic length $1$ on $G$ which is  invariant under $\group{G}$. Then either $\relstr{G}$ contains a pseudoloop, or $\relstr{G}$ together with the orbits of $\group{G}$ on finite tuples pp-interprets $\relstr{K}_3$ with parameters.
\end{conjecture}

As intermediate steps we suggest the following stronger assumptions on $\relstr{G}$.
\begin{itemize}
\item[(a)] $\relstr{A}$ is a non-bipartite graph;
\item[(b)] $\relstr{A}$ is a digraph containing
\[
(\{a,b,c\}; \{(a,b),(b,c),(c,a),(b,a)\})
\]
as a subgraph (not necessarily induced);
\item[(c)] $\relstr{A}$ is a strongly connected digraph of algebraic length $1$ (equivalently, the GCD of the length of cycles is $1$).
\end{itemize}
A positive answer to Conjecture~\ref{conj:loop} under the assumption (b) or (c) would allow a strengthening of item (iii) of Theorem~\ref{thm:main} to a $4$-variable pseudo-Siggers operation $\alpha s(r,a,r,e) \approx \beta s(a,r,e,a)$ (see~\cite{Sig10,KMM14}).
Another open problem is whether it is possible to replace item (iii) of Theorem~\ref{thm:main} by pseudo-weak-near-unanimity operations (see~\cite{MM08}).
On the negative side, it has been observed that the CSP classification for the  reducts of $(\relstr{Q};<)$ shows that
the syntactically strongest characterization of (iii) in Theorem~\ref{thm:main} in the finite case by means of cyclic operations~\cite{Cyclic} cannot be lifted to the infinite, at least not in the straightforward way of adding unary functions.

Our final remarks concern a new dichotomy conjecture that has been formulated for CSPs of reducts of finitely bounded homogeneous structures~\cite{wonderland}. An \emph{h1 clone homomorphism} is a mapping from one function clone to another which preserves arities and composition with projections (equivalently, preserves identities of height $1$). When the polymorphism clone of an $\omega$-categorical structure has a uniformly continuous h1 clone homomorphism to $\clone{P}$, then its CSP is $\mathrm{NP}$-hard. The conjecture states that the reducts of finitely bounded homogeneous structures whose polymorphism clone does not have such a mapping have  polynomial-time solvable CSP.
The following corollary summarizes all we know so far about various clone homomorphisms to the clone of projections. In particular, it shows that the new conjecture is ``better'' in that it is implied by Conjecture~\ref{conj:dicho} (but not necessarily vice-versa).

\begin{corollary}
Consider the following statements for an $\omega$-categorical core $\relstr{A}$.
\begin{enumerate}
\item[(1)] $\Pol(\relstr{A})$ has a uniformly continuous clone homomorphism to $\clone{P}$.
\item[(1')] $\Pol(\relstr{A})$ has a continuous clone homomorphism to $\clone{P}$.
\item[(2)] $\Pol(\relstr{A})$ has a clone homomorphism to $\clone{P}$.
\item[(3)] Some $\Pol(\relstr{A},c_1,\ldots,c_n)$ has a clone homomorphism to $\clone{P}$.
\item[(3')] Some $\Pol(\relstr{A},c_1,\ldots,c_n)$ has a continuous clone homomorphism to $\clone{P}$.
\item[(3'')] Some $\Pol(\relstr{A},c_1,\ldots,c_n)$ has a uniformly continuous clone homomorphism to $\clone{P}$.
\item[(4)] Some $\Pol(\relstr{A},c_1,\ldots,c_n)$ has a uniformly continuous  h1 clone homomorphism to $\clone{P}$.
\item[(4')] $\Pol(\relstr{A})$ has a uniformly continuous  h1 clone homomorphism to $\clone{P}$.
\item[(5)] $\Pol(\relstr{A})$ has a continuous  h1 clone homomorphism to $\clone{P}$.
\item[(5')] Some $\Pol(\relstr{A},c_1,\ldots,c_n)$ has a continuous  h1 clone homomorphism to $\clone{P}$.
\item[(6)] $\Pol(\relstr{A})$ has an  h1 clone homomorphism to $\clone{P}$.
\item[(6')] Some $\Pol(\relstr{A},c_1,\ldots,c_n)$ has an  h1 clone homomorphism to $\clone{P}$.
\end{enumerate}
Then all statements with equal number are equivalent, and (i) implies (j) for all $1\leq i\leq j\leq 6$.
\end{corollary}
\begin{proof}
It is clear that the strength of the statements is decreasing; the only non-trivial part are the equivalences.
(1) and (1') are equivalent by the proof in~\cite{Topo-Birk} (cf.~\cite{GPin15} for an explicit proof thereof). (3) and (3') are equivalent by Theorem~\ref{thm:main}, and (3') and (3'') again by the proof in~\cite{Topo-Birk}. (4) and (4'), (5) and (5'), as well as (6) and (6') are equivalent by~\cite{wonderland}.
\end{proof}

We remark that (4) is the weakest condition known to imply NP-hardness of the CSP.

An example communicated to us by Ross Willard shows that the implication from (2) to (3) cannot be reversed, even for finite $\relstr{A}$; another example is known among the reducts of $(\mathbb Q;<)$. For all remaining implications, no counterexamples are known. The implication from (2) to (1) is conjectured in~\cite{BPP-projective-homomorphisms}, the implication from (4) to (3) would, if true, imply that the two conjectures are equivalent.
The most optimistic speculation would be that (6) implies (3). A positive answer would show that both conjectures can be true and yield a particularly esthetically pleasing --- core-free, topology-free, and without identities of height greater than $1$ --- formulation of the tractability conjecture.

\bibliographystyle{alpha}


\section{Introduction}
Exotic hadrons are good tools to probe the internal degree of freedom of hadron
which is a composite particle made of quarks. Although exotic hadrons which consists of four or more quarks are allowed to exist in the framework of QCD,
they have never been observed in experimental searches.
Recently, the LHCb experiment reported observation of cryptoexotic pentaquark states on the $J/\psi p$ mass spectrum \cite{lhcb}. In addition,
a candidate for dibaryon system was found in measurements of $np$ scattering
by the WASA-at-COSY experiment \cite{wasacosy}.
In 2003, the first discovery of an explicitly exotic pentaquark was reported from the LEPS Collaboration \cite{leps}. In the same year, a tetraquark candidate was observed by Belle Collaboration \cite{bellex}.
The narrow widths of these states are of great interest, since they are possibly
a result of special internal structure.
The structure of such states are now still under debate. However,
it will deepen our understanding of ordinary hadrons to study the properties of exotic hadrons.

The first discovery of the pentaquark $\Theta^{+}$ was followed by many positive and negative experimental results. It should be noted that the existence is still not confirmed in most of repeated or dedicated experiments.
Under the circumstance, it is strongly desired to confirm the existence especially in a hadronic reaction in which a production cross section is expected to be higher than that in the photoproduction. Additionally, a high mass resolution is a key to realize high experimental sensitivity for a search for the narrow state.
The $\Theta^{+}$ was searched for in the $\pi^{-}p\rightarrow K^{-}X$ reaction as the first experiment at the J-PARC Hadron Facility.
It should be noted that
the pentaquark $\Theta^{+}$ was searched for in the same reaction in the KEK-PS E559 experiment \cite{e522}.
The upper limit of the production cross section was $2.9\mu$b, however the bump
structure was observed with a significance of $2.5\sigma$ which is not enough to claim the existence.
The J-PARC E19 experiment was performed in 2010 and 2012, with beam momenta of 1.92 and 2.01~GeV/$c$.
Accumulated number of beam pions are $7.8\times 10^{10}$ and $8.1\times 10^{10}$ in 2010 and 2012, respectively. The results of analyses are reported in literatures \cite{shirotori} and \cite{moritsu}. The summary of these results and future prospects are described in this paper.

\section{Experimental Apparatus}
The E19 experiment was performed at the K1.8 beamline at the J-PARC Hadron Facility.
The beamline provides separated secondary particles such as $\pi, K, \bar{p}$ up to 2~GeV/$c$ \cite{k18}.
The typical intensity of kaons is $10^{5}$~Hz, and that of $\pi$ is $10$M~Hz or higher.
At the very beginning of the beamline operation,
a duty factor of the primary beam was $10-20\%$, therefore an acceptable
averaged intensity of $\pi^{-}$ was $\sim1M$~Hz. Now the duty factor has been
improved to be $\sim50\%$, and the acceptable beam intensity is not limited
by the beam power but performances of experimental detectors.

The pentaquark $\Theta^{+}$ was searched for with the missing-mass technique
using the $\pi^{-}$ beam irradiated to a liquid hydrogen target.
The beam pions were analyzed with a K1.8 beamline spectrometer and scattered
kaons were detected with the Superconducting Kaon Spectrometer (SKS). Figure
\ref{Fig:sks} shows a schematic view of these two spectrometers.
The beam pions are identified with Time-of-Flight measurements and momentum
analyzed with a series of QQDQQ magnets together with MWPCs and DCs.
The $K^{-}$ are separated from $\pi^{-}$ with Time-of-Flight measurements.
The momentum of scattered $K^{-}$ was analyzed with DCs which were placed
at an entrance and exit of the SKS magnet.
The detail of the experimental apparatus is described elsewhere \cite{moritsu}.
\begin{figure}[htb]
  \centerline{%
    \includegraphics[width=5.5cm]{sks.eps}}
  \caption{Schematic view of K1.8 and SKS spectrometers.}
  \label{Fig:sks}
\end{figure}

The overall performance of spectrometers was examined using the
$\Sigma$ productions in the $\pi^{+}p\rightarrow K^{+}\Sigma^{+}$ and
$\pi^{-}p\rightarrow K^{+}\Sigma^{-}$ reactions.
Figure \ref{Fig:sigma} shows the missing-mass spectrum of the
$\pi^{-}p \rightarrow K^{+}X$ reaction and the production cross section
of $\Sigma^{+}$ measured in the $\pi^{+}p\rightarrow K^{+}\Sigma^{+}$ reaction.
A position of the observed peak is in a good agreement with the PDG value
taking into account the energy loss at the LH2 target.
The missing-mass resolution in the case of $\Theta^{+}$ production is
estimated to be 1.72 and $2.13$~MeV (FWHM) for the beam momenta of
1.92 and 2.01~GeV/$c$, respectively \cite{tomo,moritsu}.
The mass resolution of the former 2010 data was originally
reported as 1.4~MeV in \cite{shirotori}, however it turned out to be
1.72~MeV through an improved tracking algorithm
and systematic calibration method as described in \cite{tomo}.
The measured differential cross section of $\Sigma^{+}$ is consistent
with the past experimental result \cite{candlin}.
The more precise result has been obtained
in the forward region as shown in Fig. \ref{Fig:sigma} (right).
\begin{figure}[htb]
  \centerline{%
    \includegraphics[width=\textwidth]{sigma-combine.eps}}
  \caption{(Left) Missing mass spectrum of $\pi^{-}p \rightarrow K^{+}X$ reaction.
    The clear peak corresponds to the ground state $\Sigma^{-}$.
    (Right) The production cross section of $\Sigma^{+}$
    measured in the 1.38~GeV/$c$ $\pi^{+}p\rightarrow K^{+}\Sigma^{+}$ reaction.
    Open and closed circles correspond to 2010 and 2012 data, respectively.
    The crosses show the result of the past experiment \cite{candlin}.
    The figures are taken from the literature \cite{moritsu}.
  }
    \label{Fig:sigma}
\end{figure}

\section{Result and Discussion}
The missing-mass spectra of 1.92 and 2.01~GeV/$c$ $\pi^{-}p\rightarrow K^{-}X$ reactions are shown in Fig. \ref{Fig:mass}.
\begin{figure}[htb]
  \centerline{%
    \includegraphics[width=\textwidth]{missmass-combine.eps}}
  \caption{Missing mass spectrum of $\pi^{-}p \rightarrow K^{-}X$ reaction
    with beam momenta of (left) 1.92 \cite{shirotori} and (right) 2.01~GeV/$c$ \cite{moritsu}.
    The simulated backgrounds are overplotted with histograms.
    In the right figure, background components,
    non-resonant $\bar{K}KN$ (dashed),
    $\phi$ meson (dotted) and $\Lambda(1520)$ productions (dot-dashed) are
    plotted. }
    \label{Fig:mass}
\end{figure}
No significant peak was observed on the spectra.
Considerable background processes are $\phi$ and $\Lambda(1520)$ productions
together with a non-resonant $\bar{K}KN$ production. The cross sections
of these processes were measured in the past bubble chamber experiment \cite{dahl}.
A simulated background spectrum is overplotted on the plots showing
no peculiar structure in the mass region of $\Theta^{+}$.
It should be noted that the cross section of non-resonant $\bar{K}KN$
is scaled to present data otherwise the amplitude of background
is underestimated by a few times.
The 90\% confidence level upper limits of the production cross section of
$\pi^{-}p\rightarrow K^{-}\Theta^{+}$ reaction are plotted in Fig. \ref{Fig:upperlimit}.
The upper limits are estimated to be 0.28$\mu$b/sr in the laboratory frame in the mass region of $1.51-1.55$~GeV/$c^{2}$ for both 1.92 and 2.01~GeV/$c$
$\pi^{-}p\rightarrow K^{-}\Theta^{+}$ reactions \cite{tomo,moritsu}.
The upper limit obtained in the present experiment is smaller than that of the
previous KEK experiment \cite{e522} by an order of magnitude.
\begin{figure}[htb]
  \centerline{%
    \includegraphics[width=\textwidth]{upperlimit-combine.eps}}
  \caption{The upper limits of production cross section
    at 90\% confidence level in the 1.92 (Left) and 2.01~GeV/$c$ (right)
   $\pi^{-}p\rightarrow K^{-}\Theta^{+}$ reactions \cite{shirotori,moritsu}.}
  \label{Fig:upperlimit}
\end{figure}
The measured upper limit of the cross section can be translated into
the upper limit of decay width of $\Theta^{+}$ with a help of
model dependent theoretical calculations. The result of some
calculations with different coupling schemes and treatments of
form factors is well summarized in \cite{hyodo2}.
With 2010 and 2012 data combined, the upper limit of decay width
was obtained to be 0.36~MeV and 1.9~MeV for different spin states of
$J^{P} = 1/2^{+}$ and $1/2^{-}$, respectively,
around the $\Theta^{+}$ mass region of $1.53-1.54$~GeV/$c^{2}$.
In the case of $J^{P} = 1/2^{+}$, our upper limit is just same as
the decay width of 0.34~MeV which was derived from the measurement of $\Theta^{+}$ in $K^{+}A$ reactions reported by DIANA Collaboration \cite{diana3}.
A comparison with the LEPS results is minutely discussed in the literature \cite{tomo}. Currently there seems no theoretical framework to explain the finite
cross section reported by LEPS Collaboration within our upper limit of decay width.

\section{Future Prospects}
In the $\pi^{-}p\rightarrow K^{-}X$ reaction, the $\Theta^{+}$ might
possibly be generated through an intermediate state like a cryptoexotic $N^{*}$
as suggested by CLAS Collaboration in the $\gamma p\rightarrow \pi^{+}K^{-}K^{+}n$ reaction \cite{clasp}.
The mass of the state is around 2.4~GeV/$c^{2}$, which is unfortunately above
the maximum $\sqrt{s}$ of the $\pi^{-}p$ reaction at the K1.8 beamline.
The possibility of production through the exotic $N^{*}$ can be examined with
a higher secondary beamline which is available in near future at J-PARC.

At present, there is a few survived positive results.
Recently new analysis of a data set for 2006$-$2007 was presented
by the LEPS Collaboration
reporting that
the strong peak of pentaquark $\Theta^{+}$ was not reproduced in the same
manner originally applied to the old data \cite{kato}.
However, it was found that the peak structure seems to be clearly enhanced
when applying a new method to reject events from spectator protons.
They continue data taking so far and a new result is eagerly awaited.

At the J-PARC Hadron Facility, no experiment dedicated for
the search for the $\Theta^{+}$ is planned in the next couple of years.
However, several experimental studies concerning exotic hadrons will be
performed in the near future.
An experiment has been just started to investigate the spectral information
of $\Lambda(1405)$. Currently a new beamline which delivers higher momentum
particles is under construction.
It is named as the high-momentum beamline (high-p) providing
primary protons up to 30~GeV/$c$.
It is also designed as the secondary beamline up to 20~GeV/$c$
by inserting a production target.
A spectroscopy of $\Xi$ and charmed baryons has recently been proposed
at the new beamline,
since the higher beam momentum enable us to study these unexploited part of
baryons.

\section{Summary}
The pentaquark $\Theta^{+}$ was searched for with the missing mass technique
in the 1.92 and 2.01~GeV/$c$ $\pi^{-}p\rightarrow K^{-}X$ reactions
at the K1.8 beamline of the J-PARC Hadron Facility.
The $\Sigma^{\pm}$ productions were studied in the pion-induced reactions
to evaluate the spectrometer performances.
No significant peak structure was observed on the missing-mass spectra of
$\pi^{-}p\rightarrow K^{-}X$ reaction.
The 90\% confidence level upper limit of the production cross section of
$\pi^{-}p\rightarrow K^{-}\Theta^{+}$ is estimated to be 0.28$\mu$b/sr
in the laboratory frame. The obtained upper limit of the decay width
is 0.36 and 1.9~MeV for $J^{P} = 1/2^{+}$ and $1/2^{-}$, respectively.

\bibliographystyle{plain}


\section{Related Work}
\noindent Many recent studies have reported the success of using deep CNN in face related tasks. The pioneering work by \cite{Taigman14} proposed a very deep CNN architecture together with an alignment technique to perform face verification which achieved near human-level performance. Inspired by GoogLeNet \cite{Szegedy15}, Sun et al. \citeyear{Sun14b} used a very deep CNN network with multiple levels of supervision, which surpassed human-level face verification performance in the LFW dataset \cite{Huang13}. The recent advance in this field \cite{Schroff15} pushed the performance even further. In face detection, the state-of-the-art results were also achieved by CNN based models \cite{Yang15,Li15}. For other face related tasks such as face landmark detection and face attribute recognition \cite{Zhang15,Zhang15b}, CNN based models were also widely adopted.

The revived interest on RNN is mainly attributed to its recent success in many practical applications such as language modeling \cite{Kiros15}, speech recognition \cite{Chorowski15,Graves13}, machine translation \cite{Sutskever14,Jean15}, conversation modeling \cite{Shang15} to name a few. Among many variants of RNNs, LSTM is arguably one of the most widely used model. LSTM is a type of RNN in which the memory cells are carefully designed to store useful information to model long term dependency in sequential data \cite{Hochreiter97}. Other than supervised learning, LSTM is also used in recent work in image generation \cite{Theis15,Gregor15}, demonstrating its capability of modeling  statistical dependencies of imagery data.

In terms of the sequence learning problem across multiple modalities, LSTM based models were actively used in recent image caption generation studies \cite{Donahue15,Karpathy15,Xu15}. One common characteristic of these techniques is that CNN was used to extract the feature sequences in an image and LSTM was used to generate the corresponding text sequences. Our paper is related to this group of studies in a way that more than one modalities are involved in the learning process. However, our goal is not to generate sequences in an alternative domain but to collectively learn useful knowledge from sequence data of multiple domains. Perhaps the most closely related previous studies to our work are from \cite{Srivastava12} and \cite{Ngiam11}. Unlike these papers, we focused on high-level multimodal learning which explicitly models the temporal correlation of high-level features rather than raw inputs between different modalities. This not only provided a channel to effectively transfer the recent success of deep CNN to the multimodal learning context, the resulting efficient implementation can be directly adopted in video processing as well. We also investigated the robustness to distractors and input quality which is not considered in the previous studies. The closely related papers in multimedia speaker identification are \cite{Bauml2013,hu2015deep}, and \cite{Tapaswi2012}. However, they did not explicitly model face sequences and the interplay between face and voice sequences.

\section{LSTM - Single VS. Multi-Modal}
\paragraph{Single Modal LSTM} A regular LSTM network contains a number of memory cells within which the multiplicative gate units and the self-recurrent units are the two fundamental building blocks \cite{Hochreiter97}. For a brief revision, equations (\ref{eq:old_input}), (\ref{eq:old_forget_gate}) and (\ref{eq:old_recurrent_unit}) formally describe the memory input, the forget gate and the recurrent units of a regular LSTM in the forward pass. The input gate $i_t$ and the output gate $o_t$ in a regular LSTM resemble the forget gate in the forward pass. Figure \ref{fig:old_lstm} shows a pictorial illustration of a regular LSTM model.
\begin{eqnarray}
\hspace{-0.1in}g_t\hspace{-0.1in} &=& \hspace{-0.1in} \varphi({\bf{W}}_{xg}*X_t+{\bf{W}}_{hg}*h_{t-1}+b_g), \label{eq:old_input} \\
\hspace{-0.1in}i_t\hspace{-0.1in} &=& \hspace{-0.1in} \sigma({\bf{W}}_{xi}*X_t+{\bf{W}}_{hi}*h_{t-1}+b_i), \label{eq:old_input_gate} \\
\hspace{-0.1in}f_t\hspace{-0.1in} &=& \hspace{-0.1in} \sigma({\bf{W}}_{xf}*X_t+{\bf{W}}_{hf}*h_{t-1}+b_f), \label{eq:old_forget_gate} \\
\hspace{-0.1in}o_t\hspace{-0.1in} &=& \hspace{-0.1in} \sigma({\bf{W}}_{xo}*X_t+{\bf{W}}_{ho}*h_{t-1}+b_o), \label{eq:old_output_gate} \\
\hspace{-0.1in}C_t\hspace{-0.1in} &=& \hspace{-0.1in} f_t \odot C_{t-1}+ i_t \odot g_t, \label{eq:old_recurrent_unit} \\
\hspace{-0.1in}y_t\hspace{-0.1in} &=& \hspace{-0.1in} softmax({\bf{W}}_y*h_t). \label{eq:old_output}
\end{eqnarray}

In (\ref{eq:old_input}) and (\ref{eq:old_forget_gate}), $X$ is an input sequence where $X_t$ is an element of the sequence at time $t$, $h_{t-1}$ is the output of the memory cell at time $t-1$. ${\bf{W}}_{xg}, {\bf{W}}_{xf}, {\bf{W}}_{hg}, {\bf{W}}_{hf}$ are distinct weight matrices, and $b_g$ and $b_f$ are bias terms respectively. $\varphi$ and $\sigma$ are nonlinear functions where $\varphi$ denotes a $tanh$ function and $\sigma$ denotes a $sigmoid$ function. In (\ref{eq:old_recurrent_unit}), $\odot$ denotes an element-wise multiplication, $i_t$ is the input gate at the time step $t$, and $C_{t-1}$ is the memory unit at the time step $t-1$. The memory unit at time step $t$ is therefore generated by the collective gating of the input gate and the forget gate. In equation (\ref{eq:old_output}), the memory cell output of the current time step is multiplied by ${\bf{W}}_y$ and then transformed by the $softmax$ function to compute the model output $y_t$ at time $t$.

Generally speaking, the reason that LSTM is able to model long-term dependencies in sequential data is because $C_t$ at each time step can selectively ``remember'' (store) or ``forget'' (erase) past information which is modelled by the multiplicative gating operation. More importantly, the strategy to open or to close the gates is data driven which is automatically learned from training data. This information is captured by the trainable weights ${\bf{W}}$, including ${\bf{W}}_{hf}, {\bf{W}}_{xf}$ and so on, rather than hand-crafted. Because ${\bf{W}}$ are shared across time steps, this endows LSTM the power to explicitly model temporal relationships over the entire sequence.

\begin{figure}[t]
  \centering
  \includegraphics[width=1.0\linewidth]{figures/lstm_old.eps}\vspace{-0.1in}
  \caption{Memory Cell of Single-modal LSTM.}\vspace{-0.15in}
  \label{fig:old_lstm}
\end{figure}

\vspace{-0.15in}
\paragraph{Simple extensions of Single Modal LSTM}
In order to deal with data from different domains, perhaps the most straightforward method is to incorporate them into a single network by concatenating the data directly to produce a bigger $X$. However, this approach is problematic because the multimodal property of the inputs are completely ignored and the model does not have any explicit mechanism to model the correlation across modalites. Though some correlations may be weakly captured by the trained weights, a critical weakness is that it is incapable to handle distractors. In particular, when the face of a person A is combined with the voice of a person B, the model is confused and would fail to generate a meaningful label. Although it may be possible to put all the distractors to a single class and let the model to distinguish the speaker and the distractors automatically, this method performs much worse than our solution in practice. The major difficulty is that distractors share too many features with regular examples when organize the inputs in this way.

Another solution is to treat data from different domains completely independent. Namely, we can use multiple LSTMs in parallel and then merge the output labels at the highest layer using a voting mechanism. The advantage of this approach is that the two separate memory units can be trained to store useful information explicitly for each domain. But the weakness is that the interaction across modalities only happens at the highest level during the labelling process. The cross-model correlation is therefore very difficult, if not entirely impossible, to be encoded into the weights through the learning process. Thus, the robustness to distractors relies heavily on the voting stage where some of the temporal correlations may have already been washed out in the independent forward pass.

\vspace{-0.15in}
\paragraph{Multimodal LSTM}
Compared with the straightforward solutions, we want to develop a new multimodal LSTM which can explicitly model the long-term dependencies both within the same modality and across modalities in a single multimodal LSTM.
Instead of merging input data at pre-processing stage, or merging labels at post-processing stage, our key idea is to selectively share weights across different modalities during the forward pass. This is similar to the weight sharing in time domain in regular LSTM, but we do not share memory units for each modality within the memory cell. The modifications are illustrated in figure \ref{fig:fig2} and formally expressed in the following equations.
\begin{eqnarray}
\hspace{-0.18in}g_t^s\hspace{-0.1in} &=& \hspace{-0.1in} \varphi({\bf{W}}_{xg}^s*X_t^s+{\bf{W}}_{hg}*h_{t-1}^s+b_g^s), ~~ s = 1~to~n, \label{eq:new_input} \\
\hspace{-0.18in}i_t^s\hspace{-0.1in} &=& \hspace{-0.1in} \sigma({\bf{W}}_{xi}^s*X_t^s+{\bf{W}}_{hi}*h_{t-1}^s+b_i^s), ~~ s = 1~to~n, \label{eq:new_input_gate} \\
\hspace{-0.18in}f_t^s\hspace{-0.1in} &=& \hspace{-0.1in} \sigma({\bf{W}}_{xf}^s*X_t^s+{\bf{W}}_{hf}*h_{t-1}^s+b_f^s), ~~ s = 1~to~n,\label{eq:new_forget_gate} \\
\hspace{-0.18in}o_t^s\hspace{-0.1in} &=& \hspace{-0.1in} \sigma({\bf{W}}_{xo}^s*X_t^s+{\bf{W}}_{ho}*h_{t-1}^s+b_o^s), ~~ s = 1~to~n, \label{eq:new_output_gate} \\
\hspace{-0.18in}C_t^s\hspace{-0.1in} &=& \hspace{-0.1in} f_t^s \odot C_{t-1}^s+i_t^s \odot g_t^s, ~~ s = 1~to~n, \label{eq:new_recurrent_unit} \\
\hspace{-0.18in}h_t^s\hspace{-0.1in} &=& \hspace{-0.1in} o_t^s \odot \varphi(C_t^s), ~~ s = 1~to~n, \label{eq:new_cell_output} \\
\hspace{-0.18in}y_t^s\hspace{-0.1in} &=& \hspace{-0.1in} softmax({\bf{W}}_y*h_t^s), ~~ s = 1~to~n. \label{eq:new_output}
\end{eqnarray}

\begin{figure}[t]
  \centering
  \includegraphics[width=1.0\linewidth]{figures/lstm.eps}\vspace{-0.1in}
  \caption{Memory Cell of Multimodal LSTM.}\vspace{-0.15in}
  \label{fig:fig2}
\end{figure}
Keeping the gating mechanism the same as the regular LSTM, the equations from (\ref{eq:new_input}) to (\ref{eq:new_output}) describe a new cross-modal weight sharing scheme in the memory cell. The superscript $^s$ indexes each modality in the input sequences. $n$ is the total number of modalities in input data, where $n=2$ in the speaker identification task. The model is general enough to deal with the tasks with $n>2$. $X_t^s$ is the input sequence at time $t$ for modality $s$. Therefore, the weights with superscript $^s$ (e.g. ${\bf{W}}_{xg}^s$) are NOT shared across modalities but only across time steps, the other weights without the superscript (e.g. ${\bf{W}}_{hg}$) are shared across both modalities and time steps. Specifically, the weights associated with the inputs $X_t^s$ are not shared across modalities. The reasons are two-fold. First, we would like to learn a specialized mapping, separately for each modality, from its input space to a new space, where multimodal learning is ensured by the shared weights. Second, specialized weights are preferred to reconcile the dimension difference between different modalities, which avoids a complex implementation.

Along with the transform associated with $X_t^s$, the output of the memory cell from the previous time step $h_{t-1}^s$ also need to go through a transform in producing $g_t^s$ as well as all other gates. The weights to perform this transform, ${\bf{W}}_{hg}, {\bf{W}}_{hi}, {\bf{W}}_{hf}$ and ${\bf{W}}_{ho}$ are shared across the modalities. With these new weight definitions, the separately transformed data by the four ${\bf{W}}^s$ is essentially interconnected from $g_t^s$ all the way to the memory cell output $h_t^s$.

The key insight is that while it is preferable for each modality to have its own information flow because it enables a more focused learning objective with which it is easier to learn the long-term temporal dependency within the modality, we also make such objective correlated and essentially constrained by what happens in the rest of the modalities. More specifically, in forming the forget gate $f_t^s$ for $s=1$, it not only relates to $h_{t-1}^{s=1}$ but also constrained by $h_{t-1}^{s=2}$, ... , $h_{t-1}^{s=n}$ because ${\bf{W}}_{hf}$ is shared among them. Provided that the weights ${\bf{W}}_{hg}, {\bf{W}}_{hi}, {\bf{W}}_{hf}$ and ${\bf{W}}_{ho}$ are also shared across time steps, they play the vital role of capturing the temporal correlation across different modalities.

Another important property of the proposed model is that the memory unit $C$ is NOT shared among modalities. The rationale is that the weights have the job to capture intramodal as well as intermodal relationships, therefore placing them in a single memory unit provides much less flexibility on what can be stored or forgotten. Given all the gates are formed in a multimodal fashion, the insight of such design is that we should not hand-craft the decision on what intramodal/intermodal relationships should be stored or forgotten but to give the model enough flexibility to learn it from data. The bias terms are not shared across modalities neither to increase this flexibility.

Likewise, the network output at each time step $y_t^s$ does not relate to its own modality. Whether we should use ${\bf{W}}_y$ or ${\bf{W}}_y^s$ to transform $h_t^s$ before sending the outputs to the softmax function is not a straightforward decision. We resort to our experiment to address this issue.

\vspace{-0.15in}
\paragraph{High-Level Feature VS. Raw Inputs}
One of the most important reasons why CNN is attractive is because it is an end to end feature learning process. Previous studies \cite{Razavian14,Oquab14} have discovered that a successful CNN for a classification task also produces high-level features which are general enough to be used in a variety of tasks. This finding inspired a few recent work on image captioning \cite{Xu15,Karpathy15} where the high-level CNN features over an image sequence were extracted, and a RNN is learned on top of the extracted CNN features to perform more sophisticated tasks. Such approach is very effective to bridge the effort and success in CNN to the field of sequence modeling. We would like to extend this type of attempt to multimodal sequence learning.

\vspace{-0.15in}
\paragraph{Implementation}
In order to maximize the flexibility of our investigation and efficiently work with different variants of network architecture and working environments (e.g. Linux and Windows), we did not implement the multimodal LSTM using any third-party deep learning packages. Instead, we used MATLAB and its GPU functions in the parallel computing toolbox to build our own LSTM from scratch. Our implementation is vectorized \cite{Ren14_aaai} and very efficient in training both single-modal and multimodal LSTM described in this paper.

\section{Experiments}
Three experiments were carefully designed to test the robustness and the applicability of our proposed model.

\vspace{-0.15in}
\paragraph{Dataset overview}
We chose the TV-series The Big Bang Theory (BBT) as our data source. It has been shown that the speaker identification task over BBT is a very challenging multimodal learning problem due to various kinds of image degradation and the high variations on faces in the videos \cite{Bauml2013,hu2015deep,Tapaswi2012}. During data collection, we ran face detection and extracted all the faces in six episodes in the first season and another six episodes in the second season of BBT. We manually annotated the faces for the five leading characters, i.e. \textit{Sheldon}, \textit{Leonard}, \textit{Howard}, \textit{Raj} and \textit{Penny}. In total, we have more than 310,000 consecutively annotated face images for the five characters. For audio data, we utilized the pre-annotated subtitles and only extracted the audio segments corresponding to speeches. Data from the second season was used in training and data from the first season was used in testing for all the experiments reported below.

\vspace{-0.15in}
\paragraph{Feature extraction}
To ensure the usability of the resulting system, we adopted 0.5 second as the time window of all the sequence data including both face and audio. For feature extraction for faces, we adopted a CNN architecture resembles the one in \cite{KrizhevskySH12} and trained a classifier using the data reported in the next section. The activations of the last fully connected layer was used as the high-level feature for face. We also run principle component analysis (PCA) on all the extracted face features to reduce the dimensionality to the level comparable to audio features. By keeping 85\% of the principle components, we obtained a 53-dimension feature vector for each face in the video. The video is 24 frames per second, therefore there are 12 consecutive faces within each face sequence. For audio, we used the mel-frequency cepstral coefficients (MFCC) features \cite{Sahidullah12}. Following \cite{hu2015deep} we extracted the 25d MFCC features in a sliding window of 20 milliseconds with stride of 10 milliseconds, thus gives us 25$\times$49 MFCC features.

\subsection{LSTM for Face Sequences}
Our first task is to investigate the extend to which modeling temporal dependency of high-level CNN features improves the robustness to quality degradation and face variation. The reasons that we would like to investigate this manner is two-fold. First, though it was showed that RNN can be successfully used in speech recognition to improve the robustness to noise \cite{Graves13}, it was not clear from the literature whether similar principle applies for high-level image features. On the other hand, we would like to clearly measure the extend to which this approach works for faces because this is an important cornerstone for the rest of the experiments.

\vspace{-0.15in}
\paragraph{Data}
Only face data in the aforementioned data set was used in the experiment. We randomly sampled 40,000 face sequences from the training face images and another 40,000 face sequences in the test face images. Note that each sequence was extracted according to the temporal order in the data, however, we did not guarantee the sequence are strictly from one subtitle segment. This injected more variations in the sequence.

\vspace{-0.15in}
\paragraph{Procedure and Results}
Three methods were compared in this experiment. The first method was to use a CNN to directly classify each frame in the sequence. This CNN is the same one as used in the feature extraction for our LSTM. In our setting, the CNN will output 12 labels (12 probability distributions) for each face sequence. Then the output probabilities were averaged to compute the final label for this sequence. The second method used the same CNN to extract features for each frame and reduced the dimensionality using PCA as described in the last section. Then we used a SVM with RBF kernel to classify each feature followed by the same averaging processing before outputting the label. We used the single-modal LSTM (see figure \ref{fig:old_lstm}) with one hidden memory cell layer to train a sequential classifier. The dimensionality of the hidden layer activation is 512. In our setting, this LSTM contains 12 time steps with 12 identical supervision signals (labels). During the testing, we only look at the last output in the whole output sequence.

The results were reported in table \ref{table:svm-compare}. We can see that the two CNN alone approaches delivered very similar results, acknowledging the high representative powerful of the CNN features reported in the previous studies. The accuracy of the CNN+SVM approach slightly outperformed the CNN alone approach. This is reasonable because SVM with RBF kernel may classify the data better than the last layer of CNN. The performance of LSTM is significantly higher than the other two. By looking at the correctly classified face sequences which were failed in the other two methods, we can see that the LSTM is more robust to a number of image degradations and variations. This is illustrated in figure \ref{fig:fig1}a.

\begin{table}
\begin{center}
\caption{Face sequence classification accuracy of different algorithms.}\vspace{-0.05in}
\label{table:svm-compare}
\scalebox{0.82}{
\begin{tabular}{|l|c|}
\hline
\textsc{Algorithms} & \textsc{Accuracy ($\%$)} \\
\hline\hline
CNN & 92.33 \\
CNN+SVM & 92.42 \\
LSTM & 95.61 \\
\hline
\end{tabular}
}
\end{center}\vspace{-0.15in}
\end{table}

\subsection{Comparison among Multimodal LSTMs}
By the results from the first experiment, there is a reason to believe that performing multimodal learning of face and audio in temporal domain, if do it correctly, has the potential to perform better in speaker identification task. Therefore, the aim of the second experiment was to examine the extend to which the multimodal LSTM benefits the speaker identification performance. Multiple aforementioned multimodal LSTM solutions were tested and compared in this experiment. See the result session for details.

\vspace{-0.15in}
\paragraph{Data}
In the training process, the face data from the previous experiment was used. One problem is that each face sequence has only 12 time steps which is inconsistent with the 49 time steps in audio sequences. To circumvent this inconsistency, we simply duplicated faces evenly within the 49 time steps. The combinations of face sequences and audio sequences for each identity were randomly paired by the training program during the runtime to maximize the diversity of the training set. For test set of this task, the combinations were however pre-generated. We randomly generated 250,000 correctly paired combinations and 250,000 distractors (ill-paired combinations).

\vspace{-0.15in}
\paragraph{Procedure and Results}
During the comparison, one baseline method and three alternative multimodal LSTM methods were used. In the baseline method, we separately trained a single-modal LSTM only for audio using the same audio data in this experiment. We carefully tuned many hyper parameters, making sure it performed as well as we can achieve. We used it to classify the audio sequence. For face sequence, we used the CNN+SVM approach from the last experiment. Therefore, we shall have 49 proposals for audio labels and another 49 labels for face label proposals. We then looked at the number of labels agreed within these two groups of labels. A threshold $m$ is set to distinguish the sample between distractors and normal samples. For instance, if $m=10$ then the whole multimodal sequence will be classified to distractors if there are more than 10 label proposals temporally disagreed with each other. Otherwise, the multimodal sequence will be classified by averaging the proposals. Note that this distractor rejection procedure was used in all the compared methods in this experiment. The threshold $m$ is tuned to generate various dots in the ROC curve.

The first multimodal solution does not share any weights across the two modality resulting in two separate single-modal LSTMs. We called it ``no cross-modal weight sharing''. The second solution used the weight sharing scheme introduced previously, but did not share ${\bf{W}}_y$ across the modality. Formally, equation (\ref{eq:new_output}) should be re-written as
\begin{eqnarray}
\hspace{-0.1in}y_t^s\hspace{-0.1in} &=& \hspace{-0.1in} softmax({\bf{W}}_y^s*h_t^s), ~~ s = 1~to~n. \label{eq:new_output_2}
\end{eqnarray}

We called this solution ``half cross-modal weight sharing''. The third solution completely followed the equation (\ref{eq:new_input}) to (\ref{eq:new_output}), named ``full cross-modal weight sharing''.

As shown in figure \ref{fig:fig3}, the performance difference is clear. It was expected that the baseline method performed less competitive. However, having isolated ${\bf{W}}_y$ for each modality performed worse than the naive combination of two single-model LSTMs. On the other hand, with the full weight sharing, multimodal LSTM significantly outperforms all other methods.

\begin{figure}[t]
  \centering
  \includegraphics[width=0.9\linewidth]{figures/roc.eps}\vspace{-0.1in}
  \caption{Multimodal Long Short-Term Memory.}\vspace{-0.15in}
  \label{fig:fig3}
\end{figure}

\vspace{-0.15in}
\paragraph{Discussion}
The false alarm rate was largely increased by not sharing ${\bf{W}}_y$ across modalities. The role of ${\bf{W}}_y$ is to transform the memory cell outputs at each time step to the desirable labels. By sharing this transform across the modality, we can generate more consistent labels for normally paired samples and increased the robustness to distractors. Our experiments showed that this behavior can be automatically captured by the shared ${\bf{W}}_y$.

\subsection{Speaker Identification in The Big Bang Theory}
The last experiment is to apply our method in real-life videos and compare the performance with previous studies.

\vspace{-0.15in}
\paragraph{Data}
To compare with other speaker identification methods, we evaluated the winning multimodal LSTM from the previous experiment in The Big Bang Theory S01E03, as in \cite{Bauml2013,Tapaswi2012,hu2015deep}.

\vspace{-0.15in}
\paragraph{Procedure and Results}
We applied our model to video with the time window of 0.5 second and stride of 0.25 second (e.g. 0s-0.5s, 0.25s-0.75s...). Unlike the controlled setting in the second experiment, the number of distractors in videos varies for each scene. In some cases, there are only distractors in a scene. The evaluation criteria should be more sophisticated. We followed \cite{hu2015deep} to calculate the accuracy of speaker identification to ensure a fair comparison. Specifically, speaker identification is considered successful if a) the speaker is in the scene and the system correctly recognized him/her and correctly rejected all the distractors, or b) the speaker is not in the scene and the system correctly rejected all the distractors in the scene.

Time window more than 0.5 second was also tested to enable a more systematic comparison. We achieved this by further voting within this larger time window. For instance, by having 50\% overlapping of 0.5 second windows in the larger window of 2.0 seconds, we will have seven 0.5 second-sized small windows to vote for the final labels.

Our speaker identification results are reported in table \ref{table:sn-compare}. We compared our method against the state-of-the-art systems. Note that, in \cite{Bauml2013,Tapaswi2012}, as both of them examined the face tracks within the time window specified by the subtitle/transcript segments, they can be viewed as voting on the range of subtitle/transcript segments. As the average time of subtitle/transcript segments in the evaluation video is 2.5s, they are equivalent to our method when evaluated in the voting window of such size. We applied the same voting strategy as in \cite{hu2015deep} under different time window setup. As can be seen from the results, our method outperformed the previous works by a significant margin.

\begin{table}
\begin{center}
\caption{Speaker naming accuracy of different algorithms (\%) in terms of different voting time window (s).}\vspace{-0.1in}
\label{table:sn-compare}
\scalebox{0.82}{
\begin{tabular}{|l||c|c|c|c|c|c|}
\hline
{Time window (s)} & 0.5 & 1.0 & 1.5 & 2.0 & 2.5 & 3.0 \\
\hline\hline
Bauml et al. \citeyear{Bauml2013} & - & - & - & - & 77.81 & - \\
\hline
Tapaswi et al. \citeyear{Tapaswi2012} & - & - & - & - & 80.80 & - \\
\hline
Hu et al. \citeyear{hu2015deep} & 74.93 & 77.24 & 79.35 & 82.12 & 82.81 & 83.42 \\
\hline
Ours & 86.59 & 89.00 & 90.45 & 90.84 & 91.17 & 91.38 \\
\hline
\end{tabular}
}
\end{center}\vspace{-0.15in}
\end{table}

\section{Conclusion}
In this paper, we have introduced a new multimodal LSTM and have applied it to the speaker identification task. The key idea is to utilize the cross-modality weight sharing to capture correlation of two or more temporally coherent modalities. As demonstrated in our experiments, our proposed multimodal LSTM is robust against image degradation and distractors, and has outperformed state-of-the-art techniques in speaker identification. To our knowledge, this is the first attempt in modeling long-term dependencies over multimodal high-level features. We believe our multimodal LSTM is also useful to other applications not limited to the speaker identification task.

\bibliographystyle{aaai}


\section*{Acknowledgement}