This article is the full version of [DattaMSVZ17]. The authors acknowledge the
financial support by the DAAD-DST grant “Exploration of New Frontiers in
Dynamic Complexity”. The first and the second authors were partially funded by
a grant from Infosys foundation. The second author was partially supported by
a TCS PhD fellowship. The last three authors acknowledge the financial support
by DFG grant SCHW 678/6-2 on “Dynamic Expressiveness of Logics”.

# A Strategy for Dynamic Programs: Start over and Muddle through

Samir Datta  Chennai Mathematical Institute & UMI ReLaX, Chennai, India
<EMAIL_ADDRESS>,  Anish Mukherjee  Chennai Mathematical Institute, Chennai,
India<EMAIL_ADDRESS>,  Thomas Schwentick  TU Dortmund University, Dortmund,
Germany<EMAIL_ADDRESS>,  Nils Vortmeier  TU Dortmund
University, Dortmund, Germany<EMAIL_ADDRESS>and  Thomas Zeume
TU Dortmund University, Dortmund, Germany<EMAIL_ADDRESS>
###### Abstract.

In the setting of DynFO, dynamic programs update the stored result of a query
whenever the underlying data changes. This update is expressed in terms of
first-order logic. We introduce a strategy for constructing dynamic programs
that utilises periodic computation of auxiliary data from scratch and the
ability to maintain a query for a limited number of change steps. We show that
if some program can maintain a query for $\log n$ change steps after an
$\textsc{AC}^{1}$-computable initialisation, it can be maintained by a first-
order dynamic program as well, i.e., in DynFO. As an application, it is shown
that decision and optimisation problems defined by monadic second-order (MSO)
formulas are in DynFO, if only change sequences that produce graphs of bounded
treewidth are allowed. To establish this result, a Feferman-Vaught-type
composition theorem for MSO is established that might be useful in its own
right.

###### Key words and phrases:

dynamic complexity, treewidth, monadic second order logic

##  1\. Introduction

Each time a database is changed, any previously computed and stored result of
a fixed query might become outdated. However, when the change is small, it is
plausible that the new query result is highly related to the old result. In
that case it might be more efficient to use previously computed information
for obtaining the new answer to the query instead of recomputing the query
result from scratch. A theoretical framework for studying when the result of a
query over relational databases can be updated in a declarative fashion was
formalised by Patnaik and Immerman [PatnaikI97], and Dong, Su, and Topor
[DongST95]. In their formalisation, a dynamic program consists of a set of
logical formulas that update a query result after the insertion or deletion of
a tuple. The formulas may use additional auxiliary relations that, of course,
need to be updated as well. The queries maintainable in this way via first-
order formulas constitute the dynamic complexity class DynFO.

Recent work has confirmed that DynFO is a quite powerful class, since it
captures, e.g., the reachability query for directed graphs [DattaKMSZ18], and
even allows for more complex change operations than single-tuple changes
[SchwentickVZ18, DattaMVZ18].

In this article we introduce a general strategy for dynamic programs that
further underscores the expressive power of DynFO. All prior results for DynFO
yield dynamic programs that are able to maintain a query for arbitrary long
sequences of changes. Even if this is not (known to be) possible for a given
query, in a practical scenario it might still be favourable to maintain the
query result dynamically for a bounded number of changes, then to apply a more
complex algorithm that recomputes certain auxiliary information from scratch,
such that afterwards the query can again be maintained for some time, and so
on.

Here we formalise this approach. Let ${\mathcal{C}}$ be a complexity class and
$f\colon\mathbb{N}\rightarrow\mathbb{N}$ a function. A query $q$ is called
$({\mathcal{C}},f)$-maintainable, if there is a dynamic program (with first-
order definable updates) that, starting from some input structure
${\mathcal{A}}$ and auxiliary relations computed in ${\mathcal{C}}$ from
${\mathcal{A}}$, can answer $q$ for $f(|{\mathcal{A}}|)$ many steps, where
$|{\mathcal{A}}|$ denotes the size of the universe of ${\mathcal{A}}$.

We feel that this notion might be interesting in its own right. However, in
this article we concentrate on the case where ${\mathcal{C}}$ is (uniform)
$\textsc{AC}^{1}$ and $f(n)=\log n$. The class $\textsc{AC}^{1}$ contains all
queries that can be computed by a (uniform) circuit of depth
${\mathcal{O}}(\log n)$ that uses polynomially many $\wedge$-, $\vee$-, and
$\neg$-gates, where $\wedge$\- and $\vee$-gates may have unbounded fan-in. We
show that $(\textsc{AC}^{1},\log n)$-maintainable queries are actually in
DynFO, and thus can be maintained for arbitrary long change sequences.

We apply this insight to show that all queries and optimisation problems
definable in monadic second-order logic (MSO) are in DynFO for (classes of)
structures of bounded treewidth, by proving that they are
$(\textsc{AC}^{1},\log n)$-maintainable. The same can be said about guarded
second-order logic (GSO), simply because it is expressively equivalent to MSO
on such classes [Courcelle94]. This implies that decision problems like
3-Colourability or HamiltonCycle as well as optimisation problems like
VertexCover and DominatingSet are in DynFO, for such classes of structures.
This result is therefore a dynamic version of Courcelle’s Theorem which states
that all problems definable in (certain extensions of) MSO can statically be
solved in linear time for graphs of bounded treewidth [Courcelle90].

The proof that MSO-definable queries are $(\textsc{AC}^{1},\log
n)$-maintainable on structures of bounded treewidth makes use of a
Feferman–Vaught-type composition theorem for MSO which might be useful in its
own right.

The result that $(\textsc{AC}^{1},\log n)$-maintainable queries are in DynFO
comes with a technical restriction: in a nutshell, it holds for queries that
are invariant under insertion of (many) isolated elements. We call such
queries _almost domain independent_ and refer to Section 3 for a precise
definition.

We emphasise that the main technical challenge in maintaining MSO-queries on
graphs of bounded treewidth is that tree decompositions might change
drastically after an edge insertion, and can therefore not be maintained
incrementally in any obvious way. In particular, the result does not simply
follow from the DynFO-maintainability of regular tree languages shown in
[GeladeMS12]. We circumvent this problem by periodically recomputing a new
tree decomposition (this can be done in logarithmic space [ElberfeldJT10] and
thus in $\textsc{AC}^{1}$) and by showing that MSO-queries can be maintained
for $\mathcal{O}(\log n)$ many change operations, even if they make the tree
decomposition invalid.

### Contributions

We briefly summarise the contributions described above. In this article, we
introduce the notion of $({\mathcal{C}},f)$-maintainability and show that,
amongst others, (almost domain independent) $(\textsc{AC}^{1},\log
n)$-maintainable queries are in DynFO. We show that MSO-definable decision
problems and optimisation problems are $(\textsc{AC}^{1},\log n)$-maintainable
and therefore in DynFO, for structures of bounded treewidth. These proofs make
use of a Feferman–Vaught-type composition theorem for MSO logic.

### Related work

The simulation-based technique for proving that $(\textsc{AC}^{1},\log
n)$-maintainable queries are in DynFO is inspired by proof techniques from
[DattaKMSZ15] and [SchwentickVZ18]. As mentioned above, in [GeladeMS12] it has
been shown that tree languages, i.e. MSO on trees, can be maintained in DynFO.
Independently, the maintenance of MSO definable queries on graphs of bounded
treewidth is also studied in [BouyerJM17], though in the restricted setting
where the tree decomposition stays the same for all changes. A static but
parallel version of Courcelle’s Theorem is given in [ElberfeldJT10]: every
MSO-definable problem for graphs of bounded treewidth can be solved with
logarithmic space.

### Organisation

Basic terminology is recalled in Section 2, followed by a short introduction
into dynamic complexity in Section 3. In Section 4 we introduce the notion of
$({\mathcal{C}},f)$-maintainability and show that $(\textsc{AC}^{1},\log
n)$-maintainable queries are in DynFO. A glimpse on the proof techniques for
proving that MSO queries are in DynFO for graphs of bounded treewidth is given
in Section 5 via the example 3-Colourability. The proof of the general results
is presented in Section LABEL:section:mso. An extension to optimisation
problems can be found in Section LABEL:section:mso-opt.

This article is the full version of [DattaMSVZ17].

##  2\. Preliminaries

We now introduce some notation and notions regarding logics, graph theory and
complexity theory. We assume familiarity with first-order logic FO and other
notions from finite model theory [ImmermanDC, Libkin04].

### Relational structures

In this article we consider finite relational structures over relational
signatures $\Sigma=\\{R_{1},\ldots,R_{\ell},c_{1},\ldots,c_{m}\\}$, where each
$R_{i}$ is a relation symbol with a corresponding arity $\text{Ar}(R_{i})$,
and each $c_{j}$ is a constant symbol. A $\Sigma$-structure ${\mathcal{A}}$
consists of a finite _domain_ $A$, also called the _universe_ of
${\mathcal{A}}$, a relation $R_{i}^{\mathcal{A}}\subseteq
A^{\text{Ar}(R_{i})}$, and a constant $c_{j}^{\mathcal{A}}\in A$, for each
$i\in\\{1,\ldots,\ell\\},j\in\\{1,\ldots,m\\}$. The _active domain_
$\text{adom}({\mathcal{A}})$ of a structure ${\mathcal{A}}$ contains all
elements used in some tuple or as some constant of ${\mathcal{A}}$. For a set
$B\subseteq A$ that contains all constants and a relation $R$, the restriction
$R[B]$ of $R$ to $B$ is the relation $R\cap B^{\text{Ar}(R)}$. The structure
${\mathcal{A}}[B]$ induced by $B$ is the structure obtained from
${\mathcal{A}}$ by restricting the domain and all relations to $B$.

Sometimes, especially in Section 3, we consider relational structures as
relational databases. This terminology is common in the context of dynamic
complexity due to its original motivation from relational databases. Also for
this reason, dynamic complexity classes defined later will be defined as
classes of queries of arbitrary arity, and not as a class of decision
problems. However, we will mostly consider queries over structures with a
single binary relation symbol $E$, that is, queries on graphs.

