text: Algorithm 1 captioncolorSDCA 1: Initialize α0 and w0 = w(α0); − for do 2: t = 0, 1, 2, . . . , T 1 { } 3: Randomly sample i from 1, 2, ..., n ; 4: Find ∆α to maximize the subproblem (4); i 5: Update dual variable α through: ← 6: αt+1 αt + ∆α e ; i i 7: Update primal variable w through: ← 8: wt+1 wt + 1 ∆α x ; λn i i end for 9: Algorithm 2 captioncolorDual Free SDCA ∀ ∈ R 1: Initialize dual variable α0 = (α0, ..., α0) where i, α0 d, primal variable w0 = w(α0); − 0 n i for do 2: t = 0, 1, 2, . . . , T 1 { } 3: Randomly sample i from 1, 2, ..., n ; 4: Compute dual residue κ through: ← ∇ 5: κ φ (wt) + αt; i i 6: Update dual variable α through: ← − i 7: αt+1 αt ηλnκ; i i 8: Update primal variable w through: ← − 9: wt+1 wt ηκ; end for 10: [He and Takácˇ, 2015], the authors accelerated dfSDCA by using non-uniform sampling strategy in each iteration and proved that it admits faster convergence. sectioncolor 3 Distributed Asynchronous Dual Free Stochastic Dual Coordinate Ascent In this section, we propose Distributed Asynchronous Dual Free Stochastic Coordinate Ascent (Dis- (cid:80) dfSDCA) for distributed optimization. Dis-dfSDCA ﬁts for any parameter server framework, where the star-shape network is used. We assume that there are n samples in the dataset, and they are evenly distributed over K workers. In worker k, there are n samples. It is satisﬁed that n = K n . Different from k k=1 k sequential dfSDCA, we split the update of dual variable and primal variable into different nodes. The pseudocodes of Dis-dfSDCA for server node and worker nodes are presented in Algorithm 3 and Algorithm 4 respectively. sectioncolor 3.1 Update Global Variable on Server w ∈ R The up-to-date global variable w d is stored and updated on the server. Initially, w is set to be vector zero. At the beginning of each iteration, the server receives gradient message v from arbitrary worker k and k let vt = v . Then it updates the global variable through: k equationcolor − ws,t+1 = ws,t ηvt (5) Finally, it sends the up-to-date global variable back to the worker k for further computation. Asynchronous method is robust to straggler problem because it allows for updating the global variable when receiving from 4 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Algorithm

text: captioncolorSDCA

text: Initialize

text: α0

text: and

text: for

text: do

text: t

text: T

text: Randomly

text: sample

text: i

text: from

text: n

text: Find

text: ∆α

text: to

text: maximize

text: the

text: subproblem

text: i

text: Update

text: dual

text: variable

text: α

text: through:

text: αt

text: ∆α

text: e

text: i

text: i

text: Update

text: primal

text: variable

text: w

text: through:

text: wt

text: ∆α

text: x

text: λn

text: i

text: i

text: end

text: for

text: Algorithm

text: captioncolorDual

text: Free

text: SDCA

text: R

text: Initialize

text: dual

text: variable

text: α0

text: where

text: i,

text: α0

text: d,

text: primal

text: variable

text: n

text: i

text: for

text: do

text: t

text: T

text: Randomly

text: sample

text: i

text: from

text: n

text: Compute

text: dual

text: residue

text: κ

text: through:

text: κ

text: φ

text: (wt)

text: αt;

text: i

text: i

text: Update

text: dual

text: variable

text: α

text: through:

text: i

text: αt

text: ηλnκ;

text: i

text: i

text: Update

text: primal

text: variable

text: w

text: through:

text: wt

text: ηκ;

text: end

text: for

