$\displaystyle=\sum_{r=0}^{t}\partial T_{r}+R_{0}-\sum_{r=0}^{t}\partial
T_{r}+(\partial R_{0}+\sum_{r=0}^{t}\partial\partial T_{r})^{u}$
$\displaystyle=R_{0}+(\partial R_{0}+\sum_{r=0}^{t}\partial\partial
T_{r})^{u}$ $\displaystyle\overset{\partial\partial=0}{=}R_{0}+(\partial
R_{0})^{u}=R_{0}.$

The last equality is due to Claim 5.3 which states $\partial R_{0}=0$.

Let us understand how to perform the shifting step. Note that by the
assumption on $\boldsymbol{\psi}_{\ell}$ any vertex in $vs(R_{0})$ of color
$>i_{c_{\ell}}$ must come from $s$ itself. So let
$v_{0},v_{1},...,v_{t}\subseteq s$ be the vertices in $vs(R_{0})$ of colors
$>i_{c_{\ell}}$ (the vertices of color $\geqslant i_{c_{\ell+1}}$ are a subset
of these vertices). The sets $T_{j}$ we want will have the property that
$vs(R_{j+1})=vs(R_{j}-\partial
T_{j})=(vs(R_{j})\setminus\\{v_{j}\\})\cup\\{v_{j}^{\prime}\\}$, where the
replacing vertices $v_{0}^{\prime},v_{1}^{\prime},...,v_{t}^{\prime}$ are of
low-colors ($col(v_{j}^{\prime})=i_{c_{\ell}+j+1}$).

We construct $T_{j}$ as follows. Assume without loss of generality that
$v_{0}\prec v_{1}\prec...\prec v_{t}$ according to the order of the lattice.
This implies that $col(v_{j})\geqslant i_{c_{\ell}+j+1}$. If
$col(v_{j})=i_{c_{\ell}+j+1}$ then by setting $T_{j}=0$ we are done.
Otherwise, $col(v_{j})>i_{c_{\ell}+j+1}$. We will find a vertex
$v_{j}^{\prime}$ of color $i_{c_{\ell}+j+1}$ so that for every face
$s^{\prime}\in supp(R_{j})$ that contains $v_{j}$,
$s^{\prime}\cup\\{v_{j}^{\prime}\\}\in X$. Then we take
$T_{j}=((R_{j})_{v_{j}})^{v_{j}^{\prime}}$ (i.e. $T_{j}$ takes all faces that
contain $v_{j}$ in $R_{j}$ and adds $v_{j}^{\prime}$ to them). We will show
below that $v_{j}$ is no longer in the support of $R_{j+1}=R_{j}-\partial
T_{j}$.

The reason we can find such a $v_{j}^{\prime}$ is the fourth item of Claim
5.8; this item promises us existence of some $v_{j}^{\prime}\prec v_{j}$ so
that all the vertices in $vs((R_{j})_{v_{j}})$ of color $<col(v_{j})$ are also
neighbors of $v_{j}^{\prime}$. Moreover, as $v_{j}^{\prime}\prec v_{j}$ it
also holds that $v_{j}^{\prime}\prec v_{j+1}\prec...\prec v_{t}$, this
promises us that _all_ $vs((R_{j-1})_{v_{j}})$ are also neighbors of
$v_{j}^{\prime}$. Thus $(R_{j-1})_{v_{j}}$ is contained in the link of
$v_{j}^{\prime}$ and $T_{j}$ is well defined as a chain in $X$.

We summarize this process in the following claim. Its proof, which technically
formalizes this discussion, is given below.

######  Claim 5.10.

  1. 1.

The shifting step is always possible. That is, there exists $v^{\prime}_{j}$
so that $supp((R_{j})_{v_{j}})\subseteq X_{v^{\prime}_{j}}$ and so that
$col(v^{\prime}_{j})=i_{c_{\ell}+j+1}$. Moreover,

  2. 2.

If $R_{j}\neq R_{j-1}$ then
$vs(R_{j})\subseteq(vs(R_{j-1})\cup\\{v^{\prime}_{j}\\})\setminus\\{v_{j}\\}$
and

  3. 3.

$|supp(R_{j})|\leqslant|supp(R_{j-1})|\leqslant...\leqslant|supp(R_{0})|$.

Note that the last item will be necessary when we will bound
$\lvert\psi(s)\rvert$.

As alluded to in the discussion, after obtaining $R_{t+1}$ we need to show
that there exists some $u\in X[i_{c_{\ell+1}}]$ so that $R_{t+1}\subseteq
X_{u}$.

Let $M\subseteq vs(R_{t+1})$ be the vertices of colors $>i_{c_{\ell}}$. By the
shifting step there is at most one vertex of each color in $M$. Let
$B\subseteq vs(R_{t+1})$ be the rest of the vertices, all of which are of
color $\leqslant i_{c_{\ell}}$. By the last item of Claim 5.10 there are at
most $|vs(R_{t+1})|\leqslant|vs(R_{0})|$ vertices in $B$. This is at most
$n_{\ell+1}$ by induction hypothesis on the cone already constructed. Hence by
item 3 in Claim 5.8, there exists some $u\in X[i_{c_{\ell+1}}]$ so that the
complex induced by $M\cup B=vs(R_{t+1})$ is in the link of $u$. This shows
that $\psi(s)$ is well defined.

Now that we established that $\boldsymbol{\psi}$ is a cone, we bound its
radius and verify its other properties.

##### The radius

Obviously $|supp(R_{t+1})^{u}|=|supp(R_{t+1})|$, and by last item in Claim
5.10, this is $\leqslant|\operatorname{supp}R_{0}|$. By the inductive
assumption on $\boldsymbol{\psi}_{\ell}$,

$\lvert supp(R_{0})\rvert\leqslant 1+\sum_{i=0}^{\ell+1}\lvert
supp(\psi(s_{i}))\rvert\leqslant(\ell+2)rad(\boldsymbol{\psi_{\ell}})+1\leqslant(\ell+2)(1+D_{\ell}).$

Moreover, in every iteration of the shifting step we added $T_{j}$ to
$\psi(s)$. The faces in $T_{j}=((R_{j})_{v_{j}})^{v^{\prime}_{j}}$, the
support of this function is again of size at most $(\ell+2)(1+D_{\ell})$
(since by the last item of the size of Claim 5.10, the support of $R_{j}$ is
less or equal to the size of $R_{0}$’s support). There are at most $\ell+2$
iterations in the shifting step. So the support of $\sum_{j=0}^{t}T_{j}$ is at
most $(\ell+2)^{2}(1+D_{\ell})$. In total, for every $s\in X(\ell+1)$,

$\lvert supp(\psi(s))\rvert=\lvert
supp\left((R_{t+1})^{u}+\sum_{j=0}^{t}\partial
T_{j}\right)\rvert\leqslant(\ell+3)(\ell+2)(1+D_{\ell})=D_{\ell+1}.$

##### Colors of $vs(\psi(s))\setminus s$

The vertices in $(vs(\psi(s))\setminus s$ that come from
$R_{0}=s-\sum_{i=0}^{\ell+1}\psi(s_{i})$ have colors $\leqslant i_{c_{\ell}}$
by the induction hypothesis on $\boldsymbol{\psi_{\ell}}$. The other vertices
in $vs(\psi(s))\setminus s$ either come from the shifting step, in which case
these are the $v^{\prime}_{j}$ that have colors $\leqslant
i_{c_{\ell+1}+j+1}$, or the vertex of color $i_{c_{\ell+1}}$ from the star
step. To conclude, all vertices of $vs(\psi(s))\setminus s$ have colors
$\leqslant i_{c_{\ell+1}}$.

##### The size of $vs(\psi(s))$

The vertex support of every $T_{j}$ consists only of the vertex support of
$R_{0}$ and the new $v^{\prime}_{j}$ that we added. There are at most $\ell+2$
vertices $v^{\prime}_{j}$ introduced by the sets $T_{j}$. The vertex support
of $(R_{t+1})^{u}$ is $u$ together with the vertex support of $(R_{t+1})$.
Thus $vs(\psi(s))\subseteq
vs(R)\cup\\{v^{\prime}_{1},...,v^{\prime}_{m}\\}\cup\\{u\\}$. The vertex
support of $R_{0}$ satisfies

$|vs(R_{0})|=\lvert
vs(s-\sum_{i=0}^{j}\psi(s_{i}))\rvert\leqslant|s|+1+\sum_{i=0}^{\ell+1}\left(|vs(\psi(s_{i}))|-|s_{i}|-1\right).$

Here we subtract $|s_{i}|+1$ from the sums since we need to count the vertices
of $s$ and $u_{0}$ only once. Hence
$|vs(R_{0})|\leqslant\ell+3-(\ell+2)^{2}+(\ell+2)n_{\ell}$. Plugging this back
in we get that

$|vs(\psi(s))|\leqslant\ell+3-(\ell+2)^{2}+(\ell+2)n_{\ell}+(\ell+3)=n_{\ell+1}.$

∎

###### Proof of Claim 5.8.

Here when we write $u\leqslant v$ we mean by the order of the lattice, and
when we write $col(u)>col(v)$ we mean the usual order of integers.

  1. 1.

Let $u_{1},u_{2}\in X[i_{1}]$ the join $u_{1}\vee u_{2}$ has rank $\leqslant
2i_{1}$. By properties of the lattice, there exists some $v\in X[i_{2}]$ so
that $v\succeq u_{1}\vee u_{2}\succeq u_{1},u_{2}$. In particular, there is a
path $u_{1},v,u_{2}$ and the diameter is $2$.

  2. 2.

If $col(v)>col(u)$ and $v\sim u$ this implies that $v\succeq u$. In
particular, $w\in X_{u}[{\\{i\leqslant col(u)\\}}]$ if and only if $w\preceq
u\preceq v$ and thus $w\in X_{v}[{\\{i\leqslant col(u)\\}}]$.

  3. 3.

Let $u$ be the join of all the elements in $M\cup D$. The rank of $u$ is at
most the sum of the ranks of the elements in $M\cup D$. That is,
$col(u)\leqslant n_{j}\cdot
i_{c_{j}}+\sum_{m^{\prime}=1}^{m-1}i_{c_{j}+m^{\prime}}$. By assumption on the
colors $i_{c_{j}+m}\geqslant col(u)$. Therefore, there is some $w\in
X[i_{c_{j}+m}]$ that contains $u$ (if $col(u)<i_{c_{j}+m}$ we can always add
atoms to $u$ one by one, each increasing the rank by $1$, until we reach some
$w\succ u$ whose color is $i_{c_{j}+m}$ as required). In particular the
complex induced by $M\cup D$ is in the link of $w$.

  4. 4.

Let $v\in s$ be the vertex with the smallest rank. By the second property
proven above, it holds that
$X_{s}[\\{i_{1},...,i_{c_{j}+m}\\}]=X_{v}[\\{i_{1},...,i_{c_{j}+m}\\}]$. Note
that $X_{v}[\\{i_{1},...,i_{c_{j}+m}\\}]$ is a partially ordered set whose
elements are strictly less than $v$ in the order of the lattice. This is also
a geometric lattice (or a link of said lattice), thus the proof for item $3$
holds there as well.

∎

This following claim shall be used in the proof of Claim 5.10.

######  Claim 5.11.

Let $R\in C_{k}(X,\mathbb{Z})$ so that $\partial R=0$. Then $w\notin
vs(\partial R_{w})$ or equivalently $(\partial R_{w})_{w}=0$.

###### Proof of Claim 5.11.

We write $R=R_{w}+R^{\prime}=\sum_{w\in t}\alpha_{t}t+R^{\prime}$ and get that
$0=\partial R=\partial R_{w}+\partial R^{\prime}.$ In particular $(\partial
R_{w})_{w}=(-\partial R^{\prime})_{w}.$ As $w\notin vs(R^{\prime})$ it is also
not in $vs(\partial R^{\prime})$, so $(\partial R^{\prime})_{w_{2}}=0$. In
conclusion $(\partial R_{w})_{w}=0$. ∎

###### Proof of Claim 5.10.

We prove this by strong induction on $j$. Assume that the claim holds for all
$j^{\prime}<j$.

Let us begin with the first item. Our goal is to show that the conditions in
the last item of Claim 5.8 hold on $(R_{j-1})_{v_{j}}$. By the induction
hypothesis, we note that the vertex support of $(R_{j-1})_{v_{j}}$ is
contained in the union of:

  1. 1.

The vertices of $s^{\prime}=\left\\{v\in s\left|\;\vphantom{v\in
scol(v)\geqslant col(v_{j})}\right.col(v)\geqslant
col(v_{j})\right\\}\subseteq s$.

  2. 2.

A subset $M\subseteq\\{v^{\prime}_{1},...,v^{\prime}_{j-1}\\}$ which were
added to the support in one of the previous steps.

  3. 3.

Other vertices $D$ that came from the support of $R_{0}$. There are at most
$n_{\ell}$ of those, and they all have colors $\leqslant i_{c_{j}}$ by our
assumption on the cone in the previous steps.

Let $Q=\left\\{t\setminus s^{\prime}\left|\;\vphantom{t\setminus
s^{\prime}t\in supp((R_{j-1})_{v_{j}})}\right.t\in
supp((R_{j-1})_{v_{j}})\right\\}$. $Q$, is a subcomplex of the complex induced
by $M\cup D$, and is contained in $X_{v_{j}}[{\\{i\leqslant col(v_{j})\\}}]$.
Also, we note that by item 2 in Claim 5.8, this is equal to
$X_{s^{\prime}}[{\\{i\leqslant col(v_{p})\\}}]$ (since $v_{j}$ is the vertex
that has the smallest color out of $s^{\prime}$). By the last item in Claim
5.8, there indeed exists some $v^{\prime}_{j}\in X_{s^{\prime}}$ so that the
complex induced by $M\cup D$ is contained in $X_{v^{\prime}_{j}\cup
s^{\prime}}$. In particular, this implies that the support of $Q$ is contained
in the $X_{v^{\prime}_{j}}$. As all vertices $v\in s^{\prime}$ that are not
$v_{j}$ are greater than $v_{j}$ (in the lattice order), it also holds that
the support of $(R_{j})_{v_{j}}$ is in $X_{v^{\prime}_{j}}$.

We turn towards the second item. Assume that $R_{j}\neq R_{j-1}$. By
construction, $vs(R_{p})\subseteq vs(R_{j-1})\cup\\{v^{\prime}_{j}\\}$. So to
show that
$vs(R_{p})\subseteq(vs(R_{j-1})\cup\\{v^{\prime}_{j}\\})\setminus\\{v_{j}\\}$
we need to show that $v_{j}\notin vs(R_{j})$.

$\displaystyle R_{j}$ $\displaystyle=R_{j-1}-\partial T_{j}$
$\displaystyle=R_{j-1}-\partial(((R_{j-1})_{v_{j}})^{v^{\prime}_{j}})$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:star-
boundary}}}{{=}}R_{j-1}-(R_{j-1})_{v_{j}}+(\partial((R_{j-1})_{v_{j}})^{v^{\prime}_{j}}.$

In particular, restricting both sides to the support of $v_{j}$ we have that

$(R_{j})_{v_{j}}=(R_{j-1})_{v_{j}}-(R_{j-1})_{v_{j}}+(\partial(R_{j-1})_{v_{j}})^{v^{\prime}_{j}}_{v_{j}}=(\partial(R_{j-1})_{v_{j}})^{v^{\prime}_{j}}_{v_{j}}.$

Note that the right-hand side is equal to
$((\partial(R_{j-1})_{v_{j}})_{v_{j}}))^{v^{\prime}_{j}}$, i.e. we can first
restrict to $v_{j}$ and then append $v^{\prime}_{j}$. However, this is $0$ by
Claim 5.11 (and the fact that $\partial R_{j-1}=\partial
R_{0}-\sum_{r=0}^{j-1}\partial\partial T_{r}=0$). So in conclusion we have
that $(R_{j})_{v_{j}}=0$ and $v_{j}\notin vs(R_{j})$.