We will often use structures ${\mathcal{A}}$ with a linear order $\leq$ on the
universe $A$, and compatible ternary relations encoding arithmetical
operations $+$ and $\times$ or, alternatively, a binary relation encoding the
relation $\text{BIT}=\\{(i,j)\mid$ the $j$-th bit in the binary representation
of $i$ is $1\\}$. The linear order in particular allows us to identify $A$
with the first $|A|$ natural numbers. We write $\textsc{FO}(+,\times)$ or
$\textsc{FO}(\text{BIT})$ to emphasise that we allow first-order formulas to
use such additional relations.111The question of $<$-invariance (c.f.
[Libkin04]) will not be relevant in the context of this article as a specific
relation $\leq$ will be available in the structure. We also use that
$\textsc{FO}(+,\times)=\textsc{FO}(\text{BIT})$ [ImmermanDC].

### Tree decompositions and treewidth

A _tree decomposition_ $(T,B)$ of $G$ consists of a (rooted, directed) tree
$T=(I,F,r)$, with (tree) nodes $I$, (tree) edges $F$, a distinguished root
node $r\in I$, and a function $B\colon I\rightarrow 2^{V}$ such that

  1. (1)

the set $\\{i\in I\mid v\in B(i)\\}$ is non-empty for each node $v\in V$,

  2. (2)

there is an $i\in I$ with $\\{u,v\\}\subseteq B(i)$ for each edge $(u,v)\in
E$, and

  3. (3)

the subgraph $T[\\{i\in I\mid v\in B(i)\\}]$ is connected for each node $v\in
V$.

We refer to the number of children of a node $i$ of $T$ as its _degree_ , and
to the set $B(i)$ as its _bag_. We denote the parent node of $i$ by $p(i)$.
The _width_ of a tree decomposition is defined as the maximal size of a bag
minus $1$. The _treewidth_ of a graph $G$ is the minimal width among all tree
decompositions of $G$. A tree decomposition is _$d$ -nice_, for some
$d\in\mathbb{N}$, if

  1. (1)

$T$ has depth at most $d\log n$,

  2. (2)

the degree of the nodes is at most $2$, and

  3. (3)

all bags are distinct.

Often we do not make the constant $d$ explicit and just speak of _nice_ tree
decompositions.

Later we will use that tree decompositions can be transformed into nice tree
decompositions with slightly increased treewidth. This is formalized in the
following lemma, whose proof is an adaption of [ElberfeldJT10, Lemma 3.1].

######  Lemma 2.1.

For every $k\in\mathbb{N}$ there is a constant $d\in\mathbb{N}$ such that for
every graph of treewidth $k$, a $d$-nice tree decomposition of width $4k+5$
can be computed in logarithmic space.

######  Proof 2.2.

Let $G$ be a graph of treewidth $k$. By [ElberfeldJT10, Lemma 3.1] a tree
decomposition $(T,B)$ of width $4k+3$ can be computed in logarithmic space,
such that each non-leaf node has degree 2 and the depth is at most $d\log n$,
for a constant $d$ that only depends on $k$. To obtain a tree decomposition
with distinct bags, we compose this algorithm with three further algorithms,
each reading a tree decomposition $(T,B)$ and transforming it into a tree
decomposition $(T^{\prime},B^{\prime})$ with a particular property. Since each
of the four algorithms requires only logarithmic space, the same holds for
their composition.

The first transformation algorithm produces a tree decomposition, in which for
each leaf bag $i$ it holds $B(i)\not\subseteq B(p(i))$. In particular, after
this transformation, each bag of a leaf node $i$ contains some graph node
$u(i)$ that does not appear in any other bag. This transformation inspects
each node $i$ separately in a bottom-up fashion, and removes it if (1)
$B(i)\subseteq B(p(i))$ and (2) every bag below $i$ is a subset of $B(i)$.
Clearly, logarithmic space suffices for this.

The second transformation (inductively) removes an inner node $i$ of degree 1
with a child $i^{\prime}$ and inserts an edge between $B(p(i))$ and
$B(i^{\prime})$ whenever $B(i)\subseteq B(p(i))$ or $B(i)\subseteq
B(i^{\prime})$ holds. For this transformation, only one linear chain of nodes
in $T$ has to be considered at any time and therefore logarithmic space
suffices again. Clearly, the connectivity property is not affected by these
deletions.

The third transformation adds to every bag of an inner node $i$ the nodes
$u(i_{1})$ and $u(i_{2})$, guaranteed to exist by the first transformation, of
the leftmost and rightmost leaf nodes $i_{1}$ and $i_{2}$ of the subtree
rooted at $i$, respectively. Here, we assume the children of every node to be
ordered by the representation of $T$ as input to the algorithm. After this
transformation, each node of degree 2 has a different bag than its two
children thanks to the addition of $u(i_{1})$ and $u(i_{2})$. Each node of
degree 1 has a different bag than its child, since this was already the case
before (and to both of them the same two nodes might have been added).
Altogether, all bags are pairwise distinct and the bag sizes have increased by
at most 2.

We emphasise that, whenever a leftmost graph node $u(i_{1})$ is added to
$B(i)$, it is also added to all bags of nodes on the path from $i$ to $i_{1}$
and therefore the connectivity property is not corrupted. It is easy to see
that the third transformation can also be carried out in logarithmic space.

The three presented algorithms never increase the depth of a tree
decomposition, so the final result is a $d$-nice tree decomposition for $G$ of
width $4k+5$.

In this paper we only consider nice tree decompositions, and due to property
(3) of these decompositions we can identify bags with nodes from $I$.

For two nodes $i,i^{\prime}$ of $I$, we write $i\preceq i^{\prime}$ if
$i^{\prime}$ is in the subtree of $T$ rooted at $i$ and $i\prec i^{\prime}$
if, in addition, $i^{\prime}\not=i$. A _triangle_ $\delta$ of $T$ is a triple
$(i_{0},i_{1},i_{2})$ of nodes from $I$ such that $i_{0}\preceq i_{1}$,
$i_{0}\preceq i_{2}$, and (1) $i_{1}=i_{2}$ or (2) neither $i_{1}\preceq
i_{2}$ nor $i_{2}\preceq i_{1}$. In case of (2) we call the triangle _proper_
, in case of (1) _unary_ , unless $i_{0}=i_{1}=i_{2}$ in which we call it
_open_ (see Figure 1 for an illustration).

(a)$r$$i_{0}$$i_{1}$$i_{2}$(b)$r$$i_{0}$$i_{1}$(c)$r$$i_{0}$

Figure 1. Illustration of (a) a proper triangle $(i_{0},i_{1},i_{2})$, (b) a
unary triangle $(i_{0},i_{1},i_{1})$, and (c) an open triangle
$(i_{0},i_{0},i_{0})$. The blue shaded area is the part of the tree contained
in the triangle.

The subtree $T(\delta)$ _induced_ by a triangle consists of all nodes $j$ of
$T$ for which the following holds:

  1. (i)

$i_{0}\preceq j$,

  2. (ii)

if $i_{0}\prec i_{1}$ then $i_{1}\not\prec j$, and

  3. (iii)

if $i_{0}\prec i_{2}$ then $i_{2}\not\prec j$.

That is, for a proper or unary triangle, $T(\delta)$ contains all nodes of the
subtree rooted at $i_{0}$ which are not below $i_{1}$ or $i_{2}$. For an open
triangle $\delta=(i_{0},i_{0},i_{0})$, $T(\delta)$ is just the subtree rooted
at $i_{0}$.

Each triangle $\delta$ induces a subgraph $G(\delta)$ of $G$ as follows:
$V(\delta)$ is the union of all bags of $T(\delta)$. By $B(\delta)$ we denote
the set $B(i_{0})\cup B(i_{1})\cup B(i_{2})$ of _interface nodes_ of
$V(\delta)$. All other nodes in $V(\delta)$ are called _inner nodes_. The edge
set of $G(\delta)$ consists of all edges of $G$ that involve at least one
inner node of $V(\delta)$.

### MSO-logic and MSO-types

MSO is the extension of first-order logic that allows existential and
universal quantification over set variables $X,X_{1},\ldots$. The
_(quantifier) depth_ of an MSO formula is the maximum nesting depth of
(second-order and first-order) quantifiers in the syntax tree of the formula.

For a signature $\Sigma$ and a natural number $d\geq 0$, the _depth- $d$ MSO
type_ of a $\Sigma$-structure ${\mathcal{A}}$ is defined as the set of all MSO
sentences $\varphi$ over $\Sigma$ of quantifier depth at most $d$, for which
${\mathcal{A}}\models\varphi$ holds. We also define the notion of types for
structures with additional constants and MSO formulas with free variables. Let
${\mathcal{A}}$ be a $\Sigma$-structure and $\bar{v}=(v_{1},\ldots,v_{m})$ a
tuple of elements from ${\mathcal{A}}$. We write $({\mathcal{A}},\bar{v})$ for
the structure over $\Sigma\cup\\{c_{1},\ldots,c_{m}\\}$ which interprets
$c_{i}$ as $v_{i}$, for every $i\in\\{1,\ldots,m\\}$. For a set
${\mathcal{Y}}$ of first-order and second-order variables and an assignment
$\alpha$ for the variables of ${\mathcal{Y}}$, the depth-$d$ MSO type of
$({\mathcal{A}},\bar{v},\alpha)$ is the set of MSO formulas with free
variables from ${\mathcal{Y}}$ of depth $d$ that hold in
$({\mathcal{A}},\bar{v},\alpha)$. For every depth-$d$ MSO type $\tau$, there
is a depth-$d$ MSO formula $\alpha_{\tau}$ that is true in exactly the
structures and for those assignments of type $\tau$.

The logic _guarded second-order logic_ (GSO) extends MSO by _guarded_ second-
order quantification. Thus, it syntactically allows to quantify over non-unary
relation variables. However, this quantification is semantically restricted: a
tuple $\bar{t}=(a_{1},\ldots,a_{m})$ can only occur in a quantified relation,
if all elements from $\\{a_{1},\ldots,a_{m}\\}$ occur together in some tuple
of the structure, in which the formula is evaluated.

For more background on MSO logic and types, readers might consult, e.g.,
[Libkin04].

### Complexity classes and descriptive characterisations