text: [He

text: and

text: Takácˇ,

text: the

text: authors

text: accelerated

text: dfSDCA

text: by

text: using

text: non-uniform

text: sampling

text: strategy

text: in

text: each

text: iteration

text: and

text: proved

text: that

text: it

text: admits

text: faster

text: convergence.

text: sectioncolor

text: Distributed

text: Asynchronous

text: Dual

text: Free

text: Stochastic

text: Dual

text: Coordinate

text: Ascent

text: In

text: this

text: section,

text: we

text: propose

text: Distributed

text: Asynchronous

text: Dual

text: Free

text: Stochastic

text: Coordinate

text: Ascent

text: (Dis-

text: dfSDCA)

text: for

text: distributed

text: optimization.

text: Dis-dfSDCA

text: ﬁts

text: for

text: any

text: parameter

text: server

text: framework,

text: where

text: the

text: star-shape

text: network

text: is

text: used.

text: We

text: assume

text: that

text: there

text: are

text: n

text: samples

text: in

text: the

text: dataset,

text: and

text: they

text: are

text: evenly

text: distributed

text: over

text: K

text: workers.

text: In

text: worker

text: k,

text: there

text: are

text: n

text: samples.

text: It

text: is

text: satisﬁed

text: that

text: n

text: K

text: n

text: Different

text: from

text: k

text: k

text: sequential

text: dfSDCA,

text: we

text: split

text: the

text: update

text: of

text: dual

text: variable

text: and

text: primal

text: variable

text: into

text: different

text: nodes.

text: The

text: pseudocodes

text: of

text: Dis-dfSDCA

text: for

text: server

text: node

text: and

text: worker

text: nodes

text: are

text: presented

text: in

text: Algorithm

text: and

text: Algorithm

text: respectively.

text: sectioncolor

text: Update

text: Global

text: Variable

text: on

text: Server

text: w

text: R

text: The

text: up-to-date

text: global

text: variable

text: w

text: d

text: is

text: stored

text: and

text: updated

text: on

text: the

text: server.

text: Initially,

text: w

text: is

text: set

text: to

text: be

text: vector

text: zero.

text: At

text: the

text: beginning

text: of

text: each

text: iteration,

text: the

text: server

text: receives

text: gradient

text: message

text: v

text: from

text: arbitrary

text: worker

text: k

text: and

text: k

text: let

text: vt

text: v

text: Then

text: it

text: updates

text: the

text: global

text: variable

text: through:

text: k

text: equationcolor

text: ws,t

text: ηvt

text: Finally,

text: it

text: sends

text: the

text: up-to-date

text: global

text: variable

text: back

text: to

text: the

text: worker

text: k

text: for

text: further

text: computation.

text: Asynchronous

text: method

text: is

text: robust

text: to

text: straggler

text: problem

text: because

text: it

text: allows

text: for

text: updating

text: the

text: global

text: variable

text: when

text: receiving

text: from

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Algorithm 4 captioncolorDis-dfSDCA (Worker k) ∈ R × Initialize α d nk, η, H [k] repeat Receive global variable ws,d(t) from server; ← Initialize gradient message: v 0; k { · · · } | | Randomly select samples I from 1, , n where I = H; t k t for sample i in I do t Compute dual residue κ through: ← ∇ κ φ (ws,d(t)) + α ; i i Update local dual variable α through: ← − i α α ηλnκ; i i Update gradient message v through: ← k v v + κ; k k end for Send gradient message v to server; k until Termination well-known primal-dual relation in the equation (3) is always satisﬁed. The pseudocode of Dis-dfSDCA in worker node k is described in Algorithm 4. In Algorithm 4, we use vanilla dfSDCA in the worker which samples with uniform distribution. There are also other sampling techniques proposed to accelerate dfSDCA. As per the sampling strategy in [Shalev-Shwartz, 2015, He and Takácˇ, 2015, Shalev-Shwartz, 2016, Qu and Richtárik, 2015], there are three options: uniform sampling, importance sampling, and adaptive sampling. In importance sampling strategy [Shalev-Shwartz, 2016], it ﬁrst computes the ﬁxed probability distribution p using smoothness i parameter of each function φ , then selects samples following this probability. In adaptive sampling strategy i [He and Takácˇ, 2015], it computes the adaptive probability distribution p using dual residue κ for each i sample every iteration, then selects samples following this probability. Both of them are proved to admit faster convergence than vanilla dfSDCA with uniform sampling. We only consider the uniform sampling strategy, and analyze its corresponding convergence rate in our paper. However, other sampling techniques are straightforward to be applied to our distributed method. sectioncolor 4 Convergence Analysis In this section, we provide the theoretical convergence analysis of Dis-dfSDCA. For the case of convex losses φ , we prove that Dis-dfSDCA admits linear convergence rate. If losses φ are non-convex, we also i i prove linear convergence rate as long as the sum-of-non-convex objectives f is convex. We make the following assumptions for the primal problem (1) for further analysis. All of them are common assumptions in the theoretical analysis for the asynchronous stochastic methods. ∇ Assumption 1 (Lipschitz Constant) We assume φ is Lipschitz continuous, and there is Lipschitz constant ∀ ∈ R i L such that x, y d: equationcolor (cid:107)∇ − ∇ (cid:107) ≤ (cid:107) − (cid:107) φ (x) φ (y) L x y (9) i i 2 2 We can also know that P is (L + λ)-smooth: 6 ##LTLine## ##LTLine## ##LTLine##

text: Algorithm

label: paragraph

text: captioncolorDis-dfSDCA

text: (Worker

text: k)

text: R

text: Initialize

text: α

text: d

text: nk,

text: η,

text: H

text: [k]

text: repeat

text: Receive

text: global

text: variable

text: ws,d(t)

text: from

text: server;

text: Initialize

text: gradient

text: message:

text: v

text: k

text: Randomly

text: select

text: samples

text: I

text: from

text: n

text: where

text: I

text: H;

text: t

text: k

text: t

text: for

text: sample

text: i

text: in

text: I

text: do

text: t

text: Compute

text: dual

text: residue

text: κ

text: through:

text: κ

text: φ

text: (ws,d(t))

text: α

text: i

text: i

text: Update

text: local

text: dual

text: variable

text: α

text: through:

text: i

text: α

text: α

text: ηλnκ;

text: i

text: i

text: Update

text: gradient

text: message

text: v

text: through:

text: k

text: v

text: v

text: κ;

text: k

text: k

text: end

text: for

text: Send

text: gradient

text: message

text: v

text: to

text: server;

text: k

text: until

text: Termination

text: well-known

text: primal-dual

text: relation

text: in

text: the

text: equation

text: is

text: always

text: satisﬁed.

text: The

text: pseudocode

text: of

text: Dis-dfSDCA

text: in

text: worker

text: node

text: k

text: is

text: described

text: in

text: Algorithm

text: In

text: Algorithm

text: we

text: use

text: vanilla

text: dfSDCA

text: in

text: the

text: worker

text: which

text: samples

text: with

text: uniform

text: distribution.

text: There

text: are

text: also

text: other

text: sampling

text: techniques

text: proposed

text: to

text: accelerate

text: dfSDCA.

text: As

text: per

text: the

text: sampling

text: strategy

text: in

text: [Shalev-Shwartz,

text: He

text: and

text: Takácˇ,

text: Shalev-Shwartz,

text: Qu

text: and

text: Richtárik,

text: there

text: are

text: three

text: options:

text: uniform

text: sampling,

text: importance

text: sampling,

text: and

text: adaptive

text: sampling.

text: In

text: importance

text: sampling

text: strategy

text: [Shalev-Shwartz,

text: it

text: ﬁrst

text: computes

text: the

text: ﬁxed

text: probability

text: distribution

text: p

text: using

text: smoothness

text: i

text: parameter

text: of

text: each

text: function

text: φ

text: then

text: selects

text: samples

text: following

text: this

text: probability.

text: In

text: adaptive

text: sampling

text: strategy

text: i

text: [He

text: and

text: Takácˇ,

text: it

text: computes

text: the

text: adaptive

text: probability

text: distribution

text: p

text: using

text: dual

text: residue

text: κ

text: for

text: each

text: i

text: sample

text: every

text: iteration,

text: then

text: selects

text: samples

text: following

text: this

text: probability.

text: Both

text: of

text: them

text: are

text: proved

text: to

text: admit

text: faster

text: convergence

text: than

text: vanilla

text: dfSDCA

text: with

text: uniform

text: sampling.

text: We

text: only

text: consider

text: the

text: uniform

text: sampling

text: strategy,

text: and

text: analyze

text: its

text: corresponding

text: convergence

text: rate

text: in

text: our

text: paper.

text: However,

text: other

text: sampling

text: techniques

text: are

text: straightforward

text: to

text: be

text: applied

text: to

text: our

text: distributed

text: method.

text: sectioncolor

text: Convergence

text: Analysis

text: In

text: this

text: section,

text: we

text: provide

text: the

text: theoretical

text: convergence

text: analysis

text: of

text: Dis-dfSDCA.

text: For

text: the

text: case

text: of

text: convex

text: losses

text: φ

text: we

text: prove

text: that

text: Dis-dfSDCA

text: admits

text: linear

text: convergence

text: rate.

text: If

text: losses

text: φ

text: are

text: non-convex,

text: we

text: also

text: i

text: i

text: prove

text: linear

text: convergence

text: rate

text: as

text: long

text: as

text: the

text: sum-of-non-convex

text: objectives

text: f

text: is

text: convex.

text: We

text: make

text: the

text: following

text: assumptions

text: for

text: the

text: primal

text: problem

text: for

text: further

text: analysis.

text: All

text: of

text: them

text: are

text: common

text: assumptions

text: in

text: the

text: theoretical

text: analysis

text: for

text: the

text: asynchronous

text: stochastic

text: methods.

text: Assumption

text: (Lipschitz

text: Constant)

text: We

text: assume

text: φ

text: is

text: Lipschitz

text: continuous,

text: and

text: there

text: is

text: Lipschitz

text: constant

text: R

text: i

text: L

text: such

text: that

text: x,

text: y

text: d:

text: equationcolor

text: φ

text: (x)

text: φ

text: (y)

text: L

text: x

text: y

text: i

text: i

text: We

text: can

text: also

text: know

text: that

text: P

text: is

text: (L

text: λ)-smooth:

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: we have the following inequality: equationcolor (cid:88) (cid:88) − − T 1 T 1 E ≤ − E [Ct+1] (cid:88)(1 ηλH) [Ct] t=0 t=0 − T 1 ≤ E − [C ] + (1 ηλH)C (23) t 0 t=1 ≥ E ≤ − E (cid:3) Because C 0, then we complete the proof that [C ] (1 ηλH) [C ]. t T 0 ∇ Because P (w) is Lipschitz continuous, we know that: equationcolor − ∗ ≤ L + λ(cid:107) − ∗(cid:107) ≤ L + λ P (wt) P (w ) wt w 2 C (24) t 2 2 Theorem 2 We consider the outer iteration s, and write Ct as Cs,t. According to Algorithm 3, we know Cs+1,0 = Cs,T . Following Theorem 1 and applying (19) for S iterations, it is satisﬁed that: equationcolor E ≤ − E [C ] (1 ηλH)S [C ] (25) S,0 0,0 E − ∗ ≤ In particular, to achieve [P (wS(cid:18),0(cid:18)) P(cid:18)(w )] (cid:19)ε, it suf(cid:19)ﬁces to(cid:18)se(cid:19)t η(cid:19)= 4HLτ2+1λn+2L and equationcolor ≥ L 1 n 1 S O τ2 + + log (26) λ H H ε From Theorem 1 and 2, we know that our Dis-dfSDCA admits linear convergence if losses φ are convex. → ∞ i According to Theorem 2, we observe that τ affects the speed of our convergence, if τ , it may lead our algorithm to diverge. Therefore, it is important to keep τ within a reasonable bound. In our algorithm, τ is relevant to the number of workers and less than T . When we let H = 1 and τ = 0, S is relevant to O(L + n). λ It is compatible with the convergence analysis of sequential dfSDCA in [Shalev-Shwartz, 2015]. sectioncolor 4.2 Non-convex Case In this section, we assume that the losses φ are non-convex, while the sum-of-non-convex objectives f i is convex. We also prove that Dis-dfSDCA admits linear convergence rate for this case. Firstly, we get the following Lemma 2. ∗ ∗ −∇ ∗ Lemma 2 Let w be optimal solution to P (w), and α = φ (w ). Following the deﬁnition of A and B i i t t in Lemma 1, we prove that A and B are upper bounded: t+1 t+1 9 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: we

text: have

text: the

text: following

text: inequality:

text: equationcolor

text: T

text: T

text: E

text: E

text: ηλH)

text: [Ct]

text: T

text: E

text: [C

text: ηλH)C

text: t

text: E

text: E

text: Because

text: C

text: then

text: we

text: complete

text: the

text: proof

text: that

text: [C

text: ηλH)

text: [C

text: t

text: T

text: Because

text: P

text: (w)

text: is

text: Lipschitz

text: continuous,

text: we

text: know

text: that:

text: equationcolor

text: L

text: L

text: λ

text: P

text: (wt)

text: P

text: (w

text: wt

text: w

text: C

text: t

text: Theorem

text: We

text: consider

text: the

text: outer

text: iteration

text: s,

text: and

text: write

text: Ct

text: as

text: Cs,t.

text: According

text: to

text: Algorithm

text: we

text: know

text: Cs,T

text: Following

text: Theorem

text: and

text: applying

text: for

text: S

text: iterations,

text: it

text: is

text: satisﬁed

text: that:

text: equationcolor

text: E

text: E

text: [C

text: ηλH)S

text: [C

text: E

text: In

text: particular,

text: to

text: achieve

text: [P

text: it

text: and

text: equationcolor

text: L

text: n

text: S

text: O

text: τ2

text: log

text: λ

text: H

text: H

text: ε

text: From

text: Theorem

text: and

text: we

text: know

text: that

text: our

text: Dis-dfSDCA

text: admits

text: linear

text: convergence

text: if

text: losses

text: φ

text: are

text: convex.

text: i

text: According

text: to

text: Theorem

text: we

text: observe

text: that

text: τ

text: affects

text: the

text: speed

text: of

text: our

text: convergence,

text: if

text: τ

text: it

text: may

text: lead

text: our

text: algorithm

text: to

text: diverge.

text: Therefore,

text: it

text: is

text: important

text: to

text: keep

text: τ

text: within

text: a

text: reasonable

text: bound.

text: In

text: our

text: algorithm,

text: τ

text: is

text: relevant

text: to

text: the

text: number

text: of

text: workers

text: and

text: less

text: than

text: T

text: When

text: we

text: let

text: H

text: and

text: τ

text: S

text: is

text: relevant

text: to

text: O(L

text: n).

text: λ

text: It

text: is

text: compatible

text: with

text: the

text: convergence

text: analysis

text: of

text: sequential

text: dfSDCA

text: in

text: [Shalev-Shwartz,

text: sectioncolor

text: Non-convex

text: Case

text: In

text: this

text: section,

text: we

text: assume

text: that

text: the

text: losses

text: φ

text: are

text: non-convex,

text: while

text: the

text: sum-of-non-convex

text: objectives

text: f

text: i

text: is

text: convex.

text: We

text: also

text: prove

text: that

text: Dis-dfSDCA

text: admits

text: linear

text: convergence

text: rate

text: for

text: this

text: case.

text: Firstly,

text: we

text: get

text: the

text: following

text: Lemma

text: Lemma

text: Let

text: w

text: be

text: optimal

text: solution

text: to

text: P

text: (w),

text: and

text: α

text: φ

text: (w

text: Following

text: the

text: deﬁnition

text: of

text: A

text: and

text: B

text: i

text: i

text: t

text: t

text: in

text: Lemma

text: we

text: prove

text: that

text: A

text: and

text: B

text: are

text: upper

text: bounded:

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 12 FLORIAN FUNKE AND DAWID KIELAK → (1) Let f : X Y be a G-homotopy equivalence of ﬁnite free G-CW-complexes. Suppose that X or Y is L2-acyclic. Then both X and Y are L2-acyclic and we get N − N ρ(2)(X; (G)) ρ(2)(Y ; (G)) = ζ(τ(f)) u u ∈ where τ(f) Wh(G) is the Whitehead torsion of f and → ζ : Wh(G) Whw(G) is the obvious homomorphism. (2) Let X (cid:47)(cid:47) X 0 1 j0 j1 (cid:15)(cid:15) (cid:33)(cid:33) (cid:15)(cid:15) X j2 (cid:47)(cid:47) X 2 be a pushout of ﬁnite CW-complexes such that the top horizontal map is cellular, the left arrow is an inclusion of CW-complexes, and X carries the CW-structure coming from the ones on X , i = 0, 1, 2. Suppose that X for i∈ i i = 0, 1, 2 is L2-acyclic and that for any x X the induced homomorphism (cid:101) → (cid:101) i (cid:101) i (cid:101) π (X , x ) π (X, j (x )) is injective. Then X is L2-acyclic and we have 1 i i 1 i i − ρ(2)(X) = (j )∗(ρ(2)(X )) + (j )∗(ρ(2)(X )) (j )∗(ρ(2)(X )) u 1 u 1 2 u 2 0 u 0 → (3) Let p: X Y be a ﬁnite covering of ﬁnite connected CW-complexes. Let ∗ → p : Whw(π (Y )) Whw(π (X)) be the homomorphism induced by restric- 1 → 1 tion with π (p): π (X) π (Y ). Then X is L2-acyclic if and only if Y is 1 1 (cid:101)1 (cid:101) L2-acyclic and in this case we have ∗ ρ(2)(X) = p (ρ(2)(Y )) u u Next we apply this invariant to the groups we are interested in. Deﬁnition 2.23. Let G be a group with a ﬁnite model for its classifying space → BG, and let g: G G be a monomorphism. Let T be the mapping torus of the → ∗ −p→ −q→ Z realisation Bg: BG BG. Given a factorisation G Γ of the induced → g epimorphism, denote by T T the Γ-covering corresponding to p. Suppose that the classical Whitehead group Wh(Γ) of Γ is trivial. Then T is L2-acyclic [Lu¨c1, Theorem 1.39], and Lemma 2.22 (1) implies that we get a well-deﬁned invariant ∗ N ∈ ρ(2)(G , p) := ρ(2)(T; (Γ)) Whw(Γ) u g u which only depends on G, g and p, but not on the realisations. If p = id , then we ∗ ∗ G write ρ(2)(G ) = ρ(2)(G , id ). u g u g G ∗ A classical theorem of Waldhausen [Wal, Theorem 19.4] says that Wh(F ) = 0, ∗ n g ∗ so that we may apply this in particular to the special case where Γ = G = F , g n g and p = id. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: FLORIAN

text: FUNKE

text: AND

text: DAWID

text: KIELAK

label: list

text: Let

text: f

text: X

text: Y

text: be

text: a

text: G-homotopy

text: equivalence

text: of

text: ﬁnite

text: free

text: G-CW-complexes.

text: Suppose

text: that

text: X

text: or

text: Y

text: is

text: Then

text: both

text: X

text: and

text: Y

text: are

text: and

text: we

text: get

text: N

text: N

text: (G))

text: (G))

text: ζ(τ(f))

text: u

text: u

text: where

text: τ(f)

text: Wh(G)

text: is

text: the

text: Whitehead

text: torsion

text: of

text: f

text: and

text: ζ

text: Wh(G)

text: Whw(G)

text: is

text: the

text: obvious

text: homomorphism.

text: Let

text: X

font: default

text: X

text: X

text: X

text: be

text: a

text: pushout

text: of

text: ﬁnite

text: CW-complexes

text: such

text: that

text: the

text: top

text: horizontal

text: map

text: is

text: cellular,

text: the

text: left

text: arrow

text: is

text: an

text: inclusion

text: of

text: CW-complexes,

text: and

text: X

text: carries

text: the

text: CW-structure

text: coming

text: from

text: the

text: ones

text: on

text: X

text: i

text: Suppose

text: that

text: X

text: for

text: i∈

text: i

text: i

text: is

text: and

text: that

text: for

text: any

text: x

text: X

text: the

text: induced

text: homomorphism

text: i

text: i

text: π

text: (X

text: x

text: π

text: (X,

text: j

text: (x

text: is

text: injective.

text: Then

text: X

text: is

text: and

text: we

text: have

text: i

text: i

text: i

text: i

text: (j

text: (j

text: (j

text: u

text: u

text: u

text: u

text: Let

text: p:

text: X

text: Y

text: be

text: a

text: ﬁnite

text: covering

text: of

text: ﬁnite

text: connected

text: CW-complexes.

text: Let

text: p

text: Whw(π

text: (Y

text: Whw(π

text: (X))

text: be

text: the

text: homomorphism

text: induced

text: by

text: restric-

text: tion

text: with

text: π

text: (p):

text: π

text: (X)

text: π

text: (Y

text: Then

text: X

text: is

text: if

text: and

text: only

text: if

text: Y

text: is

text: and

text: in

text: this

text: case

text: we

text: have

text: p

text: u

text: u

text: Next

text: we

text: apply

text: this

text: invariant

text: to

text: the

text: groups

text: we

text: are

text: interested

text: in.

text: Deﬁnition

text: Let

text: G

text: be

text: a

text: group

text: with

text: a

text: ﬁnite

text: model

text: for

text: its

text: classifying

text: space

text: BG,

text: and

text: let

text: g:

text: G

text: G

text: be

text: a

text: monomorphism.

text: Let

text: T

text: be

text: the

text: mapping

text: torus

text: of

text: the

text: −p→

text: −q→

text: Z

text: realisation

text: Bg:

text: BG

text: BG.

text: Given

text: a

text: factorisation

text: G

text: Γ

text: of

text: the

text: induced

text: g

text: epimorphism,

text: denote

text: by

text: T

text: T

text: the

text: Γ-covering

text: corresponding

text: to

text: p.

text: Suppose

text: that

text: the

text: classical

text: Whitehead

text: group

text: Wh(Γ)

text: of

text: Γ

text: is

text: trivial.

text: Then

text: T

text: is

text: Theorem

text: and

text: Lemma

text: implies

text: that

text: we

text: get

text: a

text: well-deﬁned

text: invariant

text: N

text: p)

text: (Γ))

text: Whw(Γ)

text: u

text: g

text: u

text: which

text: only

text: depends

text: on

text: G,

text: g

text: and

text: p,

text: but

text: not

text: on

text: the

text: realisations.

text: If

text: p

text: id

text: then

text: we

text: G

text: write

text: id

text: u

text: g

text: u

text: g

text: G

text: A

text: classical

text: theorem

text: of

text: Waldhausen

text: [Wal,

text: Theorem

text: says

text: that

text: Wh(F

text: n

text: g

text: so

text: that

text: we

text: may

text: apply

text: this

text: in

text: particular

text: to

text: the

text: special

text: case

text: where

text: Γ

text: G

text: F

text: g

text: n

text: g

text: and

text: p

text: id.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Z ALEXANDER AND THURSTON NORMS, AND THE BNS INVARIANTS FOR Fn-BY- 15 Z Z Now let A be any ﬁnitely generated H-module. Since H is Noetherian, we may pick a presentation ZHr −M→ ZHs → A → 0 − × − The elementary ideal I(A) of A is the ideal generated by all (s 1) (s 1)-minors of the matrix M. The Alexander ideal of X is I(A(X)), and the Alexander polynomial ∆ is deﬁned as the greatest common divisor of the elements in I(A(X)). This X Z invariant is well-deﬁned∼up t−o mZultipl{i±catio| n b∈y u}nits in H and we will view it as an element in Whw(H) = T 1( H)/ h h H , where this isomorphism comes from Example 2.21. Finally, the Alexander polytope P (X) is deﬁned as the image A of ∆ under the polytope homomorphism X P → P : Whw(H) (H) T The Alexander module and hence the Alexander polynomial depend only on the fundamental group, and we deﬁne ∆ := ∆ and P (G) := P (X) for any G X A A space with π (X) = G. This applies in particular to descending HNN extensions 1 of ﬁnitely generated groups. We emphasise that the Alexander polynomial is accessible from a ﬁnite presen- Z tation of G: We can take X to be the presentation complex, so that the H-chain complex of the pair (X, x) looks like 0 → ZHr −F→ ZHs → C (X)/C (x) = 0 0 0 where C denotes the group of zero chains and F contains the Fox derivatives 0 associated to the given presentation (see ?? ). Thus A(X) is the cokernel of the map F, which immediately gives a ﬁnite presentation of A(X) as desired. ⊆ ⊗ R (cid:107) · (cid:107) R ∼ Given a polytope P H Z , we obtain a seminorm on Hom(H, ) = ⊗ R R P HomR(H Z , ) by putting (cid:107) (cid:107) { − | ∈ } ϕ := sup ϕ(x) ϕ(y) x, y P P (cid:107) · (cid:107) ⊗ R It is clear that remains unchanged when P is translated within H Z . P Moreover, if Q is another such polytope, then we get for the Minkowski sum (cid:107) (cid:107) (cid:107) (cid:107) (cid:107) (cid:107) ϕ = ϕ + ϕ P+Q P Q Thus we get a homomorphism of groups P → R R − (cid:55)→ (cid:55)→ (cid:107) (cid:107) − (cid:107) (cid:107) N: (H) Map(Hom(H, ), ), P Q (ϕ ϕ ϕ ) T P Q R R R where Map(Hom(H, ), ) denotes the group of continuous maps to with the − pointwise addition. In general, N(P Q) does not need to be a seminorm. The following deﬁnition is due to McMullen [McM]. Deﬁnition 2.25. If G is a ﬁnitely generated group, then the Alexander norm (cid:107) · (cid:107) R → R : H1(G; ) A is deﬁned as the image of the Alexander polytope P (G) under N. A If G is the fundamental group of a compact connected orientable 3-manifold M, R R the ﬁrst cohomology H1(M; ) = H1(G; ) carries another well-known seminorm (cid:107)·(cid:107) , called the Thurston seminorm. It was ﬁrst deﬁned and examined by Thurston T ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Z

text: ALEXANDER

text: AND

text: THURSTON

text: NORMS,

text: AND

text: THE

text: BNS

text: INVARIANTS

text: FOR

text: Fn-BY-

text: Z

text: Z

text: Now

text: let

text: A

text: be

text: any

text: ﬁnitely

text: generated

text: H-module.

text: Since

text: H

text: is

text: Noetherian,

text: we

text: may

text: pick

text: a

text: presentation

text: ZHr

text: −M→

text: ZHs

text: A

text: The

text: elementary

text: ideal

text: I(A)

text: of

text: A

text: is

text: the

text: ideal

text: generated

text: by

text: all

text: (s

text: (s

text: of

text: the

text: matrix

text: M.

text: The

text: Alexander

text: ideal

text: of

text: X

text: is

text: I(A(X)),

text: and

text: the

text: Alexander

text: polynomial

text: is

text: deﬁned

text: as

text: the

text: greatest

text: common

text: divisor

text: of

text: the

text: elements

text: in

text: I(A(X)).

text: This

text: X

text: Z

text: invariant

text: is

text: well-deﬁned∼up

text: t−o

text: mZultipl{i±catio|

text: n

text: b∈y

text: u}nits

text: in

text: H

text: and

text: we

text: will

text: view

text: it

text: as

text: an

text: element

text: in

text: Whw(H)

text: T

text: H)/

text: h

text: h

text: H

text: where

text: this

text: isomorphism

text: comes

text: from

text: Example

text: Finally,

text: the

text: Alexander

text: polytope

text: P

text: (X)

text: is

text: deﬁned

text: as

text: the

text: image

text: A

text: of

text: under

text: the

text: polytope

text: homomorphism

text: X

text: P

text: P

text: Whw(H)

text: (H)

text: T

text: The

text: Alexander

text: module

text: and

text: hence

text: the

text: Alexander

text: polynomial

text: depend

text: only

text: on

text: the

text: fundamental

text: group,

text: and

text: we

text: deﬁne

text: and

text: P

text: (G)

text: P

text: (X)

text: for

text: any

text: G

text: X

text: A

text: A

text: space

text: with

text: π

text: (X)

text: G.

text: This

text: applies

text: in

text: particular

text: to

text: descending

text: HNN

text: extensions

text: of

text: ﬁnitely

text: generated

text: groups.

text: We

text: emphasise

text: that

text: the

text: Alexander

text: polynomial

text: is

text: accessible

text: from

text: a

text: ﬁnite

text: presen-

text: Z

text: tation

text: of

text: G:

text: We

text: can

text: take

text: X

text: to

text: be

text: the

text: presentation

text: complex,

text: so

text: that

text: the

text: H-chain

text: complex

text: of

text: the

text: pair

text: (X,

text: x)

text: looks

text: like

text: ZHr

text: −F→

text: ZHs

text: C

text: (X)/C

text: (x)

text: where

text: C

text: denotes

text: the

text: group

text: of

text: zero

text: chains

text: and

text: F

text: contains

text: the

text: Fox

text: derivatives

text: associated

text: to

text: the

text: given

text: presentation

text: (see

text: Thus

text: A(X)

text: is

text: the

text: cokernel

text: of

text: the

text: map

text: F,

text: which

text: immediately

text: gives

text: a

text: ﬁnite

text: presentation

text: of

text: A(X)

text: as

text: desired.

text: R

text: R

text: Given

text: a

text: polytope

text: P

text: H

text: Z

text: we

text: obtain

text: a

text: seminorm

text: on

text: Hom(H,

text: R

text: R

text: P

text: HomR(H

text: Z

text: by

text: putting

text: ϕ

text: sup

text: ϕ(x)

text: ϕ(y)

text: x,

text: y

text: P

text: P

text: R

text: It

text: is

text: clear

text: that

text: remains

text: unchanged

text: when

text: P

text: is

text: translated

text: within

text: H

text: Z

text: P

text: Moreover,

text: if

text: Q

text: is

text: another

text: such

text: polytope,

text: then

text: we

text: get

text: for

text: the

text: Minkowski

text: sum

text: ϕ

text: ϕ

text: ϕ

text: P+Q

text: P

text: Q

text: Thus

text: we

text: get

text: a

text: homomorphism

text: of

text: groups

text: P

text: R

text: R

text: N:

text: (H)

text: Map(Hom(H,

text: P

text: Q

text: (ϕ

text: ϕ

text: ϕ

text: T

text: P

text: Q

text: R

text: R

text: R

text: where

text: Map(Hom(H,

text: denotes

text: the

text: group

text: of

text: continuous

text: maps

text: to

text: with

text: the

text: pointwise

text: addition.

text: In

text: general,

text: N(P

text: Q)

text: does

text: not

text: need

text: to

text: be

text: a

text: seminorm.

text: The

text: following

text: deﬁnition

text: is

text: due

text: to

text: McMullen

text: [McM].

text: Deﬁnition

text: If

text: G

text: is

text: a

text: ﬁnitely

text: generated

text: group,

text: then

text: the

text: Alexander

text: norm

text: R

text: R

text: A

text: is

text: deﬁned

text: as

text: the

text: image

text: of

text: the

text: Alexander

text: polytope

text: P

text: (G)

text: under

text: N.

text: A

text: If

text: G

text: is

text: the

text: fundamental

text: group

text: of

text: a

text: compact

text: connected

text: orientable

text: M,

text: R

text: R

text: the

text: ﬁrst

text: cohomology

text: carries

text: another

text: well-known

text: seminorm

text: called

text: the

text: Thurston

text: seminorm.

text: It

text: was

text: ﬁrst

text: deﬁned

text: and

text: examined

text: by

text: Thurston

text: T

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 16 FLORIAN FUNKE AND DAWID KIELAK [Thu] and is closely related to the question of whether (and how) M ﬁbres over the circle. One of the main results of [FL3, Theorem 3.27] is the following. (cid:54) × Theorem 2.2(cid:102)6. Let M = S1 D2 be a compact connected aspherical 3-manifold such that π (M) satisﬁes the Atiyah Conjecture. Then the image of the L2-torsion 1 (cid:107) · (cid:107) polytope P (M; π (M)) under N is the Thurston seminorm . L2 1 T Motivated by this result, we make the following deﬁnition. ∗ → Deﬁnition 2.27. Let G = F for a monomorphism g: F F . We call the im- n g ∈ P n n age of the L2-torsion polytope P (G) (H (G) ) as deﬁned in Deﬁnition 2.24 L2 T 1 f under N the Thurston seminorm on G and denote it by (cid:107) · (cid:107) R → R : H1(G; ) T In order for this deﬁnition to make sense, we need to argue that HNN extensions of free groups satisfy the Atiyah Conjecture. To this end, observe that G ﬁts into the extension → (cid:104)(cid:104) (cid:105)(cid:105) → → Z → 0 F G 0 n By the work of Linnell (see [Lu¨c1, Theorem 10.19]), we know that the Atiyah conjecture holds for F , is stable under taking directed unions, and so holds for (cid:104)(cid:104) (cid:105)(cid:105) n F , and is stable under taking extensions with elementary amenable quotients, n and thus holds for G. The proof that the terminology seminorm in the above deﬁnition is justiﬁed needs to be postponed to Corollary 3.5. In [Har1] Harvey generalised McMullen’s work and deﬁned higher Alexander norms R → R δ : H1(G; ) k (cid:107) · (cid:107) for any ﬁnitely presented group G, where δ = . While we do not need 0 A the precise deﬁnition of δ , the following ingredient will be needed throughout the k paper. Deﬁnition 2.28. The rational derived series ⊇ ⊇ ⊇ · · · G = G0 G1 G2 r r r of a group G is inductively deﬁned with Gk+1 being the kernel of the projection r → Gk H (Gk) r 1 r f Note that the quotients Γ := G/Gk+1 are torsion free and solvable, and so k r Wh(Γ ) = 0 k since solvable groups satisfy the K-theoretic Farrell–Jones Conjecture by a result of Wegner [Weg]. Moreover, Γ satisﬁes the Atiyah Conjecture by the work of k ∗ Linnell (see [Lu¨c1, Theorem 10.19]). Thus, given G = F , Deﬁnition 2.23 and n g Deﬁnition 2.24 produce an L2-torsion polytope P (G, p ) for the projections L2 k → p : G Γ k k The next result is not explicitly stated in [FL2, FL3], but we will indicate how it directly follows from it.

text: FLORIAN

text: FUNKE

text: AND

text: DAWID

text: KIELAK

text: [Thu]

text: and

text: is

text: closely

text: related

text: to

text: the

text: question

text: of

text: whether

text: (and

text: how)

text: M

text: ﬁbres

text: over

text: the

text: circle.

text: One

text: of

text: the

text: main

text: results

text: of

text: Theorem

text: is

text: the

text: following.

text: Theorem

text: Let

text: M

text: be

text: a

text: compact

text: connected

text: aspherical

text: such

text: that

text: π

text: (M)

text: satisﬁes

text: the

text: Atiyah

text: Conjecture.

text: Then

text: the

text: image

text: of

text: the

text: polytope

text: P

text: (M;

text: π

text: (M))

text: under

text: N

text: is

text: the

text: Thurston

text: seminorm

text: T

text: Motivated

text: by

text: this

text: result,

text: we

text: make

text: the

text: following

text: deﬁnition.

text: Deﬁnition

text: Let

text: G

text: F

text: for

text: a

text: monomorphism

text: g:

text: F

text: F

text: We

text: call

text: the

text: im-

text: n

text: g

text: P

text: n

text: n

text: age

text: of

text: the

text: polytope

text: P

text: (G)

text: (H

text: (G)

text: as

text: deﬁned

text: in

text: Deﬁnition

text: T

text: f

text: under

text: N

text: the

text: Thurston

text: seminorm

text: on

text: G

text: and

text: denote

text: it

text: by

text: R

text: R

text: T

text: In

text: order

text: for

text: this

text: deﬁnition

text: to

text: make

text: sense,

text: we

text: need

text: to

text: argue

text: that

text: HNN

text: extensions

text: of

text: free

text: groups

text: satisfy

text: the

text: Atiyah

text: Conjecture.

text: To

text: this

text: end,

text: observe

text: that

text: G

text: ﬁts

text: into

text: the

text: extension

text: Z

text: F

text: G

text: n

text: By

text: the

text: work

text: of

text: Linnell

text: (see

text: Theorem

text: we

text: know

text: that

text: the

text: Atiyah

text: conjecture

text: holds

text: for

text: F

text: is

text: stable

text: under

text: taking

text: directed

text: unions,

text: and

text: so

text: holds

text: for

text: n

text: F

text: and

text: is

text: stable

text: under

text: taking

text: extensions

text: with

text: elementary

text: amenable

text: quotients,

text: n

text: and

text: thus

text: holds

text: for

text: G.

text: The

text: proof

text: that

text: the

text: terminology

text: seminorm

text: in

text: the

text: above

text: deﬁnition

text: is

text: justiﬁed

text: needs

text: to

text: be

text: postponed

text: to

text: Corollary

text: In

text: Harvey

text: generalised

text: McMullen’s

text: work

text: and

text: deﬁned

text: higher

text: Alexander

text: norms

text: R

text: R

text: δ

text: k

text: for

text: any

text: ﬁnitely

text: presented

text: group

text: G,

text: where

text: δ

text: While

text: we

text: do

text: not

text: need

text: A

text: the

text: precise

text: deﬁnition

text: of

text: δ

text: the

text: following

text: ingredient

text: will

text: be

text: needed

text: throughout

text: the

text: k

text: paper.

text: Deﬁnition

text: The

text: rational

text: derived

text: series

text: G

text: r

text: r

text: r

text: of

text: a

text: group

text: G

text: is

text: inductively

text: deﬁned

text: with

text: being

text: the

text: kernel

text: of

text: the

text: projection

text: r

text: Gk

text: H

text: (Gk)

text: r

text: r

text: f

text: Note

text: that

text: the

text: quotients

text: Γ

text: are

text: torsion

text: free

text: and

text: solvable,

text: and

text: so

text: k

text: r

text: Wh(Γ

text: k

text: since

text: solvable

text: groups

text: satisfy

text: the

text: K-theoretic

text: Farrell–Jones

text: Conjecture

text: by

text: a

text: result

text: of

text: Wegner

text: [Weg].

text: Moreover,

text: Γ

text: satisﬁes

text: the

text: Atiyah

text: Conjecture

text: by

text: the

text: work

text: of

text: k

text: Linnell

text: (see

text: Theorem

text: Thus,

text: given

text: G

text: F

text: Deﬁnition

text: and

text: n

text: g

text: Deﬁnition

text: produce

text: an

text: polytope

text: P

text: (G,

text: p

text: for

text: the

text: projections

text: k

text: p

text: G

text: Γ

text: k

text: k

text: The

text: next

text: result

text: is

text: not

text: explicitly

text: stated

text: in

text: but

text: we

text: will

text: indicate

text: how

text: it

text: directly

text: follows

text: from

text: it.


text: 20 FLORIAN FUNKE AND DAWID KIELAK In order to start computing, we introduce as a last tool Fox derivatives (deﬁned by Fox in [Fox]). Deﬁnition 2.40. Let F be a free group generated by s , . . . , s , and let w be a { n } 1 n ∈ Z word in the alphabet s , . . . , s . We deﬁne the Fox derivative ∂w G of w with respect to s induct1ively: wne write w = vt where t is one of th∂esigenerators or i  their inverses, and v is strictly shorter than w, and set (cid:54)∈ { − }  ∂v t s , s 1 ∂w ∂si i i = ∂v + v if t = s ∂si ∂∂svi − w t = si−1 ∂si ∈i This deﬁnition readily extends ﬁrst to elements w F , and then linearly to ele- Z Z → Z n ments of F , forming a map ∂w : F F . n ∂si n n The following equation is known as the fundamental formula of Fox calculus [Fox, Formula (2.3)]. ∈ Proposition 2.41. Let w (cid:88)F be any word, and let s , . . . , s be a generating set n 1 n of F . Then we have n n ∂w · − − (1 s ) = 1 w ∂s i i i=1 3. The invariants for descending HNN extensions of free groups In this section we describe the Alexander polynomial and the universal L2-torsion in more explicit terms for descending HNN extensions of ﬁnitely generated free groups. The computations in this chapter follow from the general properties of the invariants, but we thought it worthwhile to collect them here in order to emphasise that a close connection between the invariants should not come as a complete surprise. Let us ﬁrst observe the following. ∗ Lemma 3.1. Let G be a descending HNN extension G = F . Pick a ﬁnite clas- → n g sifying space BF for F , and a realisation Bg: BF BF . Then the mapping n n n n torus T of Bg is a classifying space for G. Bg (cid:103) Proof. It is well-known th→at π1(TB(cid:103)g) = G. For the higher homotopy groups we observe that any map C T with compact domain C can be homotoped to a Bg (cid:3) map whose image lies in a copy of BF , which is contractible. n × We will always view an m n-matrix A over a ring R as an R-homomorphism → Rm Rn by right-multiplication since we prefer working with left-modules. → ∗ For a monomorphism g: F F , let G = F , and let s , . . . , s denote n (cid:18) n (cid:19) n g 1 n generators of F , and t the stable letter of the HNN extension. The Fox matrix of n g is F(g) = ∂g(si) n ∈ ZF n×n ∂s n j i,j=1 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: FLORIAN

text: FUNKE

text: AND

text: DAWID

text: KIELAK

text: In

text: order

text: to

text: start

text: computing,

text: we

text: introduce

text: as

text: a

text: last

text: tool

text: Fox

text: derivatives

text: (deﬁned

text: by

text: Fox

text: in

text: [Fox]).

text: Deﬁnition

text: Let

text: F

text: be

text: a

text: free

text: group

text: generated

text: by

text: s

text: s

text: and

text: let

text: w

text: be

text: a

text: n

text: n

text: Z

text: word

text: in

text: the

text: alphabet

text: s

text: s

text: We

text: deﬁne

text: the

text: Fox

text: derivative

text: ∂w

text: G

text: of

text: w

text: with

text: respect

text: to

text: s

text: wne

text: write

text: w

text: vt

text: where

text: t

text: is

text: one

text: of

text: th∂esigenerators

text: or

text: i

text: their

text: inverses,

text: and

text: v

text: is

text: strictly

text: shorter

text: than

text: w,

text: and

text: set

text: ∂v

text: t

text: s

text: s

text: ∂w

text: ∂si

text: i

text: i

text: ∂v

text: v

text: if

text: t

text: s

text: ∂si

text: ∂∂svi

text: w

text: t

text: ∂si

text: ∈i

text: This

text: deﬁnition

text: readily

text: extends

text: ﬁrst

text: to

text: elements

text: w

text: F

text: and

text: then

text: linearly

text: to

text: ele-

text: Z

text: Z

text: Z

text: n

text: ments

text: of

text: F

text: forming

text: a

text: map

text: ∂w

text: F

text: F

text: n

text: ∂si

text: n

text: n

text: The

text: following

text: equation

text: is

text: known

text: as

text: the

text: fundamental

text: formula

text: of

text: Fox

text: calculus

text: [Fox,

text: Formula

text: Proposition

text: Let

text: w

text: be

text: any

text: word,

text: and

text: let

text: s

text: s

text: be

text: a

text: generating

text: set

text: n

text: n

text: of

text: F

text: Then

text: we

text: have

text: n

text: n

text: ∂w

text: s

text: w

text: ∂s

text: i

text: i

text: The

text: invariants

text: for

text: descending

text: HNN

text: extensions

text: of

text: free

text: groups

text: In

text: this

text: section

text: we

text: describe

text: the

text: Alexander

text: polynomial

text: and

text: the

text: universal

text: in

text: more

text: explicit

text: terms

text: for

text: descending

text: HNN

text: extensions

text: of

text: ﬁnitely

text: generated

text: free

text: groups.

text: The

text: computations

text: in

text: this

text: chapter

text: follow

text: from

text: the

text: general

text: properties

text: of

text: the

text: invariants,

text: but

text: we

text: thought

text: it

text: worthwhile

text: to

text: collect

text: them

text: here

text: in

text: order

text: to

text: emphasise

text: that

text: a

text: close

text: connection

text: between

text: the

text: invariants

text: should

text: not

text: come

text: as

text: a

text: complete

text: surprise.

text: Let

text: us

text: ﬁrst

text: observe

text: the

text: following.

text: Lemma

text: Let

text: G

text: be

text: a

text: descending

text: HNN

text: extension

text: G

text: F

text: Pick

text: a

text: ﬁnite

text: clas-

text: n

text: g

text: sifying

text: space

text: BF

text: for

text: F

text: and

text: a

text: realisation

text: Bg:

text: BF

text: BF

text: Then

text: the

text: mapping

text: n

text: n

text: n

text: n

text: torus

text: T

text: of

text: Bg

text: is

text: a

text: classifying

text: space

text: for

text: G.

text: Bg

text: Proof.

text: It

text: is

text: well-known

text: th→at

text: G.

text: For

text: the

text: higher

text: homotopy

text: groups

text: we

text: observe

text: that

text: any

text: map

text: C

text: T

text: with

text: compact

text: domain

text: C

text: can

text: be

text: homotoped

text: to

text: a

text: Bg

text: map

text: whose

text: image

text: lies

text: in

text: a

text: copy

text: of

text: BF

text: which

text: is

text: contractible.

text: n

text: We

text: will

text: always

text: view

text: an

text: m

text: n-matrix

text: A

text: over

text: a

text: ring

text: R

text: as

text: an

text: R-homomorphism

text: Rm

text: Rn

text: by

text: right-multiplication

text: since

text: we

text: prefer

text: working

text: with

text: left-modules.

text: For

text: a

text: monomorphism

text: g:

text: F

text: F

text: let

text: G

text: F

text: and

text: let

text: s

text: s

text: denote

text: n

text: n

text: n

text: g

text: n

text: generators

text: of

text: F

text: and

text: t

text: the

text: stable

text: letter

text: of

text: the

text: HNN

text: extension.

text: The

text: Fox

text: matrix

text: of

text: n

text: g

text: is

text: F(g)

text: ∂g(si)

text: n

text: ZF

text: n×n

text: ∂s

text: n

text: j

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Z ALEXANDER AND THURSTON NORMS, AND THE BNS INVARIANTS FOR Fn-BY- 35 The main result of Cashen-Levitt [CL, Theorem 1.1] reads as follows. (cid:111) Z (cid:62) Theorem 6.2. Let G = F with n 2 and g polynomially growing. Then n ∈g (cid:114) there are elements t , ..., t − G F such that 1 n 1 n − { ∈ | (cid:54) (cid:54) (cid:54) − } Σ(G) = Σ(G) = [ϕ] S(G) ϕ(t ) = 0 for all 1 i n 1 i Motivated by this, we prove (cid:111) Z (cid:62) Theorem 6.3. Let G = F with n 1 and g a UPG automorphism. Denote → n g by p : G Γ = G/Gk+1 the projection, where Gk denotes the k-th subgroup of k k r r the rational derived series. For simplicity write Γ∞ for G and p∞ for id . ∈ (cid:114) G Then there are elements t , ..., t − G F which can be chosen to coincide 1 n 1 ∈ N ∪n{∞} with those of Theorem 6.2 such that for k (cid:88) − (6.1) ρ(2)(G; p ) = − n 1 [ZΓ pk−(1→−ti) ZΓ ] u k k k i=1 (cid:88) In particular, − n 1 − ∈ P P (G; p ) = P(1 t ) (H (G) ) L2 k i 1 f i=1 is a polytope (and not merely a diﬀerence of polytopes) which is independent of ∈ N ∪ {∞} k . Combining the previous two results, we see that the BNS-invariant of UPG automorphisms is easily determined by their L2-torsion polytope. More precisely, we have the following analogue of [FT, Theorem 1.1]. (cid:111) Z (cid:62) Corollary 6.4. Let G = F with n 2 and g a UPG automorphism. Let ∈ R ∈ n g P ϕ H1(G; ). Then [ϕ] Σ(G) if and only if F (P (G)) = 0 in (H (G) ). ϕ L2 T 1 f (cid:88) Proof. Any one-dimensional face of − n 1 − P (G) = P(1 t ) L2 i i=1 − (cid:54) (cid:54) − contains a translate of P(1 t ) for some 1 i n 1. i (cid:54) Now F (P (G)) = 0 if and only if F (P (G)) contains a one-dimensional face, ϕ L2 − ϕ L2 i.e. a translate of P(1 t ) for some i. This is equivalent to ϕ(t ) = 0 for some i, i ∈ i (cid:3) which by Theorem 6.2 is equivalent to [ϕ] / Σ(G). Remark 6.5. We suspect Theorem 6.3 to hold as well for polynomially growing automorphisms. It is well-known that any polynomially growing automorphism has a power that is UPG, see Bestvina–Feighn–Handel’s [BFH, Corollary 5.7.6]. Thus, in order to reduce Theorem 6.3 for polynomially growing automorphisms to

text: Z

text: ALEXANDER

text: AND

text: THURSTON

text: NORMS,

text: AND

text: THE

text: BNS

text: INVARIANTS

text: FOR

text: Fn-BY-

text: The

text: main

text: result

text: of

text: Cashen-Levitt

text: [CL,

text: Theorem

text: reads

text: as

text: follows.

text: Z

text: Theorem

text: Let

text: G

text: F

text: with

text: n

text: and

text: g

text: polynomially

text: growing.

text: Then

text: n

text: ∈g

text: there

text: are

text: elements

text: t

text: t

text: G

text: F

text: such

text: that

text: n

text: n

text: Σ(G)

text: Σ(G)

text: [ϕ]

text: S(G)

text: ϕ(t

text: for

text: all

text: i

text: n

text: i

text: Motivated

text: by

text: this,

text: we

text: prove

text: Z

text: Theorem

text: Let

text: G

text: F

text: with

text: n

text: and

text: g

text: a

text: UPG

text: automorphism.

text: Denote

text: n

text: g

text: by

text: p

text: G

text: Γ

text: the

text: projection,

text: where

text: Gk

text: denotes

text: the

text: k-th

text: subgroup

text: of

text: k

text: k

text: r

text: r

text: the

text: rational

text: derived

text: series.

text: For

text: simplicity

text: write

text: Γ∞

text: for

text: G

text: and

text: p∞

text: for

text: id

text: G

text: Then

text: there

text: are

text: elements

text: t

text: t

text: G

text: F

text: which

text: can

text: be

text: chosen

text: to

text: coincide

text: n

text: N

text: ∪n{∞}

text: with

text: those

text: of

text: Theorem

text: such

text: that

text: for

text: k

text: p

text: n

text: [ZΓ

text: ZΓ

text: u

text: k

text: k

text: k

text: In

text: particular,

text: n

text: P

text: P

text: (G;

text: p

text: t

text: (H

text: (G)

text: k

text: i

text: f

text: is

text: a

text: polytope

text: (and

text: not

text: merely

text: a

text: diﬀerence

text: of

text: polytopes)

text: which

text: is

text: independent

text: of

text: N

text: k

text: Combining

text: the

text: previous

text: two

text: results,

text: we

text: see

text: that

text: the

text: BNS-invariant

text: of

text: UPG

text: automorphisms

text: is

text: easily

text: determined

text: by

text: their

text: polytope.

text: More

text: precisely,

text: we

text: have

text: the

text: following

text: analogue

text: of

text: [FT,

text: Theorem

text: Z

text: Corollary

text: Let

text: G

text: F

text: with

text: n

text: and

text: g

text: a

text: UPG

text: automorphism.

text: Let

text: R

text: n

text: g

text: P

text: ϕ

text: Then

text: [ϕ]

text: Σ(G)

text: if

text: and

text: only

text: if

text: F

text: (P

text: (G))

text: in

text: (H

text: (G)

text: ϕ

text: T

text: f

text: Proof.

text: Any

text: one-dimensional

text: face

text: of

text: n

text: P

text: (G)

text: t

text: i

text: contains

text: a

text: translate

text: of

text: t

text: for

text: some

text: i

text: n

text: i

text: Now

text: F

text: (P

text: (G))

text: if

text: and

text: only

text: if

text: F

text: (P

text: (G))

text: contains

text: a

text: one-dimensional

text: face,

text: ϕ

text: ϕ

text: i.e.

text: a

text: translate

text: of

text: t

text: for

text: some

text: i.

text: This

text: is

text: equivalent

text: to

text: ϕ(t

text: for

text: some

text: i,

text: i

text: i

text: which

text: by

text: Theorem

text: is

text: equivalent

text: to

text: [ϕ]

text: Σ(G).

text: Remark

text: We

text: suspect

text: Theorem

text: to

text: hold

text: as

text: well

text: for

text: polynomially

text: growing

text: automorphisms.

text: It

text: is

text: well-known

text: that

text: any

text: polynomially

text: growing

text: automorphism

text: has

text: a

text: power

text: that

text: is

text: UPG,

text: see

text: Bestvina–Feighn–Handel’s

text: [BFH,

text: Corollary

text: Thus,

text: in

text: order

text: to

text: reduce

text: Theorem

text: for

text: polynomially

text: growing

text: automorphisms

text: to


text: (a) SP dataset using Hardline Bound-setting. (b) SP dataset using Elastic Bound-setting. (c) ARIC dataset using Hardline Bound-setting. (d) ARIC dataset using Elastic Bound-setting. Fig. 2: Average probability vs. budget by dataset (Student Performance or ARIC) and by bound-setting method. Solid lines represent a result obtained using the logistic model, while dotted lines represent a result obtained using the SVM model. PGD denotes use of the gradient method, while Sens denotes use of the sensitivity analysis-based method. The cyan dashed line is a randomly selected individual whose recommendations will be shown and discussed in the next subsection. (a) Student 135. (b) Patient 15. Fig. 3: Recommended changes vs. budget for a randomly selected individual from each dataset. sensitivity analysis-based method when using the nonlinear Unexpectedly, looking at the results obtained for a randomly SVM classiﬁer and that the sensitivity analysis-based method selected individual from either dataset, we can see that there outperformed PGD when using the linear logistic classiﬁer. is no difference in probabilistic improvement between the two However, in Figure 2d, which represents results obtained using bound-setting methods based when using SVM with PGD. the Elastic bound-setting method PGD has dominated in the The speciﬁc recommendations made to these individuals are case of both classiﬁers. This result seems to suggest that, discussed in the next subsection along with recommendations regardless of classiﬁer complexity, if there exist optimizations most commonly made to individuals in each dataset at a budget that beneﬁt from an Elastic setting (recall that no beneﬁts were of four. found from such a setting on Student Performance), PGD may dominate (on average). D. Results: Cumulative and Individual Recommendations ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

text: (a)

text: SP

label: caption

text: dataset

text: using

text: Hardline

text: Bound-setting.

text: (b)

text: SP

text: dataset

text: using

text: Elastic

text: Bound-setting.

text: (c)

text: ARIC

text: dataset

text: using

text: Hardline

text: Bound-setting.

text: (d)

text: ARIC

text: dataset

text: using

text: Elastic

text: Bound-setting.

text: Fig.

text: Average

text: probability

text: vs.

text: budget

text: by

text: dataset

text: (Student

text: Performance

text: or

text: ARIC)

text: and

text: by

text: bound-setting

text: method.

text: Solid

text: lines

text: represent

text: a

text: result

text: obtained

text: using

text: the

text: logistic

text: model,

text: while

text: dotted

text: lines

text: represent

text: a

text: result

text: obtained

text: using

text: the

text: SVM

text: model.

text: PGD

text: denotes

text: use

text: of

text: the

text: gradient

text: method,

text: while

text: Sens

text: denotes

text: use

text: of

text: the

text: sensitivity

text: analysis-based

text: method.

text: The

text: cyan

text: dashed

text: line

text: is

text: a

text: randomly

text: selected

text: individual

text: whose

text: recommendations

text: will

text: be

text: shown

text: and

text: discussed

text: in

text: the

text: next

text: subsection.

text: (a)

text: Student

text: (b)

text: Patient

text: Fig.

text: Recommended

text: changes

text: vs.

text: budget

text: for

text: a

text: randomly

text: selected

text: individual

text: from

text: each

text: dataset.

text: sensitivity

text: analysis-based

text: method

text: when

text: using

text: the

text: nonlinear

text: Unexpectedly,

text: looking

text: at

text: the

text: results

text: obtained

text: for

text: a

text: randomly

text: SVM

text: classiﬁer

text: and

text: that

text: the

text: sensitivity

text: analysis-based

text: method

text: selected

text: individual

text: from

text: either

text: dataset,

text: we

text: can

text: see

text: that

text: there

text: outperformed

text: PGD

text: when

text: using

text: the

text: linear

text: logistic

text: classiﬁer.

text: is

text: no

text: difference

text: in

text: probabilistic

text: improvement

text: between

text: the

text: two

text: However,

text: in

text: Figure

text: which

text: represents

text: results

text: obtained

text: using

text: bound-setting

text: methods

text: based

text: when

text: using

text: SVM

text: with

text: PGD.

text: the

text: Elastic

text: bound-setting

text: method

text: PGD

text: has

text: dominated

text: in

text: the

text: The

text: speciﬁc

text: recommendations

text: made

text: to

text: these

text: individuals

text: are

text: case

text: of

text: both

text: classiﬁers.

text: This

text: result

text: seems

text: to

text: suggest

text: that,

text: discussed

text: in

text: the

text: next

text: subsection

text: along

text: with

text: recommendations

text: regardless

text: of

text: classiﬁer

text: complexity,

text: if

text: there

text: exist

text: optimizations

text: most

text: commonly

text: made

text: to

text: individuals

text: in

text: each

text: dataset

text: at

text: a

text: budget

text: that

text: beneﬁt

text: from

text: an

text: Elastic

text: setting

text: (recall

text: that

text: no

text: beneﬁts

text: were

text: of

text: four.

text: found

text: from

text: such

text: a

text: setting

text: on

text: Student

text: Performance),

text: PGD

text: may

text: dominate

text: (on

text: average).

text: D.

text: Results:

text: Cumulative

text: and

text: Individual

text: Recommendations

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: (a) Stud. Perf. Average (cid:15) by bud- (b) Stud. Perf. Average γ by bud- get. get. (c) ARIC. Average (cid:15) by budget. (d) ARIC. Average γ by budget. (e) Stud. Perf. Average (cid:15) by bud- (f) Stud. Perf. Average γ by bud- get. get. (g) ARIC. Average (cid:15) by budget. (h) ARIC. Average γ by budget. Fig. 4: ((cid:15), γ)-support for Student Performance and ARIC using both the Hardline (4a-4d) and Elastic (4e-4h) bound-setting methods with k = 10. In this subsection we brieﬂy relate the most common another, whereas in the case of the latter, optimization of changes recommended to individuals in each dataset and then several features happened in tandem. discuss the deﬁnitive recommendations made to two randomly In examining the speciﬁc recommendations made to Student selected instances. 135 in Figure 3a, we can see that ﬁrst weekday drinking was Table I shows the most common recommendations by raw curbed, followed by a reduction in school absences, weekend count, the highest ranking of which pertain to features relevant alcohol consumption, and time out with friends, as the budget to nearly all individuals (time with friends and eating food, for was increased. Last, at the second highest budgetary level, instance). time spent studying was increased. In the aggregate, it seems as though risk-related behavioral mitigations were determined Rank Student Perf. ARIC to be optimal for this student. 1 Time w/ friends Eat dark/grain bread Looking at the recommendations made to Patient 15 in 2 Study time Eat fruit 3 Absences Cigs/day Figure 3b we can see that, at low budgetary levels, an increase 4 Weekday alco. cons. Eat veggies in dark or grain breads and a decrease in the number of TABLE I: Most commonly recommended feature changes by cigarettes were recommended. Following these, as the budget dataset using SVM with the PGD method at a budget of four. was further incremented, consumption of more fruits and vegetables, in tandem, was recommended. At a budget of 13 it was also recommended that the patient decrease sodium Not all changes could be made to all individuals, how- intake and then subsequently, at a budget of 18, dietary ﬁber ever. For instance, not all individuals drink during the week- intake was increased. Finally, at a budget of 20, an increase in days (Student Performance) and not all individuals smoke the consumption of nuts was recommended. Comprehensively, cigarettes(ARIC). Therefore, red shows that when recommen- the recommendations deemed optimal for this patient were dation commonality is normalized by the number of individ- dietary-based, with the exception of a reduction in the number uals who were engaging in weekday drinking and smoking, of cigarettes. 97.97% and 99.98% of the time alterations to such behaviors were respectively recommended. Such a result shows that E. Results: ((cid:15), γ)-support while such risky behaviors are not necessarily common among The results in Figure 4 show that our inverse classiﬁcations all individuals, those who do engage in them are frequently recommended to make alterations. are well supported in terms of probability space ((cid:15)) and Figures 3a and 3b show the changes recommended to a underlying training data (γ) for both Student Performance and ARIC, up to certain budgetary levels (sans SVM/PGD randomly selected individual from Student Performance and in 4h). This suggests that, in future work, a constraint on ARIC, respectively, using SVM with the PGD method. Contrasting Figure 3a with Figure 3b we can see that, in the underlying γ-support may be desirable. The results were the case of the former, a single feature was optimized to obtained by taking the average over the (cid:15), γ values of all optimized test instances for each budgetary level explored in the extent of feasibility before perturbations were made to past experiments. ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##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##

text: (a)

text: Stud.

text: Perf.

text: Average

text: by

text: bud-

text: (b)

text: Stud.

text: Perf.

text: Average

text: γ

text: by

text: bud-

text: get.

text: get.

text: (c)

text: ARIC.

text: Average

text: by

text: budget.

text: (d)

text: ARIC.

text: Average

text: γ

text: by

text: budget.

text: (e)

text: Stud.

text: Perf.

text: Average

text: by

text: bud-

text: (f)

text: Stud.

text: Perf.

text: Average

text: γ

text: by

text: bud-

text: get.

text: get.

text: (g)

text: ARIC.

text: Average

text: by

text: budget.

text: (h)

text: ARIC.

text: Average

text: γ

text: by

text: budget.

text: Fig.

text: γ)-support

text: for

text: Student

text: Performance

text: and

text: ARIC

text: using

text: both

text: the

text: Hardline

text: and

text: Elastic

text: bound-setting

text: methods

text: with

text: k

text: In

text: this

text: subsection

text: we

text: brieﬂy

text: relate

text: the

text: most

text: common

text: another,

text: whereas

text: in

text: the

text: case

text: of

text: the

text: latter,

text: optimization

text: of

text: changes

text: recommended

text: to

text: individuals

text: in

text: each

text: dataset

text: and

text: then

text: several

text: features

text: happened

text: in

text: tandem.

text: discuss

text: the

text: deﬁnitive

text: recommendations

text: made

text: to

text: two

text: randomly

text: In

text: examining

text: the

text: speciﬁc

text: recommendations

text: made

text: to

text: Student

text: selected

text: instances.

text: in

text: Figure

text: we

text: can

text: see

text: that

text: ﬁrst

text: weekday

text: drinking

text: was

text: Table

text: I

text: shows

text: the

text: most

text: common

text: recommendations

text: by

text: raw

text: curbed,

text: followed

text: by

text: a

text: reduction

text: in

text: school

text: absences,

text: weekend

text: count,

text: the

text: highest

text: ranking

text: of

text: which

text: pertain

text: to

text: features

text: relevant

text: alcohol

text: consumption,

text: and

text: time

text: out

text: with

text: friends,

text: as

text: the

text: budget

text: to

text: nearly

text: all

text: individuals

text: (time

text: with

text: friends

text: and

text: eating

text: food,

text: for

text: was

text: increased.

text: Last,

text: at

text: the

text: second

text: highest

text: budgetary

text: level,

text: instance).

text: time

text: spent

text: studying

text: was

text: increased.

text: In

text: the

text: aggregate,

text: it

text: seems

text: as

text: though

text: risk-related

text: behavioral

text: mitigations

text: were

text: determined

text: Rank

text: Student

text: Perf.

text: ARIC

text: to

text: be

text: optimal

text: for

text: this

text: student.

text: Time

text: w/

text: friends

text: Eat

text: dark/grain

text: bread

text: Looking

text: at

text: the

text: recommendations

text: made

text: to

text: Patient

text: in

text: Study

text: time

text: Eat

text: fruit

text: Absences

text: Cigs/day

text: Figure

text: we

text: can

text: see

text: that,

text: at

text: low

text: budgetary

text: levels,

text: an

text: increase

text: Weekday

text: alco.

text: cons.

text: Eat

text: veggies

text: in

text: dark

text: or

text: grain

text: breads

text: and

text: a

text: decrease

text: in

text: the

text: number

text: of

text: TABLE

text: I:

text: Most

text: commonly

text: recommended

text: feature

text: changes

text: by

text: cigarettes

text: were

text: recommended.

text: Following

text: these,

text: as

text: the

text: budget

text: dataset

text: using

text: SVM

text: with

text: the

text: PGD

text: method

text: at

text: a

text: budget

text: of

text: four.

text: was

text: further

text: incremented,

text: consumption

text: of

text: more

text: fruits

text: and

text: vegetables,

text: in

text: tandem,

text: was

text: recommended.

text: At

text: a

text: budget

text: of

text: it

text: was

text: also

text: recommended

text: that

text: the

text: patient

text: decrease

text: sodium

text: Not

text: all

text: changes

text: could

text: be

text: made

text: to

text: all

text: individuals,

text: how-

text: intake

text: and

text: then

text: subsequently,

text: at

text: a

text: budget

text: of

text: dietary

text: ﬁber

text: ever.

text: For

text: instance,

text: not

text: all

text: individuals

text: drink

text: during

text: the

text: week-

text: intake

text: was

text: increased.

text: Finally,

text: at

text: a

text: budget

text: of

text: an

text: increase

text: in

text: days

text: (Student

text: Performance)

text: and

text: not

text: all

text: individuals

text: smoke

text: the

text: consumption

text: of

text: nuts

text: was

text: recommended.

text: Comprehensively,

text: cigarettes(ARIC).

text: Therefore,

text: red

text: shows

text: that

text: when

text: recommen-

text: the

text: recommendations

text: deemed

text: optimal

text: for

text: this

text: patient

text: were

text: dation

text: commonality

text: is

text: normalized

text: by

text: the

text: number

text: of

text: individ-

text: dietary-based,

text: with

text: the

text: exception

text: of

text: a

text: reduction

text: in

text: the

text: number

text: uals

text: who

text: were

text: engaging

text: in

text: weekday

text: drinking

text: and

text: smoking,

text: of

text: cigarettes.

text: and

text: of

text: the

text: time

text: alterations

text: to

text: such

text: behaviors

text: were

text: respectively

text: recommended.

text: Such

text: a

text: result

text: shows

text: that

text: E.

text: Results:

text: γ)-support

text: while

text: such

text: risky

text: behaviors

text: are

text: not

text: necessarily

text: common

text: among

text: The

text: results

text: in

text: Figure

text: show

text: that

text: our

text: inverse

text: classiﬁcations

text: all

text: individuals,

text: those

text: who

text: do

text: engage

text: in

text: them

text: are

text: frequently

text: recommended

text: to

text: make

text: alterations.

text: are

text: well

text: supported

text: in

text: terms

text: of

text: probability

text: space

text: and

text: Figures

text: and

text: show

text: the

text: changes

text: recommended

text: to

text: a

text: underlying

text: training

text: data

text: (γ)

text: for

text: both

text: Student

text: Performance

text: and

text: ARIC,

text: up

text: to

text: certain

text: budgetary

text: levels

text: (sans

text: SVM/PGD

text: randomly

text: selected

text: individual

text: from

text: Student

text: Performance

text: and

text: in

text: This

text: suggests

text: that,

text: in

text: future

text: work,

text: a

text: constraint

text: on

text: ARIC,

text: respectively,

text: using

text: SVM

text: with

text: the

text: PGD

text: method.

text: Contrasting

text: Figure

text: with

text: Figure

text: we

text: can

text: see

text: that,

text: in

text: the

text: underlying

text: γ-support

text: may

text: be

text: desirable.

text: The

text: results

text: were

text: the

text: case

text: of

text: the

text: former,

text: a

text: single

text: feature

text: was

text: optimized

text: to

text: obtained

text: by

text: taking

text: the

text: average

text: over

text: the

text: γ

text: values

text: of

text: all

text: optimized

text: test

text: instances

text: for

text: each

text: budgetary

text: level

text: explored

text: in

text: the

text: extent

text: of

text: feasibility

text: before

text: perturbations

text: were

text: made

text: to

text: past

text: experiments.

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

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: 1 Introduction 1.1 Composition theorems A basic structural question that can be asked in any model of computation is whether there can be resource savings when computing the same function on several independent inputs. We say a direct sum theorem holds in a model of computation if solving a problem on n independent inputs requires roughly n times the resources needed to solve one instance of the problem. Direct sum theorems hold for deterministic and randomized query complexity [JKS10], fail for circuit size [Pan12], and remain open for communication complexity [KRW95, BBCR13, FKNN95]. More generally, instead of merely outputting the n answers, we could compute another function of these n answers. If f is an n-bit Boolean function and g is an m-bit Boolean function, we ◦ ◦ deﬁne the composed function f g to be an nm-bit Boolean function such that f g(x , . . . , x ) = 1 n f(g(x ), . . . , g(x )), where each x is an m-bit string. The composition question now asks if there 1 n i ◦ can be signiﬁcant savings in computing f g compared to simply running the best algorithm for f and using the best algorithm for g to evaluate the input bits needed to compute f. If we let f be the identity function on n bits that just outputs all its inputs, we recover the direct sum problem. Composition theorems are harder to prove and are known for only a handful of models, such as deterministic [Tal13, Mon14] and quantum query complexity [Rei11, LMR+11, Kim12]. More precisely, let D(f), R(f), and Q(f) denote the deterministic, randomized, and quantum query complexities of f. Then for all (possibly partial) Boolean1 functions f and g, we have ◦ ◦ D(f g) = D(f) D(g) and Q(f g) = Θ(Q(f) Q(g)). (1) ◦ In contrast, in the randomized setting we only have the upper bound direction, R(f g) = O(R(f) R(g) log R(f)). Proving a composition theorem for randomized query complexity remains a major open problem. ◦ Open Problem 1. Does it hold that R(f g) = Ω(R(f) R(g)) for all Boolean functions f and g? In this paper we prove something close to a composition theorem for randomized query com- ◦ plexity. While we cannot rule out the possibility of synergistic savings in computing f g, we show that a composition theorem does hold if we insert a small gadget in between f and g to obfuscate the output of g. Our gadget is “small” in the sense that its randomized (and even deterministic) query complexity is Θ(log R(g)). Speciﬁcally we choose the index function, which on an input of size k + 2k interprets the ﬁrst k bits as an address into the next 2k bits and outputs the bit stored at that address. The index function’s query complexity is k + 1 and we choose k = Θ(log R(g)). Theorem 1. Let f and g be (partial) Boolean functions and let Ind be the index function with ◦ ◦ R(Ind) = Θ(log R(g)). Then R(f Ind g) = Ω(R(f) R(Ind) R(g)) = Ω(R(f) R(g) log R(g)). Theorem 1 can be used instead of a true composition theorem in many applications. For example, recently a composition theorem for randomized query complexity was needed in the special case when g is the And function [ABK16]. Our composition theorem would suﬃce for this application, since the separation shown there only changes by a logarithmic factor if an index gadget is inserted between f and g. We prove Theorem 1 by introducing a new lower bound technique for randomized query com- plexity. This is not surprising since the composition theorems for deterministic and quantum query 1Composition theorems usually fail for trivial reasons for non-Boolean functions. Hence we restrict our attention { } { } { } to Boolean functions, which have domain 0, 1 n (or a subset of 0, 1 n) and range 0, 1 . 2 ##LTLine##

label: section

text: Introduction

text: Composition

text: theorems

text: A

text: basic

text: structural

text: question

text: that

text: can

text: be

text: asked

text: in

text: any

text: model

text: of

text: computation

text: is

text: whether

text: there

text: can

text: be

text: resource

text: savings

text: when

text: computing

text: the

text: same

text: function

text: on

text: several

text: independent

text: inputs.

text: We

text: say

text: a

text: direct

text: sum

text: theorem

text: holds

text: in

text: a

text: model

text: of

text: computation

text: if

text: solving

text: a

text: problem

text: on

text: n

text: independent

text: inputs

text: requires

text: roughly

text: n

text: times

text: the

text: resources

text: needed

text: to

text: solve

text: one

text: instance

text: of

text: the

text: problem.

text: Direct

text: sum

text: theorems

text: hold

text: for

text: deterministic

text: and

text: randomized

text: query

text: complexity

text: fail

text: for

text: circuit

text: size

text: and

text: remain

text: open

text: for

text: communication

text: complexity

text: More

text: generally,

text: instead

text: of

text: merely

text: outputting

text: the

text: n

text: answers,

text: we

text: could

text: compute

text: another

text: function

text: of

text: these

text: n

text: answers.

text: If

text: f

text: is

text: an

text: n-bit

text: Boolean

text: function

text: and

text: g

text: is

text: an

text: m-bit

text: Boolean

text: function,

text: we

text: deﬁne

text: the

text: composed

text: function

text: f

text: g

text: to

text: be

text: an

text: nm-bit

text: Boolean

text: function

text: such

text: that

text: f

text: g(x

text: x

text: n

text: f(g(x

text: g(x

text: where

text: each

text: x

text: is

text: an

text: m-bit

text: string.

text: The

text: composition

text: question

text: now

text: asks

text: if

text: there

text: n

text: i

text: can

text: be

text: signiﬁcant

text: savings

text: in

text: computing

text: f

text: g

text: compared

text: to

text: simply

text: running

text: the

text: best

text: algorithm

text: for

text: f

text: and

text: using

text: the

text: best

text: algorithm

text: for

text: g

text: to

text: evaluate

text: the

text: input

text: bits

text: needed

text: to

text: compute

text: f.

text: If

text: we

text: let

text: f

text: be

text: the

text: identity

text: function

text: on

text: n

text: bits

text: that

text: just

text: outputs

text: all

text: its

text: inputs,

text: we

text: recover

text: the

text: direct

text: sum

text: problem.

text: Composition

text: theorems

text: are

text: harder

text: to

text: prove

text: and

text: are

text: known

text: for

text: only

text: a

text: handful

text: of

text: models,

text: such

text: as

text: deterministic

text: and

text: quantum

text: query

text: complexity

text: More

text: precisely,

text: let

text: D(f),

text: R(f),

text: and

text: Q(f)

text: denote

text: the

text: deterministic,

text: randomized,

text: and

text: quantum

text: query

text: complexities

text: of

text: f.

text: Then

text: for

text: all

text: (possibly

text: partial)

text: functions

text: f

text: and

text: g,

text: we

text: have

text: D(f

text: g)

text: D(f)

text: D(g)

text: and

text: Q(f

text: g)

text: Θ(Q(f)

text: Q(g)).

text: In

text: contrast,

text: in

text: the

text: randomized

text: setting

text: we

text: only

text: have

text: the

text: upper

text: bound

text: direction,

text: R(f

text: g)

text: O(R(f)

text: R(g)

text: log

text: R(f)).

text: Proving

text: a

text: composition

text: theorem

text: for

text: randomized

text: query

text: complexity

text: remains

text: a

text: major

text: open

text: problem.

text: Open

text: Problem

text: Does

text: it

text: hold

text: that

text: R(f

text: g)

text: Ω(R(f)

text: R(g))

text: for

text: all

text: Boolean

text: functions

text: f

text: and

text: g?

text: In

text: this

text: paper

text: we

text: prove

text: something

text: close

text: to

text: a

text: composition

text: theorem

text: for

text: randomized

text: query

text: com-

text: plexity.

text: While

text: we

text: cannot

text: rule

text: out

text: the

text: possibility

text: of

text: synergistic

text: savings

text: in

text: computing

text: f

text: g,

text: we

text: show

text: that

text: a

text: composition

text: theorem

text: does

text: hold

text: if

text: we

text: insert

text: a

text: small

text: gadget

text: in

text: between

text: f

text: and

text: g

text: to

text: obfuscate

text: the

text: output

text: of

text: g.

text: Our

text: gadget

text: is

text: “small”

text: in

text: the

text: sense

text: that

text: its

text: randomized

text: (and

text: even

text: deterministic)

text: query

text: complexity

text: is

text: Θ(log

text: R(g)).

text: Speciﬁcally

text: we

text: choose

text: the

text: index

text: function,

text: which

text: on

text: an

text: input

text: of

text: size

text: k

text: interprets

text: the

text: ﬁrst

text: k

text: bits

text: as

text: an

text: address

text: into

text: the

text: next

text: bits

text: and

text: outputs

text: the

text: bit

text: stored

text: at

text: that

text: address.

text: The

text: index

text: function’s

text: query

text: complexity

text: is

text: k

text: and

text: we

text: choose

text: k

text: Θ(log

text: R(g)).

text: Theorem

text: Let

text: f

text: and

text: g

text: be

text: (partial)

text: Boolean

text: functions

text: and

text: let

text: Ind

text: be

text: the

text: index

text: function

text: with

text: R(Ind)

text: Θ(log

text: R(g)).

text: Then

text: R(f

text: Ind

text: g)

text: Ω(R(f)

text: R(Ind)

text: R(g))

text: Ω(R(f)

text: R(g)

text: log

text: R(g)).

text: Theorem

text: can

text: be

text: used

text: instead

text: of

text: a

text: true

text: composition

text: theorem

text: in

text: many

text: applications.

text: For

text: example,

text: recently

text: a

text: composition

text: theorem

text: for

text: randomized

text: query

text: complexity

text: was

text: needed

text: in

text: the

text: special

text: case

text: when

text: g

text: is

text: the

text: And

text: function

text: Our

text: composition

text: theorem

text: would

text: suﬃce

text: for

text: this

text: application,

text: since

text: the

text: separation

text: shown

text: there

text: only

text: changes

text: by

text: a

text: logarithmic

text: factor

text: if

text: an

text: index

text: gadget

text: is

text: inserted

text: between

text: f

text: and

text: g.

text: We

text: prove

text: Theorem

text: by

text: introducing

text: a

text: new

text: lower

text: bound

text: technique

text: for

text: randomized

text: query

text: com-

text: plexity.

text: This

text: is

text: not

text: surprising

text: since

text: the

text: composition

text: theorems

text: for

text: deterministic

text: and

text: quantum

text: query

text: theorems

text: usually

text: fail

text: for

text: trivial

text: reasons

text: for

text: non-Boolean

text: functions.

text: Hence

text: we

text: restrict

text: our

text: attention

text: to

text: Boolean

text: functions,

text: which

text: have

text: domain

text: n

text: (or

text: a

text: subset

text: of

text: n)

text: and

text: range

text: ##LTLine##


text: with this input. It then returns to A an answer consistent with the new y . If x is 1, B selects a − ∗ † ∗ † i i consistent input from f 1(1) instead. If x is a or , B returns a or respectively. i ∗ † Now B only makes queries to x when it ﬁnds a or in an input to g . But this solves that sab instance of g , which was drawn from the hard distribution for g . Thus the query complexity of sab sab B is upper bounded by the number of instances of g that can be solved by a T -query algorithm sab with access to n instances of g . We know from Theorem 18 that if A makes T expected queries, ∗ †sab the expected number of or entries it ﬁnds among y , y , . . . , y is at most T/ RS(g). Hence the 1 2 n ≤ expected number of queries B makes to x is at most T/ RS(g). Thus we have RS(f) T/ RS(g), ≥ which gives T RS(f) RS(g). Using this we can lower bound the randomized query complexity of composed functions. In the ◦ following, fn denotes the function f composed with itself n times, i.e., f1 = f and fi+1 = f fi. ≥ Corollary 20. Let f be a partial function. Then R(fn) RS(f)n/3. ≥ − This follows straightforwardly from observing that R(fn) = R (fn) (1 2/3) RS(fn) (using ≥ 1/3 Theorem 12) and RS(fn) RS(f)n (using Theorem 19). We can also prove a composition theorem for zero-error and bounded-error randomized query complexity in terms of randomized sabotage complexity. In particular this yields a composition ◦ theorem for R(f g) when R(g) = Θ(RS(g)). ◦ ≥ Theorem 21. Let f and g be partial functions. Then R (f g) R (f) RS(g). (cid:15) (cid:15) Proof. The proof follows a similar argument to the proof of Theorem 19. Let A be a randomized ◦ algorithm for f g that uses T expected queries and makes error (cid:15). We turn A into an algorithm B for f by having B generate inputs from µ, the hard distribution for g , and feeding them to A, sab as before. The only diﬀerence is that this time, the input x to B is not a sabotaged input. This ∗ † means it has no or entries, so all the sabotaged inputs that B generates turn into 0- or 1-inputs ∗ † if A tries to query a or in them. Since A uses T queries, by Theorem 18, it ﬁnds at most T/ RS(g) asterisks or obelisks (in expectation). Therefore, B makes at most T/ RS(g) expected queries to x. Since B is correct ≤ ≥ whenever A is correct, its error probability is at most (cid:15). Thus R (f) T/ RS(g), and thus T (cid:15) R (f) RS(g). (cid:15) Setting (cid:15) to 0 yields the following corollary. ◦ ≥ Corollary 22. Let f and g be partial functions. Then R (f g) R (f) RS(g). 0 0 ◦ For the more commonly used R(f g), we obtain the following composition result. ◦ ≥ Corollary 23. Let f and g be partial functions. Then R(f g) R(f) RS(g)/10. ≥ ◦ ≥ This follows from Lemma 6, which gives R (f) R(f)/10, and Theorem 21, since R(f g) ◦ ≥ ≥ 1/3 R (f g) R (f) RS(g) R(f) RS(g)/10. 1/3 1/3 Finally, we can also show an upper bound composition result for randomized sabotage com- plexity. ◦ ≤ Theorem 24. Let f and g be partial functions. Then RS(f g) RS(f) R (g). We also have ◦ 0 RS(f g) = O(RS(f) R(g) log RS(f)). 11 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: with

text: this

text: input.

text: It

text: then

text: returns

text: to

text: A

text: an

text: answer

text: consistent

text: with

text: the

text: new

text: y

text: If

text: x

text: is

text: B

text: selects

text: a

text: i

text: i

text: consistent

text: input

text: from

text: f

text: instead.

text: If

text: x

text: is

text: a

text: or

text: B

text: returns

text: a

text: or

text: respectively.

text: i

text: Now

text: B

text: only

text: makes

text: queries

text: to

text: x

text: when

text: it

text: ﬁnds

text: a

text: or

text: in

text: an

text: input

text: to

text: g

text: But

text: this

text: solves

text: that

text: sab

text: instance

text: of

text: g

text: which

text: was

text: drawn

text: from

text: the

text: hard

text: distribution

text: for

text: g

text: Thus

text: the

text: query

text: complexity

text: of

text: sab

text: sab

text: B

text: is

text: upper

text: bounded

text: by

text: the

text: number

text: of

text: instances

text: of

text: g

text: that

text: can

text: be

text: solved

text: by

text: a

text: T

text: -query

text: algorithm

text: sab

text: with

text: access

text: to

text: n

text: instances

text: of

text: g

text: We

text: know

text: from

text: Theorem

text: that

text: if

text: A

text: makes

text: T

text: expected

text: queries,

text: †sab

text: the

text: expected

text: number

text: of

text: or

text: entries

text: it

text: ﬁnds

text: among

text: y

text: y

text: y

text: is

text: at

text: most

text: T/

text: RS(g).

text: Hence

text: the

text: n

text: expected

text: number

text: of

text: queries

text: B

text: makes

text: to

text: x

text: is

text: at

text: most

text: T/

text: RS(g).

text: Thus

text: we

text: have

text: RS(f)

text: T/

text: RS(g),

text: which

text: gives

text: T

text: RS(f)

text: RS(g).

text: Using

text: this

text: we

text: can

text: lower

text: bound

text: the

text: randomized

text: query

text: complexity

text: of

text: composed

text: functions.

text: In

text: the

text: following,

text: fn

text: denotes

text: the

text: function

text: f

text: composed

text: with

text: itself

text: n

text: times,

text: i.e.,

text: f

text: and

text: f

text: fi.

text: Corollary

text: Let

text: f

text: be

text: a

text: partial

text: function.

text: Then

text: R(fn)

text: This

text: follows

text: straightforwardly

text: from

text: observing

text: that

text: R(fn)

text: R

text: (fn)

text: RS(fn)

text: (using

text: Theorem

text: and

text: RS(fn)

text: RS(f)n

text: (using

text: Theorem

text: We

text: can

text: also

text: prove

text: a

text: composition

text: theorem

text: for

text: zero-error

text: and

text: bounded-error

text: randomized

text: query

text: complexity

text: in

text: terms

text: of

text: randomized

text: sabotage

text: complexity.

text: In

text: particular

text: this

text: yields

text: a

text: composition

text: theorem

text: for

text: R(f

text: g)

text: when

text: R(g)

text: Θ(RS(g)).

text: Theorem

text: Let

text: f

text: and

text: g

text: be

text: partial

text: functions.

text: Then

text: R

text: (f

text: g)

text: R

text: (f)

text: RS(g).

text: Proof.

text: The

text: proof

text: follows

text: a

text: similar

text: argument

text: to

text: the

text: proof

text: of

text: Theorem

text: Let

text: A

text: be

text: a

text: randomized

text: algorithm

text: for

text: f

text: g

text: that

text: uses

text: T

text: expected

text: queries

text: and

text: makes

text: error

text: We

text: turn

text: A

text: into

text: an

text: algorithm

text: B

text: for

text: f

text: by

text: having

text: B

text: generate

text: inputs

text: from

text: µ,

text: the

text: hard

text: distribution

text: for

text: g

text: and

text: feeding

text: them

text: to

text: A,

text: sab

text: as

text: before.

text: The

text: only

text: diﬀerence

text: is

text: that

text: this

text: time,

text: the

text: input

text: x

text: to

text: B

text: is

text: not

text: a

text: sabotaged

text: input.

text: This

text: means

text: it

text: has

text: no

text: or

text: entries,

text: so

text: all

text: the

text: sabotaged

text: inputs

text: that

text: B

text: generates

text: turn

text: into

text: or

text: if

text: A

text: tries

text: to

text: query

text: a

text: or

text: in

text: them.

text: Since

text: A

text: uses

text: T

text: queries,

text: by

text: Theorem

text: it

text: ﬁnds

text: at

text: most

text: T/

text: RS(g)

text: asterisks

text: or

text: obelisks

text: (in

text: expectation).

text: Therefore,

text: B

text: makes

text: at

text: most

text: T/

text: RS(g)

text: expected

text: queries

text: to

text: x.

text: Since

text: B

text: is

text: correct

text: whenever

text: A

text: is

text: correct,

text: its

text: error

text: probability

text: is

text: at

text: most

text: Thus

text: R

text: (f)

text: T/

text: RS(g),

text: and

text: thus

text: T

text: R

text: (f)

text: RS(g).

text: Setting

text: to

text: yields

text: the

text: following

text: corollary.

text: Corollary

text: Let

text: f

text: and

text: g

text: be

text: partial

text: functions.

text: Then

text: R

text: (f

text: g)

text: R

text: (f)

text: RS(g).

text: For

text: the

text: more

text: commonly

text: used

text: R(f

text: g),

text: we

text: obtain

text: the

text: following

text: composition

text: result.

text: Corollary

text: Let

text: f

text: and

text: g

text: be

text: partial

text: functions.

text: Then

text: R(f

text: g)

text: R(f)

text: This

text: follows

text: from

text: Lemma

text: which

text: gives

text: R

text: (f)

text: and

text: Theorem

text: since

text: R(f

text: g)

text: R

text: (f

text: g)

text: R

text: (f)

text: RS(g)

text: R(f)

text: Finally,

text: we

text: can

text: also

text: show

text: an

text: upper

text: bound

text: composition

text: result

text: for

text: randomized

text: sabotage

text: com-

text: plexity.

text: Theorem

text: Let

text: f

text: and

text: g

text: be

text: partial

text: functions.

text: Then

text: RS(f

text: g)

text: RS(f)

text: R

text: (g).

text: We

text: also

text: have

text: RS(f

text: g)

text: O(RS(f)

text: R(g)

text: log

text: RS(f)).

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: ≤ Proof. For any function DS(f) D(f) since a deterministic algorithm that correctly computes f ∗ † must ﬁnd a or when run on a sabotaged input, otherwise its output is independent of how the sabotaged bits are ﬁlled in. − To show the other direction, let D(f) = k. This means for every k 1 query algorithm, there (cid:54) are two inputs x and y with f(x) = f(y), such that they have the same answers to the queries made by the algorithm. If this is not the case then this algorithm computes f(x), contradicting the fact − that D(f) = k. Thus if there is a deterministic algorithm for f that makes k 1 queries, there (cid:54) sab exist two inputs x and y with f(x) = f(y) that have the same answers to the queries made by the algorithm. If we ﬁll in the rest of the inputs bits with either asterisks or obelisks, it is clear that this is a sabotaged input (since it can be completed to either x or y), but the purported algorithm ≥ ≥ for f cannot distinguish them. Hence D(f ) k, which means DS(f) D(f). sab sab Acknowledgements We thank Mika G¨o¨os for ﬁnding an error in an earlier proof of Theorem 18. We also thank the anonymous referees of Theory of Computing for their comments. This work is partially supported by ARO grant number W911NF-12-1-0486. This preprint is MIT-CTP #4806. 19 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Proof.

text: For

text: any

text: function

text: DS(f)

text: D(f)

text: since

text: a

text: deterministic

text: algorithm

text: that

text: correctly

text: computes

text: f

text: must

text: ﬁnd

text: a

text: or

text: when

text: run

text: on

text: a

text: sabotaged

text: input,

text: otherwise

text: its

text: output

text: is

text: independent

text: of

text: how

text: the

text: sabotaged

text: bits

text: are

text: ﬁlled

text: in.

text: To

text: show

text: the

text: other

text: direction,

text: let

text: D(f)

text: k.

text: This

text: means

text: for

text: every

text: k

text: query

text: algorithm,

text: there

text: are

text: two

text: inputs

text: x

text: and

text: y

text: with

text: f(x)

text: f(y),

text: such

text: that

text: they

text: have

text: the

text: same

text: answers

text: to

text: the

text: queries

text: made

text: by

text: the

text: algorithm.

text: If

text: this

text: is

text: not

text: the

text: case

text: then

text: this

text: algorithm

text: computes

text: f(x),

text: contradicting

text: the

text: fact

text: that

text: D(f)

text: k.

text: Thus

text: if

text: there

text: is

text: a

text: deterministic

text: algorithm

text: for

text: f

text: that

text: makes

text: k

text: queries,

text: there

text: sab

text: exist

text: two

text: inputs

text: x

text: and

text: y

text: with

text: f(x)

text: f(y)

text: that

text: have

text: the

text: same

text: answers

text: to

text: the

text: queries

text: made

text: by

text: the

text: algorithm.

text: If

text: we

text: ﬁll

text: in

text: the

text: rest

text: of

text: the

text: inputs

text: bits

text: with

text: either

text: asterisks

text: or

text: obelisks,

text: it

text: is

text: clear

text: that

text: this

text: is

text: a

text: sabotaged

text: input

text: (since

text: it

text: can

text: be

text: completed

text: to

text: either

text: x

text: or

text: y),

text: but

text: the

text: purported

text: algorithm

text: for

text: f

text: cannot

text: distinguish

text: them.

text: Hence

text: D(f

text: k,

text: which

text: means

text: DS(f)

text: D(f).

text: sab

text: sab

text: Acknowledgements

text: We

text: thank

text: Mika

text: G¨o¨os

text: for

text: ﬁnding

text: an

text: error

text: in

text: an

text: earlier

text: proof

text: of

text: Theorem

text: We

text: also

text: thank

text: the

text: anonymous

text: referees

text: of

text: Theory

text: of

text: Computing

text: for

text: their

text: comments.

text: This

text: work

text: is

text: partially

text: supported

text: by

text: ARO

text: grant

text: number

text: This

text: preprint

text: is

text: MIT-CTP

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##