Finally we explain why the last item holds. Indeed, we notice that
$supp(R_{j-1})\setminus supp(R_{j})$ contains all faces in
$supp((R_{j-1})_{v_{j}})$. On the other hand, the faces in
$supp(R_{j})\setminus supp(R_{j-1})$ are faces of the form $(s\setminus
v_{j})\cup\\{v_{j^{\prime}}\\}$ for faces $s\in supp((R_{j-1})_{v_{j}})$. This
is because faces in $supp(R_{j})\setminus supp(R_{j-1})$ can come from
$\partial T_{j}$. Faces in $\partial T_{j}$ that are not of the form
$(s\setminus v_{j})\cup\\{v_{j^{\prime}}\\}$ for faces $s\in
supp((R_{j-1})_{v_{j}})$, must contain $v_{j}$ (since
$T_{j}=((R_{j-1})_{v_{j}})^{v^{\prime}_{j}}$ and thus all its faces contain
$v_{j}$) but as we saw $v_{j}\notin vs(R_{j})$ so all these faces are not in
the support of $R_{j}$. Hence $\lvert supp(R_{j})\rvert\leqslant\lvert
supp(R_{j-1})\rvert$. ∎

###  5.3 Proof of Theorem 5.1

###### Proof.

Lemma 5.2 says that the homogeneous geometric lattice satisfies the
assumptions of Theorem 4.1, with $\beta=\beta^{\prime}_{k}=\exp(-O(k^{2}\log
k))$ and $p=p_{k}=\exp(-O(k^{5}\log k))$. Thus concluding that $X$ is a
coboundary expander and that

$h^{k}(X,\Gamma)\geqslant\frac{p_{k}\beta_{k}^{\prime
k+1}}{e(k+2)!}=\exp(-O(k^{5}\log k)).$

∎

##  6 Applications to known bounded degree complexes

###  6.1 Cosystolic expansion of known complexes

####  6.1.1 [LSV05] complexes

We now put everything together and show that complexes constructed by
Lubotzky, Samuels and Vishne have degree and dimension independent cosystolic
expansion. Recall the following properties of their construction.

######  Theorem (Restatement of Theorem 2.7).

For any prime power $q$ and integer $d>1$, there is a family
$\mathcal{X}_{q,d}=\\{X_{n}\\}_{n=1}^{\infty}$ of connected complexes whose
links are (isomorphic copies of) the $SL_{d}(\mathbb{F}_{q})$-spherical
building. In particular, For every $\lambda>0$ there is some $q_{0}$ so that
every $X_{n}$ is a $\lambda$-one sided high dimensional expander when
$q\geqslant q_{0}$.

######  Theorem 6.1.

For every $k>0$ there is some constant $\beta_{k}=\exp(-O(k^{6}\log k))>0$ and
integer $q_{0}$ so that for every prime power $q>q_{0}$, integer $d>k+2$,
group $\Gamma$, and $X\in\mathcal{X}_{q,d}$ it holds that

$h^{k}(X,\Gamma)\geqslant\beta_{k}.$

###### Proof of Theorem 6.1.

We wish to apply Theorem 1.2 to the complexes of Theorem 2.7. By Theorem 5.1
there is a sequence of constants $\\{\beta_{\ell}=\exp(-O(\ell^{5}\log
k))\\}_{\ell=0}^{k}$ so that for every $q,d$ the spherical building
$SL_{d}(\mathbb{F}_{q})$ satisfies
$h^{\ell}(SL_{d}(\mathbb{F}_{q}),\Gamma)\geqslant\beta_{\ell}$ for every group
$\Gamma$. There is some $q_{0}$ so that for every $q>q_{0}$, $X_{n}$ are also
$\lambda$-expanders for $\lambda=\exp(-O(k^{6}\log k))$. Applying Theorem 1.2,
we get that $h^{\ell}(X_{n},\Gamma)\geqslant\exp(-O(\ell^{6}\log\ell))$ for
every $\ell\leqslant k$, and in particular, this holds for $h^{k}$ as claimed.
∎

Observe that our theorem (as well as previous bounds of [KKL14, EK16]) holds
only for LSV complexes $\mathcal{X}_{q,d}$ with sufficiently large $q>q_{0}$.
It seems reasonable that even for $q=2$ the theorem should hold, but we leave
this as an open question.

####  6.1.2 [KO21] complexes

Kaufman and Oppenheim showed that links of their complexes are spectral
expanders, and also coboundary expanders for $1$-chains.

######  Theorem (Restatement of Theorem 2.8).

For every $\lambda>0$ there exists a family of $4$-partite complexes
$\mathcal{Y}_{\lambda}=\\{Y_{n}\\}_{n=1}^{\infty}$ so that

  1. 1.

$Y_{n}$ is a $\lambda$-one sided high dimensional expander.

  2. 2.

There exists a constant $\beta>0$ (independent of $\lambda$) so that for every
abelian group $\Gamma$ and every $s\in Y_{n}(0)$, the link of $s$ has
$h^{1}(Y_{s},\Gamma)\geqslant\beta$.

Applying our Theorem 1.2 implies stronger bounds on the cosystolic expansion
of $Y_{n}$:

######  Theorem 6.2.

For every $d$ there exists some $\lambda>0$ and some
$\beta^{\prime}=\frac{\beta^{2}}{2}(1-O(\lambda))$ so that for every abelian
group $\Gamma$ and every $Y_{n}\in\mathcal{Y}_{\lambda,d}$

$h^{1}(Y_{n},\Gamma)\geqslant\beta^{\prime}.$

The proof of Theorem 6.2 is just applying Theorem 1.2 on every
$Y_{n}\in\mathcal{Y}_{\lambda,d}$, and is therefore omitted.

###  6.2 Topological overlap of LSV complexes

Let $X$ be $d$-dimensional simplicial complex. $X$ is also a topological space
constructed by taking a $d$-simplex for every $t\in X(d)$ and gluing two
simplexes $t_{1},t_{2}$ over their intersection $t_{1}\cap t_{2}$.

######  Definition 6.3.

Let $X$ be a $d$-dimensional simplicial complex and let $c>0$. We say that $X$
has $(c,k)$-topological overlap if for every continuous map
$f:X\to\mathbb{R}^{k}$ there exists a point $p\in\mathbb{R}^{k}$ so that

$\operatorname*{\mathbb{P}}_{{t\in X(d)}}\left[p\in f(t)\right]\geqslant c.$

We call such a point $p$ a $c$-heavily covered point (with respect to $f$),
since if the measure on $X(d)$ is uniform, this is proportional to the number
of $d$-faces covering $p$.

######  Theorem 6.4 ([Gro03]).

Let $X$ be a simplicial complex so that

  1. 1.

For every $\ell\leqslant k$, $h^{\ell}(X,\mathbb{F}_{2})\geqslant\beta$.

  2. 2.

For every $\ell\leqslant k$ and every $g\in Z^{k}(X,\mathbb{F}_{2})\setminus
B^{k}(X,\mathbb{F}_{2})$, $wt(g)\geqslant\nu$.

  3. 3.

$\max_{v\in
X(0)}\operatorname*{\mathbb{P}}\left[{v}\right]\leqslant\varepsilon$.

Then the $k$-skeleton of $X$ has $(c,k)$-topological overlap (i.e. for
continuous functions to $R^{k}$) for
$c=\frac{\nu\beta^{k+1}}{2(k+1)!}-\varepsilon k^{2}\beta^{-(2k+1)}$.

The constant $c$ was estimated by [DKW18]. In addition, it turns out that one
can replace $R^{k}$ with any $k$-dimensional manifold that admits a piecewise-
linear triangulation, and this theorem still holds.

The work by [EK16] used this theorem to show that [LSV05] complexes have the
topological overlap properties. Namely, they showed that these complexes have

$h^{k}(X,\beta)=\Omega(\min\\{\frac{1}{Q},(d!)^{-O(2^{k})}\\}),$