Our main result refers to the complexity class (uniform) $\textsc{AC}^{1}$. It
contains all queries that can be computed by (families of uniform) circuits of
depth $\mathcal{O}(\log n)$, consisting of polynomially many “and”, “or” and
“not” gates with unbounded fan-in. It contains the classes LOGSPACE and NL,
and it can be characterised as the class $\text{IND}[\log n]$ of problems that
can be expressed by applying a first-order formula $\mathcal{O}(\log n)$ times
[ImmermanDC, Theorem 5.22]. Here, $n$ denotes the size of the universe and the
formulas can use built-in relations $+$ and $\times$. More generally, this
characterisation is also valid for the analogously defined classes
$\textsc{AC}[f(n)]$ and $\text{IND}[f(n)]$, where the depth of the circuits
and the number of applications of the first-order formula is $f(n)$,
respectively, for some function $f\colon\mathbb{N}\to\mathbb{N}$. Technically,
the function $f$ needs to be _first-order constructible_ , that is, there has
to be a FO$(+,\\!\times\\!)$ formula $\psi_{f}(\bar{x})$ such that
${\mathcal{A}}\models\psi_{f}(\bar{a})$ if and only if $\bar{a}$ is a base-$n$
representation of $f(n)$, for any ordered structure ${\mathcal{A}}$ with
domain $\\{0,\ldots,n-1\\}$.

Our proofs often assume that $\log n$ is a natural number, but they can be
easily adapted to the general case.

##  3\. Dynamic Complexity

We briefly repeat the essentials of dynamic complexity, closely following
[SchwentickZ16, DattaKMSZ18].

The goal of a dynamic program is to answer a given query on an _input
database_ subjected to changes that insert or delete single tuples. The
program may use an auxiliary data structure represented by an _auxiliary
database_ over the same domain. Initially, both input and auxiliary database
are empty; and the domain is fixed during each run of the program.

A dynamic program has a set of update rules that specify how auxiliary
relations are updated after a change of the input database. An _update rule_
for updating an auxiliary relation $T$ is basically a formula $\varphi$. As an
example, if $\varphi(\bar{x},\bar{y})$ is the update rule for auxiliary
relation $T$ under insertions into input relation $R$, then the new version of
$T$ after insertion of a tuple $\bar{a}$ to $R$ is
$T\mathrel{\smash{\stackrel{{\scriptstyle\scriptscriptstyle{\text{def}}}}{{=}}}}\;\\{\bar{b}\mid({\mathcal{I}},Aux)\models\varphi(\bar{a},\bar{b})\\}$
where ${\mathcal{I}}$ and $Aux$ are the current input and auxiliary databases.
For a state ${\mathcal{S}}=({\mathcal{I}},Aux)$ of the dynamic program
${\mathcal{P}}$ with input database ${\mathcal{I}}$ and auxiliary database
$Aux$ we denote the state of the program after applying a sequence $\alpha$ of
changes by ${\mathcal{P}}_{\alpha}({\mathcal{S}})$. The dynamic program
${\mathcal{P}}$ _maintains_ a $k$-ary query $q$ if, for each non-empty
sequence $\alpha$ of changes and each empty input structure
${\mathcal{I}}_{\emptyset}$, a designated auxiliary relation $Q$ in
${\mathcal{P}}_{\alpha}({\mathcal{S}}_{\emptyset})$ and
$q(\alpha({\mathcal{I}}_{\emptyset}))$ coincide. Here,
${\mathcal{S}}_{\emptyset}=({\mathcal{I}}_{\emptyset},Aux_{\emptyset})$, where
$Aux_{\emptyset}$ denotes the empty auxiliary structure over the domain of
${\mathcal{I}}_{\emptyset}$, and $\alpha({\mathcal{I}}_{\emptyset})$ is the
input database after applying $\alpha$.

In this article, we are particularly interested in maintaining queries for
structures of bounded treewidth. There are several ways to adjust the dynamic
setting to restricted classes ${\mathcal{C}}$ of structures. Here, we simply
disallow change sequences that construct structures outside ${\mathcal{C}}$.
That is, in the above definition, only change sequences $\alpha$ are
considered, for which each prefix transforms an initially empty structure into
a structure from ${\mathcal{C}}$. We say that a program maintains $q$ for a
class ${\mathcal{C}}$ of structures, if $Q$ contains its result after each
change sequence $\alpha$ such that the application of each prefix of $\alpha$
to ${\mathcal{I}}_{\emptyset}$ yields a structure from ${\mathcal{C}}$.

The class of queries that can be maintained by a dynamic program with first-
order update formulas is called DynFO. We say that a query $q$ is in DynFO for
a class ${\mathcal{C}}$ of structures, if there is such a dynamic program that
maintains $q$ for ${\mathcal{C}}$. Programs for queries in DynFO$(+,\times)$
have three particular auxiliary relations $\leq,+,\times$ that are initialised
as a linear order and the corresponding addition and multiplication relations.

For a wide class of queries, membership in DynFO$(+,\times)$ implies
membership in DynFO [DattaKMSZ18]. Queries of this class have the property
that the query result does not change considerably when elements are added to
the domain but not to any relation. Informally, a query $q$ is called almost
domain independent if there is a constant $c$ such that if a structure already
has at least $c$ “non-active” elements, adding more “non-active” elements does
not change the query result with respect to the original elements. More
formally, a query $q$ is _almost domain independent_ if there is a
$c\in\mathbb{N}$ such that, for every structure ${\mathcal{A}}$ and every set
$B\subseteq A\setminus\text{adom}({\mathcal{A}})$ with $|B|\geq c$ it holds
$q({\mathcal{A}})[(\text{adom}({\mathcal{A}})\cup
B)]=q({\mathcal{A}}[(\text{adom}({\mathcal{A}})\cup B)])$.

  1. (a)

The binary reachability query $q_{\text{Reach}}$, that maps a directed input
graph $G=(V,E)$ to its transitive closure relation, is almost domain
independent with $c=0$: adding any set $B\subseteq V\setminus\text{adom}(G)$
of isolated nodes to a graph does not create or destroy paths in the remaining
graph. Note that, for each node $v\in V$, the tuple $(v,v)$ is part of the
query result $q_{\text{Reach}}(G)$, so $q_{\text{Reach}}(G)\neq
q_{\text{Reach}}(G[\text{adom}(G)])$ in general and therefore
$q_{\text{Reach}}$ is not _domain independent_ in the sense of [DattaKMSZ15].

  2. (b)

The FO definable Boolean query $q_{|\neg\text{adom}|=2}$, which is true if and
only if exactly two elements are not in the active domain, is almost domain
independent with $c=3$.

  3. (c)

The Boolean query $q_{\text{even}}$, which is true for domains of even size
and false otherwise, is not almost domain independent.

Furthermore, all properties definable in monadic second-order logic are almost
domain dependent.

######  Proposition 3.1.

All MSO-definable queries are almost domain independent.

######  Proof 3.2 (Proof sketch.).

This can be easily shown by an Ehrenfeucht game. Let $\varphi$ be an MSO-
formula of quantifier depth $d$ with $e$ free (node) variables and let
$c=2^{d}d+e$. Consider two graphs ${\mathcal{A}}_{1}$ and ${\mathcal{A}}_{2}$
that result from adding $c_{1}\geq c$ and $c_{2}\geq c$ isolated nodes to some
graph ${\mathcal{A}}$, respectively. Since $\varphi$ might have free
variables, the game is played on $({\mathcal{A}}_{1},\bar{a}_{1})$ and
$({\mathcal{A}}_{2},\bar{a}_{2})$, where $\bar{a}_{1}$ and $\bar{a}_{2}$ are
tuples of elements of length $e$. Within $d$ moves the spoiler can use at most
$d$ set moves and can therefore induce at most $2^{d}$ different “colours” on
${\mathcal{A}}_{1}$ and ${\mathcal{A}}_{2}$. However, the duplicator can
easily guarantee that, for each such “colour”, the number of isolated nodes
(which do not occur in the initial tuples on both structures) of that colour
is the same in ${\mathcal{A}}_{1}$ and ${\mathcal{A}}_{2}$ _or_ it is larger
than $d$, in both of them. Since the spoiler can have at most $d$ node moves,
he can not make use of this difference in the two structures.

The following proposition adapts Proposition 7 from [DattaKMSZ18].

######  Proposition 3.3.

Let $q$ be an almost domain independent query. If
$q\in\textsc{DynFO$(+,\times)$}$ then also $q\in\textsc{DynFO}$.

The same statement is proved for weakly domain independent queries in
[DattaKMSZ18, Proposition 7]. A query $q$ is weakly domain independent, if
$q({\mathcal{A}})[\text{adom}({\mathcal{A}})]=q({\mathcal{A}}[\text{adom}({\mathcal{A}})])$
for all structures ${\mathcal{A}}$, that is, if it is almost domain
independent with $c=0$. The proof of [DattaKMSZ18, Proposition 7] can easily
be adapted for this more general statement, so we omit a full proof here.
However, for readers who are familiar with the proof of [DattaKMSZ18,
Proposition 7], we sketch the necessary changes.

######  Proof 3.4 (Proof sketch.).

We assume familiarity with the proof of [DattaKMSZ18, Proposition 7] and only
repeat its main outline. That proof explains, for a given
DynFO$(+,\times)$-program ${\mathcal{P}}$, how to construct a DynFO-program
${\mathcal{P}}^{\prime}$ that is equivalent to ${\mathcal{P}}$. This program
${\mathcal{P}}^{\prime}$ relies on the observation that a linear order,
addition and multiplication can be maintained on the _activated_ domain
[Etessami98], that is, on all elements that were part of the active domain at
some time during the dynamic process. The linear order is determined by the
order in which the elements are activated.

The program ${\mathcal{P}}^{\prime}$ can be regarded as the parallel
composition of multiple copies, called _threads_ , of the same dynamic
program. Each thread simulates ${\mathcal{P}}$ for a certain period of time:
thread $i$ _starts_ when $f(i-1)$ elements are activated and does some
initialisation, and it is _in charge_ of answering the query whenever more
than $f(i)$ but at most $f(i+1)$ elements are activated, for some function
$f$. Thanks to weak domain independence, thread $i$ only needs to simulate
${\mathcal{P}}$ on a domain with $f(i+1)$ elements, for which it can define
the arithmetic relations $\leq$, $+$ and $\times$ based on the available
arithmetic relations on the $f(i-1)$ activated elements.

