text: There is a well-known and easy way of proving hardness of MIS on graphs with large girth: subdividing edges increases girth and the size of the largest independent set changes in a controlled way. Lemma 5.4. If there is an 2o(n)-time algorithm for MIS on n-vertex graphs of maximum degree 3 and girth more than g for any ﬁxed g > 0, then the ETH fails. Proof. Let g be a ﬁxed constant and let G be a simple graph with n vertices, m edges, and maximum degree O (cid:48) 3 (hence m = (n)). We construct a graph G by subdividing each edge with 2g new vertices. We have that (cid:48) (cid:48) O O G has n = (n + gm) = (n) vertices, maximum degree 3, and girth at least 3(2g + 1) > g. It is known and easy to show that subdividing the edges this way increases the size of the maximum independent set (cid:48) (cid:48) exactly by gm. Thus a 2o(n )- time algorithm for n -vertex graphs of maximum degree 3 and girth at least g could be used to give a 2o(n)-time algorithm for n-vertex graphs of maximum degree 3, hence the ETH would fail by Theorem 5.2. We use the lower bound of Lemma 5.4 to prove lower bounds for Scattered Set on C -free graphs. t Theorem 5.5. Assuming the ETH, d-Scattered Set does not have a 2o(n) algorithm on n-vertex C -free ≥ ≥ t graphs with maximum degree 3 for any ﬁxed t 3 and d 2. Proof. Let G be an n-vertex m-edge graph of maximum degree 3 and girth more than t. We construct a (cid:48) − graph G the following way: we subdivide each edge of G with d 2 new vertices to create a path of length − − − O d 1, and attach a path of length d 1 to each of the (d 2)m = (dn) new vertices created. The resulting O − graph has maximum degree 3, (d2n) vertices and edges, and girth more than (d 1)t (hence it is C -free). We claim that α (G(cid:48)) = α(G) + m(d − 2) holds. This means that an 2o(n(cid:48))-time algorithm for Scatttered Set n(cid:48)-vertex C d-free graphs with maximum degree 3 would give a 2o(n)-time algorithm for n-vertex graphs t of maximum degree 3 and girth more than t and this would violate the ETH by Lemma 5.4. (cid:48) − To see that α (G ) = α(G)+m(d 2) holds, consider ﬁrst an independent set S of G. When constructing (cid:48) d − − (cid:48) − G , we attached m(d 2) paths of length d 1. Let S contain the degree-1 endpoints of these m(d 2) (cid:48) paths, plus the vertices of G corresponding to the vertices of S. It is easy to see that any two vertices of (cid:48) S has distance at least d from each other: S is an independent set in G, hence the corresponding vertices (cid:48) − ≥ in G are at distance at least 2(d 1) d from each other, while the degree-1 endpoints of the paths of − (cid:48) length d 1 are at distance at least d from every other vertex that can potentially be in S . This shows (cid:48) ≥ − (cid:48) (cid:48) α (G ) α(G) + m(d 2). Conversely, let S be a set of vertices in G that are at distance at least d d (cid:48) (cid:48) from each other. The set S contains two types of vertices: let S be the vertices that correspond to the (cid:48) 1 − original vertices of G and let S be the vertices that come from the m(d 2)d new vertices introduced in the (cid:48) 2 (cid:48) − − construction of G . Observe that S can be covered by m(d 2) paths of length d 1 and each such path 2(cid:48) − (cid:48) (cid:48) (cid:48) can contain at most one vertex of S , hence at most m(d 2) vertices of S can be in S . We claim that S (cid:48) ∩ (cid:48) 2 1 can contain at most α(G) vertices, as S S corresponds to an independent set of G. Indeed, if u and v are 1 (cid:48) − adjacent vertices of G, then the corresponding two vertices of G are at distance d 1, hence they cannot (cid:48) (cid:48) ≤ − be both present in S . This shows α (G ) α(G) + m(d 2), completing the proof of the correctness of the d reduction. As the following corollary shows, putting together Theorems 5.3 and 5.5 implies Theorem 1.4(2). Corollary 5.6. If H is a graph having a component that is not a path, then, assuming the ETH, d- ≥ Scattered Set has no 2o(n+m)-time algorithm on n-vertex m-edge H-free graphs for any ﬁxed d 3. ≥ Proof. Suppose ﬁrst that H is not a forest and hence some cycle C for t 3 appears as an induced subgraph t in H. Then the class of H-free graphs is a superset of C -free graphs, which means that statement follows t from Theorem 5.5 (which gives a lower bound for a more restricted class of graphs). Assume therefore that H is a forest. Then it must have a component that is a tree, but not a path, hence it has a vertex v of degree at least 3. The neighbors of v are independent in the forest H, which means that the claw K appears in H as an induced subgraph. Then the class of H-free graphs is a superset of 1,3 claw-free graphs, which means that statement follows from Theorem 5.3 (which gives a lower bound for a more restricted class of graphs). 11 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: There

text: is

text: a

text: well-known

text: and

text: easy

text: way

text: of

text: proving

text: hardness

text: of

text: MIS

text: on

text: graphs

text: with

text: large

text: girth:

text: subdividing

text: edges

text: increases

text: girth

text: and

text: the

text: size

text: of

text: the

text: largest

text: independent

text: set

text: changes

text: in

text: a

text: controlled

text: way.

text: Lemma

text: If

text: there

text: is

text: an

text: algorithm

text: for

text: MIS

text: on

text: n-vertex

text: graphs

text: of

text: maximum

text: degree

text: and

text: girth

text: more

text: than

text: g

text: for

text: any

text: ﬁxed

text: g

text: then

text: the

text: ETH

text: fails.

text: Proof.

text: Let

text: g

text: be

text: a

text: ﬁxed

text: constant

text: and

text: let

text: G

text: be

text: a

text: simple

text: graph

text: with

text: n

text: vertices,

text: m

text: edges,

text: and

text: maximum

text: degree

text: O

text: (hence

text: m

text: (n)).

text: We

text: construct

text: a

text: graph

text: G

text: by

text: subdividing

text: each

text: edge

text: with

text: new

text: vertices.

text: We

text: have

text: that

text: O

text: O

text: G

text: has

text: n

text: (n

text: gm)

text: (n)

text: vertices,

text: maximum

text: degree

text: and

text: girth

text: at

text: least

text: g.

text: It

text: is

text: known

text: and

text: easy

text: to

text: show

text: that

text: subdividing

text: the

text: edges

text: this

text: way

text: increases

text: the

text: size

text: of

text: the

text: maximum

text: independent

text: set

text: exactly

text: by

text: gm.

text: Thus

text: a

text: time

text: algorithm

text: for

text: n

text: -vertex

text: graphs

text: of

text: maximum

text: degree

text: and

text: girth

text: at

text: least

text: g

text: could

text: be

text: used

text: to

text: give

text: a

text: algorithm

text: for

text: n-vertex

text: graphs

text: of

text: maximum

text: degree

text: hence

text: the

text: ETH

text: would

text: fail

text: by

text: Theorem

text: We

text: use

text: the

text: lower

text: bound

text: of

text: Lemma

text: to

text: prove

text: lower

text: bounds

text: for

text: Scattered

text: Set

text: on

text: C

text: -free

text: graphs.

text: t

text: Theorem

text: Assuming

text: the

text: ETH,

text: d-Scattered

text: Set

text: does

text: not

text: have

text: a

text: algorithm

text: on

text: n-vertex

text: C

text: -free

text: t

text: graphs

text: with

text: maximum

text: degree

text: for

text: any

text: ﬁxed

text: t

text: and

text: d

text: Proof.

text: Let

text: G

text: be

text: an

text: n-vertex

text: m-edge

text: graph

text: of

text: maximum

text: degree

text: and

text: girth

text: more

text: than

text: t.

text: We

text: construct

text: a

text: graph

text: G

text: the

text: following

text: way:

text: we

text: subdivide

text: each

text: edge

text: of

text: G

text: with

text: d

text: new

text: vertices

text: to

text: create

text: a

text: path

text: of

text: length

text: O

text: d

text: and

text: attach

text: a

text: path

text: of

text: length

text: d

text: to

text: each

text: of

text: the