where $d$ is the dimension of the complex, and $Q$ is the maximal number of
edges adjacent to a vertex. They also show that $g\in
Z^{k}(X,\mathbb{F}_{2})\setminus B^{k}(X,\mathbb{F}_{2})$ has weight at least
$\nu=(d!)^{-O(2^{k})}$. Plugging this in Theorem 6.4 gives a topological
overlap constant of $c=Q^{-k}\exp(-O(2^{k}d\log d))$.

A direct application of our cosystolic expansion bounds, together with
Proposition 3.2, gives us bounds that are independent of the degree of the
vertices, and the ambient dimension of the complex. In addition, it gives a
better dependence in $k$ (exponential instead of doubly exponential).

######  Corollary 6.5.

Let $\\{X_{n}\\}$ be the simplicial complexes in Theorem 6.1. Then $X_{n}$
have the $(c,k)$-topological overlap with $c=\exp(-O(k^{7}\log
k))-\varepsilon\cdot\exp(O(k^{7}\log k)),$ where
$\varepsilon=\frac{1}{|X_{n}(0)|}$ (and goes to $0$ independent of $k$).

We note that a similar corollary holds for the spherical building and other
homogenuous lattices.

###### Proof.

The corollary follows from plugging in the parameters of the complexes in
Theorem 6.1, to Theorem 6.4. Theorem 6.1 gives us
$h^{k}(X,\mathbb{F}_{2})=\exp(-O(k^{6}\log k))$ cosystolic expansion.
Proposition 3.2 give us a bound of $\nu=\exp(-O(k^{6}\log k))$ on the weight
of all $g\in Z^{k}(X,\mathbb{F}_{2})\setminus B^{k}(X,\mathbb{F}_{2})$. ∎

Our bounds also directly imply that the $2$-skeletons of all complexes
constructed in [KO21] have $\Omega(1)$-topological overlap (where previously
the bound depended on the maximal degree of a vertex). We omit the direct
proof.

######  Corollary 6.6.

Let $\\{Y_{n}^{\prime}\\}$ be the two skeletons of complexes in Theorem 6.2
with a sufficiently large number of vertices. Then every $Y_{n}$ is a
$(c,1)$-topological overlap for some universal constant $c>0$. ∎

###  6.3 Cover stability

Dinur and Meshulam studied local testability of covers [DM22], and showed that
covering maps of a simplicial complex $X$ are locally testable if and only if
$X$ is a cosystolic expander on $1$-chains. We briefly describe their result
below, and show that our new bounds on cosystolic expansion of $1$-chains of
[LSV05] and [KO21] complexes, show that covering maps to these complexes are
locally testable.

######  Definition 6.7 (covering map).

Let $X,Y$ be pure simplicial complexes. A covering map is a surjective
simplicial map999that is, for every $i\leqslant d$ and every $s\in Y(i)$,
$\rho(s)\in X(i)$. $\rho:Y(0)\to X(0)$ such that for every $\tilde{u}\in Y(0)$
that maps to $\rho(\tilde{u})=u\in X(0)$, it holds that
$\rho|_{Y_{\tilde{u}}(0)}:Y_{\tilde{u}}(0)\to X_{u}(0)$ is an isomorphism. If
there exists such a map $\rho$ we say that $Y$ is a cover of $X$.

While covering maps are described combinatorially in simplicial complexes,
they are a well-known topological notion in general topological spaces. They
are classified by the fundamental group of the complex $X$ [Sur84]. This is an
interesting example for a non-trivial topological property that is locally
testable.

The one-dimensional case, i.e. graph covers, have been useful in construction
of expander graphs. Bilu and Linial showed that random covers of Ramanujan
graphs are almost Ramanujan [BL06]. A celebrated result by [MSS15] used these
techniques to construct bipartite Ramanujan graphs of every degree. Recently,
[Dik22] showed that random covers could also be applied for constructing new
local spectral expanders.

##### Local testability of covering maps

Given a map $\rho:Y(0)\to X(0)$, we wish to test whether $(Y,\rho)$ is close
to a covering map (in Hamming distance), while querying only a few of the
values $(u,\rho(u))$.

To describe such a test restrict ourselves to the following family of maps.
Fix $X$ to be some pure $d$-dimensional simplicial complex. Let $S$ be a set,
and $\Gamma\leqslant Sym(S)$ be a group acting on $S$. The family of functions
we consider are $M(\Gamma,S)$ (suppressing $X$ in the notation). These are all
$(\rho,Y)$ such that

  1. 1.

$Y(0)=X(0)\times S$,

  2. 2.

$\rho(u,s)=u$ and

  3. 3.

For every $uv\in X(1)$ the complex induced by the vertices
$\left\\{(u,s),(v,s)\left|\;\vphantom{(u,s),(v,s)s\in S}\right.s\in
S\right\\}\subseteq Y(0)$ is a perfect matching where
$(u,s)\sim(v,\gamma_{uv}.s)$ for some $\gamma_{uv}\in\Gamma$.

The distance between two maps is

$\operatorname{dist}((Y_{1},\rho_{1}),(Y_{2},\rho_{2}))=\operatorname*{\mathbb{P}}_{{uv\in
X(1)}}\left[\gamma^{Y_{1}}_{uv}\neq\gamma^{Y_{2}}_{uv}\right],$

where $\gamma^{Y_{i}}_{uv}$ is the member in $\Gamma$ that describes the
bipartite graph induced by
$\left\\{(u,s),(v,s)\left|\;\vphantom{(u,s),(v,s)s\in S}\right.s\in
S\right\\}\subseteq Y_{i}$. We note that when $S$ is finite this is
proportional to the Hamming distance between $Y(1),Y(2)$.

While this restriction seems arbitrary, it turns out that for every pair
$(Y,\rho:Y(0)\to X(0))$ where $\rho$ is a covering map, there exists some
$\Gamma,S$ and an identification $Y(0)\cong X(0)\times S$ such that
$\rho(u,s)=u$ [Sur84]. However, being in $M(\Gamma,S)$ is not sufficient to
being a covering map. A map in $M(\Gamma,S)$ above is a covering map if and
only if for every $uvw\in\overset{\to}{X}(2)$,

$\displaystyle\gamma_{uv}\gamma_{vw}\gamma_{wu}=e.$ (6.1)

We denote by $M_{0}(\Gamma,S)\subseteq M(\Gamma,S)$ the family of covering
maps $(Y,\rho)$ satisfying (6.1).

The local condition (6.1) gives rise to a local test.

######  Test 6.8.

Input: $(Y,\rho)\in M(\Gamma,S)$.

  1. 1.

Sample $uvw\in\overset{\to}{X}(2)$.

  2. 2.

Accept if (6.1) holds for $uvw$.

We note that this test could be realized by sampling $3|S|$ points in $Y(0)$
and their values. We denote by $c(Y,\rho)=\operatorname*{\mathbb{P}}_{{uvw\in
X(2)}}\left[\text{test fails}\right],$ and for a complex $X$ we define its
$(G,S)$-_cover-stability_ to be

$C(X,\Gamma,S)=\min_{(Y,\rho)\in M(\Gamma,S)\setminus
M_{0}(\Gamma,S)}\frac{C(Y,\rho)}{\operatorname{dist}((Y,\rho),M_{0}(\Gamma,S))}.$

We say that $X$ is $c$-cover stable, if for all $\Gamma,S$ it holds that
$C(X,\Gamma,S)\geqslant c$.

######  Theorem 6.9 ([DM22]).

Let $X$ be a $d$-dimensional simplicial complex for $d\geqslant 2$. Then
$C(X,\Gamma,S)=h^{1}(X,\Gamma)$.

This test has been used as a component in the agreement test by [GK22, Lemma
3.26]101010While they don’t use this language to define their test, one may
verify that their test is equivalent to this one.. Our results show directly
that the complexes of [LSV05] and [KO21] are cover-stable.

######  Corollary 6.10.

There exists some absolute constant $c>0$, such that

  * –

Order complexes of homogenuous lattices,

  * –

the complexes in Theorem 6.1,

  * –

and the complexes in Theorem 6.2.

are all $c$-cover stable. ∎

We point out in particular the meaning of this theorem for the case of the
spherical building. The fundamental group of the spherical building is
trivial, so it has no non-trivial covers. In other words, any cover is just a
bunch of disjoint copies of the original complex. The theorem says that any
approximate cover of the spherical building must approximately split into a
bunch of disjoint copies.