For almost domain independent queries we extend this technique slightly. Let
$c$ be the constant from almost domain independence. The query result for a
structure with domain size $n$ coincides with the result of a simulation on a
domain of size $n^{\prime}$, if $n=n^{\prime}$ or if there are at least $c$
non-activated elements in both domains. To ensure that the simulation can in
principle represent these $c$ elements, phase $i$ is generally in charge as
long as the number of activated elements is at least $f(i)-c+1$ but at most
$f(i+1)-c$, as in phase $i$ one can simulate ${\mathcal{P}}$ on a domain of
size $f(i+1)$.

However, if in the original structure the number of non-activated elements
becomes smaller than $c$, the simulation has to switch to a domain of the same
size as the original domain. Therefore in phase $i$ there is not only one
simulation with domain size $f(i+1)$, but one simulation (denoted by the pair
$(i,\ell)$) for each domain size $\ell\in\\{f(i)-c+1,\ldots,f(i+1)\\}$. During
phase $i$ the simulation denoted by $(i,f(i+1))$ is in charge unless there are
fewer than $c$ non-activated elements in the original domain, which can be
easily detected by a first-order formula. As soon as that happens, the
simulation denoted by $(i,n)$ takes over, where $n$ is the size of the domain.

##  4\. Algorithmic Technique

The definition of DynFO requires that for the problem at hand each change can
be handled by a first-order definable update operation. There are alternative
definitions of DynFO, where the initial structure is non-empty and the initial
auxiliary relations can be computed within some complexity class [PatnaikI97,
WeberS07]. However, in a practical scenario of dynamic query answering it is
conceivable that the quality of the auxiliary relations decreases over time
and that they are therefore recomputed from scratch at times. We formalise
this notion by a relaxed definition of maintainability in which the initial
structure is non-empty, the dynamic program is allowed to apply some
preprocessing, and query answers need only be given for a certain number of
change steps.

A query $q$ is called _$({\mathcal{C}},f)$ -maintainable_, for some complexity
class222Strictly speaking ${\mathcal{C}}$ should be a complexity class of
functions. In this paper, the implied class of functions will always be clear
from the stated class of decision problems. ${\mathcal{C}}$ and some function
$f:\mathbb{N}\to\mathbb{R}$, if there is a dynamic program ${\mathcal{P}}$ and
a ${\mathcal{C}}$-algorithm ${\mathcal{A}}$ such that for each input database
${\mathcal{I}}$ over a domain of size $n$, each linear order $\leq$ on the
domain, and each change sequence $\alpha$ of length $|\alpha|\leq f(n)$, the
relation $Q$ in ${\mathcal{P}}_{\alpha}({\mathcal{S}})$ and
$q(\alpha({\mathcal{I}}))$ coincide where
${\mathcal{S}}=({\mathcal{I}},{\mathcal{A}}({\mathcal{I}},\leq))$.

Although we feel that $({\mathcal{C}},f)$-maintainability deserves further
investigation, in this paper we exclusively use it as a tool to prove that
queries are actually maintainable in DynFO. To this end, we show next that
every $(\textsc{AC}^{1},\log n)$-maintainable query is actually in DynFO and
prove later that the queries in which we are interested are
$(\textsc{AC}^{1},\log n)$-maintainable.

######  Theorem 4.1.

Every $(\textsc{AC}^{1},\log n)$-maintainable, almost domain independent query
is in DynFO.

We do not prove this theorem directly, but instead give a more general result,
strengthening the correspondence between depth of the initialising circuit
families and number of change steps the query has to be maintained.

######  Theorem 4.2.

Let $f:\mathbb{N}\to\mathbb{N}$ be a first-order constructible function with
$f\in\mathcal{O}(n)$. Every $(\textsc{AC}[f(n)],f(n))$-maintainable, almost
domain independent query is in DynFO.

######  Proof 4.3.

Let $f:\mathbb{N}\to\mathbb{N}$ be first-order constructible with
$f\in\mathcal{O}(n)$ and assume that an $\textsc{AC}[f(n)]$ algorithm
${\mathcal{A}}$ and a dynamic program ${\mathcal{P}}$ witness that an almost
domain independent query $q$ is $(\textsc{AC}[f(n)],f(n))$-maintainable.
Thanks to Proposition 3.3 it suffices to construct a dynamic program
${\mathcal{P}}^{\prime}$ that witnesses $q\in\textsc{DynFO$(+,\times)$}$. We
restrict ourselves to graphs, for simplicity.

The overall idea is to use a simulation technique similar to the ones used in
Proposition 3.3 and in [SchwentickVZ18, Theorem 8.1]. We first present the
computations performed by ${\mathcal{P}}^{\prime}$ intuitively and later
explain how they can be expressed in first-order logic.

We consider each application of one change as a _time step_ and refer to the
graph after time step $t$ as $G_{t}=(V,E_{t})$. After each time step $t$, the
program ${\mathcal{P}}^{\prime}$ starts a thread that is in charge of
answering the query at time point $t+f(n)$. Each thread works in two phases,
each lasting $\frac{f(n)}{2}$ time steps. Roughly speaking, the first phase is
in charge of simulating ${\mathcal{A}}$ and in the second phase
${\mathcal{P}}$ is used to apply all changes that occur from time step $t+1$
to time step $t+f(n)$. Using $f(n)$ many threads, ${\mathcal{P}}^{\prime}$ is
able to answer the query from time point $f(n)$ onwards.

We now give more details on the two phases and describe afterwards how to deal
with time points earlier than $f(n)$. For the first phase, we make use of the
equality $\textsc{AC}[f(n)]=\text{IND}[f(n)]$, see [ImmermanDC]. Let $\psi$ be
an inductive formula that is applied $df(n)$ times, for some $d$, to get the
auxiliary relations ${\mathcal{A}}(G,\leq)$ for a given graph $G$ and the
given order $\leq$. The program ${\mathcal{P}}^{\prime}$ applies $\psi$ to
$G_{t}$, $2d$ times during each time step, and thus the result of
${\mathcal{A}}$ on $(G_{t},\leq)$ is obtained after $\frac{f(n)}{2}$ steps.
The change operations that occur during these steps are not applied to $G_{t}$
directly but rather stored in some additional relation. If some edge $e$ is
changed multiple times, the stored change for $e$ is adjusted accordingly.

During the second phase the $\frac{f(n)}{2}$ stored change operations and the
$\frac{f(n)}{2}$ change operations that happen during the next
$\frac{f(n)}{2}$ steps are applied to the state after phase 1. To this end, it
suffices for ${\mathcal{P}}^{\prime}$ to apply two changes during each time
step by simulating two update steps of ${\mathcal{P}}$. Observe that
${\mathcal{P}}^{\prime}$ processes the changes in a different order than they
actually occur. However, both change sequences result in the same graph. Since
${\mathcal{P}}$ can maintain $q$ for $f(n)$ changes, the program
${\mathcal{P}}^{\prime}$ can give the correct query answer for $q$ about
$G_{t+f(n)}$ at the end of phase 2, that is, at time point $t+f(n)$.

The following auxiliary relations are used by thread $i$:

  * •

a binary relation $\hat{E}_{i}$ that contains the edges currently considered
by the thread,

  * •

binary relations $\Delta^{+}_{i}$ and $\Delta^{-}_{i}$ that cache edges
inserted and deleted during the first phase, respectively,

  * •

a relation $\hat{R}_{i}$ for each auxiliary relation $R$ of ${\mathcal{P}}$
with the same arity,

  * •

and a relation $C_{i}$ that is used as a counter: it contains exactly one
tuple which is interpreted as the counter value, according to its position in
the lexicographic order induced by $\leq$.

When thread $i$ starts its first phase at time point $t$, it sets
$\hat{E}_{i}$ to $E_{t}$ and the counter $C_{i}$ to $0$; its other auxiliary
relations are empty in the beginning. Whenever an edge $(u,v)$ is inserted (or
deleted), $\hat{E}_{i}$ is not changed, $(u,v)$ is inserted into
$\Delta^{+}_{i}$ (or $\Delta^{-}_{i}$)333If an edge $(u,v)$ with
$(u,v)\in\Delta^{-}_{i}$ is inserted, it is instead deleted from
$\Delta^{-}_{i}$, and accordingly for deletions of edges
$(u,v)\in\Delta^{+}_{i}$., and the counter $C_{i}$ is incremented by one. The
relations $\hat{R}_{i}$ are replaced by the result of applying their defining
first-order formulas $2d$ times, as explained above.

When the counter value is at least $\frac{f(n)}{2}$, the thread enters its
second phase and proceeds as follows. When an edge $(u,v)$ is inserted (or
deleted), it applies this change and the change implied by the
lexicographically smallest tuple in $\Delta^{+}_{i}$ and $\Delta^{-}_{i}$, if
these relations are not empty: it simulates ${\mathcal{P}}$ for these changes
using the edge set $\hat{E}_{i}$ and auxiliary relations $\hat{R}_{i}$,
replaces the auxiliary relations accordingly and adjusts
$\hat{E}_{i},\Delta^{+}_{i}$ and $\Delta^{-}_{i}$. Again, the counter $C_{i}$
is incremented. If the counter value is $f(n)$, the thread’s query result is
used as the query result of ${\mathcal{P}}^{\prime}$, and the thread stops.
All steps are easily seen to be first-order expressible.

So far we have seen how ${\mathcal{P}}^{\prime}$ can give the query answer
from time step $f(n)$ onwards. For time steps earlier than $f(n)$ the approach
needs to be slightly adapted as the program does not have enough time to
simulate ${\mathcal{A}}$. The idea is that for time steps $t<f(n)$ the active
domain is small and, exploiting the almost domain independence of $q$, it
suffices to compute the query result with respect to this small domain
extended by $c$ isolated elements, where $c$ is the constant from almost
domain independence. The result on this restricted domain can afterwards be
used to define the result for the whole domain.

Towards making this idea more precise, let $n_{0},b$ be such that $bn\geq
f(n)$ for all $n\geq n_{0}$. We focus on explaining how
${\mathcal{P}}^{\prime}$ handles structures with $n\geq n_{0}$, as small
graphs with less than $n_{0}$ nodes can be dealt with separately.