text: (d

text: (dn)

text: new

text: vertices

text: created.

text: The

text: resulting

text: O

text: graph

text: has

text: maximum

text: degree

text: vertices

text: and

text: edges,

text: and

text: girth

text: more

text: than

text: (d

text: (hence

text: it

text: is

text: C

text: -free).

text: We

text: claim

text: that

text: α

text: α(G)

text: m(d

text: holds.

text: This

text: means

text: that

text: an

text: algorithm

text: for

text: Scatttered

text: Set

text: C

text: d-free

text: graphs

text: with

text: maximum

text: degree

text: would

text: give

text: a

text: algorithm

text: for

text: n-vertex

text: graphs

text: t

text: of

text: maximum

text: degree

text: and

text: girth

text: more

text: than

text: t

text: and

text: this

text: would

text: violate

text: the

text: ETH

text: by

text: Lemma

text: To

text: see

text: that

text: α

text: (G

text: α(G)+m(d

text: holds,

text: consider

text: ﬁrst

text: an

text: independent

text: set

text: S

text: of

text: G.

text: When

text: constructing

text: d

text: G

text: we

text: attached

text: m(d

text: paths

text: of

text: length

text: d

text: Let

text: S

text: contain

text: the

text: endpoints

text: of

text: these

text: m(d

text: paths,

text: plus

text: the

text: vertices

text: of

text: G

text: corresponding

text: to

text: the

text: vertices

text: of

text: S.

text: It

text: is

text: easy

text: to

text: see

text: that

text: any

text: two

text: vertices

text: of

text: S

text: has

text: distance

text: at

text: least

text: d

text: from

text: each

text: other:

text: S

text: is

text: an

text: independent

text: set

text: in

text: G,

text: hence

text: the

text: corresponding

text: vertices

text: in

text: G

text: are

text: at

text: distance

text: at

text: least

text: d

text: from

text: each

text: other,

text: while

text: the

text: endpoints

text: of

text: the

text: paths

text: of

text: length

text: d

text: are

text: at

text: distance

text: at

text: least

text: d

text: from

text: every

text: other

text: vertex

text: that

text: can

text: potentially

text: be

text: in

text: S

text: This

text: shows

text: α

text: (G

text: α(G)

text: m(d

text: Conversely,

text: let

text: S

text: be

text: a

text: set

text: of

text: vertices

text: in

text: G

text: that

text: are

text: at

text: distance

text: at

text: least

text: d

text: d

text: from

text: each

text: other.

text: The

text: set

text: S

text: contains

text: two

text: types

text: of

text: vertices:

text: let

text: S

text: be

text: the

text: vertices

text: that

text: correspond

text: to

text: the

text: original

text: vertices

text: of

text: G

text: and

text: let

text: S

text: be

text: the

text: vertices

text: that

text: come

text: from

text: the

text: m(d

text: new

text: vertices

text: introduced

text: in

text: the

text: construction

text: of

text: G

text: Observe

text: that

text: S

text: can

text: be

text: covered

text: by

text: m(d

text: paths

text: of

text: length

text: d

text: and

text: each

text: such

text: path

text: can

text: contain

text: at

text: most

text: one

text: vertex

text: of

text: S

text: hence

text: at

text: most

text: m(d

text: vertices

text: of

text: S

text: can

text: be

text: in

text: S

text: We

text: claim

text: that

text: S

text: can

text: contain

text: at

text: most

text: α(G)

text: vertices,

text: as

text: S

text: S

text: corresponds

text: to

text: an

text: independent

text: set

text: of

text: G.

text: Indeed,

text: if

text: u

text: and

text: v

text: are

text: adjacent

text: vertices

text: of

text: G,

text: then

text: the

text: corresponding

text: two

text: vertices

text: of

text: G

text: are

text: at

text: distance

text: d

text: hence

text: they

text: cannot

text: be

text: both

text: present

text: in

text: S

text: This

text: shows

text: α

text: (G

text: α(G)

text: m(d

text: completing

text: the

text: proof

text: of

text: the

text: correctness

text: of

text: the

text: d

text: reduction.

text: As

text: the

text: following

text: corollary

text: shows,

text: putting

text: together

text: Theorems

text: and

text: implies

text: Theorem

text: Corollary

text: If

text: H

text: is

text: a

text: graph

text: having

text: a

text: component

text: that

text: is

text: not

text: a

text: path,

text: then,

text: assuming

text: the

text: ETH,

text: d-

text: Scattered

text: Set

text: has

text: no

text: algorithm

text: on

text: n-vertex

text: m-edge

text: H-free

text: graphs

text: for

text: any

text: ﬁxed

text: d

text: Proof.

text: Suppose

text: ﬁrst

text: that

text: H

text: is

text: not

text: a

text: forest

text: and

text: hence

text: some

text: cycle

text: C

text: for

text: t

text: appears

text: as

text: an

text: induced

text: subgraph

text: t

text: in

text: H.

text: Then

text: the

text: class

text: of

text: H-free

text: graphs

text: is

text: a

text: superset

text: of

text: C

text: -free

text: graphs,

text: which

text: means

text: that

text: statement

text: follows

text: t

text: from

text: Theorem

text: (which

text: gives

text: a

text: lower

text: bound

text: for

text: a

text: more

text: restricted

text: class

text: of

text: graphs).

text: Assume

text: therefore

text: that

text: H

text: is

text: a

text: forest.

text: Then

text: it

text: must

text: have

text: a

text: component

text: that

text: is

text: a

text: tree,

text: but

text: not

text: a

text: path,

text: hence

text: it

text: has

text: a

text: vertex

text: v

text: of

text: degree

text: at

text: least

text: The

text: neighbors

text: of

text: v

text: are

text: independent

text: in

text: the

text: forest

text: H,

text: which

text: means

text: that

text: the

text: claw

text: K

text: appears

text: in

text: H

text: as

text: an

text: induced

text: subgraph.

text: Then

text: the

text: class

text: of

text: H-free

text: graphs

text: is

text: a

text: superset

text: of

text: claw-free

text: graphs,

text: which

text: means

text: that

text: statement

text: follows

text: from

text: Theorem

text: (which

text: gives

text: a

text: lower

text: bound

text: for

text: a

text: more

text: restricted

text: class

text: of

text: graphs).

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Proof. In what follows, a connected component C of an induced subgraph H of G is big if w(C) > w(V (G))/2. Note that there can be at most one big connected component in any induced subgraph of G. − { } { } { } If G v does not contain a big component, we can set X = v . Otherwise, let A = v and B 0 − 0 − 0 0 0 be the big component of G A . As G is connected, every component of G A is adjacent to A , thus ∈ 0 0 0 v N(B ) holds. We will inductively deﬁne vertices v , v , v , . . . such that v , v , v , . . . induce a path in 0 0 1 2 3 0 1 2 G. Given vertices v , v , v , . . . , v , we deﬁne sets A and B as follows. We set A = N [v , v , . . . , v ]. − 0 1 2 i i+1 i+1 i+1 G 0 1 i If G A does not contain a big connected component, we stop the construction. Otherwise, we set B i+1 − i+1 to be the big connected component of G A . During the process we maintain the invariant that B is − ∈ i+1 i the big component of G A and that v N(B ). Note that this is true for i = 0 by the choice of A and i i i 0 B . 0 It remains to show how to choose v , given vertices v , v , . . . , v and sets A and B . Note ∪ ∈ i+1 0 1 i i+1 \i+1 that A = A N [v ] and v N(B ), so B is the big connected component of G[(B N (v ))]. i+1 i G i i ∈i ∩ i+1 ∩ i G i Consequently, we can choose some v B N (B ) N (v ) that satisﬁes all the desired properties. i+1 i G i+1 G i Since G does not contain an induced P with one endpoint in v , the aforementioned process stops after − t − 0 deﬁning a set A for some i < t 1, when G A does not contain a big component. Observe that i+1 i+1 | | ≤ · ≤ − A (∆ + 1) + i ∆ = (i + 1)∆ + 1 (t 1)∆ + 1. i+1 Consequently, the set X := A satisﬁes the desired properties. i+1 For the algorithmic claim, note that the entire proof can be made algorithmic in a straightforward manner. It is well known that if graph G has a set X of size k for every weight function w : V (G) → Z≥ such − ≤ O 0 that every connected component C of G X satisﬁes w(C) w(V (G))/2, then G has treewidth (w) (see, O e.g., [12, Theorem 11.17(2)]). Thus Lemma 3.1 implies a treewidth bound of (t∆). Algorithmically, it is O also a standard consequence of Lemma 3.1 that a tree decomposition of width (t∆) can be obtained in polynomial time. What needs to be observed is that standard 4-approximation algorithms for treewidth, which run in time exponential in treewidth, can be made to run in polynomial time if we are given a polynomial-time subroutine for ﬁnding the separator X as in Lemma 3.1. For completeness, we sketch the proof here. O Corollary 3.2. A P -free graph with maximum degree ∆ has treewidth (t∆). Furthermore, a tree decom- t position of this width can be computed in polynomial time. Proof. We follow standard constant approximation algorithm for treewidth, as described in [10, Section 7.6]. This algorithm, given a graph G and an integer k, either correctly concludes that tw(G) > k or computes a tree decomposition of G of width at most 4k + 4. Let G be a P -free graph with maximum degree at most ∆. We may assume that G is connected, t − otherwise we can handle the connected components separately. Let us start by setting k := (t 1)∆ so that any application of Lemma 3.1 gives a set of size at most k + 1. The only step of the algorithm that runs in exponential time is the following. We are given an induced ⊆ subgraph G[W] of G and a set S W with the following properties: | | ≤ \ (cid:54) ∅ 1. S 3k + 4 and W S = ; \ 2. both G[W] and G[W S] are connected; 3. S = N (W \ S). (cid:98) (cid:98) (cid:98) G (cid:98) The goal is to compute a(cid:98) set S (cid:40) S ⊆ W such that |S| ≤ 4k +5 an(cid:98)d every connected component of G[W \S] is adjacent to at most 3k + 4 vertices of S. | | ∪{ } ∈ \ The construction of S is trivial for S < 3k+4, as we can take S = S v for an arbitrary v W S. The crucial step happens for sets S of size exactly 3k+4. Instead of the exponential search of [10, Section 7.6], we 6 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Proof.

label: paragraph

text: In

text: what

text: follows,

text: a

text: connected

text: component

text: C

text: of

text: an

text: induced

text: subgraph

text: H

text: of

text: G

text: is

text: big

text: if

text: w(C)

text: w(V

text: Note

text: that

text: there

text: can

text: be

text: at

text: most

text: one

text: big

text: connected

text: component

text: in

text: any

text: induced

text: subgraph

text: of

text: G.

text: If

text: G

text: v

text: does

text: not

text: contain

text: a

text: big

text: component,

text: we

text: can

text: set

text: X

text: v

text: Otherwise,

text: let

text: A

text: v

text: and

text: B

text: be

text: the

text: big

text: component

text: of

text: G

text: A

text: As

text: G

text: is

text: connected,

text: every

text: component

text: of

text: G

text: A

text: is

text: adjacent

text: to

text: A

text: thus

text: v

text: N(B

text: holds.

text: We

text: will

text: inductively

text: deﬁne

text: vertices

text: v

text: v

text: v

text: such

text: that

text: v

text: v

text: v

text: induce

text: a

text: path

text: in

text: G.

text: Given

text: vertices

text: v

text: v

text: v

text: v

text: we

text: deﬁne

text: sets

text: A

text: and

text: B

text: as

text: follows.

text: We

text: set

text: A

text: N

text: [v

text: v

text: v

text: i

text: G

text: i

text: If

text: G

text: A

text: does

text: not

text: contain

text: a

text: big

text: connected

text: component,

text: we

text: stop

text: the

text: construction.

text: Otherwise,

text: we

text: set

text: B

text: to

text: be

text: the

text: big

text: connected

text: component

text: of

text: G

text: A

text: During

text: the

text: process

text: we

text: maintain

text: the

text: invariant

text: that

text: B

text: is

text: i

text: the

text: big

text: component

text: of

text: G

text: A

text: and

text: that

text: v

text: N(B

text: Note

text: that

text: this

text: is

text: true

text: for

text: i

text: by

text: the

text: choice

text: of

text: A

text: and

text: i

text: i

text: i

text: B

text: It

text: remains

text: to

text: show

text: how

text: to

text: choose

text: v

text: given

text: vertices

text: v

text: v

text: v

text: and

text: sets

text: A

text: and

text: B

text: Note

text: i

text: that

text: A

text: A

text: N

text: [v

text: and

text: v

text: N(B

text: so

text: B

text: is

text: the

text: big

text: connected

text: component

text: of

text: G[(B

text: N

text: (v

text: i

text: G

text: i

text: i

text: ∈i

text: i

text: G

text: i

text: Consequently,

text: we

text: can

text: choose

text: some

text: v

text: B

text: N

text: (B

text: N

text: (v

text: that

text: satisﬁes

text: all

text: the

text: desired

text: properties.

text: i

text: G

text: G

text: i

text: Since

text: G

text: does

text: not

text: contain

text: an

text: induced

text: P

text: with

text: one

text: endpoint

text: in

text: v

text: the

text: aforementioned

text: process

text: stops

text: after

text: t

text: deﬁning

text: a

text: set

text: A

text: for

text: some

text: i

text: t

text: when

text: G

text: A

text: does

text: not

text: contain

text: a

text: big

text: component.

text: Observe

text: that

text: A

text: i

text: (i

text: (t

text: Consequently,

text: the

text: set

text: X

text: A

text: satisﬁes

text: the

text: desired

text: properties.

text: For

text: the

text: algorithmic

text: claim,

text: note

text: that

text: the

text: entire

text: proof

text: can

text: be

text: made

text: algorithmic

text: in

text: a

text: straightforward

text: manner.

text: It

text: is

text: well

text: known

text: that

text: if

text: graph

text: G

text: has

text: a

text: set

text: X

text: of

text: size

text: k

text: for

text: every

text: weight

text: function

text: w

text: V

text: (G)

text: Z≥

text: such

text: O

text: that

text: every

text: connected

text: component

text: C

text: of

text: G

text: X

text: satisﬁes

text: w(C)

text: w(V

text: then

text: G

text: has

text: treewidth

text: (w)

text: (see,

text: O

text: e.g.,

text: Theorem

text: Thus

text: Lemma

text: implies

text: a

text: treewidth

text: bound

text: of

text: (t∆).

text: Algorithmically,

text: it

text: is

text: O

text: also

text: a

text: standard

text: consequence

text: of

text: Lemma

text: that

text: a

text: tree

text: decomposition

text: of

text: width

text: (t∆)

text: can

text: be

text: obtained

text: in

text: polynomial

text: time.

text: What

text: needs

text: to

text: be

text: observed

text: is

text: that

text: standard

text: algorithms

text: for

text: treewidth,

text: which

text: run

text: in

text: time

text: exponential

text: in

text: treewidth,

text: can

text: be

text: made

text: to

text: run

text: in

text: polynomial

text: time

text: if

text: we

text: are

text: given

text: a

text: polynomial-time

text: subroutine

text: for

text: ﬁnding

text: the

text: separator

text: X

text: as

text: in

text: Lemma

text: For

text: completeness,

text: we

text: sketch

text: the

text: proof

text: here.

text: O

text: Corollary

text: A

text: P

text: -free

text: graph

text: with

text: maximum

text: degree

text: has

text: treewidth

text: (t∆).

text: Furthermore,

text: a

text: tree

text: decom-

text: t

text: position

text: of

text: this

text: width

text: can

text: be

text: computed

text: in

text: polynomial

text: time.

text: Proof.

text: We

text: follow

text: standard

text: constant

text: approximation

text: algorithm

text: for

text: treewidth,

text: as

text: described

text: in

text: Section

text: This

text: algorithm,

text: given

text: a

text: graph

text: G

text: and

text: an

text: integer

text: k,

text: either

text: correctly

text: concludes

text: that

text: tw(G)

text: k

text: or

text: computes

text: a

text: tree

text: decomposition

text: of

text: G

text: of

text: width

text: at

text: most

text: Let

text: G

text: be

text: a

text: P

text: -free

text: graph

text: with

text: maximum

text: degree

text: at

text: most

text: We

text: may

text: assume

text: that

text: G

text: is

text: connected,

text: t

text: otherwise

text: we

text: can

text: handle

text: the

text: connected

text: components

text: separately.

text: Let

text: us

text: start

text: by

text: setting

text: k

text: (t

text: so

text: that

text: any

text: application

text: of

text: Lemma

text: gives

text: a

text: set

text: of

text: size

text: at

text: most

text: k

text: The

text: only

text: step

text: of

text: the

text: algorithm

text: that

text: runs

text: in

text: exponential

text: time

text: is

text: the

text: following.

text: We

text: are

text: given

text: an

text: induced

text: subgraph

text: G[W]

text: of

text: G

text: and

text: a

text: set

text: S

text: W

text: with

text: the

text: following

text: properties:

text: S

text: and

text: W

text: S

text: both

text: G[W]

text: and

text: G[W

text: S]

text: are

text: connected;

text: S

text: N

text: (W

text: S).

text: G

text: The

text: goal

text: is

text: to

text: compute

text: set

text: S

text: S

text: W

text: such

text: that

text: |S|

text: every

text: connected

text: component

text: of

text: G[W

text: \S]

text: is

text: adjacent

text: to

text: at

text: most

text: vertices

text: of

text: S.

text: The

text: construction

text: of

text: S

text: is

text: trivial

text: for

text: S

text: as

text: we

text: can

text: take

text: S

text: S

text: v

text: for

text: an

text: arbitrary

text: v

text: W

text: S.

text: The

text: crucial

text: step

text: happens

text: for

text: sets

text: S

text: of

text: size

text: exactly

text: Instead

text: of

text: the

text: exponential

text: search

text: of

text: Section

text: we

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 5 C FIG. 2: vs κ. Numerical values from the diagonalization of the 1BDM of hard–core anyons (red dots) and bosonization result (dashed line): excellent agreement is found. ∈ − [45] with t = 2πx/L [0, 2π], j, l run from(cid:90) 1 to N 1 and (cid:18) (cid:19) (cid:16) (cid:17) 2π − 2 − − τ t τ φκ = dτ ei(j l)τA(τ t) sin sin , j,l π 2 2 0 − − − with A(τ t) = eiπ(1 κ) for τ < t and A(τ t) = 1 for τ > t. Proceeding as done before for the LL bosons, we have computed the largest eigenvalue λ of the 1BDM for diﬀerent values of the statistical parameter κ and number 0 C of particles N, with N up to N = 241. The results for are plotted in Fig.2. For κ = 0 (hard-core bosons) one has C C = 1/2, while for κ = 1 (fermions) one has = 0, and for all other values the curve monotonically interpolates as expected between 1/2 and 0 when κ increases. VI. LIEB–LINIGER ANYONS The behaviour shown in Fig.2 refers to hard-core anyons. For a ﬁnite, soft-core energy coupling γ [46] one has the C possibility to fully interpolate between = 0 and 1: when κ = 0, then the LL Bose gas at the coupling constant γ C is retrieved. To study how depends on γ and κ, we resort to the bosonization approach, in light of its successful C estimates of both for the LL Bose gas and for hard-core anyons given above. For LL anyons, ρ(x) at large distances is given by [47] (cid:88) ∞ − e2i(m+κ2 )kFxe πi(m+κ2 )sgn(x) ρ(x) = n b , (8) m=−∞ m [nL sin(πx/L)](m+κ2 )22K+21K where b are non–universal amplitudes. F(cid:88)rom (8) one gets for small k and in the thermodynamic limit m (cid:2) (cid:0) (cid:1)(cid:3) ∝ ∞ (nπ)−21K −(m+κ2 )22K n(k) n b . (9) m=−∞ m k + 2kF m + κ2 1−21K −2K(m+κ2 )2 As a general consequence of this expression, the momentum distribution in general does not have the maximum at k = 0: there is in fact rather a shift due to the imaginary terms of the 1BDM [47]. The leading term of n(k) is the − one relative to m = 0 for any κ (for κ = 1, also the term m = 1 has the same power law behaviour). Hence, we conclude λ0 ∝ N1−21K −K2κ2 , and therefore the scaling coeﬃcient C for the LL–anyons is expressed by C − 1 − Kκ2 (κ, γ) = 1 . (10) 2K 2 C For κ = 0 we obtain the result (6) for the LL, while for κ = 1 (the fermionic limit) one gets = 0 since K = 1 for all C (cid:48) C γ, in both cases the correct values. In Fig.3 we plot vs γ for diﬀerent κ: it is evident that is always less than one, ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: C

label: caption

text: FIG.

text: vs

text: κ.

text: Numerical

text: values

text: from

text: the

text: diagonalization

text: of

text: the

text: of

text: hard–core

text: anyons

text: (red

text: dots)

text: and

text: bosonization

text: result

text: (dashed

text: line):

text: excellent

text: agreement

text: is

text: found.

text: with

text: t

text: j,

text: l

text: run

text: to

text: N

text: and

text: 2π

text: τ

text: t

text: τ

text: φκ

text: dτ

text: ei(j

text: l)τA(τ

text: t)

text: sin

text: sin

text: j,l

text: π

text: with

text: A(τ

text: t)

text: κ)

text: for

text: τ

text: t

text: and

text: A(τ

text: t)

text: for

text: τ

text: t.

text: Proceeding

text: as

text: done

text: before

text: for

text: the

text: LL

text: bosons,

text: we

text: have

text: computed

text: the

text: largest

text: eigenvalue

text: λ

text: of

text: the

text: for

text: diﬀerent

text: values

text: of

text: the

text: statistical

text: parameter

text: κ

text: and

text: number

text: C

text: of

text: particles

text: N,

text: with

text: N

text: up

text: to

text: N

text: The

text: results

text: for

text: are

text: plotted

text: in

text: For

text: κ

text: (hard-core

text: bosons)

text: one

text: has

text: C

text: C

text: while

text: for

text: κ

text: (fermions)

text: one

text: has

text: and

text: for

text: all

text: other

text: values

text: the

text: curve

text: monotonically

text: interpolates

text: as

text: expected

text: between

text: and

text: when

text: κ

text: increases.

text: VI.

text: LIEB–LINIGER

text: ANYONS

text: The

text: behaviour

text: shown

text: in

text: refers

text: to

text: hard-core

text: anyons.

text: For

text: a

text: ﬁnite,

text: soft-core

text: energy

text: coupling

text: γ

text: one

text: has

text: the

text: C

text: possibility

text: to

text: fully

text: interpolate

text: between

text: and

text: when

text: κ

text: then

text: the

text: LL

text: Bose

text: gas

text: at

text: the

text: coupling

text: constant

text: γ

text: C

text: is

text: retrieved.

text: To

text: study

text: how

text: depends

text: on

text: γ

text: and

text: κ,

text: we

text: resort

text: to

text: the

text: bosonization

text: approach,

text: in

text: light

text: of

text: its

text: successful

text: C

text: estimates

text: of

text: both

text: for

text: the

text: LL

text: Bose

text: gas

text: and

text: for

text: hard-core

text: anyons

text: given

text: above.

text: For

text: LL

text: anyons,

text: ρ(x)

text: at

text: large

text: distances

text: is

text: given

text: by

text: )kFxe

text: )sgn(x)

text: ρ(x)

text: n

text: b

text: m=−∞

text: m

text: [nL

text: where

text: b

text: are

text: non–universal

text: amplitudes.

text: one

text: gets

text: for

text: small

text: k

text: and

text: in

text: the

text: thermodynamic

text: limit

text: m

text: n(k)

text: n

text: b

text: m=−∞

text: m

text: k

text: m

text: κ2

text: As

text: a

text: general

text: consequence

text: of

text: this

text: expression,

text: the

text: momentum

text: distribution

text: in

text: general

text: does

text: not

text: have

text: the

text: maximum

text: at

text: k

text: there

text: is

text: in

text: fact

text: rather

text: a

text: shift

text: due

text: to

text: the

text: imaginary

text: terms

text: of

text: the

text: The

text: leading

text: term

text: of

text: n(k)

text: is

text: the

text: one

text: relative

text: to

text: m

text: for

text: any

text: κ

text: (for

text: κ

text: also

text: the

text: term

text: m

text: has

text: the

text: same

text: power

text: law

text: behaviour).

text: Hence,

text: we

text: conclude

text: λ0

text: and

text: therefore

text: the

text: scaling

text: coeﬃcient

text: C

text: for

text: the

text: LL–anyons

text: is

text: expressed

text: by

text: C

text: (κ,

text: γ)

text: C

text: For

text: κ

text: we

text: obtain

text: the

text: result

text: for

text: the

text: LL,

text: while

text: for

text: κ

text: (the

text: fermionic

text: limit)

text: one

text: gets

text: since

text: K

text: for

text: all

text: C

text: C

text: γ,

text: in

text: both

text: cases

text: the

text: correct

text: values.

text: In

text: we

text: plot

text: vs

text: γ

text: for

text: diﬀerent

text: κ:

text: it

text: is

text: evident

text: that

text: is

text: always

text: less

text: than

text: one,

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 8 [5] M.H. Anderson, J.R. Ensher, M.R. Matthews, C.E. Wieman and E.A. Cornell, Science 269, 198 (1995). [6] G. Mussardo, Statistical ﬁeld theory: an introduction to exactly solved models in statistical physics (Oxford, Oxford Uni- versity Press, 2010). [7] T. Giamarchi, Quantum Physics in One Dimension (Oxford, Oxford University Press, 2003). [8] M.A. Cazalilla, R. Citro, T. Giamarchi, E. Orignac and M. Rigol, Rev. Mod. Phys. 83, 1405 (2011). [9] F.D.M. Haldane, Phys. Rev. Lett. 47, 1840 (1981). [10] U. Schollwo¨ck, Rev. Mod. Phys. 77, 259 (2005). [11] V.E. Korepin, N.M. Bogoliubov and A.G. Izergin, Quantum inverse scattering method and correlation functions (Cam- bridge, Cambridge University Press, 1993). [12] F. Franchini, An Introduction to Integrable Techniques for One–Dimensional Quantum Systems (Cham, Springer, 2017). [13] A. Kundu, Phys. Rev. Lett. 83, 1275 (1999). [14] M. T. Batchelor, X. W. Guan and N. Oelkers, Phys. Rev. Lett. 96, 210402 (2006). [15] V.A. Yurovsky, M. Olshanii and D.S. Weiss, Adv. At. Mol. Opt. Phys. 55, 61 (2008). [16] M. Olshanii, Phys. Rev. Lett. 81, 938 (1998). [17] M. Girardeau, J. Math. Phys. 1, 516 (1960). [18] I. Bouchoule, N. J. van Druten, and C. I. Westbrook, arXiv:0901.3303| [19] E.H. Lieb and W. Liniger, Phys. Rev. 130, 1605 (1963). [20] C.N. Yang and C.P. Yang, J. Math. Phys. 10, 1115 (1969). [21] M. Gaudin, The Bethe Wavefunction (Cambridge, Cambridge University Press, 2014). [22] F. Mancarella, G. Mussardo and A. Trombettoni, Nucl. Phys. B 887, 216 (2014). [23] M.A. Cazalilla, R. Citro, T. Giamarchi, E. Orignac and M. Rigol, Nucl. Phys. B 83, 1405 (2011). [24] G. Lang, F. Hekking and A. Minguzzi, SciPost Phys. 3, 003 (2017). ∝ − (cid:126) (cid:126) [25] Since K = vF/s, one has n(k) kα 1 with α = ms/2π n, that, once in the units = 1, m = 1/2 as used in [28], coincides with Eq.(48) presented there [28]. Notice also tha putting time t to zero in Eq.(2.6) of Chapter XVIII in [11], one gets as well agreement with the results presented in [11]. [26] J.-S. Caux and P. Calabrese, Phys. Rev. A 74, 031605 (2006). [27] M. Panfil and J.-S. Caux, Phys. Rev. A 89, 033605 (2014). [28] J.-S. Caux, P. Calabrese and N.A. Slavnov, J. Stat. Mech. P01008 (2007). [29] M. Olshanii and V. Dunjko, Phys. Rev. Lett 91, 090401 (2003). [30] A.Shashi, L.I. Glazman, J.-S. Caux and A. Imambekov, Phys. Rev. B 84, 045408 (2011). [31] A. Shashi, M. Panfil, J.-S. Caux and A. Imambekov, Phys. Rev. B 85, 155136 (2012). [32] M. Jimbo and T. Miwa, Phys. Rev. D 24, 3169 (1981). [33] C. Mora and Y. Castin, Phys. Rev. A 67, 053615 (2003). [34] D.M. Gangardt and G.V.Shlyapnikov, New J. Phys. 5, 79 (2003). [35] P.J. Forrester, N.E. Frankel and M.I. Makin, Phys. Rev. A 74, 043614 (2006). [36] A. Imambekov, I.E. Mazets, D.S. Petrov, V. Gritsev, S. Manz, S. Hofferberth, T. Schumm, E. Demler and J. Schmiedmayer, Phys. Rev. A 80, 033604 (2009). [37] We checked up to N = 100 that doing the Fourier transform or diagonalizing the 1BDM one gets indeed the same results within the numerical precision. [38] A. Lenard, J. Math. Phys. 5, 930 (1964). [39] P.J. Forrester, N.E. Frankel, T.M. Garoni and N.S. Witte, Phys. Rev. A 67, 043607 (2003). [40] Y. Hao, Y. Zhang and S. Chen, Phys. Rev. A 78, 023631 (2008). [41] O.I. Patu, V.E. Korepin and D.V. Averin, J. Phys. A 40, 14963 (2007). [42] M.T. Batchelor, X.W. Guan and J.D. He, J. Stat. Mech. P03007 (2007). [43] G. Marmorini, M. Pepe and P. Calabrese, J. Stat. Mech. 073106 (2006). [44] Y. Hao, Phys. Rev. A 93, 063627 (2016). [45] R. Santachiara and P. Calabrese, J. Stat. Mech. P06005 (2008). [46] P. Calabrese and R. Santachiara, J. Stat. Mech. P03002 (2009). [47] P. Calabrese and M. Mintchev, Phys. Rev. B 75, 233104 (2007). [48] Bose-Einstein Condensation, A. Griffin, D.W. Snoke and S. Stringari eds. (Cambridge, Cambridge University Press, 1995).

label: reference

text: M.H.

text: Anderson,

text: J.R.

text: Ensher,

text: M.R.

text: Matthews,

text: C.E.

text: Wieman

text: and

text: E.A.

text: Cornell,

text: Science

text: G.

text: Mussardo,

text: Statistical

text: ﬁeld

text: theory:

text: an

text: introduction

text: to

text: exactly

text: solved

text: models

text: in

text: statistical

text: physics

text: (Oxford,

text: Oxford

text: Uni-

text: versity

text: Press,

text: T.

text: Giamarchi,

text: Quantum

text: Physics

text: in

text: One

text: Dimension

text: (Oxford,

text: Oxford

text: University

text: Press,

text: M.A.

text: Cazalilla,

text: R.

text: Citro,

text: T.

text: Giamarchi,

text: E.

text: Orignac

text: and

text: M.

text: Rigol,

text: Rev.

text: Mod.

text: Phys.

text: F.D.M.

text: Haldane,

text: Phys.

text: Rev.

text: Lett.

text: U.

text: Schollwo¨ck,

text: Rev.

text: Mod.

text: Phys.

text: V.E.

text: Korepin,

text: N.M.

text: Bogoliubov

text: and

text: A.G.

text: Izergin,

text: Quantum

text: inverse

text: scattering

text: method

text: and

text: correlation

text: functions

text: (Cam-

text: bridge,

text: Cambridge

text: University

text: Press,

text: F.

text: Franchini,

text: An

text: Introduction

text: to

text: Integrable

text: Techniques

text: for

text: One–Dimensional

text: Quantum

text: Systems

text: (Cham,

text: Springer,

text: A.

text: Kundu,

text: Phys.

text: Rev.

text: Lett.

text: M.

text: T.

text: Batchelor,

text: X.

text: W.

text: Guan

text: and

text: N.

text: Oelkers,

text: Phys.

text: Rev.

text: Lett.

text: V.A.

text: Yurovsky,

text: M.

text: Olshanii

text: and

text: D.S.

text: Weiss,

text: Adv.

text: At.

text: Mol.

text: Opt.

text: Phys.

text: M.

text: Olshanii,

text: Phys.

text: Rev.

text: Lett.

text: M.

text: Girardeau,

text: J.

text: Math.

text: Phys.

text: I.

text: Bouchoule,

text: N.

text: J.

text: van

text: Druten,

text: and

text: C.

text: I.

text: Westbrook,

text: E.H.

text: Lieb

text: and

text: W.

text: Liniger,

text: Phys.

text: Rev.

text: C.N.

text: Yang

text: and

text: C.P.

text: Yang,

text: J.

text: Math.

text: Phys.

text: M.

text: Gaudin,

text: The

text: Bethe

text: Wavefunction

text: (Cambridge,

text: Cambridge

text: University

text: Press,

text: F.

text: Mancarella,

text: G.

text: Mussardo

text: and

text: A.

text: Trombettoni,

text: Nucl.

text: Phys.

text: B

text: M.A.

text: Cazalilla,

text: R.

text: Citro,

text: T.

text: Giamarchi,

text: E.

text: Orignac

text: and

text: M.

text: Rigol,

text: Nucl.

text: Phys.

text: B

text: G.

text: Lang,

text: F.

text: Hekking

text: and

text: A.

text: Minguzzi,

text: SciPost

text: Phys.

text: Since

text: K

text: vF/s,

text: one

text: has

text: n(k)

text: kα

text: with

text: α

text: n,

text: that,

text: once

text: in

text: the

text: units

text: m

text: as

text: used

text: in

text: coincides

text: with

text: presented

text: there

text: Notice

text: also

text: tha

text: putting

text: time

text: t

text: to

text: zero

text: in

text: of

text: Chapter

text: XVIII

text: in

text: one

text: gets

text: as

text: well

text: agreement

text: with

text: the

text: results

text: presented

text: in

text: J.-S.

text: Caux

text: and

text: P.

text: Calabrese,

text: Phys.

text: Rev.

text: A

text: M.

text: Panfil

text: and

text: J.-S.

text: Caux,

text: Phys.

text: Rev.

text: A

text: J.-S.

text: Caux,

text: P.

text: Calabrese

text: and

text: N.A.

text: Slavnov,

text: J.

text: Stat.

text: Mech.

text: M.

text: Olshanii

text: and

text: V.

text: Dunjko,

text: Phys.

text: Rev.

text: Lett

text: A.Shashi,

text: L.I.

text: Glazman,

text: J.-S.

text: Caux

text: and

text: A.

text: Imambekov,

text: Phys.

text: Rev.

text: B

text: A.

text: Shashi,

text: M.

text: Panfil,

text: J.-S.

text: Caux

text: and

text: A.

text: Imambekov,

text: Phys.

text: Rev.

text: B

text: M.

text: Jimbo

text: and

text: T.

text: Miwa,

text: Phys.

text: Rev.

text: D

text: C.

text: Mora

text: and

text: Y.

text: Castin,

text: Phys.

text: Rev.

text: A

text: D.M.

text: Gangardt

text: and

text: G.V.Shlyapnikov,

text: New

text: J.

text: Phys.

text: P.J.

text: Forrester,

text: N.E.

text: Frankel

text: and

text: M.I.

text: Makin,

text: Phys.

text: Rev.

text: A

text: A.

text: Imambekov,

text: I.E.

text: Mazets,

text: D.S.

text: Petrov,

text: V.

text: Gritsev,

text: S.

text: Manz,

text: S.

text: Hofferberth,

text: T.

text: Schumm,

text: E.

text: Demler

text: and

text: J.

text: Schmiedmayer,

text: Phys.

text: Rev.

text: A

text: We

text: checked

text: up

text: to

text: N

text: that

text: doing

text: the

text: Fourier

text: transform

text: or

text: diagonalizing

text: the

text: one

text: gets

text: indeed

text: the

text: same

text: results

text: within

text: the

text: numerical

text: precision.

text: A.

text: Lenard,

text: J.

text: Math.

text: Phys.

text: P.J.

text: Forrester,

text: N.E.

text: Frankel,

text: T.M.

text: Garoni

text: and

text: N.S.

text: Witte,

text: Phys.

text: Rev.

text: A

text: Y.

text: Hao,

text: Y.

text: Zhang

text: and

text: S.

text: Chen,

text: Phys.

text: Rev.

text: A

text: O.I.

text: Patu,

text: V.E.

text: Korepin

text: and

text: D.V.

text: Averin,

text: J.

text: Phys.

text: A

text: M.T.

text: Batchelor,

text: X.W.

text: Guan

text: and

text: J.D.

text: He,

text: J.

text: Stat.

text: Mech.

text: G.

text: Marmorini,

text: M.

text: Pepe

text: and

text: P.

text: Calabrese,

text: J.

text: Stat.

text: Mech.

text: Y.

text: Hao,

text: Phys.

text: Rev.

text: A

text: R.

text: Santachiara

text: and

text: P.

text: Calabrese,

text: J.

text: Stat.

text: Mech.

text: P.

text: Calabrese

text: and

text: R.

text: Santachiara,

text: J.

text: Stat.

text: Mech.

text: P.

text: Calabrese

text: and

text: M.

text: Mintchev,

text: Phys.

text: Rev.

text: B

text: Bose-Einstein

text: Condensation,

text: A.

text: Griffin,

text: D.W.

text: Snoke

text: and

text: S.

text: Stringari

text: eds.

text: (Cambridge,

text: Cambridge

text: University

text: Press,


text: Figure 3: (top) CHAMP assimilated ROM densities on day 320 for year 2009. Magenta: prediction with ROM after 12 hours of data assimilation. (bottom) KF estimated and ROM predicted densities with KF estimated 1σ uncertainties along CHAMP orbit. temporal coverage of measurements. Figure 9 shows the comparison of MSIS proﬁles against the ROM assimilated proﬁles at a series of altitudes. As seen, except for the proﬁle at 100 km, the MSIS and assimilated ROM proﬁles show similar distributions. The diﬀerence at 100 km is due to the lower boundary eﬀects. The absolute scale of the assimilated densities suggests that MSIS overpredicts the mass density across all altitudes during periods of low solar activity. While this is not a new revelation, the new framework eﬀectively calibrates existing physical models by adjusting the absolute scale, which is a major driver of orbit prediction errors. 8 Conclusions This paper has demonstrated a new, transformative framework for data assimilation and calibration of physical ionosphere-thermosphere models. A robust yet simple and eﬀective approach for data assimilation has thus far eluded the community. The new framework has two major components: (i) Model order reduction for a quasi-physical linear representation of the dynamics, and (ii) data assimilation calibration of the reduced order model (ROM) using a Kalman Filter. Development of a ROM was discussed in a previous paper. This paper demonstrates the second component. The new framework combines the best of both empirical and physical models. The ROM reduces the cost of model evaluation to the level of empirical models while inherently providing forecast/predictive capabilities. Unlike large scale physical models, the ROM formulation allows rapid modiﬁcations in the time-step of model evaluation or simulation with a negligible increase in the computational cost. This allows the model to be easily projected to the time of next measurement. The ROM formulation also allows large ensemble runs of 11 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

text: Figure

text: (top)

text: CHAMP

text: assimilated

text: ROM

text: densities

text: on

text: day

text: for

text: year

text: Magenta:

text: prediction

text: with

text: ROM

text: after

text: hours

text: of

text: data

text: assimilation.

text: (bottom)

text: KF

text: estimated

text: and

text: ROM

text: predicted

text: densities

text: with

text: KF

text: estimated

text: 1σ

text: uncertainties

text: along

text: CHAMP

text: orbit.

text: temporal

text: coverage

text: of

text: measurements.

text: Figure

text: shows

text: the

text: comparison

text: of

text: MSIS

text: proﬁles

text: against

text: the

text: ROM

text: assimilated

text: proﬁles

text: at

text: a

text: series

text: of

text: altitudes.

text: As

text: seen,

text: except

text: for

text: the

text: proﬁle

text: at

text: km,

text: the

text: MSIS

text: and

text: assimilated

text: ROM

text: proﬁles

text: show

text: similar

text: distributions.

text: The

text: diﬀerence

text: at

text: km

text: is

text: due

text: to

text: the

text: lower

text: boundary

text: eﬀects.

text: The

text: absolute

text: scale

text: of

text: the

text: assimilated

text: densities

text: suggests

text: that

text: MSIS

text: overpredicts

text: the

text: mass

text: density

text: across

text: all

text: altitudes

text: during

text: periods

text: of

text: low

text: solar

text: activity.

text: While

text: this

text: is

text: not

text: a

text: new

text: revelation,

text: the

text: new

text: framework

text: eﬀectively

text: calibrates

text: existing

text: physical

text: models

text: by

text: adjusting

text: the

text: absolute

text: scale,

text: which

text: is

text: a

text: major

text: driver

text: of

text: orbit

text: prediction

text: errors.

text: Conclusions

text: This

text: paper

text: has

text: demonstrated

text: a

text: new,

text: transformative

text: framework

text: for

text: data

text: assimilation

text: and

text: calibration

text: of

text: physical

text: ionosphere-thermosphere

text: models.

text: A

text: robust

text: yet

text: simple

text: and

text: eﬀective

text: approach

text: for

text: data

text: assimilation

text: has

text: thus

text: far

text: eluded

text: the

text: community.

text: The

text: new

text: framework

text: has

text: two

text: major

text: components:

text: (i)

text: Model

text: order

text: reduction

text: for

text: a

text: quasi-physical

text: linear

text: representation

text: of

text: the

text: dynamics,

text: and

text: (ii)

text: data

text: assimilation

text: calibration

text: of

text: the

text: reduced

text: order

text: model

text: (ROM)

text: using

text: a

text: Kalman

text: Filter.

text: Development

text: of

text: a

text: ROM

text: was

text: discussed

text: in

text: a

text: previous

text: paper.

text: This

text: paper

text: demonstrates

text: the

text: second

text: component.

text: The

text: new

text: framework

text: combines

text: the

text: best

text: of

text: both

text: empirical

text: and

text: physical

text: models.

text: The

text: ROM

text: reduces

text: the

text: cost

text: of

text: model

text: evaluation

text: to

text: the

text: level

text: of

text: empirical

text: models

text: while

text: inherently

text: providing

text: forecast/predictive

text: capabilities.

text: Unlike

text: large

text: scale

text: physical

text: models,

text: the

text: ROM

text: formulation

text: allows

text: rapid

text: modiﬁcations

text: in

text: the

text: time-step

text: of

text: model

text: evaluation

text: or

text: simulation

text: with

text: a

text: negligible

text: increase

text: in

text: the

text: computational

text: cost.

text: This

text: allows

text: the

text: model

text: to

text: be

text: easily

text: projected

text: to

text: the

text: time

text: of

text: next

text: measurement.

text: The

text: ROM

text: formulation

text: also

text: allows

text: large

text: ensemble

text: runs

text: of

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: 12 80 11 60 10 40 9 20 8 0 7 -20 6 -40 5 4 -60 3 -80 0 5 10 15 20 Local Time, hrs Figure 7: 3σ error prediction at mean CHAMP altitude after assimilation of all CHAMP data on day 320 of year 2009. Red: Satellite location at the current time. Green: back propagated CHAMP orbit from current location. 18 ged ,edutitaL % ,rorrE 3 ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

font: default

text: Local

text: Time,

text: hrs

text: Figure

text: 3σ

text: error

text: prediction

text: at

text: mean

text: CHAMP

text: altitude

text: after

text: assimilation

text: of

text: all

text: CHAMP

text: data

text: on

text: day

text: of

text: year

text: Red:

text: Satellite

text: location

text: at

text: the

text: current

text: time.

text: Green:

text: back

text: propagated

text: CHAMP

text: orbit

text: from

text: current

text: location.

text: ged

text: ,edutitaL

text: ,rorrE

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Algorithm 2 Kalman Filter Time update 1. Project the initial state estimate forward in time − x = Ax + Bu (14) k+1 k k 2. Project the initial covariance estimate forward in time − P = AP AT + Q (15) k+1 k Measurement update (cid:0) (cid:1) 3. Compute the Kalman Gain K = P− HT H P− HT + R −1 (16) k+1 k+1 k+1 k+1 k+1 k+1 k+1 (cid:0) (cid:1) 4. Update the State Estimate − − − x+ = x + K y˜ H x (17) k+1 k+1 k+1 k+1 k+1 k+1 5. Update the Covariance Estimate − − P+ = (I K H ) P (18) k+1 k+1 k+1 k+1 6 Observability Analysis The new framework begs two diﬀerent questions on observability: (i) Is there enough data available to derive/extract the POD modes for model order reduction, and (ii) Can the reduced state, z, be estimated using discrete point measurements of density along an orbit. The ﬁrst question is easy to answer because unlike some previous works where the POD modes or EOFs are derived from discrete measurements of density along an orbit (e.g., [Matsuo and Forbes(2010)]), we use model simulation output that provides complete global spatial coverage to derive the POD modes. In addition, simulation output over a full solar cycle is used which ensures suﬃcient temporal coverage. For linear time-invariant systems, such as the ROM formulation in Eq. 1, answer to the second question can be provided using the observability matrix      H   0  OOO ⇒ OOO H1A k = Hr,kAkr = = H2A2 (19) . . . OOO The matrix is populated at each time for the location at which the observation is made. The state OOO z is considered to be observable when the observability matrix is full rank or rank( ) = r. In addition, the observability matrix can artiﬁcially become full rank because of noise. Therefore, we also compute the OOO condition number of to conﬁrm that this is not the case. A relatively large condition number suggests that the observability matrix is not full rank because of noise. Figure 2 shows the rank and condition number for the demonstration case presented in this work assimilating a full days’ worth of measurements along the CHAMP orbit for r = 10. The ﬁgure shows that the observability matrix becomes full rank very quickly. 8 ##LTLine## ##LTLine## ##LTLine##

text: Algorithm

label: section

text: Kalman

text: Filter

text: Time

text: update

text: Project

text: the

text: initial

text: state

text: estimate

text: forward

text: in

text: time

label: equation

text: x

text: Ax

text: Bu

text: k

text: k

text: Project

text: the

text: initial

text: covariance

text: estimate

text: forward

text: in

text: time

text: P

text: AP

text: AT

text: Q

text: k

text: Measurement

text: update

text: Compute

text: the

text: Kalman

text: Gain

text: K

text: P−

text: HT

text: H

text: P−

text: HT

text: R

text: −1

text: Update

text: the

text: State

text: Estimate

text: x+

text: x

text: K

text: y˜

text: H

text: x

text: Update

text: the

text: Covariance

text: Estimate

text: P+

text: (I

text: K

text: H

text: P

text: Observability

text: Analysis

text: The

text: new

text: framework

text: begs

text: two

text: diﬀerent

text: questions

text: on

text: observability:

text: (i)

text: Is

text: there

text: enough

text: data

text: available

text: to

text: derive/extract

text: the

text: POD

text: modes

text: for

text: model

text: order

text: reduction,

text: and

text: (ii)

text: Can

text: the

text: reduced

text: state,

text: z,

text: be

text: estimated

text: using

text: discrete

text: point

text: measurements

text: of

text: density

text: along

text: an

text: orbit.

text: The

text: ﬁrst

text: question

text: is

text: easy

text: to

text: answer

text: because

text: unlike

text: some

text: previous

text: works

text: where

text: the

text: POD

text: modes

text: or

text: EOFs

text: are

text: derived

text: from

text: discrete

text: measurements

text: of

text: density

text: along

text: an

text: orbit

text: (e.g.,

text: [Matsuo

text: and

text: we

text: use

text: model

text: simulation

text: output

text: that

text: provides

text: complete

text: global

text: spatial

text: coverage

text: to

text: derive

text: the

text: POD

text: modes.

text: In

text: addition,

text: simulation

text: output

text: over

text: a

text: full

text: solar

text: cycle

text: is

text: used

text: which

text: ensures

text: suﬃcient

text: temporal

text: coverage.

text: For

text: linear

text: time-invariant

text: systems,

text: such

text: as

text: the

text: ROM

text: formulation

text: in

text: Eq.

text: answer

text: to

text: the

text: second

text: question

text: can

text: be

text: provided

text: using

text: the

text: observability

text: matrix

text: H

text: OOO

text: OOO

text: k

text: Hr,kAkr

text: OOO

text: The

text: matrix

text: is

text: populated

text: at

text: each

text: time

text: for

text: the

text: location

text: at

text: which

text: the

text: observation

text: is

text: made.

text: The

text: state

text: OOO

text: z

text: is

text: considered

text: to

text: be

text: observable

text: when

text: the

text: observability

text: matrix

text: is

text: full

text: rank

text: or

text: rank(

text: r.

text: In

text: addition,

text: the

text: observability

text: matrix

text: can

text: artiﬁcially

text: become

text: full

text: rank

text: because

text: of

text: noise.

text: Therefore,

text: we

text: also

text: compute

text: the

text: OOO

text: condition

text: number

text: of

text: to

text: conﬁrm

text: that

text: this

text: is

text: not

text: the

text: case.

text: A

text: relatively

text: large

text: condition

text: number

text: suggests

text: that

text: the

text: observability

text: matrix

text: is

text: not

text: full

text: rank

text: because

text: of

text: noise.

text: Figure

text: shows

text: the

text: rank

text: and

text: condition

text: number

text: for

text: the

text: demonstration

text: case

text: presented

text: in

text: this

text: work

text: assimilating

text: a

text: full

text: days’

text: worth

text: of

text: measurements

text: along

text: the

text: CHAMP

text: orbit

text: for

text: r

text: The

text: ﬁgure

text: shows

text: that

text: the

text: observability

text: matrix

text: becomes

text: full

text: rank

text: very

text: quickly.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: E δ − − = p (n + n ) + n q (n n ) α∆n = p (n , n ) α∆n , (30) δn (cid:15) 1 2 2 m 1 2 1 1(cid:15),m 1 2 1 E1 δ − − = p (n + n ) + n q (n n ) α∆n = p (n , n ) α∆n . (31) δn (cid:15) 1 2 1 m 1 2 2 2(cid:15),m 1 2 2 2 Indeed, the computati(cid:90)on for the ﬁrst derivative is given by E E δ δ(cid:16) (cid:17) < , δn > := (n , n ) δn dx 1 1 2 1 δn R δn 1 d (cid:90)1 (cid:16) (cid:17) 1 E − E = lim (n + h δn , n ) (n , n ) → 1 1 2 1 2 h 0 h (cid:90) 1 (cid:16) − (cid:17) = lim P (n + h δn + n )(x) P (n + n )(x) dx → (cid:15) 1 1 2 (cid:15) 1 2 h 0 h Rd (cid:90) 1 (cid:16) − (cid:17) + lim Q ((n + h δn )n )(x) Q (n n )(x) dx → m 1 1 2 m 1 2 h 0 h Rd (cid:90) (cid:16) α |∇ | − |∇ | (cid:17) + lim (n + hδn ) 2 n 2 dx → 1 1 1 h 0 2h Rd (cid:90) (cid:16)∂P ∂Q ∇ (cid:17) ∇ (cid:15) m = (n + n ) + (n n ) + α n δn δn dx 1 2 1 2 1 1 1 R ∂n ∂n d 1 1 − = p (n + n ) + n q (n n ) α∆n δn dx. (cid:15) 1 2 2 m 1 2 1 1 R d E The expression of δ follows from a similar computation. Therefore the gradient ﬂow δn2 associated to the free energy (6) according to the Wasserstein metric can be written as follows [36], E − ∇ · ∇ δ ∂ n (n (n , n )) = 0, (32) t 1 1 1 2 δn E1 − ∇ · ∇ δ ∂ n (n (n , n )) = 0. (33) t 2 2 1 2 δn 2 R The metric used here is not the traditional distance on L2( d), but the Wasserstein R distance. This distance is deﬁned on the set of probability distributions on d. It is used in a wide variety of physically meaningful equations like the porous medium equation or degenerate parabolic equations [33, 30, 36]. We recover Eqs. (8) and (9) of the GFM by adding growth terms G and G to (32) and (33). 1 2 It is worth noting that the free energy decreases along the trajectories of the equation in the absence of growth terms. Indeed, using the Green formula and the Eqs. (32) and (33), we have 14 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: E

text: δ

text: p

text: (n

text: n

text: n

text: q

text: (n

text: n

text: α∆n

text: p

text: (n

text: n

text: α∆n

text: δn

text: m

text: δ

text: p

text: (n

text: n

text: n

text: q

text: (n

text: n

text: α∆n

text: p

text: (n

text: n

text: α∆n

text: δn

text: m

text: Indeed,

text: the

text: for

text: the

text: ﬁrst

text: derivative

text: is

text: given

text: by

text: E

text: E

text: δ

text: δn

text: (n

text: n

text: δn

text: dx

text: δn

text: R

text: δn

text: d

text: E

text: E

text: lim

text: (n

text: h

text: δn

text: n

text: (n

text: n

text: h

text: h

text: lim

text: P

text: (n

text: h

text: δn

text: n

text: )(x)

text: P

text: (n

text: n

text: )(x)

text: dx

text: h

text: h

text: Rd

text: lim

text: Q

text: ((n

text: h

text: δn

text: )n

text: )(x)

text: Q

text: (n

text: n

text: )(x)

text: dx

text: m

text: m

text: h

text: h

text: Rd

text: α

text: lim

text: (n

text: hδn

text: n

text: dx

text: h

text: Rd

text: ∂Q

text: m

text: (n

text: n

text: (n

text: n

text: α

text: n

text: δn

text: δn

text: dx

text: R

text: ∂n

text: ∂n

text: d

text: p

text: (n

text: n

text: n

text: q

text: (n

text: n

text: α∆n

text: δn

text: dx.

text: m

text: R

text: d

text: E

text: The

text: expression

text: of

text: δ

text: follows

text: from

text: a

text: similar

text: computation.

text: Therefore

text: the

text: gradient

text: ﬂow

text: associated

text: to

text: the

text: free

text: energy

text: according

text: to

text: the

text: Wasserstein

text: metric

text: can

text: be

text: written

text: as

text: follows

text: E

text: δ

text: n

text: (n

text: (n

text: n

text: t

text: δn

text: δ

text: n

text: (n

text: (n

text: n

text: t

text: δn

text: R

text: The

text: metric

text: used

text: here

text: is

text: not

text: the

text: traditional

text: distance

text: on

text: d),

text: but

text: the

text: Wasserstein

text: R

text: distance.

text: This

text: distance

text: is

text: deﬁned

text: on

text: the

text: set

text: of

text: probability

text: distributions

text: on

text: d.

text: It

text: is

text: used

text: in

text: a

text: wide

text: variety

text: of

text: physically

text: meaningful

text: equations

text: like

text: the

text: porous

text: medium

text: equation

text: or

text: degenerate

text: parabolic

text: equations

text: We

text: recover

text: Eqs.

text: and

text: of

text: the

text: GFM

text: by

text: adding

text: growth

text: terms

text: G

text: and

text: G

text: to

text: and

text: It

text: is

text: worth

text: noting

text: that

text: the

text: free

text: energy

text: decreases

text: along

text: the

text: trajectories

text: of

text: the

text: equation

text: in

text: the

text: absence

text: of

text: growth

text: terms.

text: Indeed,

text: using

text: the

text: Green

text: formula

text: and

text: the

text: Eqs.

text: and

text: we

text: have

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Submitted for peer review to IEEE/OSA Journal of Lightwave Technology 1 End-to-end Deep Learning of Optical Fiber Communications Boris Karanov, Student Member, IEEE, Mathieu Chagnon, Member, IEEE, Fe´lix Thouin, Tobias A. Eriksson, Henning Bu¨low, Domanic¸ Lavery, Member, IEEE, Polina Bayvel, Fellow, IEEE, and Laurent Schmalen, Senior Member, IEEE Abstract— In this paper, we implement an optical ﬁber commu- been recently considered in [14] for the realization of low- nication system as an end-to-end deep neural network, including complexity nonlinearity compensation by digital backpropaga- the complete chain of transmitter, channel model, and receiver. tion (DBP) [15]. It has been shown that the proposed ANN- This approach enables the optimization of the transceiver in based DBP achieves similar performance than conventional a single end-to-end process. We illustrate the beneﬁts of this method by applying it to intensity modulation/direct detection DBP for a single channel 16-QAM system while reducing (IM/DD) systems and show that we can achieve bit error rates the computational demands. Deep learning has also been con- below the 6.7% hard-decision forward error correction (HD- sidered for short-reach communications. For instance, in [17] FEC) threshold. We model all componentry of the transmitter ANNs are considered for equalization in PAM8 IM/DD sys- and receiver, as well as the ﬁber channel, and apply deep learning tems. Bit-error rates (BERs) below the forward error correction to ﬁnd transmitter and receiver conﬁgurations minimizing the symbol error rate. We propose and verify in simulations a (FEC) threshold have been experimentally demonstrated over training method that yields robust and ﬂexible transceivers 4 km transmission distance. In [18], deep ANNs are used at that allow—without reconﬁguration—reliable transmission over the receiver of the IM/DD system as an advanced detection a large range of link dispersions. The results from end-to-end block, which accounts for channel memory and linear and deep learning are successfully veriﬁed for the ﬁrst time in an nonlinear signal distortions. For short reaches (1.5 km), BER experiment. In particular, we achieve information rates of 42Gb/s below the HD-FEC threshold at distances beyond 40km. We ﬁnd improvements over common feed-forward linear equalization that our results outperform conventional IM/DD solutions based were achieved. on 2 and 4 level pulse amplitude modulation (PAM2/PAM4) with In all the aforementioned examples, deep learning tech- feedforward equalization (FFE) at the receiver. Our study is the niques have been applied to optimize a speciﬁc function ﬁrst step towards end-to-end deep learning-based optimization in the ﬁber-optic system, which itself consists of several of optical ﬁber communication systems. signal processing blocks at both transmitter and receiver, each Index Terms—Machine learning, deep learning, neural net- carrying out an individual task, e.g. coding, modulation and works, optical ﬁber communication, modulation, detection. equalization. In principle, such a modular implementation allows the system components to be analyzed, optimized and controlled separately and thus presents a convenient way of I. INTRODUCTION building the communication link. Nevertheless, this approach T HE application of machine learning techniques in com- can be sub-optimal, especially for communication systems munication systems has attracted a lot of attention in where the optimum receivers or optimum blocks are not known recent years [1], [2]. In the ﬁeld of optical ﬁber com- or not available due to complexity reasons. As a consequence, munications, various tasks such as performance monitoring, in some systems, a block-based receiver with one or several ﬁber nonlinearity mitigation, carrier recovery and modulation sub-optimum modules does not necessarily achieve the optimal format recognition have been addressed from the machine end-to-end system performance. Especially if the optimum learning perspective [3]–[5]. In particular, since chromatic joint receiver is not known or too complex to implement, we dispersion and nonlinear Kerr effects in the ﬁber are regarded require carefully chosen approximations. as the major information rate-limiting factors in modern opti- Deep learning techniques, which can approximate any non- cal communication systems [6], the application of artiﬁcial linear function [13], allow us to design the communication neural networks (ANNs), known as universal function ap- system by carrying out the optimization in a single end-to- proximators [7], for channel equalization has been of great end process including the transmitter and receiver as well as research interest [8]–[12]. For example, a multi-layer ANN the communication channel. Such a novel design based on architecture, which enables deep learning techniques [13], has full system learning avoids the conventional modular structure, because the system is implemented as a single deep neural B. Karanov is with Nokia Bell Labs, Stuttgart, Germany and Opti- network, and has the potential to achieve an optimal end-to- cal Networks Group (ONG), Dept. Electronic and Electrical Engineering, end performance. The objective of this approach is to acquire University College London (UCL), UK (email:boris.karanov.16@ucl.ac.uk). M. Chagnon, H. Bu¨low and L. Schmalen are with Nokia Bell Labs, Stuttgart, a robust representation of the input message at every layer of Germany. F. Thouin is with the School of Physics, Georgia Institute of the network. Importantly, this enables a communication system Technology, Atlanta, GA, USA. T. A. Eriksson is with NICT, Japan. D. Lavery to be adapted for information transmission over any type of and P. Bayvel are with ONG, Dept. Electronic and Electrical Engineering, UCL, UK. channel without requiring prior mathematical modeling and

text: Submitted

text: for

text: peer

text: review

text: to

text: IEEE/OSA

text: Journal

text: of

text: Lightwave

text: Technology

text: End-to-end

label: title

text: Deep

text: Learning

text: of

text: Optical

text: Fiber

text: Communications

text: Boris

label: author

text: Karanov,

text: Student

text: Member,

text: IEEE,

text: Mathieu

text: Chagnon,

text: Member,

text: IEEE,

text: Fe´lix

text: Thouin,

text: Tobias

text: A.

text: Eriksson,

text: Henning

text: Bu¨low,

text: Domanic¸

text: Lavery,

text: Member,

text: IEEE,

text: Polina

text: Bayvel,

text: Fellow,

text: IEEE,

text: and

text: Laurent

text: Schmalen,

text: Senior

text: Member,

text: IEEE

text: Abstract—

text: In

label: abstract

text: this

text: paper,

text: we

text: implement

text: an

text: optical

text: ﬁber

text: commu-

text: been

text: recently

text: considered

text: in

text: for

text: the

text: realization

text: of

text: low-

text: nication

text: system

text: as

text: an

text: end-to-end

text: deep

text: neural

text: network,

text: including

text: complexity

text: nonlinearity

text: compensation

text: by

text: digital

text: backpropaga-

text: the

text: complete

text: chain

text: of

text: transmitter,

text: channel

text: model,

text: and

text: receiver.

text: tion

text: (DBP)

text: It

text: has

text: been

text: shown

text: that

text: the

text: proposed

text: ANN-

text: This

text: approach

text: enables

text: the

text: optimization

text: of

text: the

text: transceiver

text: in

text: based

text: DBP

text: achieves

text: similar

text: performance

text: than

text: conventional

text: a

text: single

text: end-to-end

text: process.

text: We

text: illustrate

text: the

text: beneﬁts

text: of

text: this

text: method

text: by

text: applying

text: it

text: to

text: intensity

text: modulation/direct

text: detection

text: DBP

text: for

text: a

text: single

text: channel

text: system

text: while

text: reducing

text: (IM/DD)

text: systems

text: and

text: show

text: that

text: we

text: can

text: achieve

text: bit

text: error

text: rates

text: the

text: computational

text: demands.

text: Deep

text: learning

text: has

text: also

text: been

text: con-

text: below

text: the

text: hard-decision

text: forward

text: error

text: correction

text: (HD-

text: sidered

text: for

text: short-reach

text: communications.

text: For

text: instance,

text: in

text: FEC)

text: threshold.

text: We

text: model

text: all

text: componentry

text: of

text: the

text: transmitter

text: ANNs

text: are

text: considered

text: for

text: equalization

text: in

text: IM/DD

text: sys-

text: and

text: receiver,

text: as

text: well

text: as

text: the

text: ﬁber

text: channel,

text: and

text: apply

text: deep

text: learning

text: tems.

text: Bit-error

text: rates

text: (BERs)

text: below

text: the

text: forward

text: error

text: correction

text: to

text: ﬁnd

text: transmitter

text: and

text: receiver

text: conﬁgurations

text: minimizing

text: the

text: symbol

text: error

text: rate.

text: We

text: propose

text: and

text: verify

text: in

text: simulations

text: a

text: (FEC)

text: threshold

text: have

text: been

text: experimentally

text: demonstrated

text: over

text: training

text: method

text: that

text: yields

text: robust

text: and

text: ﬂexible

text: transceivers

text: km

text: transmission

text: distance.

text: In

text: deep

text: ANNs

text: are

text: used

text: at

text: that

text: allow—without

text: reconﬁguration—reliable

text: transmission

text: over

text: the

text: receiver

text: of

text: the

text: IM/DD

text: system

text: as

text: an

text: advanced

text: detection

text: a

text: large

text: range

text: of

text: link

text: dispersions.

text: The

text: results

text: from

text: end-to-end

text: block,

text: which

text: accounts

text: for

text: channel

text: memory

text: and

text: linear

text: and

text: deep

text: learning

text: are

text: successfully

text: veriﬁed

text: for

text: the

text: ﬁrst

text: time

text: in

text: an

text: nonlinear

text: signal

text: distortions.

text: For

text: short

text: reaches

text: km),

text: BER

text: experiment.

text: In

text: particular,

text: we

text: achieve

text: information

text: rates

text: of

text: below

text: the

text: HD-FEC

text: threshold

text: at

text: distances

text: beyond

text: We

text: ﬁnd

text: improvements

text: over

text: common

text: feed-forward

text: linear

text: equalization

text: that

text: our

text: results

text: outperform

text: conventional

text: IM/DD

text: solutions

text: based

text: were

text: achieved.

text: on

text: and

text: level

text: pulse

text: amplitude

text: modulation

text: with

text: In

text: all

text: the

text: aforementioned

text: examples,

text: deep

text: learning

text: tech-

text: feedforward

text: equalization

text: (FFE)

text: at

text: the

text: receiver.

text: Our

text: study

text: is

text: the

text: niques

text: have

text: been

text: applied

text: to

text: optimize

text: a

text: speciﬁc

text: function

text: ﬁrst

text: step

text: towards

text: end-to-end

text: deep

text: learning-based

text: optimization

text: in

text: the

text: ﬁber-optic

text: system,

text: which

text: itself

text: consists

text: of

text: several

text: of

text: optical

text: ﬁber

text: communication

text: systems.

text: signal

text: processing

text: blocks

text: at

text: both

text: transmitter

text: and

text: receiver,

text: each

text: Index

text: Terms—Machine

text: learning,

text: deep

text: learning,

text: neural

text: net-

text: carrying

text: out

text: an

text: individual

text: task,

text: e.g.

text: coding,

text: modulation

text: and

text: works,

text: optical

text: ﬁber

text: communication,

text: modulation,

text: detection.

text: equalization.

text: In

text: principle,

text: such

text: a

text: modular

text: implementation

text: allows

text: the

text: system

text: components

text: to

text: be

text: analyzed,

text: optimized

text: and

text: controlled

text: separately

text: and

text: thus

text: presents

text: a

text: convenient

text: way

text: of

text: I.

text: INTRODUCTION

text: building

text: the

text: communication

text: link.

text: Nevertheless,

text: this

text: approach

text: T

text: HE

text: application

text: of

text: machine

text: learning

text: techniques

text: in

text: com-

text: can

text: be

text: sub-optimal,

text: especially

text: for

text: communication

text: systems

text: munication

text: systems

text: has

text: attracted

text: a

text: lot

text: of

text: attention

text: in

text: where

text: the

text: optimum

text: receivers

text: or

text: optimum

text: blocks

text: are

text: not

text: known

text: recent

text: years

text: In

text: the

text: ﬁeld

text: of

text: optical

text: ﬁber

text: com-

text: or

text: not

text: available

text: due

text: to

text: complexity

text: reasons.

text: As

text: a

text: consequence,

text: munications,

text: various

text: tasks

text: such

text: as

text: performance

text: monitoring,

text: in

text: some

text: systems,

text: a

text: block-based

text: receiver

text: with

text: one

text: or

text: several

text: ﬁber

text: nonlinearity

text: mitigation,

text: carrier

text: recovery

text: and

text: modulation

text: sub-optimum

text: modules

text: does

text: not

text: necessarily

text: achieve

text: the

text: optimal

text: format

text: recognition

text: have

text: been

text: addressed

text: from

text: the

text: machine

text: end-to-end

text: system

text: performance.

text: Especially

text: if

text: the

text: optimum

text: learning

text: perspective

text: In

text: particular,

text: since

text: chromatic

text: joint

text: receiver

text: is

text: not

text: known

text: or

text: too

text: complex

text: to

text: implement,

text: we

text: dispersion

text: and

text: nonlinear

text: Kerr

text: effects

text: in

text: the

text: ﬁber

text: are

text: regarded

text: require

text: carefully

text: chosen

text: approximations.

text: as

text: the

text: major

text: information

text: rate-limiting

text: factors

text: in

text: modern

text: opti-

text: Deep

text: learning

text: techniques,

text: which

text: can

text: approximate

text: any

text: non-

text: cal

text: communication

text: systems

text: the

text: application

text: of

text: artiﬁcial

text: linear

text: function

text: allow

text: us

text: to

text: design

text: the

text: communication

text: neural

text: networks

text: (ANNs),

text: known

text: as

text: universal

text: function

text: ap-

text: system

text: by

text: carrying

text: out

text: the

text: optimization

text: in

text: a

text: single

text: end-to-

text: proximators

text: for

text: channel

text: equalization

text: has

text: been

text: of

text: great

text: end

text: process

text: including

text: the

text: transmitter

text: and

text: receiver

text: as

text: well

text: as

text: research

text: interest

text: For

text: example,

text: a

text: multi-layer

text: ANN

text: the

text: communication

text: channel.

text: Such

text: a

text: novel

text: design

text: based

text: on

text: architecture,

text: which

text: enables

text: deep

text: learning

text: techniques

text: has

text: full

text: system

text: learning

text: avoids

text: the

text: conventional

text: modular

text: structure,

text: because

text: the

text: system

text: is

text: implemented

text: as

text: a

text: single

text: deep

text: neural

text: B.

text: Karanov

text: is

text: with

text: Nokia

text: Bell

text: Labs,

text: Stuttgart,

text: Germany

text: and

text: Opti-

text: network,

text: and

text: has

text: the

text: potential

text: to

text: achieve

text: an

text: optimal

text: end-to-

text: cal

text: Networks

text: Group

text: (ONG),

text: Dept.

text: Electronic

text: and

text: Electrical

text: Engineering,

text: end

text: performance.

text: The

text: objective

text: of

text: this

text: approach

text: is

text: to

text: acquire

text: University

text: College

text: London

text: (UCL),

text: UK

text: M.

text: Chagnon,

text: H.

text: Bu¨low

text: and

text: L.

text: Schmalen

text: are

text: with

text: Nokia

text: Bell

text: Labs,

text: Stuttgart,

text: a

text: robust

text: representation

text: of

text: the

text: input

text: message

text: at

text: every

text: layer

text: of

text: Germany.

text: F.

text: Thouin

text: is

text: with

text: the

text: School

text: of

text: Physics,

text: Georgia

text: Institute

text: of

text: the

text: network.

text: Importantly,

text: this

text: enables

text: a

text: communication

text: system

text: Technology,

text: Atlanta,

text: GA,

text: USA.

text: T.

text: A.

text: Eriksson

text: is

text: with

text: NICT,

text: Japan.

text: D.

text: Lavery

text: to

text: be

text: adapted

text: for

text: information

text: transmission

text: over

text: any

text: type

text: of

text: and

text: P.

text: Bayvel

text: are

text: with

text: ONG,

text: Dept.

text: Electronic

text: and

text: Electrical

text: Engineering,

text: UCL,

text: UK.

text: channel

text: without

text: requiring

text: prior

text: mathematical

text: modeling

text: and


text: Submitted for peer review to IEEE/OSA Journal of Lightwave Technology 9 [2] F. Khan, C. Lu, A. Lau, ”Machine learning methods for optical commu- nication systems,” in Advanced Photonics 2017 (IPR, NOMA, Sensors, Networks, SPPCom, PS), OSA Technical Digest (online) (Optical Society of America, 2017), paper SpW2F.3. [3] J. Thrane et al., ”Machine learning techniques for optical performance monitoring from directly detected PDM-QAM signals,” J. Lightwave Technol., vol. 35, no. 4, pp. 868-875, 2017. [4] D. Zibar, M. Piels, R. Jones, and C. Scha¨ffer, ”Machine learning techniques in optical communication,” J. Lightwave Technol., vol. 34, no. 6, pp. 1442-1452, 2016. [5] F. Khan, Y. Zhou, A. Lau, and C. Lu, ”Modulation format identiﬁcation in heterogeneous ﬁber-optic networks using artiﬁcial neural networks,” Opt. Express, vol. 20, no. 11, pp. 12422-12431, 2012. [6] R.-J. Essiambre, G. Kramer, P. Winzer, G. Foschini, and B. Goebel, ”Capacity limits of optical ﬁber networks,” J. Lightwave Technol., vol. 28, no. 4, pp. 662-701, 2010. [7] K. Hornik, M. Stinchcombe, and H. White, ”Multilayer feedforward networks are universal approximators,” Neural Networks, vol. 2, no. 5, pp. 359-366, 1989. [8] K. Burse, R. Yadav, S. Shrivastava, ”Channel equalization using neural networks: a review,” IEEE Trans. Syst., Man, Cybern. C, Appl. Rev., vol. 40, no. 3, pp. 352-357, 2010. [9] M. Ibnkahla, ”Applications of neural networks to digital communica- tions - a survey,” Elsevier Signal Processing, vol. 80, no. 7, pp. 1185- 1215, 2000. [10] M. Jarajreh et al., ”Artiﬁcial neural network nonlinear equalizer for coherent optical OFDM,” IEEE Photonics Technol. Lett., vol. 27, no. 4, pp. 387-390, 2014. [11] E. Giacoumidis et al., ”Fiber nonlinearity-induced penalty reduction in CO-OFDM by ANN-based nonlinear equalization,” Opt. Lett., vol. 40, no. 21, pp. 5113-5116, 2015. [12] T. Eriksson, H. Bu¨low, and A. Leven, ”Applying neural networks in optical communication systems: possible pitfalls”, IEEE Photon. Technol. Lett., vol. 29, no. 23, pp. 2091-2094, 2017. [13] I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning. MIT Press, 2016. [14] C. Ha¨ger and H. Pﬁster, ”Nonlinear interference mitigation via deep neural networks,” ArXiv preprint arXiv:1710.06234, 2017. [15] E. Ip and J. Kahn, ”Compensation of dispersion and nonlinear impair- ments using digital backpropagation,” J. Lightwave Technol., vol. 26, no. 20, pp. 3416-3425, 2008. [16] Available online: https://www.tensorﬂow.org/. [17] S. Gaiarin et al., ”High speed PAM-8 optical interconnects with digital equalization based on neural network,” in Proc. Asia Communications and Photonics Conference (ACP), (Optical Society of America, 2016), paper AS1C-1. [18] J. Estara´n et al., ”Artiﬁcial neural networks for linear and non-linear impairment mitigation in high-baudrate IM/DD systems,” In Proc. of 42nd European Conference on Optical Communications (ECOC), (Institute of Eletrical and Electronics Engineers, 2016), pp. 106-108. [19] T. O’Shea and J. Hoydis, ”An introduction to deep learning for the physical layer,” IEEE Trans. Cogn. Commun. Netw., vol. 3, no. 4, pp. 563-575, 2017. [20] S. Do¨rner, S. Cammerer, J. Hoydis, and S. ten Brink, ”Deep learning- based communication over the air,” IEEE J. Sel. Topics Signal Process., vol. 12., no. 1, 2018. [21] M. Eiselt, N. Eiselt and A. Dochhan, ”Direct detection solutions for 100G and beyond,” in Proc. of Optical Fiber Communication Conference (OFC), (Optical Society of America, 2017), paper Tu3I.3. [22] V. Nair and G. Hinton, ”Rectiﬁed linear units improve restricted Boltz- mann machines,” in Proc. of Int. Conf. Mach. Learn. (ICML), ACM, 2010, pp. 807-814. [23] D. Rumelhart, G. Hinton, and R. Williams, ”Learning representations by back-propagating errors,” Nature, vol. 323, pp. 533-536, 1986. [24] D. Kingma and J. Ba, ”Adam: A method for stochastic optimization,” ArXiv preprint arXiv:1412.6980, 2014. [25] G. Agrawal, Fiber-optic Communication systems, 4th ed. John Wiley & Sons, Inc., 2010. [26] A. Napoli et al., ”Digital Predistortion techniques for ﬁnite extinction ratio IQ Mach-Zehnder modulators,” J. Lightwave Technol., vol. 35, no. 19, 2017. [27] C. Pearson, ”High-speed, analog-to-digital converter basics,” Texas In- struments, Dallas, Texas, App. Rep. SLAA510, Jan. 2011. Available: http://www.ti.com/lit/an/slaa510/slaa510.pdf

text: Submitted

text: for

text: peer

text: review

text: to

text: IEEE/OSA

text: Journal

text: of

text: Lightwave

text: Technology

text: F.

text: Khan,

text: C.

text: Lu,

text: A.

text: Lau,

text: ”Machine

text: learning

text: methods

text: for

text: optical

text: commu-

text: nication

text: systems,”

text: in

text: Advanced

text: Photonics

text: (IPR,

text: NOMA,

text: Sensors,

text: Networks,

text: SPPCom,

text: PS),

text: OSA

text: Technical

text: Digest

text: (online)

text: (Optical

text: Society

text: of

text: America,

text: paper

text: J.

text: Thrane

text: et

text: al.,

text: ”Machine

text: learning

text: techniques

text: for

text: optical

text: performance

text: monitoring

text: from

text: directly

text: detected

text: PDM-QAM

text: signals,”

text: J.

text: Lightwave

text: Technol.,

text: vol.

text: no.

text: pp.

text: D.

text: Zibar,

text: M.

text: Piels,

text: R.

text: Jones,

text: and

text: C.

text: Scha¨ffer,

text: ”Machine

text: learning

text: techniques

text: in

text: optical

text: communication,”

text: J.

text: Lightwave

text: Technol.,

text: vol.

text: no.

text: pp.

text: F.

text: Khan,

text: Y.

text: Zhou,

text: A.

text: Lau,

text: and

text: C.

text: Lu,

text: ”Modulation

text: format

text: identiﬁcation

text: in

text: heterogeneous

text: ﬁber-optic

text: networks

text: using

text: artiﬁcial

text: neural

text: networks,”

text: Opt.

text: Express,

text: vol.

text: no.

text: pp.

text: R.-J.

text: Essiambre,

text: G.

text: Kramer,

text: P.

text: Winzer,

text: G.

text: Foschini,

text: and

text: B.

text: Goebel,

text: ”Capacity

text: limits

text: of

text: optical

text: ﬁber

text: networks,”

text: J.

text: Lightwave

text: Technol.,

text: vol.

text: no.

text: pp.

text: K.

text: Hornik,

text: M.

text: Stinchcombe,

text: and

text: H.

text: White,

text: ”Multilayer

text: feedforward

text: networks

text: are

text: universal

text: approximators,”

text: Neural

text: Networks,

text: vol.

text: no.

text: pp.

text: K.

text: Burse,

text: R.

text: Yadav,

text: S.

text: Shrivastava,

text: ”Channel

text: equalization

text: using

text: neural

text: networks:

text: a

text: review,”

text: IEEE

text: Trans.

text: Syst.,

text: Man,

text: Cybern.

text: C,

text: Appl.

text: Rev.,

text: vol.

text: no.

text: pp.

text: M.

text: Ibnkahla,

text: ”Applications

text: of

text: neural

text: networks

text: to

text: digital

text: communica-

text: tions

text: a

text: survey,”

text: Elsevier

text: Signal

text: Processing,

text: vol.

text: no.

text: pp.

text: M.

text: Jarajreh

text: et

text: al.,

text: ”Artiﬁcial

text: neural

text: network

text: nonlinear

text: equalizer

text: for

text: coherent

text: optical

text: OFDM,”

text: IEEE

text: Photonics

text: Technol.

text: Lett.,

text: vol.

text: no.

text: pp.

text: E.

text: Giacoumidis

text: et

text: al.,

text: ”Fiber

text: nonlinearity-induced

text: penalty

text: reduction

text: in

text: CO-OFDM

text: by

text: ANN-based

text: nonlinear

text: equalization,”

text: Opt.

text: Lett.,

text: vol.

text: no.

text: pp.

text: T.

text: Eriksson,

text: H.

text: Bu¨low,

text: and

text: A.

text: Leven,

text: ”Applying

text: neural

text: networks

text: in

text: optical

text: communication

text: systems:

text: possible

text: pitfalls”,

text: IEEE

text: Photon.

text: Technol.

text: Lett.,

text: vol.

text: no.

text: pp.

text: I.

text: Goodfellow,

text: Y.

text: Bengio,

text: and

text: A.

text: Courville,

text: Deep

text: Learning.

text: MIT

text: Press,

text: C.

text: Ha¨ger

text: and

text: H.

text: Pﬁster,

text: ”Nonlinear

text: interference

text: mitigation

text: via

text: deep

text: neural

text: networks,”

text: ArXiv

text: preprint

text: E.

text: Ip

text: and

text: J.

text: Kahn,

text: ”Compensation

text: of

text: dispersion

text: and

text: nonlinear

text: impair-

text: ments

text: using

text: digital

text: backpropagation,”

text: J.

text: Lightwave

text: Technol.,

text: vol.

text: no.

text: pp.

text: Available

text: online:

text: S.

text: Gaiarin

text: et

text: al.,

text: ”High

text: speed

text: optical

text: interconnects

text: with

text: digital

text: equalization

text: based

text: on

text: neural

text: network,”

text: in

text: Proc.

text: Asia

text: Communications

text: and

text: Photonics

text: Conference

text: (ACP),

text: (Optical

text: Society

text: of

text: America,

text: paper

text: J.

text: Estara´n

text: et

text: al.,

text: ”Artiﬁcial

text: neural

text: networks

text: for

text: linear

text: and

text: non-linear

text: impairment

text: mitigation

text: in

text: high-baudrate

text: IM/DD

text: systems,”

text: In

text: Proc.

text: of

text: European

text: Conference

text: on

text: Optical

text: Communications

text: (ECOC),

text: (Institute

text: of

text: Eletrical

text: and

text: Electronics

text: Engineers,

text: pp.

text: T.

text: O’Shea

text: and

text: J.

text: Hoydis,

text: ”An

text: introduction

text: to

text: deep

text: learning

text: for

text: the

text: physical

text: layer,”

text: IEEE

text: Trans.

text: Cogn.

text: Commun.

text: Netw.,

text: vol.

text: no.

text: pp.

text: S.

text: Do¨rner,

text: S.

text: Cammerer,

text: J.

text: Hoydis,

text: and

text: S.

text: ten

text: Brink,

text: ”Deep

text: learning-

text: based

text: communication

text: over

text: the

text: air,”

text: IEEE

text: J.

text: Sel.

text: Topics

text: Signal

text: Process.,

text: vol.

text: no.

text: M.

text: Eiselt,

text: N.

text: Eiselt

text: and

text: A.

text: Dochhan,

text: ”Direct

text: detection

text: solutions

text: for

text: and

text: beyond,”

text: in

text: Proc.

text: of

text: Optical

text: Fiber

text: Communication

text: Conference

text: (OFC),

text: (Optical

text: Society

text: of

text: America,

text: paper

text: V.

text: Nair

text: and

text: G.

text: Hinton,

text: ”Rectiﬁed

text: linear

text: units

text: improve

text: restricted

text: Boltz-

text: mann

text: machines,”

text: in

text: Proc.

text: of

text: Int.

text: Conf.

text: Mach.

text: Learn.

text: (ICML),

text: ACM,

text: pp.

text: D.

text: Rumelhart,

text: G.

text: Hinton,

text: and

text: R.

text: Williams,

text: ”Learning

text: representations

text: by

text: back-propagating

text: errors,”

text: Nature,

text: vol.

text: pp.

text: D.

text: Kingma

text: and

text: J.

text: Ba,

text: ”Adam:

text: A

text: method

text: for

text: stochastic

text: optimization,”

text: ArXiv

text: preprint

text: G.

text: Agrawal,

text: Fiber-optic

text: Communication

text: systems,

text: ed.

text: John

text: Wiley

text: Sons,

text: Inc.,

text: A.

text: Napoli

text: et

text: al.,

text: ”Digital

text: Predistortion

text: techniques

text: for

text: ﬁnite

text: extinction

text: ratio

text: IQ

text: Mach-Zehnder

text: modulators,”

text: J.

text: Lightwave

text: Technol.,

text: vol.

text: no.

text: C.

text: Pearson,

text: ”High-speed,

text: analog-to-digital

text: converter

text: basics,”

text: Texas

text: In-

text: struments,

text: Dallas,

text: Texas,

text: App.

text: Rep.

text: Jan.

text: Available:


text: Supplementary Materials 13

text: Supplementary

text: Materials


text: CONTENTS IM. ethods 14 ASi.mulation method 14 S1.ource code 14 A2.lgorithm description 14 R3.eproduction of the polymer equilibrium dynamics 15 I4r.reversible crosslinking process 17 BSi.mulation data analysis 20 G1.eneration of contact matrices 20 C2.alculation of P (s) in the simulation 20 D3.etermination of the collapse transition 21 ∗ D4.etermination of the transition values t and ξ 22 D5.etermination of the Rouse coeﬃcient from MSD scaling 22 CG.eneration of Hi-C data-sets 22 C1.rosslink conditions on G1 elutriated cells 22 G2.eneration of Hi-C libraries 22 R3.aw data processing 23 EDx. perimental data analysis 23 C1.alculation of P exp(s) from Hi-C data 24 D2.etermination of the collapse transition 25 IAI.ppendix 26 AM.easurement of pearls with Louvain algorithm 26 (cid:29) ∗ BSh.ort-scale exponent γ at the end of ﬁxation (t t ) 27 lim CEﬀ. ects of additional steric interactions 27 VDi.deos of the simulations 27 EA.nalytical phenomenology of a scale-free Rouse model 28 T1.he Rouse equation 28 S2.caling laws and relaxation times 29 C3.alculation of the thermal noise intensity G 32 η R4.elaxation times for out-of-equilibrium loops 32 14

text: CONTENTS

text: IM.

text: ethods

text: ASi.mulation

text: method

text: code

text: description

text: of

text: the

text: polymer

text: equilibrium

text: dynamics

text: crosslinking

text: process

text: BSi.mulation

text: data

text: analysis

text: of

text: contact

text: matrices

text: of

text: P

text: (s)

text: in

text: the

text: simulation

text: of

text: the

text: collapse

text: transition

text: of

text: the

text: transition

text: values

text: t

text: and

text: ξ

text: of

text: the

text: Rouse

text: coeﬃcient

text: from

text: MSD

text: scaling

text: CG.eneration

text: of

text: Hi-C

text: data-sets

text: conditions

text: on

text: elutriated

text: cells

text: of

text: Hi-C

text: libraries

text: data

text: processing

text: EDx.

text: perimental

text: data

text: analysis

text: of

text: P

text: exp(s)

text: from

text: Hi-C

text: data

text: of

text: the

text: collapse

text: transition

text: IAI.ppendix

text: AM.easurement

text: of

text: pearls

text: with

text: Louvain

text: algorithm

text: BSh.ort-scale

text: exponent

text: γ

text: at

text: the

text: end

text: of

text: ﬁxation

text: (t

text: t

text: lim

text: CEﬀ.

text: ects

text: of

text: additional

text: steric

text: interactions

text: VDi.deos

text: of

text: the

text: simulations

text: EA.nalytical

text: phenomenology

text: of

text: a

text: scale-free

text: Rouse

text: model

text: Rouse

text: equation

text: laws

text: and

text: relaxation

text: times

text: of

text: the

text: thermal

text: noise

text: intensity

text: G

text: η

text: times

text: for

text: out-of-equilibrium

text: loops