## References

  * [FK81] Z. Furedi and J. Komlos  “The eigenvalues of random symmetric matrices”  In _Combinatorica_ 1, 1981, pp. 233–241  DOI: 10.1007/BF02579329
  * [Bjö84] Anders Björner  “Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings”  In _Advances in Mathematics_ 52, 1984, pp. 173–212
  * [Sur84] David Surowski  “Covers of simplicial complexes and applications to geometry”  In _Geometriae Dedicata_ 16, 1984, pp. 35–62  DOI: 10.1007/BF00147420
  * [Gro03] M. Gromov  “Random walk in random groups”  In _Geom. Funct. Anal._ 13, 2003, pp. 73–146  DOI: 10.1007/s000390300002
  * [LSV05] Alexander Lubotzky, Beth Samuels and Uzi Vishne  “Explicit constructions of Ramanujan complexes of type $\tilde{A_{d}}$”  In _European J. Combin._ 26.6, 2005, pp. 965–993  DOI: 10.1016/j.ejc.2004.06.007
  * [LSV05a] Alexander Lubotzky, Beth Samuels and Uzi Vishne  “Ramanujan complexes of type $\tilde{A_{d}}$”  In _Israel J. Math._ 149.1, 2005, pp. 267–299  DOI: 10.1007/BF02772543
  * [BL06] Yehonatan Bilu and Nathan Linial  “Lifts, Discrepancy and Nearly Optimal Spectral Gap”  In _Combinatorica_ 26.1439-6912, 2006, pp. 495–519  DOI: https://doi.org/10.1007/s00493-006-0029-7
  * [LM06] Nathan Linial and Roy Meshulam  “Homological Connectivity Of Random 2-Complexes”  In _Combinatorica_ 26, 2006, pp. 475–487  DOI: 10.1007/s00493-006-0027-9
  * [Koz08] Dmitry N. Kozlov  “Combinatorial Algebraic Topology” 21, Algorithms and computation in mathematics  Springer, 2008  DOI: 10.1007/978-3-540-71962-5
  * [MW09] Roy Meshulam and N. Wallach  “Homological connectivity of random _k_ -dimensional complexes”  In _Random Struct. Algorithms_ 34.3, 2009, pp. 408–417  DOI: 10.1002/rsa.20238
  * [Gro10] M. Gromov  “Singularities, Expanders and Topology of Maps. Part 2: from Combinatorics to Topology Via Algebraic Isoperimetry”  In _Geom. Funct. Anal._ 20, 2010, pp. 416–526  DOI: 10.1007/s00039-010-0073-8
  * [KKL14] Tali Kaufman, David Kazhdan and Alexander Lubotzky  “Ramanujan Complexes and Bounded Degree Topological Expanders”  In _Proc. $55$th IEEE Symp. on Foundations of Comp. Science (FOCS)_, 2014, pp. 484–493  DOI: 10.1109/FOCS.2014.58
  * [KL14] Tali Kaufman and Alexander Lubotzky  “High dimensional expanders and property testing”  In _Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12-14, 2014_ , 2014, pp. 501–506
  * [MSS15] Adam W. Marcus, Daniel A. Spielman and Nikhil Srivastava  “Interlacing families I: Bipartite Ramanujan graphs of all degrees”  In _Annals of Mathematics_ 182, 2015, pp. 307–325  DOI: 10.4007/annals.2015.182.1.7
  * [EK16] Shai Evra and Tali Kaufman  “Bounded degree cosystolic expanders of every dimension”  In _Proc. $48$th ACM Symp. on Theory of Computing (STOC)_, 2016, pp. 36–48  DOI: 10.1145/2897518.2897543
  * [LMM16] Alexander Lubotzky, Roy Meshulam and Shahar Mozes  “Expansion of building-like complexes”  In _Groups, Geometry, and Dynamics_ 10.1, 2016, pp. 155–175
  * [Dik+18] Yotam Dikstein, Irit Dinur, Yuval Filmus and Prahladh Harsha  “Boolean function analysis on high-dimensional expanders”  In _Proc. $20$th International Workshop on Randomization and Computation (RANDOM)_ 116 Princeton, NJ: RANDOM/APPROX, 2018, pp. 37:1–37:21  DOI: 10.4230/LIPIcs.APPROX/RANDOM.2018.37
  * [DKW18] Dominic Dotterrer, Tali Kaufman and Uli Wagner  “On expansion and topological overlap”  In _Geometriae Dedicata_ 195, 2018, pp. 307–317
  * [KM18] Tali Kaufman and David Mass  “Good Distance Lattices from High Dimensional Expanders” (manuscript), 2018  eprint: 1803.02849
  * [KO18] Tali Kaufman and Izhar Oppenheim  “Construction of new local spectral high dimensional expanders”  In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018_ , 2018, pp. 773–786
  * [Opp18] Izhar Oppenheim  “Local Spectral Expansion Approach to High Dimensional Expanders Part I: Descent of Spectral Gaps”  In _Discrete Comput. Geom._ 59.2, 2018, pp. 293–330  DOI: 10.1007/s00454-017-9948-x
  * [Ana+19] Nima Anari, Kuikui Liu, Shayan Oveis Gharan and Cynthia Vinzant  “Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid”  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019_ ACM, 2019, pp. 1–12  DOI: 10.1145/3313276.3316385
  * [KM19] Dmitry N Kozlov and Roy Meshulam  “Quantitative aspects of acyclicity”  In _Research in the Mathematical Sciences_ 6.4 Springer, 2019, pp. 1–32
  * [CLY20] Michael Chapman, Nathan Linial and Peled Yuval  “Expander Graphs — Both Local and Global”  In _Combinatorica_ 40, 2020, pp. 473–509  DOI: 10.1007/s00493-019-4127-8
  * [EKZ20] Shai Evra, Tali Kaufman and Gilles Zémor  “Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders”  In _61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020_ IEEE, 2020, pp. 218–227  DOI: 10.1109/FOCS46700.2020.00029
  * [KO20] Tali Kaufman and Izhar Oppenheim  “High Order Random Walks: Beyond Spectral Gap”  In _Comb._ 40.2, 2020, pp. 245–281  DOI: 10.1007/s00493-019-3847-0
  * [LMY20] Siqi Liu, Sidhanth Mohanty and Elizabeth Yang  “High-Dimensional Expanders from Expanders”  In _11th Innovations in Theoretical Computer Science Conference (ITCS 2020)_ , 2020
  * [Gol21] Louis Golowich  “Improved Product-Based High-Dimensional Expanders”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)_ 207, 2021  DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.38
  * [KM21] Tali Kaufman and David Mass  “Unique-Neighbor-Like Expansion and Group-Independent Cosystolic Expansion”  In _32nd International Symposium on Algorithms and Computation (ISAAC 2021)_ 212, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, pp. 56:1–56:17  DOI: 10.4230/LIPIcs.ISAAC.2021.56
  * [KO21] Tali Kaufman and Izhar Oppenheim  “Coboundary and Cosystolic Expansion from Strong Symmetry”  In _48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference)_ 198, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, pp. 84:1–84:16  DOI: 10.4230/LIPIcs.ICALP.2021.84
  * [KT21] Tali Kaufman and Ran J. Tessler  “New cosystolic expanders from tensors imply explicit Quantum LDPC codes with $\Omega$($\surd$_n_ log${}^{\mbox{\emph{k}}}$ _n_) distance”  In _STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021_ ACM, 2021, pp. 1317–1329  DOI: 10.1145/3406325.3451029
  * [Baf+22] Mitali Bafna, Max Hopkins, Tali Kaufman and Shachar Lovett  “High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games”  In _Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022_ SIAM, 2022, pp. 1069–1128  DOI: 10.1137/1.9781611977073.47
  * [Dik22] Yotam Dikstein  “New High Dimensional Expanders from Covers”, 2022
  * [Din+22] Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky and Shahar Mozes  “Locally testable codes with constant rate, distance, and locality”  In _STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022_ ACM, 2022, pp. 357–374  DOI: 10.1145/3519935.3520024
  * [DM22] Irit Dinur and Roy Meshulam  “Near coverings and cosystolic expansion”  In _Archiv der Mathematik_ 118.5, 2022, pp. 549–561  DOI: 10.1007/s00013-022-01720-6
  * [Gai+22] Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett and Ruizhe Zhang  “Eigenstripping, Spectral Decay, and Edge-Expansion on Posets”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022, September 19-21, 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference)_ 245, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 16:1–16:24  DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.16
  * [GK22] Roy Gotlib and Tali Kaufman  “List Agreement Expansion from Coboundary Expansion”, 2022  eprint: arXiv:2210.15714
  * [GLL22] Tom Gur, Noam Lifshitz and Siqi Liu  “Hypercontractivity on high dimensional expanders”  In _STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022_ ACM, 2022, pp. 176–184  DOI: 10.1145/3519935.3520004
  * [HL22] Max Hopkins and Ting-Chun Lin  “Explicit Lower Bounds Against $\backslash$ Omega (n)-Rounds of Sum-of-Squares”  In _arXiv preprint arXiv:2204.11469_ , 2022
  * [KM22] Tali Kaufman and David Mass  “Double Balanced Sets in High Dimensional Expanders”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)_ 245, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 3:1–3:17  DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.3
  * [OP22] Ryan O’Donnell and Kevin Pratt  “High-Dimensional Expanders from Chevalley Groups”  In _37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA_ 234, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 18:1–18:26  DOI: 10.4230/LIPIcs.CCC.2022.18
  * [PK22] Pavel Panteleev and Gleb Kalachev  “Asymptotically good Quantum and locally testable classical LDPC codes”  In _STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022_ ACM, 2022, pp. 375–388  DOI: 10.1145/3519935.3520017
  * [Din+] Irit Dinur, Yuval Filmus, Prahladh Harsha and Madhur Tulsiani  “Explicit SoS lower bounds from high-dimensional expanders”  In _12th Innovations in Theoretical Computer Science (ITCS 2021)_ URL: https://arxiv.org/abs/2009.05218

##  Appendix A Non-abelian $1$-coboundary expansion in geometric lattices

In this appendix we give a proof that geometric lattices have constant
$1$-coboundary expansion, that applies to coefficients coming from non-abelian
groups.

######  Theorem A.1.

Let $d\geqslant 3$ be and integer. Let $X$ be the poset complex for some non-
abelian homogeneous lattice $P$ of rank $d$. Let $\Gamma$ be any group. Then
$H^{1}(X,\Gamma)=0$ and

$h^{1}(X,\Gamma)\geqslant\frac{1}{324\left(2+\frac{28}{6-3\sqrt{2}}\right)}.$

For this theorem we need the following lemma, whose proof is elementary
(although it uses ideas that also appear in Theorem 4.1).

######  Lemma A.2.

Let $i,j,k\in[d]$ so that $j>3i,k>3j$, or $i=1,j=2,k=3$. Then
$H^{1}(X^{\\{i,j,k\\}},\Gamma)=0$ and
$h^{1}(X^{\\{i,j,k\\}},\Gamma)\geqslant\left(2+\frac{28}{6-3\sqrt{2}}\right)^{-1}$
for any group $\Gamma$.

###### Proof of Theorem A.1.

Let $\mathcal{F}\subseteq\binom{[d]}{3}$ be the set of all $\\{i,j,k\\}$ so
that $j>2i,k>3j$ or so that $i=1,j=2,k=3$. It is easy to see that
$\operatorname*{\mathbb{P}}\left[{\mathcal{F}}\right]\geqslant\frac{1}{54}$.
By Lemma A.2, For every $F\in\mathcal{F}$ it holds that
$h^{1}(X^{F},\Gamma)\geqslant\left(2+\frac{28}{6-3\sqrt{2}}\right)^{-1}$. It
is also true that for every $F$ and $v$ so that $col(v)\notin F$ it holds that
$h^{0}(X_{v}^{F},\Gamma)\geqslant\left(2+\frac{28}{6-3\sqrt{2}}\right)^{-1}$
(recall that Claim 2.6 implies that every link is an edge expander, which by
Claim 2.3 says $h^{0}$ of the link is bounded). By Theorem 4.1, we get that

$h^{1}(X)\geqslant\frac{1}{324\left(2+\frac{28}{6-3\sqrt{2}}\right)}.$

∎

###### Proof of Lemma A.2.

Fix $i,j,k$ as in the lemma statement and set $Y=X^{\\{i,j,k\\}}$. Let
$f:Y(1)\to\Gamma$ and denote by $T=\left\\{t\in Y(2)\left|\;\vphantom{t\in
Y(2){\delta}f(t)\neq 0}\right.{\delta}f(t)\neq 0\right\\}$. Let
$\varepsilon=\operatorname*{\mathbb{P}}\left[{T}\right]$. We need to find some
$g:X(0)\to\Gamma$ so that
$\frac{1}{\left(2+\frac{28}{6-3\sqrt{2}}\right)}\operatorname{dist}(f,{\delta}g)\leqslant\varepsilon$
or equivalently
$\operatorname{dist}(f,{\delta}g)\leqslant\left(2+\frac{28}{6-3\sqrt{2}}\right)\varepsilon$.

To do so, we exploit the short cycle structure of the graph between
$Y[i],Y[j]$.

######  Claim A.3.

There is a distribution over $(w,c)$ where $w\in Y[k]$ and
$c=(u_{0},v_{0},u_{1},v_{1},u_{2},v_{2})$ is a $6$-cycle, that has the
following properties:

  1. 1.

For every $\ell\in\\{0,1,2\\}$, $u_{\ell}\in Y[\ell]$, $v_{\ell}\in Y[j]$.

  2. 2.

The vertices and edges of the cycle $c$ is contained in $Y_{w}$.

  3. 3.

Moreover, for every $\ell=0,1,2$, the marginals $(w,u_{\ell},v_{\ell})$ and
$(w,v_{\ell},u_{\ell+1})$ has the distribution of triangles in $Y$. That is,
the uniform distribution. Here the index $\ell$ is taken modulo $3$.

  4. 4.

The choice of the vertex $u_{0}$ and the edge $v_{1}u_{2}$ are uniformly
random given that $u_{0}\neq u_{2}$.

  5. 5.

Given $u_{0},v_{1},u_{2}$ in $c$, that is $c=(u_{0},*,*,v_{1},u_{2},*)$, the
path between $u_{0}$ and $v_{1}$ and the path between $u_{0}$ and $u_{2}$ are
chosen independently from one another.

Next we define a randomized labeling $\boldsymbol{g}$ to the vertices of
$Y^{\\{i,j\\}}(0)$ based on the cycle distribution above. We’ll show that the
expected distance between $f$ and ${\delta}\boldsymbol{g}$ over
$Y^{\\{i,j\\}}(0)$ is $\leqslant 6\varepsilon$. We’ll take some $g$ whose
distance is less or equal to the expectation. Then we’ll show, using a similar
argument to that of Theorem 4.1 that we can extend $g$ to $Y[k]$ so that its
distance to $f$ is still $O(\varepsilon)$.

We define a randomized labeling $\boldsymbol{g}$ to $Y[i]\cup Y[j]$ as
follows.

  1. 1.

We choose some $\hat{u}\in Y[i]$. Set $\boldsymbol{g}(\hat{u})=0$.

  2. 2.

For $v\in Y[j]$ We choose some cycle $c=(u_{0},...,v_{2})$ so that
$u_{0}=\hat{u}$ and $v_{1}=v$. We set $g(v)=f(u_{0}v_{0})\cdot
f(v_{0}u_{1})\cdot f(u_{1}v_{1})$.

  3. 3.