The program ${\mathcal{P}}^{\prime}$ starts a new thread at time $\frac{t}{2}$
for the graph $G_{\frac{t}{2}}$ with at most $\frac{t}{2}$ edges. Such a
thread is responsible for providing the query result after $t$ time steps, and
works in two phases that are similar to the phases described above. It
computes relative to a domain $D_{t}$ of size $\min\\{2t+c,n\\}$, where $c$ is
the constant from (almost) domain independence. The size of $D_{t}$ is large
enough to account for possible new nodes used in edge insertions in the
following $\frac{t}{2}$ change steps. The domain $D_{t}$ is chosen as the
first $|D_{t}|$ elements of the full domain (with respect to $\leq$). The
program ${\mathcal{P}}^{\prime}$ maintains a bijection $\pi$ between the
active domain $D_{G}$ of the current graph $G$ and the first $|D_{G}|$
elements of the domain to allow a translation between $D_{G}$ and $D_{t}$.

The first phase of the thread for $t$ starts at time point $\frac{t}{2}+1$ and
applies $\psi$ for $8bcd$ times during each of the next time steps. This
simulation of ${\mathcal{A}}$ is finished after at most
$\frac{(2t+c)b}{8bc}\leq\frac{t}{4}$ time steps, and therefore the auxiliary
relations are properly initialised at time point $\frac{3t}{4}$.

In the second phase, starting at time step $\frac{3t}{4}+1$ and ending at time
step $t$, the changes that occurred in in the first phase are applied, two at
a time. The thread is then ready to answer $q$ at time point $t$. Since at
time $t$ at most $2t$ elements are used by edges, the almost domain
independence of $q$ guarantees that the result computed by the thread relative
to $D_{t}$ coincides with the $D_{t}$-restriction of the query result for
$\pi(G_{t})$. The query result for $G_{t}$ is obtained by translating the
obtained result according to $\pi^{-1}$, and extending it to the full domain.
More precisely, a tuple $\bar{t}$ is included in the query result, if it can
be generated from a tuple $\bar{t}^{\prime}$ of the restricted query result by
replacing elements from $\pi^{-1}(D_{t})\setminus\text{adom}(G_{t})$ by
elements from $V\setminus\text{adom}(G_{t})$ (under consideration of equality
constraints among these elements). Again, all steps are easily seen to be
first-order definable using the auxiliary relations from above.

The above presentation assumes a separate thread for each time point and each
thread uses its own relations. These threads can be combined into one dynamic
program as follows. Since at each time point at most $f(n)$ threads are
active, we can number them in a round robin fashion with numbers
$1,\ldots,f(n)$ that we can encode by tuples of constant arity. The arity of
all auxiliary relations is incremented accordingly and the additional
dimensions are used to indicate the number of the thread to which a tuple
belongs.

##  5\. Warm-up: 3-Colourability

In this section, we show that the 3-colourability problem

######  Problem 5.1.

3Col for graphs of bounded treewidth can be maintained in DynFO. Given an
undirected graph,


# Observation of high-energy neutrinos from the
Galactic plane

The IceCube Collaboration
(a complete list of authors can be found at the end of the proceedings)

###### Abstract

IceCube has discovered a flux of astrophysical neutrinos and presented
evidence for the first neutrino sources, a flaring blazar known as TXS
0506+056 and the active galaxy NGC 1068. However, the sources responsible for
the majority of the astrophysical neutrino flux remain elusive. In addition to
hypothetical sources within our Galaxy, high energy neutrinos are produced
when cosmic rays interact at their acceleration sites and during propagation
through the interstellar medium. The Galactic plane has therefore long been
hypothesized as a neutrino source. In this contribution, new results are
presented for searches of neutrino sources utilizing a dataset that builds
upon recent advances in deep-learning-based reconstruction methods for
neutrino-induced cascades. This work presents the first observation of high-
energy neutrinos from the Milky Way Galaxy, rejecting the background-only
hypothesis at 4.5 $\sigma$. The neutrino signal is consistent with diffuse
emission from the Galactic plane, potentially in combination with emission by
a population of sources.

Corresponding authors: Steve Sclafani1∗, Mirco Hünnefeld2
1 University of Maryland
2 TU Dortmund University
∗ Presenter

##  1 Neutrino Production in the Milky Way

The Milky Way Galaxy has been observed over many wavelengths of light, from
radio waves to gamma rays. At energies above 1 GeV, the sky as observed by
Fermi-LAT [1] is dominated by emission from the Galactic plane of the Milky
Way. Cosmic rays can interact at their acceleration site creating high-energy
neutrinos and gamma rays, but can also escape the acceleration environment.
The cosmic rays will generally diffuse through the Galaxy, and may interact
with the dust and gas of the plane, producing emission at the site of these
interactions. The observed emission reflects the density and energy of cosmic
rays, as well as the column density of matter. This diffuse emission has been
observed in gamma rays [1, 2, 3], and the counterpart has been predicted in
high-energy neutrinos [4, 5]. This work presents the first evidence of high-
energy neutrinos from the Milky Way Galaxy [6].

The IceCube Neutrino Observatory, a cubic-kilometer detector located in the
geographic South Pole, is instrumented with 5160 Digital Optical Modules
(DOMs), each with a PMT and digitizing hardware. When a neutrino interacts
with the ice, charged secondary particles produce Cherenkov light in the
detector that can be used to reconstruct the direction and energy of the
primary neutrino. These interactions occur in two main topologies. “Track”
events are mostly produced from “charged-current” (CC) $\nu_{\mu}$
interactions that produce an outgoing muon, which traverses the detector and
deposits light along the particle track, whereas “cascade” events are produced
from “neutral-current” (NC) interactions of all flavors, as well as
CC$-\nu_{e}$ or CC-$\nu_{\tau}$ interactions. These produce a shower of
particles that appear as a nearly spherically expanding light front. For this
reason, typical cascade events have inferior angular resolution (>10∘ at 10
TeV) when compared to track events (<1∘). After IceCube discovered a flux of
astrophysical neutrinos [7], it used track events to present evidence for two
sources [8, 9]. The sources responsible for the majority of the astrophysical
flux, however, remain unknown. The diffuse flux from the Galactic plane can
account for up to $\sim$10% of this flux at TeV energies [10].

Previous searches for emission from the Galactic plane did not find any
significant emission [11, 10, 12, 13]. The level of Galactic emission is
expected to be low when compared to the measured all-sky astrophysical flux,
and due to the direction of the Galactic center, diffuse emission is
concentrated in the southern sky. For IceCube, due to the location of the
detector at the South Pole, selections in the southern celestial sky are
composed of events downgoing in the detector. Searches in this region are
particularly difficult due to the large background of atmospheric muons.
Through-going track-based analyses see a reduction of sensitivity due to this
irreducible background [14]. This is especially true for galactic sources,
which are assumed to follow a softer spectrum. This work, however, makes use
of cascade events, which have a much reduced background in the southern sky,
and lead to an improvement of sensitivity. Further, machine learning
techniques applied to IceCube cascade events improve the sensitivity by a
factor of 3-4 over previous searches [6]. Consequently, this work improves
sensitivity to diffuse Galactic plane emission models, leading to the first
evidence of high-energy neutrino emission from the Milky Way at a significance
of 4.5$\sigma$.

##  2 Application of Deep Learning to Cascade Events

In the southern sky, the primary background for IceCube consists of
atmospheric muons, which trigger the detector at a rate a billion times higher
than astrophysical neutrinos. This background appears in the detector as
downgoing track events which pass through the detector. These events cannot be
distinguished from neutrino-induced muons entering the detector. Thus, the
event selection in this work is optimized to search for events that start
within the detector and have cascade-like topologies. The selection of cascade
events instead of track events reduces the atmospheric muon background, and
also suppresses the atmospheric neutrino background, which primarily consists
of muon flavored neutrinos. Previous cascade searches [12] used an event
selection based on veto layers that improved the effective area over tracks in
the 1-100 TeV range [15]. This work, however, relies heavily on a Deep-Neural-
Network (DNN) based selection [16] that improves the selection efficiency [6]
at low energies. Further, this work includes events that are partially
contained within the detector, which improves the efficiency mostly at higher
energies. Due to the reduced backgrounds, the lower energy threshold is pushed
lower, from a tens of TeV down to around 1 TeV. The effective area at 10 TeV
is increased by a factor of $\sim$5 when compared to previous cascade
selections, as shown in Figure 1A. This increase in effective area corresponds
to a an increase of astrophysical events by up to a factor of 20, assuming the
measurement in [17], as shown in Figure 1B. Relative improvements are largest
at energies below a few tens of TeV.

Figure 1:  (A) The all-flavor southern sky effective area (AEff) of the
IceCube dataset, averaged over solid angle in the declination ($\delta$) range
between $-90^{\circ}$ and $-5^{\circ}$ as a function of Eν, the true neutrino
energy. Results are shown for the deep learning event selection used in this
work, (dark blue), a previous cascade event selection [12] (light blue), and ,
as an example, a previous though-going track event selection [14] (grey)
applied to the IceCube data. (B) The number of expected signal events (NAstro)
in the southern sky per energy bin per year for each event selection, assuming
an isotropic astrophysical flux [17]. Calculations are based on equal
contributions of each neutrino flavor at Earth due to neutrino oscillations,
(figure from [6])

The event selection also relies on a novel reconstruction that combines the
advantages of DNNs with traditional maximum likelihood methods [18]. The new
reconstruction technique results in a similar, sample-averaged angular
resolution at high energies as obtained by the previous cascade sample,
despite the inclusion of more challenging events. At low energies, the sample-
averaged resolution is improved by up to a factor of two. These improvements
are achieved due to better exploitation of available information and
symmetries in the novel reconstruction method [18].

##  3 Searches for Galactic neutrino emission