For $u\in Y[i]\setminus\\{\hat{u}\\}$ We choose some cycle
$c=(u_{0},...,v_{2})$ so that $u_{0}=\hat{u}$ and $u_{2}=u$. We set
$g(u)=f(u_{0}v_{2})\cdot f(v_{2}u_{2})$.

######  Claim A.4.

$\operatorname*{\mathbb{E}}_{{\boldsymbol{g}}}\left[\operatorname*{\mathbb{P}}_{{vu}}\left[f(vu)\neq\boldsymbol{g}(u)^{-1}\cdot\boldsymbol{g}(v)\right]\right]\leqslant
6\varepsilon$.

Let $g:Y^{\\{i,j\\}}(0)\to\Gamma$ be some labeling so that

$\operatorname*{\mathbb{P}}_{{vu}}\left[f(vu)\neq g(u)^{-1}\cdot
g(v)\right]\leqslant\operatorname*{\mathbb{E}}_{{\boldsymbol{g}}}\left[\operatorname*{\mathbb{P}}_{{vu}}\left[f(vu)\neq\boldsymbol{g}(u)^{-1}\cdot\boldsymbol{g}(v)\right]\right]\leqslant
6\varepsilon.$

We extend $g$ to $Y[k]$ in a similar way as in Theorem 4.1. For every $r\in
Y[k]$ we set

$g(w)=\operatorname*{maj}\left\\{g(x)f(wx)^{-1}\left|\;\vphantom{g(x)f(wx)^{-1}w\in
Y_{r}(0)}\right.w\in Y_{r}(0)\right\\}.$

To complete the proof we bound the distance between $f$ and ${\delta}g$ over
edges $wx$ where $w\in Y[k]$.

Note that $f(wx)\neq g(w)^{-1}g(x)$ if and only if $x$ doesn’t agree with the
majority vote on $g(w)$. Fix $w\in Y[k]$ and partition $Y_{w}(0)$ to sets
$S_{r}=\left\\{x\in Y_{w}(0)\left|\;\vphantom{x\in
Y_{w}(0)g(x)f(wx)^{-1}=r}\right.g(x)f(wx)^{-1}=r\right\\}$. By Claim 2.6
$Y_{w}$ is a $\frac{1-\frac{1}{\sqrt{2}}}{2}$-edge-expander, ergo by Claim
2.3, it holds for $r^{\prime}=g(w)$ that

$\operatorname*{\mathbb{P}}_{{x\in Y_{w}(0)}}\left[g(w)\neq
g(x)f(wx)^{-1}\right]=\operatorname*{\mathbb{P}}\left[{V\setminus
S_{r^{\prime}}}\right]\leqslant\frac{\sqrt{2}}{\sqrt{2}-1}\operatorname*{\mathbb{P}}_{{xy\in
Y_{r}(1)}}\left[g(x)f(wx)^{-1}\neq g(y)f(wy)^{-1}\right],$

that is, $\frac{\sqrt{2}}{\sqrt{2}-1}$ times the probability that an edge $xy$
crosses between two sets $S_{r_{1}},S_{r_{2}}$.

Taking expectation over $w$, we get that

$\displaystyle\operatorname*{\mathbb{P}}_{{w\in Y{[k]},wx\in
Y(1)}}\left[f(wx)\neq g(x)^{-1}g(w)\right]$
$\displaystyle\leqslant\operatorname*{\mathbb{E}}_{{w}}\left[\operatorname*{\mathbb{P}}_{{x\in
Y_{w}(0)}}\left[f(wx)\neq g(x)^{-1}g(w)\right]\right]$ (A.1)
$\displaystyle\leqslant\frac{\sqrt{2}}{\sqrt{2}-1}\operatorname*{\mathbb{P}}_{{wxy\in
Y(2)}}\left[g(x)f(wx)^{-1}\neq g(y)f(wy)^{-1}\right].$

When ${\delta}f(wxy)=e$ and $f(xy)=g(x)^{-1}g(y)$ then it holds that
$g(x)f(wx)^{-1}=g(y)f(wy)^{-1}$ since

$\displaystyle f(wx)^{-1}\cdot f(wy)=$ $\displaystyle
f(yx)f(wx)^{-1}f(wy)=f(yx)f(xw)f(yw)$ $\displaystyle={\delta}f(yxw)=e.$

Hence

$\displaystyle\operatorname*{\mathbb{P}}_{{wxy\in
Y(2)}}\left[g(x)f(wx)^{-1}\neq g(y)f(wy)^{-1}\right]$ $\displaystyle\leqslant$
$\displaystyle\operatorname*{\mathbb{P}}_{{xy\in Y^{ij}(0)}}\left[f(xy)\neq
g(x)^{-1}g(y)\right]+\operatorname*{\mathbb{P}}_{{wxy\in
Y(2)}}\left[{\delta}f(wxy)\neq e\right]$ $\displaystyle\leqslant
7\varepsilon.$

Plugging this back in (A.1), we get that

$\operatorname*{\mathbb{P}}_{{wx\in Y(1),w\in Y{[k]}}}\left[f(wx)\neq
g(x)^{-1}g(w)\right]\leqslant\frac{7\sqrt{3}}{\sqrt{3}-1}\varepsilon.$

Combining this with the distance of $f,{\delta}g$ on $Y^{ij}$ we have that

$\operatorname{dist}(f,{\delta}g)=\frac{1}{3}\cdot
6\varepsilon+\frac{2}{3}\cdot\frac{7\sqrt{2}}{\sqrt{2}-1}\varepsilon=\left(2+\frac{28}{6-3\sqrt{2}}\right)\varepsilon.$

∎

###### Proof of Claim A.3.

First let us ignore $w$, and describe the choice of
$c=(u_{0},v_{0},u_{1},v_{1},u_{2},v_{2})$:

  1. 1.

We choose $u_{0}\in Y[i]$.

  2. 2.

We choose an edge $v_{1}u_{2}\in Y^{\\{i,j\\}}(1)$ (where $v_{1}\in
Y[j],u_{2}\in Y[i]$), given that $u_{2}\neq u_{0}$.

  3. 3.

We choose a random neighbour $u_{1}\sim v_{1}$.

  4. 4.

We choose $v_{0},v_{2}\in Y[j]$ independently and uniformly at random given
that $u_{0}\vee u_{1}\subseteq v_{0}$ and $u_{0}\vee u_{2}\subseteq v_{2}$.

Recall that every $u_{\ell}$ is has color $i$, and every $v_{\ell}$ has color
$j\geqslant 2i$ (since $rk(a\vee b)\leqslant rk(a)+rk(b)=2i$).

It is easy to see that For every $\ell\in\\{0,1,2\\}$, $u_{\ell}\in Y[\ell]$,
$v_{\ell}\in Y[j]$. Also, by definition the choice of $u_{0}$ and the edge
$v_{1}u_{2}$ is independent given that $u_{0}\neq u_{2}$, and done according
to the distribution over $Y[i]$ and $Y^{\\{i,j\\}}(1)$ respectively.

Moreover, note that every edge in the cycle is indeed distributed uniformly
over all edges (i.e. a random $j$-colored element and $i$-colored element less
or equal to it). For example, let us consider the edge $u_{0}v_{0}$. The
vertex $u_{0}$ is a random $i$-element. The vertex $u_{1}$ is also random
(since we chose it by choosing a random $v_{1}$ and then choosing a random
element less or equal to it). Thus the choice of $v_{1}$ is also uniformly at
random over elements that contain $u_{0}$, i.e. the edge $u_{0}v_{0}$ is
chosen uniformly at random.

It is also apparent from the construction that given
$c=(u_{0},*,*,v_{1},u_{2},*)$ (which is determined in the first two steps),
the path between $u_{0}$ and $v_{1}$ and the path between $u_{0}$ and $u_{2}$
are chosen independently from one another.

Finally, the distribution of $(w,c)$ is done choosing $c$ and then choosing
uniformly some $w\in Y[k]$ that is greater or equal to vertices in $c$.

  1. 1.

If $k\geqslant 3j$ then this is possible since $rk(v_{0}\vee v_{1}\vee
v_{2})\leqslant 3j$ and since this join is randomly chosen, then we can just
choose some $c$ that contains this join.

  2. 2.

If $i=1,j=2,k=3$ then we explain why $rk(v_{0}\vee v_{1}\vee v_{2})\leqslant
3$. If all $u_{0},u_{1},u_{2}$ are distinct, then $v_{\ell}=u_{\ell}\vee
u_{\ell+1}$ and in particular $v_{0}\vee v_{1}\vee v_{2}=u_{0}\vee u_{1}\vee
u_{2}$ (and this has rank at most $3$ since every element has rank $1$).
Otherwise, either $u_{0}=u_{1}\neq u_{2}$ or $u_{0}\neq u_{1}=u_{2}$. Let’s
consider the case where $u_{0}=u_{1}\neq u_{2}$ (the second case is similar).
Then $v_{2}=v_{1}=u_{0}\vee u_{2}$. The element $v_{0}=u_{0}\vee u^{*}$ for
some $u^{*}$ of rank one. It follows that $v_{0}\vee v_{1}\vee v_{2}=u_{0}\vee
u_{2}\vee u^{*}$ and the join has rank $3$.

It needs to be verified for every $\ell=0,1,2$, the marginals
$(w,u_{\ell},v_{\ell})$ and $(w,v_{\ell},u_{\ell+1})$ has the distribution of
triangles in $Y$. But this holds since by the above, the distribution of
$(u_{\ell},v_{\ell})$ and $(v_{\ell},u_{\ell+1})$ is the distribution of edges
in $Y_{w}^{\\{i,j\\}}(1)$, and $w$ is chosen uniformly given that $w\geqslant
v_{\ell}$. ∎

###### Proof of Claim A.4.

$\operatorname*{\mathbb{E}}_{{\boldsymbol{g}}}\left[\operatorname*{\mathbb{P}}_{{vu}}\left[f(vu)\neq\boldsymbol{g}(u)^{-1}\cdot\boldsymbol{g}(v)\right]\right]=\operatorname*{\mathbb{E}}_{{g,vu}}\left[{\mathbf{1}}_{f(vu)\neq\boldsymbol{g}(u)^{-1}\cdot\boldsymbol{g}(v)}\right]$
(A.2)

Fix and edge $vu$ so that $v\in Y[j],u\in Y[i]$. The marginal of the values of
$\boldsymbol{g}(u),\boldsymbol{g}(v)$ could be described as follows:

  1. 1.

Choose $u_{0}$.

  2. 2.

Choose $(w,c)$ as in Claim A.3 given that $c=(u_{0},*,*,v_{1}=v,u_{2}=u,*)$
(or if $u_{0}=u_{2}$ given that $c=(0_{0},*,*,v_{1}=v,*,*)$).

  3. 3.

Set $\boldsymbol{g}(v)=f(u_{0}v_{0})\cdot f(v_{0}u_{1})\cdot f(u_{1}v_{1})$
and set $\boldsymbol{g}(u)=f(u_{0}v_{2})\cdot f(v_{2}u_{2})$ (or if
$u_{0}=u_{2}$ then $\boldsymbol{g}(u_{2})=e$).

The reason we can choose _one_ cycle and not two in the second step in the
common case where $u_{0}\neq u_{2}$, is because given that
$c=(u_{0},*,*,v_{1}=v,u_{2}=u,*)$, the paths from $u_{0}$ to $v_{1}$ and from
$u_{2}$ to $u_{2}$ are independent.

Let us analyze the more common case where $u_{2}\neq u_{0}$ first. In this
case (A.2) is equal to

$\displaystyle\operatorname*{\mathbb{P}}_{{c}}\left[f(v_{1}u_{2})\neq\boldsymbol{g}(u_{2})^{-1}\cdot\boldsymbol{g}(v_{1})^{-1}\left|\;\vphantom{f(v_{1}u_{2})\neq\boldsymbol{g}(u_{2})^{-1}\cdot\boldsymbol{g}(v_{1})^{-1}u_{2}\neq
u_{0}}\right.u_{2}\neq u_{0}\right]$ $\displaystyle=$ (A.3)
$\displaystyle\operatorname*{\mathbb{P}}_{{c}}\left[f(v_{1}u_{2})\neq[f(u_{2}v_{2})\cdot
f(v_{2}u_{0})]\cdot[f(u_{0}v_{0})\cdot f(v_{0}u_{1})\cdot
f(u_{1}v_{1})]\right]=$
$\displaystyle\operatorname*{\mathbb{P}}_{{c}}\left[f(u_{0}v_{0})\cdot
f(v_{0}u_{1})\cdot f(u_{1}v_{1})\cdot f(v_{1}u_{2})\cdot f(u_{2}v_{2})\cdot
f(v_{2}u_{0})\neq e\right]$

Suppose there is some $w\in Y[k]$ that contains $c$ so that for every
$(u_{\ell},v_{\ell})$ and every $(v_{\ell},u_{\ell+1})$ it holds that
${\delta}f(wu_{\ell}v_{\ell})={\delta}f(wv_{\ell}u_{\ell+1})=e$. By
multiplying by $e=f(u_{\ell}w)f(wu_{\ell})=f(v_{\ell}w)f(wv_{\ell})$ between
the original edges we get that

$\displaystyle\begin{aligned} f(u_{0}v_{0})\cdot f(v_{0}u_{1})\cdot
f(u_{1}v_{1})\cdot f(v_{1}u_{2})\cdot f(u_{2}v_{2})\cdot f(v_{2}u_{2})&=\\\
&f(u_{0}w)[f(wu_{0})f(u_{0}v_{0})f(v_{0}w)]\cdot&\\\
&\cdot[f(wv_{0})f(v_{0}u_{1})f(u_{1}w)]\\\
&\cdot...\cdot[f(wv_{2})f(v_{2}u_{0})f(u_{0}w)]f(wu_{0})=\\\
&f(u_{0}w)\cdot{\delta}f(wu_{0}v_{0})\cdot...\cdot{\delta}f(wv_{2}u_{0})\cdot
f(wu_{0})=\\\ e\end{aligned}$ (A.4)

Thus the probability in (A.3) is upper bounded by
$\operatorname*{\mathbb{P}}_{{(w,c)}}\left[\exists uv\in c\;{\delta}f(wuv)\neq
0\right]$. As the marginal of every $wuv$ for $uv\in c$ is the probability of
sampling a uniform triangle, and there are $6$ edges in $c$, by union bound

$\operatorname*{\mathbb{E}}_{{\boldsymbol{g}}}\left[\operatorname*{\mathbb{P}}_{{vu}}\left[f(vu)\neq\boldsymbol{g}(u)^{-1}\cdot\boldsymbol{g}(v)\right]\right]\leqslant\operatorname*{\mathbb{P}}_{{(w,c)}}\left[\exists
uv\in c\;{\delta}f(wuv)\neq 0\right]\leqslant 6\varepsilon.$

The case where $u_{0}=u_{2}$ is even simpler. In this case,
$f(u_{0}v_{1})\neq\boldsymbol{g}(u_{0})^{-1}\boldsymbol{g}(v_{2})=f(u_{0}v_{0})f(v_{0}u_{1})f(u_{1}v_{1})$.
Here again, if there is a $w\in Y[k]$ that contains $c$ so that the
coboundaries

${\delta}f(wu_{0}v_{0})={\delta}f(wv_{0}u_{1})={\delta}f(wu_{1}v_{1})={\delta}f(wv_{1}u_{0})=0$

then the same analysis above (where we multiply by elements of the form
$f(wx)f(xw)$) shows that
$f(u_{0}v_{1})=\boldsymbol{g}(u_{0})^{-1}\boldsymbol{g}(v_{2})$. This happens
with probability $\leqslant 4\varepsilon$. ∎

##  Appendix B Cosystolic expansion of dense complexes is at most $1+o(1)$

In this section we give a simple upper bound on cosystolic expansion of dense
complexes.

######  Proposition B.1.

Let $\varepsilon>0$. Let $X$ be a $d$-dimensional simplicial complex for
$d\geqslant k+1$. Assume that for every $j$, the probability of $s\in X(j)$ is
$\frac{1}{|X(j)|}$. Let
$\varepsilon=\max(\sqrt{\frac{8|X(k-1)|}{|X(k)|}},\sqrt{\frac{9}{|X(k+1)|}})$
and assume that $\varepsilon\leqslant\frac{1}{2}$. Then
$h^{k}(X,\mathbb{F}_{2})\leqslant 1+8\varepsilon$.

For example, this proposition implies the following. If a $\\{X_{n}\\}$ are a
family of simplicial complexes whose vertex set is growing to infinity, and so
that $\lim_{n\to\infty}\frac{|X(k-1)|}{|X(k)|}=0$ then for every
$\varepsilon>0$, all but finitely many $X_{n}$ have that
$h^{k}(X_{n},\mathbb{F}_{2})\leqslant 1+\varepsilon$.

There are many complexes so that these conditions hold. For example, the
complete complex, the complete bipartite complex, and the spherical building
(when $d>\frac{k}{2}$).

###### Proof.

We sample $f\in C_{k}(X,\mathbb{F}_{2})$ uniformly at random (i.e. we fix some
global order of the vertices. For every $s\in\overset{\to}{X}(k)$ that is
ordered according to this global order we sample $f(s)\in\mathbb{F}_{2}$, and
extend this asymmetrically). We note that every $s$ was chosen independently.

Fixed some $g\in C_{k-1}(X,\mathbb{F}_{2})$. Let
$X_{g}(f)=\operatorname*{\mathbb{P}}_{{s\in
X(k)}}\left[f(s)={\delta}g(s)\right]$. Obviously, $X_{g}(f)=\sum_{s\in
X(k)}\operatorname*{\mathbb{P}}\left[{s}\right]{\mathbf{1}}_{f(s)={\delta}g(s)}$.
As all the random variables ${\mathbf{1}}_{f(s)=g(s)}$ are independent, and
have expectation $\frac{1}{2}$ it holds by Chernoff’s bound that

$\operatorname*{\mathbb{P}}_{{f}}\left[X_{g}(f)\geqslant\frac{1}{2}+\varepsilon\right]\leqslant
e^{-\frac{\varepsilon^{2}}{1+\varepsilon}|X(k)|}.$

There are $\lvert B^{k}(X,\mathbb{F}_{2})\rvert\leqslant\lvert
C_{k-1}(X,\mathbb{F}_{2})\rvert\leqslant 2^{|X(k-1)|}$ possible coboundaries.
Hence, the probability that there exists some $g$ so that
$X_{g}(f)\geqslant\frac{1}{2}+\varepsilon$ is at most

$e^{|X(k-1)|\ln 2}e^{-\frac{\varepsilon^{2}}{1+\varepsilon}|X(k)|},$

which is less than $\frac{1}{2}$ by the assumption on $\varepsilon$. Note that
when $X_{g}(f)\leqslant\frac{1}{2}+\varepsilon$ for all $g$ this implies that
$\operatorname{dist}(f,Z_{k}(X,\mathbb{F}_{2}))\geqslant\frac{1}{2}-\varepsilon$.

On the other hand, let $Y(f)=\operatorname*{\mathbb{P}}_{{t\in
X(k+1)}}\left[f(t)=0\right]$. As above it holds that
$\operatorname*{\mathbb{E}}[Y]=\frac{1}{2}$. Furthermore, $Y=\sum_{t\in
X(k+1)}\operatorname*{\mathbb{P}}\left[{t}\right]{\mathbf{1}}_{{\delta}f(t)=0}$
where the set $\\{{\mathbf{1}}_{{\delta}f(t)=0}\\}_{t\in X(k+1)}$ are pairwise
independent. This is because any two distinct $t,t^{\prime}\in X(k+1)$ share
only one $k$-face. By pairwise independence, $Var(Y(f))=\sum_{t\in
X(k+1)}Var(\operatorname*{\mathbb{P}}\left[{t}\right]{\mathbf{1}}_{{\delta}f(t)=0})=\frac{1}{4|X(k+1)|}.$
In particular,

$\operatorname*{\mathbb{P}}_{{f}}\left[Y(f)\leqslant\frac{1}{2}-\varepsilon\right]\leqslant\frac{1}{4|X(k+1)|\varepsilon^{2}}.$

Which is also strictly less than $\frac{1}{2}$ by assumption.

In particular, as the events $\\{\forall
g;X_{g}(f)\geqslant\frac{1}{2}+\varepsilon\\}$ and
$\\{Y(f)\leqslant\frac{1}{2}-\varepsilon\\}$ happen with probability less than
$\frac{1}{2}$, there exists some $f$ so that for every $g\in
C_{k-1}(X,\Gamma)$,
$\operatorname{dist}(f,{\delta}g)\geqslant\frac{1}{2}-\varepsilon$ but
$wt({\delta}f)\geqslant\frac{1}{2}+\varepsilon.$ Hence
$h^{k}(f,\Gamma)\leqslant\frac{\frac{1}{2}+\varepsilon}{\frac{1}{2}-\varepsilon}\leqslant
1+8\varepsilon$. ∎


11institutetext:  Sorbonne Université, Inserm, LIMICS, Paris, France
22institutetext: SCAI, Sorbonne Université, Paris, France

# Effect of depth order on iterative nested named entity recognition models

Perceval Wajsbürt 11 Yoann Taillé 1122 Xavier Tannier
11

###### Abstract

This paper studies the effect of the order of depth of mention on nested named
entity recognition (NER) models. NER is an essential task in the extraction of
biomedical information, and nested entities are common since medical concepts
can assemble to form larger entities. Conventional NER systems only predict
disjointed entities. Thus, iterative models for nested NER use multiple
predictions to enumerate all entities, imposing a predefined order from
largest to smallest or smallest to largest. We design an order-agnostic
iterative model and a procedure to choose a custom order during training and
prediction. To accommodate for this task, we propose a modification of the
Transformer architecture to take into account the entities predicted in the
previous steps. We provide a set of experiments to study the model’s
capabilities and the effects of the order on performance. Finally, we show
that the smallest to largest order gives the best results.

###### Keywords:

named entity recognition, biomedical, nested entities

##  1 Introduction

Biomedical concept recognition is a classical and essential task of natural
language processing for biomedical applications [25], aiming to extract
information such as symptoms, treatments, proteins, genes, dates, and
durations from free text. Classic methods assume that entities are disjoint
and formulate the problem as a sequence segmentation task, using word tagging
schemes. However, in a real-world scenario, entities can compose or overlap,
thus breaking the assumption that they are disjoint. For example, a temporal
event "after anesthesia" contains the nested treatment entity "anesthesia."

Multiple methods have been proposed to tackle this problem, ranging from
exhaustive filtering of all possible spans to complex graph structures.

A class of methods deals with this problem of nested named entity recognition
with a cascade of flat (non-nested) named entity recognition layers for
different depths, i.e., predict the entities at a given depth iteratively
starting either from large entities or short entities. The predictions of a
given depth are used as additional input for the next prediction. We can argue
whether the depth order matters during the training of such a model: is it
easier for the model to predict large entities first and look inside its
previous predictions for smaller ones, or predict small entities and compose
them to build larger ones? To answer this question, we design an order-
agnostic auto-regressive model based on the Transformer encoder architecture
and a procedure to let it choose a custom order during training and
prediction.

This work was originally designed to address Task 3 of the DEFT 2020
evaluation campaign (in French), and we further evaluated it on the classical
GENIA dataset (in English). This DEFT task deals with the detection of named
entities in texts describing clinical cases [7]. The different types of
entities are, on the one hand, pathologies and signs or symptoms (task 3.1),
and on the other hand, anatomy, anatomy examinations, substances, doses,
administration methods, treatments (surgical or medical), values, time. More
details about the challenge are presented in [1], in which we describe our 3
official submissions.

To our knowledge, our work is the first to evaluate a nested biomedical
concept recognition system in the French language, which constitutes an
additional contribution, as resources for languages other than English are
very scarce [22].

##  2 Related works

Nested named entity recognition has been the subject of renewed attention in
the biomedical NLP community since 2018, leading to many different approaches.