Multiple source hypotheses were tested. The focus of this work is the testing
of three models of diffuse Galactic plane emission. The first model, referred
to here as $\pi^{0}$, is based on the extrapolation from the Fermi-LAT fit to
the first 21 months of data [1]. The spatial template from Fermi-LAT is
assumed unchanged at TeV energies, and the energy spectrum is assumed to be an
unbroken power-law with fixed spectral index $\gamma$=2.7. The other two
models, referred to as KRAγ, model the Galactic cosmic ray diffusion
coefficient as radially dependent [19]. This results in a harder spectrum
towards the galactic center which then results in an enhanced flux after
extrapolation to IceCube’s energies. Here we test the extrapolated flux, but
use a global energy dependant spectrum, averaged over all directions. Two
cutoffs are tested. KRA${}_{\gamma}^{5}$ and KRA${}_{\gamma}^{50}$ correspond
to cutoffs in Galactic cosmic rays at 5 PeV and 50 PeV respectively. These
energies are propagated down to lower energies in neutrinos. The sky-
integrated flux of these models are shown in Figure 2.

For each template, the number of signal events is fitted while the spectrum is
held fixed. A likelihood-ratio test is performed with the log-likelihood ratio
as the test statistic (TS) [11]. Background TS distributions are calculated
from scrambled data, and the true TS for each template is compared with this
background distribution to calculate the p-value. Due to IceCube’s location on
the Earth, scrambling the Right Ascension (RA) direction produces background-
like pseudo-experiments, but preserves any detector effects. Using this data
driven technique to derive p-values, any unmodeled effect will result in a
reduction of sensitivity, but not risk a false signal.

In addition to the diffuse Galactic plane analyses, searches were performed
for neutrino emission from Galactic source classes corresponding to supernova
remnants (SNR), pulsar wind nebulae (PWN) and unidentified TeV gamma-ray
sources (UNID). Stacking sources can result in an improved sensitivity over
searching for each source individually. Three classes of 12 potential Galactic
sources are selected based on their TeV gamma-ray flux, and each is source is
weighted to equally contribute. The complete source list is available in Ref.
[6].

##  4 Neutrinos from the Milky Way

The results for the diffuse Galactic plane and source stacking are shown in
Table 1 and Table 2 respectively, which was first reported in [6]. Each of the
diffuse emission hypotheses is significant with pre-trial p-values
corresponding to 4.71$\sigma$, 4.37$\sigma$ and 3.96$\sigma$, respectively.
These fluxes correspond to best-fitting values of 748, 276, and 211 signal
events ($n_{s}$) in the IceCube dataset for the $\pi^{0}$,
KRA${}_{\gamma}^{5}$ and KRA${}_{\gamma}^{50}$ models, respectively. After
accounting for the three tested hypotheses, the resulting post-trials p-value
is calculated,and coresponds to a significance of 4.5$\sigma$.

$\begin{array}[]{cc}\textbf{Diffuse Galactic}\\\ \textbf{plane analyses}\end{array}$ | $\begin{array}[]{cc}\textbf{Flux Sensitvity}\\\ \textbf{$\Phi$}\end{array}$ | $\begin{array}[]{cc}\textbf{Best-fitting}\\\ \textbf{$n_{s}$}\end{array}$ | p-value | $\begin{array}[]{cc}\textbf{Best-fitting}\\\ \textbf{flux $\Phi$}\end{array}$
---|---|---|---|---
$\pi^{0}$ | 5.98 | 748 | 1.3$\times$10-6 (4.71$\sigma$) | 21.8 ${}^{+5.3}_{-4.9}$
KRA${}_{\gamma}^{5}$ | 0.16$\times$MF | 276 | 6.1$\times$10-6 (4.37$\sigma$) | 0.55${}^{+0.18}_{-0.15}\times$MF
KRA${}_{\gamma}^{50}$ | 0.11$\times$MF | 211 | 3.7$\times$10-5 (3.96$\sigma$) | 0.37${}^{+0.13}_{-0.11}\times$MF
Table 1:  The flux sensitivity and best-fitting flux normalization ($\Phi$)
are given in units of model flux (MF) for KRAγ templates and as E2
$\frac{dN}{dE}$ at 100 TeV in units of 10-12 TeV cm-2 s-1 for the $\pi^{0}$
analyses ($\frac{dN}{dE}$ is the differential number of neutrinos per flavor,
N, and neutrino energy, E). P-values and significance are calculated with
respect to the background-only hypothesis. Pre-trial p-values for each
individual result are shown for the three diffuse Galactic plane analyses.

Also included in Table 1 are best-fit flux normalizations for each template.
The $\pi^{0}$ flux is reported at 100 TeV. Since the KRAγ models do not follow
a power-law, the flux is reported as multiples of the model prediction. Those
normalizations are shown compared to the model for each template in Figure 2.
The KRAγ best-fitting normalization is less than the models, whereas the
$\pi^{0}$ best-fit is larger by a factor of $\sim$5 than the $\pi^{0}$ model.
This could be an indication that the underlying diffuse emission spectrum is
more complex than assumed in any of the tested models, possibly containing a
contribution from unresolved Galactic sources. These results are based on the
all-sky template and model-to-model flux comparisons depend on the considered
sky region. When considering regions of the sky tested by gamma-ray
experiments like Tibet-AS$\gamma$ the best-fit $\pi^{0}$ model fits well with
the measured gamma-ray flux. The IceCube result, however, is a measurement
over the entire sky and it does not attempt to mask out any galactic sources,
as none have been identified.

Figure 2: Energy-scaled, sky-integrated, per-flavor neutrino flux as a
function of neutrino energy (Eν) for each of the Galactic plane models. Dotted
lines are the predicted values for the $\pi^{0}$ (dark blue),
KRA${}_{\gamma}^{5}$ (orange) and KRA${}_{\gamma}^{50}$ (light blue) models
while solid lines are our best-fitting flux normalizations from the IceCube
data. Shaded regions indicate the 1$\sigma$ uncertainties, extending over the
energy range that contributes to 90$\%$ of the significance. These results are
based on the all-sky (4$\pi$ sr) template and are presented as an all-sky
flux. For comparison, the grey hatching shows the flux of the IceCube all-sky
neutrino flux [17], scaled to an all-sky flux by multiplying by 4$\pi$, with
its 1$\sigma$ uncertainty. Figure from [6]

In addition to the Galactic diffuse templates, the three Galactic stacking
analyses also resulted in evidence above 3$\sigma$ with pre-trial significance
of 3.24$\sigma$, 3.24$\sigma$, and 3.40$\sigma$ for the SNR, PWN, and UNID
classes respectively. The full results are shown in Table 2. Due to the large
spatial overlap in source hypotheses, these significances are expected in the
scenario of diffuse emission at the best-fit values reported in Table 1. This
analysis cannot distinguish the contribution of individual sources or classes
of sources from diffuse emission.

Catalog | Sensitivity $\Phi$ | ns | $\gamma$ | p-value | Significance ($\sigma$) | Flux $\Phi$ | UL $\Phi$
---|---|---|---|---|---|---|---
SNR | 2.24 | 218.6 | 2.75 | 5.9$\times$10-4 | 3.24 | 6.22 | <9.01
PWN | 2.25 | 279.6 | 3.00 | 5.9$\times$10-4 | 3.24 | 3.80 | <9.50
UNID | 1.89 | 238.4 | 2.85 | 3.4$\times$10-4 | 3.40 | 5.03 | <7.76
Table 2:  Pre-trial significance, sensitivity, best-fitting spectrum
($\gamma$), total number of signal events (ns), flux, and 90% Upper Limits
(UL) for the Galactic stacking catalog analyses. Upper limits are with respect
to a source emitting following an E-2 spectrum. The per-flavor neutrino flux
sensitivity, best-fit, and upper limits are given as E2 $\frac{dN}{dE}$ at 100
TeV in units of 10-12 TeV cm-2 s-1 for the entire catalog of sources.

Finally, an all-sky scan was performed, searching at each location on the sky
for an excess of point-like neutrino emission. The visualization of this all-
sky search is shown in equatorial coordinates in Figure 3. Excesses are
visible along the Galactic plane and near well known gamma-ray emitters, such
as the Crab Nebula, 3C 454.3, and the Cygnus X region, however, no single
point is significant once trials are accounted for.

Figure 3: The best-fitting pre-trial significance for the all-sky search is
shown as a function of direction in an Aitoff projection of the celestial
sphere, in equatorial coordinates (J2000 equinox). The Galactic plane is
indicated by a grey curve, and the Galactic Center as a dot. Although some
locations appear to have significant emission, the trial factor for the number
of points searched means these points are all individually statistically
consistent with background fluctuations. The clustering of larger
significances along the galactic plane reflects the significant excess that is
observed in the template searches for the Galactic plane. Figure from [6].

##  5 Conclusion

This work presents the first evidence of high-energy neutrino emission from
the Milky Way Galaxy. The result is consistent with a diffuse neutrino
emission hypothesis or a collection of unresolved sources.

Round-trip tests were performed to investigate the correlation between the
source stacking analyses and the diffuse Galactic plane analyses. Injecting
the best-fitted flux from the $\pi^{0}$ template results in a significance for
the other templates that is compatible with the observed results. Injecting
any one of the stacking source hypotheses individually, does not recover the
best-fitted flux for the diffuse emission models. Further, it is possible that
some of these sources still contribute to the observed flux.

More information is needed to characterize the Galactic component of the
astrophysical neutrino flux. A larger range of Galactic templates, including
more recent models [20], have been tested with a dataset of northern sky track
events in IceCube [21]. A search for the same diffuse templates was also
performed with IceCube starting track events [22, 23]. Both results are
compatible with the results presented in this work. Further work will require
the identification of sources and their spectra. This could be done by
combining the signal purity of cascade events with the angular resolution of
track events [24].