##### Exhaustive or semi-exhaustive methods

There are multiple approaches to tackle the task of nested named entity
recognition. One class of method addresses the problem by enumerating all
possible spans of the input sequence and classify each one with its label,
including a "no entity" class. [27] classify each span independently by
pooling its tokens reprentations. [34] consider the left and right context
when classifying the spans. [33] uses an LSTM cell [8] to model dependencies
between spans that differ by one token. [35] first filters candidate mentions
by predicting all possible start and end tokens and then predicting a label
for every mention that starts or end at one of the boundaries.

##### Layered methods

A different research direction focuses on layered models that iteratively
predicts entity spans until none can be found. [5] uses a fixed number of
layers and updates spans representations using a novel neural architecture.
[9] designs a layered architecture that predicts entities at each layer and
merges the word representations before applying the next layer. [26] computes
tag scores for each word and decodes the spans by applying the Viterbi
algorithm multiple times on a previously extracted subsequence, starting from
the full sentence.

##### Hypergraph methods

Some methods model the span detection with hypergraphs to account for the non-
linear structure of the tag sequences. [17] design a CRF hyper-graph with
various node types to model entity types and boundaries. However, cycles in
the graphs of some samples required that the CRF normalization term had to be
approximated, leading to a decreased performance [21]. [21] models the mention
edges and transitions instead of solely modeling token tags. Their method,
however, requires multiple graphs if more there is more than one entity type.
Alternatively, [10] only models mention tags and not their transitions, but
allows a multi-label prediction for each token. They modify an LSTM layer to
represent multiple states for a single token and perform decoding during the
neural network execution.

##### Neural transition models

Transition models iteratively build the detected spans by chaining different
actions. [31] employs a set of three actions types (SHIFT, REDUCE-X, UNARY-X)
that build a forest of binary word trees. [18] adds a new action (OUT) to
allow building multiple mentions for a given span, especially fine-grained
entity classes according to a predefined semantic hierarchy.

##### Other methods

[16] uses Anchor Region Networks to first predict an anchor token that is
contained by an entity and then predict the range of the mention from that
anchor. This method leverage the insight that most mentions contain to a head
token.

##### Language embedding

Pre-trained self-supervised language models [20, 23, 3] have improved
downstream NLP tasks’ performance. Most state-of-the-art methods use
pretrained models as contextualized token features but do not alter the
underlying model’s structure. In contrast, we experiment with the augmentation
of a pretrained transformer model to address the nested entity recognition
task.

##  3 Method

###  3.1 Model

We detail here a new model to handle nested entity recognition. The model is
an auto-regressive encoder-only Transformer [30] taking as input a sequence of
words and a list of entity mentions already extracted (empty list at the first
iteration) and predicts as output a list of new mentions. The entities
predicted at each iteration do not overlap, but all the entities predicted at
the end of the iterations may overlap.

We handle entity mentions in the form of tags assigned to each token with the
conventional BIO or BIOUL formats [2, 24], by embedding each tag into a
multidimensional vector space. We then sum the tag embeddings of different
entities (depths) at the same position with each other. The sentences are
tokenized and represented with the contextual embedding, Transformer model
BERT (for English documents [3]) or CamemBERT (for French [19]). The word
embedding and the tag embeddings from previous iterations are fed into a
linear CRF [13] predicting flat entity mentions (Figure 1a).

Each iteration of this model receives the tags predicted by the previous
iteration as input to predict different mentions at each step (Figure 1b).

(a)

(b)

Figure 1: (a) modified Transformer conditionnned on the tags of the previously
observed mentions at the end of the layer $L_{tag}$ \- figure adapted from
[30]; (b) Global model prediction diagram

###  3.2 Greedy order training

During training, the goal is to maximize the probabilities assigned by the
model to the lists of target entities. This goal comes with the difficulty of
dealing with overlapping entities.

We proceed in several steps and predict only non-interleaved entities at each
run. However, several permutations, or valid prediction paths, lead to the
same list of entities. For two nested statements

(annotations that we call $T$ and $H$), we can predict $T$ first, then $H$
knowing $T$, or the opposite, i.e. choose to optimize between two objectives :

  * •

$P(T,H)=P(T,H|T)\times P(T)$

  * •

$P(T,H)=P(T,H|H)\times P(H)$

In this symmetrical situation, a solution that would optimize both paths
simultaneously, for example, by summing several tag losses for different
depths, could lead to a non-optimal situation in which we ask the model to
detect an incorrect combination of the two mentions. For example, these two
non-overlapping but sub-optimal mentions:

Models like [9] choose a strategy in advance (smaller mentions first, for
example), but the risk is not to take advantage of all the interdependencies
that make some mentions easier to find when you know the others.

Another solution is to choose the order of extraction leading to the model’s
best performance, measured in F-measurement. A greedy strategy is applied to
select, among the non-overlapping combinations of mentions not observed in
this batch, the closest to the mentions predicted in terms of F1 overlap.
Intuitively, this means that a combination that is easier for the model to
predict is preferred. During training, to simulate an extraction in progress,
we randomly select in each sentence a subset of the entities and label them as
already predicted entities.

###  3.3 Inference

For each sentence in the corpus, our model starts by predicting the most
likely sequence of entities from the input token sequence alone since no
mention has already been predicted. Then, we add them to the observed entities
list and repeat the prediction until no more entities can be found.

###  3.4 Model parameters

We initialize the Transformer with CamemBERT [19] weights for DEFT and BioBERT
[15] for GENIA unless mentioned otherwise, and the remaining parameters using
the method of [6]. Dropout [28] is applied with a probability of 0.25
everywhere. We optimize the parameters by backpropagation with Adam [12]
without weight decay, over 40 epochs for DEFT and 10 epochs for GENIA. We use
two learning steps: one for the Transformer weights, initialized at $4\times
10^{-5}$, and one for the rest of the model, initialized at $9\times 10^{-3}$.
The learning rate follows a linear decay schedule with a warmup for 10% of the
steps. We insert the tag embeddings in the Transformers at layer $L_{tag}=6$
for BERT with 12 layers and 19 for BERT with 24 layers. On an Nvidia K80 GPU
graphics card, learning on 100 documents takes about 20 minutes.

##  4 Experiments and discussions

###  4.1 Datasets

We conduct experiments on two nested named entity recognition datasets: DEFT
[1] and GENIA [11], which present documents with different languages and
different types and depths of entities (see Table 1). For GENIA, we perform
splits following [4]: the last 10% of the sentences are used to test the
model, the remaining 90% are the training set. For DEFT, we used the provided
train and test splits. In both cases, we split the training data into 90% for
training the model and 10% for the development (validation) set. We selected
the hyperparameters by grid search on the development set and trained on the
training split for GENIA, and both training and development splits for DEFT.

| GENIA (English) | DEFT (French)
---|---|---
| train | dev | test | train | dev | test
sentences | 15022 | 1669 | 1855 | 1481 | 365 | 1024
documents | 1599 | 190 | 213 | 82 | 18 | 67
mentions | 47027 | 4469 | 5600 | 6439 | 1498 | 4791
mentions $D_{0}$ | 42965 | 4072 | 5007 | 5098 | 1226 | 3538
mentions $D_{1}$ | 3959 | 394 | 1282 | 1282 | 261 | 1163
mentions $D_{2}$ | 102 | 3 | 59 | 59 | 12 | 90
mentions $D_{3}$ | 1 | 0 | 0 | 0 | 0 | 0
Table 1: Statistics of the datasets. $D_{0}$ are all the mentions that does
not contain any mentions, $D_{1}$ are the mentions that contain one or more
$D_{0}$ mention, etc.

###  4.2 Baselines

We compare our results against a simple flat NER model composed of a
transformer and a CRF decoding layer that can only predict non-nested
mentions. Since a choice is required during training as to which mentions
should be predicted, we evaluate three modes: we only recover the shortest
mention in a nested group, or only the largest, or let the model decide
greedily. We also compare our model against the state-of-the-art models on
GENIA and the other participants’ models on DEFT.

###  4.3 Results

The results of our system and the baselines are presented in Tables 2 and 3.

On the DEFT task 3.1, our model obtains the best F1 result of 0.66 (with the
exact delimitation of mentions). On the DEFT task 3.2, the same model obtains
a F1 of 0.778. Flat NER models lose between 10 and 20 points in F1, due to the
large number of nested mentions. The 3.1 task containing longer entities, the
flat large entities model, reaches the best performance of the flat models.
Conversely, the flat short entities model obtains the best performance on the
3.2 task.

On the GENIA dataset, our best model reaches 0.7683 F1 with BioBERT large. We
hypothesize that our method ranks lower on the latter dataset because it only
uses BERT instead of BERT and other word features, and that the insertion of
tags directly in BERT architecture may lead to loose some of the pretrained
model abilities. We can also observe that flat NER is competitive with
iterative models, which can be explained by the low ratio of nested mentions
in the dataset.

_GENIA dataset_ | Precision | Recall | F1
---|---|---|---
Ju et al. [9] | 0.785 | 0.713 | 0.747
Wang et al. [32] | 0.780 | 0.702 | 0.739
Wang and Lu [31] | 0.770 | 0.733 | 0.751
Sohrab and Miwa [27] | 0.932 | 0.642 | 0.771
Lin et al. [16] | 0.758 | 0.739 | 0.748
Shibuya and Hovy [26] | 0.763 | 0.747 | 0.755
Straková et al. [29] (BERT, Flair) |  |  | 0.783
WANG et al. [33] (BERT, Flair) | 0.803 | 0.783 | 0.793
Flat short entities (BERT base) | 0.7929 | 0.6975 | 0.7422
Flat large entities (BERT base) | 0.8149 | 0.7070 | 0.7571
Flat greedy (BERT base) | 0.8141 | 0.7095 | 0.7582
(our) greedy (BERT base) | 0.8126 | 0.7211 | 0.7641
(our) large-to-short (BERT base) | 0.8016 | 0.7184 | 0.7577
(our) short-to-large (BERT base) | 0.8028 | 0.7336 | 0.7666
(our) short-to-large (BERT large) | 0.7933 | 0.7448 | 0.7683
Table 2: GENIA test performance (systems reaching performance above 0.74 F1) | DEFT 3.1 | DEFT 3.2 | Global
---|---|---|---
| P | R | F1 | P | R | F1 | F1
HESGE (BERT large) | 0.702 | 0.624 | 0.660 | 0.788 | 0.725 | 0.755 |
Median DEFT |  |  | 0.4557 |  |  | 0.6151 |
Flat short (BERT base) | 0.6093 | 0.2277 | 0.3315 | 0.7570 | 0.6690 | 0.7103 | 0.6228
Flat large (BERT base) | 0.6093 | 0.6076 | 0.6085 | 0.7223 | 0.3152 | 0.4389 | 0.5094
Flat greedy (BERT base) | 0.6082 | 0.3481 | 0.4428 | 0.7848 | 0.6046 | 0.6830 | 0.6201
(our) greedy | 0.6263 | 0.6090 | 0.6175 | 0.7615 | 0.7416 | 0.7514 | 0.7134
(our) large to short | 0.6257 | 0.6062 | 0.6158 | 0.7407 | 0.7470 | 0.7439 | 0.7082
(our) short to large | 0.6105 | 0.6194 | 0.6149 | 0.7564 | 0.7449 | 0.7506 | 0.7120
(our) short to large (BERT large) | 0.6613 | 0.6595 | 0.6604 | 0.7806 | 0.7759 | 0.7783 | 0.7447
Table 3: DEFT test performance

###  4.4 Ablations

####  4.4.1 Tag embeddings

##### Insertion layer

We study the effect of different tag embeddings configurations on the system’s
performance. We can see in Figure 2 the validation f1 metrics of the system
against the index of the BERT layer at which we add the embeddings. The
performance decreases in the last layers since the system has no "time" to
take the previous predictions into account. However, we also observe a maximum
at layer 6 and lower performance in earlier layers.

(a) GENIA

(b) DEFT