## References

  * [1] Fermi-LAT Collaboration, M. Ackermann et al. Astrophys. J. 750 no. 1, (Apr, 2012) 3.
  * [2] Z. Cao et al. arXiv:2305.05372.
  * [3] Tibet ${\mathrm{AS}}_{\gamma}$ Collaboration, M. Amenomori et al. Phys. Rev. Lett. 126 (Apr, 2021) 141101.
  * [4] F. W. Stecker Astrophys. J. 228 (Mar., 1979) 919–927.
  * [5] V. Berezinsky et al. Astropart. Phys. 1 no. 3, (1993) 281–287.
  * [6] IceCube Collaboration, R. Abbasi et al. Science 380 no. 6652, (2023) .
  * [7] IceCube Collaboration Science 342 no. 6161, (2013) 1242856.
  * [8] IceCube Collaboration, M. Aartsen et al. Science 361 no. 6398, (2018) 147–151.
  * [9] IceCube Collaboration, R. Abbasi et al. Science 378 no. 6619, (2022) 538–543.
  * [10] A. Albert et al. The Astrophysical Journal 868 no. 2, (Nov., 2018) L20.
  * [11] IceCube Collaboration, M. G. Aartsen et al. Astrophys. J. 849 no. 1, (Oct, 2017) 67.
  * [12] IceCube Collaboration, M. G. Aartsen et al. Astrophys. J. 886 no. 1, (Nov, 2019) 12.
  * [13] ANTARES Collaboration, A. Albert et al. Physics Letters B 841 (June, 2023) 137951.
  * [14] IceCube Collaboration, M. Aartsen et al. Physical Review Letters 124 no. 5, (Feb., 2020) .
  * [15] IceCube Collaboration, M. G. Aartsen et al. Phys. Rev. D 91 (Jan., 2015) 022001.
  * [16] IceCube Collaboration, R. Abbasi et al. J. Instrum. 16 no. 07, (July, 2021) P07041.
  * [17] IceCube Collaboration, M. G. Aartsen et al. Phys. Rev. Lett. 125 no. 12, (Sep, 2020) 121104.
  * [18] IceCube Collaboration, M. Huennefeld, R. Abbasi, et al. PoS ICRC2021 (2021) 1065.
  * [19] D. Gaggero et al. Astrophys. J. 815 no. 2, (Dec, 2015) L25.
  * [20] G. Schwefer, P. Mertsch, and C. Wiebusch The Astrophysical Journal 949 no. 1, (May, 2023) 16.
  * [21] IceCube Collaboration PoS ICRC2023 (these proceedings) 1046.
  * [22] IceCube Collaboration PoS ICRC2023 (these proceedings) 1008.
  * [23] IceCube Collaboration, M. G. Aartsen et al. To be submitted to Physical Review D .
  * [24] IceCube Collaboration PoS ICRC2023 (these proceedings) 1010.

## Full Author List: IceCube Collaboration

R. Abbasi17, M. Ackermann63, J. Adams18, S. K. Agarwalla40, 64, J. A.
Aguilar12, M. Ahlers22, J.M. Alameddine23, N. M. Amin44, K. Andeen42, G.
Anton26, C. Argüelles14, Y. Ashida53, S. Athanasiadou63, S. N. Axani44, X.
Bai50, A. Balagopal V.40, M. Baricevic40, S. W. Barwick30, V. Basu40, R. Bay8,
J. J. Beatty20, 21, J. Becker Tjus11, 65, J. Beise61, C. Bellenghi27, C.
Benning1, S. BenZvi52, D. Berley19, E. Bernardini48, D. Z. Besson36, E.
Blaufuss19, S. Blot63, F. Bontempo31, J. Y. Book14, C. Boscolo Meneguolo48, S.
Böser41, O. Botner61, J. Böttcher1, E. Bourbeau22, J. Braun40, B. Brinson6, J.
Brostean-Kaiser63, R. T. Burley2, R. S. Busse43, D. Butterfield40, M. A.
Campana49, K. Carloni14, E. G. Carnie-Bronca2, S. Chattopadhyay40, 64, N.
Chau12, C. Chen6, Z. Chen55, D. Chirkin40, S. Choi56, B. A. Clark19, L.
Classen43, A. Coleman61, G. H. Collin15, A. Connolly20, 21, J. M. Conrad15, P.
Coppin13, P. Correa13, D. F. Cowen59, 60, P. Dave6, C. De Clercq13, J. J.
DeLaunay58, D. Delgado14, S. Deng1, K. Deoskar54, A. Desai40, P. Desiati40, K.
D. de Vries13, G. de Wasseige37, T. DeYoung24, A. Diaz15, J. C. Díaz-Vélez40,
M. Dittmer43, A. Domi26, H. Dujmovic40, M. A. DuVernois40, T. Ehrhardt41, P.
Eller27, E. Ellinger62, S. El Mentawi1, D. Elsässer23, R. Engel31, 32, H.
Erpenbeck40, J. Evans19, P. A. Evenson44, K. L. Fan19, K. Fang40, K. Farrag16,
A. R. Fazely7, A. Fedynitch57, N. Feigl10, S. Fiedlschuster26, C. Finley54, L.
Fischer63, D. Fox59, A. Franckowiak11, A. Fritz41, P. Fürst1, J. Gallagher39,
E. Ganster1, A. Garcia14, L. Gerhardt9, A. Ghadimi58, C. Glaser61, T.
Glauch27, T. Glüsenkamp26, 61, N. Goehlke32, J. G. Gonzalez44, S. Goswami58,
D. Grant24, S. J. Gray19, O. Gries1, S. Griffin40, S. Griswold52, K. M.
Groth22, C. Günther1, P. Gutjahr23, C. Haack26, A. Hallgren61, R. Halliday24,
L. Halve1, F. Halzen40, H. Hamdaoui55, M. Ha Minh27, K. Hanson40, J. Hardin15,
A. A. Harnisch24, P. Hatch33, A. Haungs31, K. Helbing62, J. Hellrung11, F.
Henningsen27, L. Heuermann1, N. Heyer61, S. Hickford62, A. Hidvegi54, C.
Hill16, G. C. Hill2, K. D. Hoffman19, S. Hori40, K. Hoshina40, 66, W. Hou31,
T. Huber31, K. Hultqvist54, M. Hünnefeld23, R. Hussain40, K. Hymon23, S. In56,
A. Ishihara16, M. Jacquart40, O. Janik1, M. Jansson54, G. S. Japaridze5, M.
Jeong56, M. Jin14, B. J. P. Jones4, D. Kang31, W. Kang56, X. Kang49, A.
Kappes43, D. Kappesser41, L. Kardum23, T. Karg63, M. Karl27, A. Karle40, U.
Katz26, M. Kauer40, J. L. Kelley40, A. Khatee Zathul40, A. Kheirandish34, 35,
J. Kiryluk55, S. R. Klein8, 9, A. Kochocki24, R. Koirala44, H. Kolanoski10, T.
Kontrimas27, L. Köpke41, C. Kopper26, D. J. Koskinen22, P. Koundal31, M.
Kovacevich49, M. Kowalski10, 63, T. Kozynets22, J. Krishnamoorthi40, 64, K.
Kruiswijk37, E. Krupczak24, A. Kumar63, E. Kun11, N. Kurahashi49, N. Lad63, C.
Lagunas Gualda63, M. Lamoureux37, M. J. Larson19, S. Latseva1, F. Lauber62, J.
P. Lazar14, 40, J. W. Lee56, K. Leonard DeHolton60, A. Leszczyńska44, M.
Lincetto11, Q. R. Liu40, M. Liubarska25, E. Lohfink41, C. Love49, C. J. Lozano
Mariscal43, L. Lu40, F. Lucarelli28, W. Luszczak20, 21, Y. Lyu8, 9, J.
Madsen40, K. B. M. Mahn24, Y. Makino40, E. Manao27, S. Mancina40, 48, W. Marie
Sainte40, I. C. Mariş12, S. Marka46, Z. Marka46, M. Marsee58, I. Martinez-
Soler14, R. Maruyama45, F. Mayhew24, T. McElroy25, F. McNally38, J. V. Mead22,
K. Meagher40, S. Mechbal63, A. Medina21, M. Meier16, Y. Merckx13, L. Merten11,
J. Micallef24, J. Mitchell7, T. Montaruli28, R. W. Moore25, Y. Morii16, R.
Morse40, M. Moulai40, T. Mukherjee31, R. Naab63, R. Nagai16, M. Nakos40, U.
Naumann62, J. Necker63, A. Negi4, M. Neumann43, H. Niederhausen24, M. U.
Nisa24, A. Noell1, A. Novikov44, S. C. Nowicki24, A. Obertacke Pollmann16, V.
O’Dell40, M. Oehler31, B. Oeyen29, A. Olivas19, R. Ørsøe27, J. Osborn40, E.
O’Sullivan61, H. Pandya44, N. Park33, G. K. Parker4, E. N. Paudel44, L.
Paul42, 50, C. Pérez de los Heros61, J. Peterson40, S. Philippen1, A.
Pizzuto40, M. Plum50, A. Pontén61, Y. Popovych41, M. Prado Rodriguez40, B.
Pries24, R. Procter-Murphy19, G. T. Przybylski9, C. Raab37, J. Rack-Helleis41,
K. Rawlins3, Z. Rechav40, A. Rehman44, P. Reichherzer11, G. Renzi12, E.
Resconi27, S. Reusch63, W. Rhode23, B. Riedel40, A. Rifaie1, E. J. Roberts2,
S. Robertson8, 9, S. Rodan56, G. Roellinghoff56, M. Rongen26, C. Rott53, 56,
T. Ruhe23, L. Ruohan27, D. Ryckbosch29, I. Safa14, 40, J. Saffer32, D.
Salazar-Gallegos24, P. Sampathkumar31, S. E. Sanchez Herrera24, A. Sandrock62,
M. Santander58, S. Sarkar25, S. Sarkar47, J. Savelberg1, P. Savina40, M.
Schaufel1, H. Schieler31, S. Schindler26, L. Schlickmann1, B. Schlüter43, F.
Schlüter12, N. Schmeisser62, T. Schmidt19, J. Schneider26, F. G. Schröder31,
44, L. Schumacher26, G. Schwefer1, S. Sclafani19, D. Seckel44, M. Seikh36, S.
Seunarine51, R. Shah49, A. Sharma61, S. Shefali32, N. Shimizu16, M. Silva40,
B. Skrzypek14, B. Smithers4, R. Snihur40, J. Soedingrekso23, A. Søgaard22, D.
Soldin32, P. Soldin1, G. Sommani11, C. Spannfellner27, G. M. Spiczak51, C.
Spiering63, M. Stamatikos21, T. Stanev44, T. Stezelberger9, T. Stürwald62, T.
Stuttard22, G. W. Sullivan19, I. Taboada6, S. Ter-Antonyan7, M. Thiesmeyer1,
W. G. Thompson14, J. Thwaites40, S. Tilav44, K. Tollefson24, C. Tönnis56, S.
Toscano12, D. Tosi40, A. Trettin63, C. F. Tung6, R. Turcotte31, J. P.
Twagirayezu24, B. Ty40, M. A. Unland Elorrieta43, A. K. Upadhyay40, 64, K.
Upshaw7, N. Valtonen-Mattila61, J. Vandenbroucke40, N. van Eijndhoven13, D.
Vannerom15, J. van Santen63, J. Vara43, J. Veitch-Michaelis40, M. Venugopal31,
M. Vereecken37, S. Verpoest44, D. Veske46, A. Vijai19, C. Walck54, C.
Weaver24, P. Weigel15, A. Weindl31, J. Weldert60, C. Wendt40, J. Werthebach23,
M. Weyrauch31, N. Whitehorn24, C. H. Wiebusch1, N. Willey24, D. R. Williams58,
L. Witthaus23, A. Wolf1, M. Wolf27, G. Wrede26, X. W. Xu7, J. P. Yanez25, E.
Yildizci40, S. Yoshida16, R. Young36, F. Yu14, S. Yu24, T. Yuan40, Z. Zhang55,
P. Zhelnin14, M. Zimmerman40

1 III. Physikalisches Institut, RWTH Aachen University, D-52056 Aachen,
Germany
2 Department of Physics, University of Adelaide, Adelaide, 5005, Australia
3 Dept. of Physics and Astronomy, University of Alaska Anchorage, 3211
Providence Dr., Anchorage, AK 99508, USA
4 Dept. of Physics, University of Texas at Arlington, 502 Yates St., Science
Hall Rm 108, Box 19059, Arlington, TX 76019, USA
5 CTSPS, Clark-Atlanta University, Atlanta, GA 30314, USA
6 School of Physics and Center for Relativistic Astrophysics, Georgia
Institute of Technology, Atlanta, GA 30332, USA
7 Dept. of Physics, Southern University, Baton Rouge, LA 70813, USA
8 Dept. of Physics, University of California, Berkeley, CA 94720, USA
9 Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA
10 Institut für Physik, Humboldt-Universität zu Berlin, D-12489 Berlin,
Germany
11 Fakultät für Physik & Astronomie, Ruhr-Universität Bochum, D-44780 Bochum,
Germany
12 Université Libre de Bruxelles, Science Faculty CP230, B-1050 Brussels,
Belgium
13 Vrije Universiteit Brussel (VUB), Dienst ELEM, B-1050 Brussels, Belgium
14 Department of Physics and Laboratory for Particle Physics and Cosmology,
Harvard University, Cambridge, MA 02138, USA
15 Dept. of Physics, Massachusetts Institute of Technology, Cambridge, MA
02139, USA
16 Dept. of Physics and The International Center for Hadron Astrophysics,
Chiba University, Chiba 263-8522, Japan
17 Department of Physics, Loyola University Chicago, Chicago, IL 60660, USA
18 Dept. of Physics and Astronomy, University of Canterbury, Private Bag 4800,
Christchurch, New Zealand
19 Dept. of Physics, University of Maryland, College Park, MD 20742, USA
20 Dept. of Astronomy, Ohio State University, Columbus, OH 43210, USA
21 Dept. of Physics and Center for Cosmology and Astro-Particle Physics, Ohio
State University, Columbus, OH 43210, USA
22 Niels Bohr Institute, University of Copenhagen, DK-2100 Copenhagen, Denmark
23 Dept. of Physics, TU Dortmund University, D-44221 Dortmund, Germany
24 Dept. of Physics and Astronomy, Michigan State University, East Lansing, MI
48824, USA
25 Dept. of Physics, University of Alberta, Edmonton, Alberta, Canada T6G 2E1
26 Erlangen Centre for Astroparticle Physics, Friedrich-Alexander-Universität
Erlangen-Nürnberg, D-91058 Erlangen, Germany
27 Technical University of Munich, TUM School of Natural Sciences, Department
of Physics, D-85748 Garching bei München, Germany
28 Département de physique nucléaire et corpusculaire, Université de Genève,
CH-1211 Genève, Switzerland
29 Dept. of Physics and Astronomy, University of Gent, B-9000 Gent, Belgium
30 Dept. of Physics and Astronomy, University of California, Irvine, CA 92697,
USA
31 Karlsruhe Institute of Technology, Institute for Astroparticle Physics,
D-76021 Karlsruhe, Germany
32 Karlsruhe Institute of Technology, Institute of Experimental Particle
Physics, D-76021 Karlsruhe, Germany
33 Dept. of Physics, Engineering Physics, and Astronomy, Queen’s University,
Kingston, ON K7L 3N6, Canada
34 Department of Physics & Astronomy, University of Nevada, Las Vegas, NV,
89154, USA
35 Nevada Center for Astrophysics, University of Nevada, Las Vegas, NV 89154,
USA
36 Dept. of Physics and Astronomy, University of Kansas, Lawrence, KS 66045,
USA
37 Centre for Cosmology, Particle Physics and Phenomenology - CP3, Université
catholique de Louvain, Louvain-la-Neuve, Belgium
38 Department of Physics, Mercer University, Macon, GA 31207-0001, USA
39 Dept. of Astronomy, University of Wisconsin–Madison, Madison, WI 53706, USA
40 Dept. of Physics and Wisconsin IceCube Particle Astrophysics Center,
University of Wisconsin–Madison, Madison, WI 53706, USA
41 Institute of Physics, University of Mainz, Staudinger Weg 7, D-55099 Mainz,
Germany
42 Department of Physics, Marquette University, Milwaukee, WI, 53201, USA
43 Institut für Kernphysik, Westfälische Wilhelms-Universität Münster, D-48149
Münster, Germany
44 Bartol Research Institute and Dept. of Physics and Astronomy, University of
Delaware, Newark, DE 19716, USA
45 Dept. of Physics, Yale University, New Haven, CT 06520, USA
46 Columbia Astrophysics and Nevis Laboratories, Columbia University, New
York, NY 10027, USA
47 Dept. of Physics, University of Oxford, Parks Road, Oxford OX1 3PU, United
Kingdom
48 Dipartimento di Fisica e Astronomia Galileo Galilei, Università Degli Studi
di Padova, 35122 Padova PD, Italy
49 Dept. of Physics, Drexel University, 3141 Chestnut Street, Philadelphia, PA
19104, USA
50 Physics Department, South Dakota School of Mines and Technology, Rapid
City, SD 57701, USA
51 Dept. of Physics, University of Wisconsin, River Falls, WI 54022, USA
52 Dept. of Physics and Astronomy, University of Rochester, Rochester, NY
14627, USA
53 Department of Physics and Astronomy, University of Utah, Salt Lake City, UT
84112, USA
54 Oskar Klein Centre and Dept. of Physics, Stockholm University, SE-10691
Stockholm, Sweden
55 Dept. of Physics and Astronomy, Stony Brook University, Stony Brook, NY
11794-3800, USA
56 Dept. of Physics, Sungkyunkwan University, Suwon 16419, Korea
57 Institute of Physics, Academia Sinica, Taipei, 11529, Taiwan
58 Dept. of Physics and Astronomy, University of Alabama, Tuscaloosa, AL
35487, USA
59 Dept. of Astronomy and Astrophysics, Pennsylvania State University,
University Park, PA 16802, USA
60 Dept. of Physics, Pennsylvania State University, University Park, PA 16802,
USA
61 Dept. of Physics and Astronomy, Uppsala University, Box 516, S-75120
Uppsala, Sweden
62 Dept. of Physics, University of Wuppertal, D-42119 Wuppertal, Germany
63 Deutsches Elektronen-Synchrotron DESY, Platanenallee 6, 15738 Zeuthen,
Germany
64 Institute of Physics, Sachivalaya Marg, Sainik School Post, Bhubaneswar
751005, India
65 Department of Space, Earth and Environment, Chalmers University of
Technology, 412 96 Gothenburg, Sweden
66 Earthquake Research Institute, University of Tokyo, Bunkyo, Tokyo 113-0032,
Japan

### Acknowledgements

The authors gratefully acknowledge the support from the following agencies and
institutions: USA – U.S. National Science Foundation-Office of Polar Programs,
U.S. National Science Foundation-Physics Division, U.S. National Science
Foundation-EPSCoR, Wisconsin Alumni Research Foundation, Center for High
Throughput Computing (CHTC) at the University of Wisconsin–Madison, Open
Science Grid (OSG), Advanced Cyberinfrastructure Coordination Ecosystem:
Services & Support (ACCESS), Frontera computing project at the Texas Advanced
Computing Center, U.S. Department of Energy-National Energy Research
Scientific Computing Center, Particle astrophysics research computing center
at the University of Maryland, Institute for Cyber-Enabled Research at
Michigan State University, and Astroparticle physics computational facility at
Marquette University; Belgium – Funds for Scientific Research (FRS-FNRS and
FWO), FWO Odysseus and Big Science programmes, and Belgian Federal Science
Policy Office (Belspo); Germany – Bundesministerium für Bildung und Forschung
(BMBF), Deutsche Forschungsgemeinschaft (DFG), Helmholtz Alliance for
Astroparticle Physics (HAP), Initiative and Networking Fund of the Helmholtz
Association, Deutsches Elektronen Synchrotron (DESY), and High Performance
Computing cluster of the RWTH Aachen; Sweden – Swedish Research Council,
Swedish Polar Research Secretariat, Swedish National Infrastructure for
Computing (SNIC), and Knut and Alice Wallenberg Foundation; European Union –
EGI Advanced Computing for research; Australia – Australian Research Council;
Canada – Natural Sciences and Engineering Research Council of Canada, Calcul
Québec, Compute Ontario, Canada Foundation for Innovation, WestGrid, and
Compute Canada; Denmark – Villum Fonden, Carlsberg Foundation, and European
Commission; New Zealand – Marsden Fund; Japan – Japan Society for Promotion of
Science (JSPS) and Institute for Global Prominent Research (IGPR) of Chiba
University; Korea – National Research Foundation of Korea (NRF); Switzerland –
Swiss National Science Foundation (SNSF); United Kingdom – Department of
Physics, University of Oxford.