Figure 2: Model performance on the GENIA and DEFT validation datasets wrt
different insertion layer indices of the observed tag embeddings and training
depth orders. Each point is the average over 3 runs. We only plotted the
results from the second layer for DEFT to improve readability, all models
reaching around 0.50 F1 when layer = 0.

##### Tag scheme

We analyze the performance of two common tag schemes: BIO (Begin, Inside,
Outside) and BIOUL (BIO with Unary and Last tags) to encode observed (i.e.,
previously predicted entities). Results can be found in Table 4. The BIOUL tag
scheme shows better overall results than the BIO scheme. This conclusion is
similar to what others [14] have observed for flat named entity recognition.
However, the BIOUL "reading" tag scheme’s better results show that the system
can better use previous entities for its predictions when given begin and end
bounds.

| write BIO | write BIOUL
---|---|---
read BIO |  0.7221 ($\pm 2.98e^{-3}$) |  0.7341 ($\pm 6.09e^{-3}$)
read BIOUL |  0.7261 ($\pm 5.40e^{-3}$) |  0.7368 ($\pm 4.28e^{-3}$)
Table 4: Performance of the BIO and BIOUL reading and writing tag schemes on
the DEFT validation dataset.

####  4.4.2 Depth prediction order

We study the effect that forced prediction order during training has on model
performance. We compared three prediction modes: top to bottom, bottom to top,
and greedy decoding. In the top to bottom mode, given a previously predicted
entity at depth D, we force the model to predict a named entity located at
depth D+1. In the bottom to top mode, we use the inverse depth as training
order. Finally, in greedy decoding mode, we let the model choose the mentions
by selecting those closest to its prediction.

From Figure 2 we can observe that the short-to-large training order obtains
the highest performance on both GENIA and DEFT validation splits. The large-
to-short depth training order obtains the lowest accuracy. We hypothesize that
learning to detect the smallest, and often easier, entities first leads the
model to learn how to compose new entities from small entities. On the other
hand, learning to predict large, and often more difficult, mentions first,
must lead the model to overfit on these large mentions and fail to recover
smaller nested mentions when the largest ones are wrongly predicted. The
greedy training reaches an intermediate performance, so we conclude that a
learned prediction order is suboptimal.

##  5 Conclusion

This paper proposes an architecture to perform named entity recognition based
on iterative predictions and dynamic mention matching during training. We also
provided insights into the model behavior and showed that training depth
mention order impacts performance on auto-regressive layered named entity
recognition models, and short-to-large order obtains the best results.

## References

  * Cardon et al. [2020] Cardon, R., Grabar, N., Grouin, C., Hamon, T.: Presentation of the DEFT 2020 Challenge : open domain textual similarity and precise information extraction from clinical cases. In: Actes de la 6e conférence conjointe Journées d’Études sur la Parole (JEP, 33e édition), Traitement Automatique des Langues Naturelles (TALN, 27e édition), Rencontre des Étudiants Chercheurs en Informatique pour le Traitement Automatique des Langues (RÉCIT, pp. 1–13 (2020)
  * Dai et al. [2015] Dai, H.J., Lai, P.T., Chang, Y.C., Tsai, R.T.H.: Enhancing of chemical compound and drug name recognition using representative tag scheme and fine-grained tokenization. Journal of Cheminformatics 7(Suppl 1), S14 (2015), ISSN 17582946
  * Devlin et al. [2019] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: BERT: Pre-training of deep bidirectional transformers for language understanding. NAACL HLT 2019 - 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies - Proceedings of the Conference 1, 4171–4186 (10 2019)
  * Finkel and Manning [2009] Finkel, J.R., Manning, C.D.: Nested named entity recognition. In: Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing Volume 1 - EMNLP ’09, vol. 1, p. 141, Association for Computational Linguistics, Morristown, NJ, USA (4 2009), ISBN 9781932432596
  * Fisher and Vlachos [2019] Fisher, J., Vlachos, A.: Merge and Label: A Novel Neural Network Architecture for Nested NER. In: Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 5840–5850, Association for Computational Linguistics, Stroudsburg, PA, USA (2019), ISSN 23318422
  * Glorot and Bengio [2010] Glorot, X., Bengio, Y.: Understanding the difficulty of training deep feedforward neural networks. Journal of Machine Learning Research 9, 249–256 (2010), ISSN 15324435
  * Grabar et al. [2018] Grabar, N., Claveau, V., Dalloux, C.: CAS: French Corpus with Clinical Cases. In: Proceedings of the Ninth International Workshop on Health Text Mining and Information Analysis, pp. 122–128, Association for Computational Linguistics, Stroudsburg, PA, USA (6 2018)
  * Hochreiter and Schmidhuber [1997] Hochreiter, S., Schmidhuber, J.: Long Short-Term Memory. Neural Computation 9(8), 1735–1780 (11 1997), ISSN 0899-7667
  * Ju et al. [2018] Ju, M., Miwa, M., Ananiadou, S.: A Neural Layered Model for Nested Named Entity Recognition. In: Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), vol. 1, pp. 1446–1459, Association for Computational Linguistics, Stroudsburg, PA, USA (2018), ISBN 9781948087278
  * Katiyar and Cardie [2018] Katiyar, A., Cardie, C.: Nested Named Entity Recognition Revisited. In: Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), vol. 1, pp. 861–871, Association for Computational Linguistics, Stroudsburg, PA, USA (2018), ISBN 9781948087278
  * Kim et al. [2003] Kim, J.D., Ohta, T., Tateisi, Y., Tsujii, J.: GENIA corpus - A semantically annotated corpus for bio-textmining. Bioinformatics 19(SUPPL. 1), i180–i182 (7 2003), ISSN 13674803
  * Kingma and Ba [2015] Kingma, D.P., Ba, J.L.: Adam: A method for stochastic optimization. In: 3rd International Conference on Learning Representations, ICLR 2015 - Conference Track Proceedings (2015)
  * Lafferty et al. [2001] Lafferty, J., McCallum, A., Pereira, F.C.N.: Conditional random fields: Probabilistic models for segmenting and labeling sequence data. ICML ’01 Proceedings of the Eighteenth International Conference on Machine Learning 8(June), 282–289 (2001)
  * Lample et al. [2016] Lample, G., Ballesteros, M., Subramanian, S., Kawakami, K., Dyer, C.: Neural Architectures for Named Entity Recognition. In: Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 260–270, Association for Computational Linguistics, Stroudsburg, PA, USA (2016), ISBN 9781941643914, ISSN 1045-9227
  * Lee et al. [2020] Lee, J., Yoon, W., Kim, S., Kim, D., Kim, S., So, C.H., Kang, J.: BioBERT: A pre-trained biomedical language representation model for biomedical text mining. Bioinformatics 36(4), 1234–1240 (2020), ISSN 14602059
  * Lin et al. [2019] Lin, H., Lu, Y., Han, X., Sun, L.: Sequence-to-Nuggets: Nested Entity Mention Detection via Anchor-Region Networks. In: Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 5182–5192, Association for Computational Linguistics, Stroudsburg, PA, USA (2019), ISSN 23318422
  * Lu and Roth [2015] Lu, W., Roth, D.: Joint Mention Extraction and Classification with Mention Hypergraphs. In: Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pp. 857–867, Association for Computational Linguistics, Stroudsburg, PA, USA (2015), ISBN 9781941643327
  * Marinho et al. [2019] Marinho, Z., Mendes, A., Miranda, S., Nogueira, D.: Hierarchical Nested Named Entity Recognition. In: Proceedings of the 2nd Clinical Natural Language Processing Workshop, pp. 28–34, Association for Computational Linguistics, Stroudsburg, PA, USA (2019)
  * Martin et al. [2020] Martin, L., Muller, B., Ortiz Suarez, P.J., Dupont, Y., Romary, L., de la Clergerie, E., Seddah, D., Sagot, B.: CamemBERT: a Tasty French Language Model. In: Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 7203–7219, Association for Computational Linguistics, Stroudsburg, PA, USA (2020), ISSN 23318422
  * Mikolov et al. [2013] Mikolov, T., Chen, K., Corrado, G., Dean, J.: Efficient estimation of word representations in vector space. In: 1st International Conference on Learning Representations, ICLR 2013 - Workshop Track Proceedings (2013)
  * Muis and Lu [2017] Muis, A.O., Lu, W.: Labeling Gaps Between Words: Recognizing Overlapping Mentions with Mention Separators. In: Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 2608–2618, Association for Computational Linguistics, Stroudsburg, PA, USA (2017), ISSN 23318422
  * Névéol et al. [2016] Névéol, A., Cohen, K.B., Grouin, C., Hamon, T., Lavergne, T., Kelly, L., Goeuriot, L., Rey, G., Robert, A., Tannier, X., Zweigenbaum, P.: Clinical Information Extraction at the CLEF eHealth Evaluation lab 2016. Tech. rep. (2016)
  * Peters et al. [2018] Peters, M.E., Neumann, M., Iyyer, M., Gardner, M., Clark, C., Lee, K., Zettlemoyer, L.: Deep contextualized word representations. NAACL HLT 2018 - 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies - Proceedings of the Conference 1, 2227–2237 (2 2018)
  * Ratinov and Roth [2009] Ratinov, L., Roth, D.: Design challenges and misconceptions in named entity recognition. In: Proceedings of the Thirteenth Conference on Computational Natural Language Learning - CoNLL ’09, p. 147, Association for Computational Linguistics, Morristown, NJ, USA (2009), ISBN 9781932432299
  * Ravanbakhsh et al. [2012] Ravanbakhsh, S., Yu, C.N., Greiner, R.: A generalized loop correction method for approximate inference in graphical models. Tech. rep. (2012)
  * Shibuya and Hovy [2020] Shibuya, T., Hovy, E.: Nested Named Entity Recognition via Second-best Sequence Learning and Decoding. Transactions of the Association for Computational Linguistics 8, 605–620 (12 2020), ISSN 2307-387X
  * Sohrab and Miwa [2018] Sohrab, M.G., Miwa, M.: Deep Exhaustive Model for Nested Named Entity Recognition. In: Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2843–2849, Association for Computational Linguistics, Stroudsburg, PA, USA (2018), ISBN 9781948087841
  * Srivastava et al. [2014] Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., Salakhutdinov, R.: Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research 15(56), 1929–1958 (2014), ISSN 15337928
  * Straková et al. [2019] Straková, J., Straka, M., Hajic, J.: Neural Architectures for Nested NER through Linearization. In: Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 5326–5331, Association for Computational Linguistics, Stroudsburg, PA, USA (2019), ISSN 23318422
  * Vaswani et al. [2017] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, L., Polosukhin, I.: Attention is all you need. Advances in Neural Information Processing Systems 2017-Decem, 5999–6009 (6 2017), ISSN 10495258
  * Wang and Lu [2018] Wang, B., Lu, W.: Neural Segmental Hypergraphs for Overlapping Mention Recognition. In: Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 204–214, Association for Computational Linguistics, Stroudsburg, PA, USA (2018), ISSN 23318422
  * Wang et al. [2018] Wang, B., Lu, W., Wang, Y., Jin, H.: A Neural Transition-based Model for Nested Mention Recognition. In: Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 1011–1017, Association for Computational Linguistics, Stroudsburg, PA, USA (2018), ISSN 23318422
  * WANG et al. [2020] WANG, J., Shou, L., Chen, K., Chen, G.: Pyramid: A Layered Model for Nested Named Entity Recognition. In: Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 5918–5928, Association for Computational Linguistics, Stroudsburg, PA, USA (2020)
  * Xu et al. [2017] Xu, M., Jiang, H., Watcharawittayakul, S.: A local detection approach for named entity recognition and mention detection. ACL 2017 - 55th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference (Long Papers) 1, 1237–1247 (2017)
  * Zheng et al. [2019] Zheng, C., Cai, Y., Xu, J., Leung, H.f., Xu, G.: A Boundary-aware Neural Model for Nested Named Entity Recognition. In: Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 357–366, Association for Computational Linguistics, Stroudsburg, PA, USA (2019), ISBN 9781950737901