text: Proof. The second part of the assertion follows immediately from the ﬁrst part, deﬁnition of rank of the origin, and the following identity (cid:183)(cid:90) (cid:90) (cid:184) − = − − x − x + + + rkt 1(x) rkt(x) [rkt 1(0) rkt(0)] dXt 1 dXt . (57) 0 0 < Now we show the ﬁrst part. We may assume x y since both hand sides in (55) are anti-symmetric = + under exchanging x and y. Observe that it sufﬁces to show the assertion for y x 1, since then (cid:88) (cid:88) − − y 1 − + = k 1 − = (dXt+1 dXt)(i,i 1) = 1(xi is excited at time t) 1(xi+1 is excited at time t) (58) i x = i 0 − 1(x is excited at time t) 1(y is excited at time t), (59) ∈ where the left hand side equals that of (55). It remains to verify that for any x (cid:90), − + = − + + (dXt 1 dXt)(x,x 1) 1(x is excited at time t) 1(x 1 is excited at time t) (60) ∈ for any x (cid:90). The argument is based on the particle system expansion and Lemma 2.2; namely, the left hand side of (60) equals the “ﬂux” of particles, which we deﬁne it to be the net change in the + + number of r particles minus l particles on edge (x,x 1) from time t to t 1. + First assume that x excites x 1 at time t, so x blinks at time t and is not excited at the same − + time, so the right hand side of (60) equals 1. The assumption yields that edge (x,x 1) has only r particles, and its bottom r particle is released at time t; since x is not excited at time t, there is no r − + (cid:55)→ particle released from (x 1,x), so (x,x 1) loses one r particle during the transition X X + . Then − t t 1 by Lemma 2.2, the left hand side of (60) also equals 1, as desired. Second, suppose that x does not + + + − excite x 1, but x 1 is excited by x 2 at time t. If x is also excited by x 1 at time t, then no particle + leaves the edge (x,x 1), but there is both an incoming l particle from the right and an r particle from + the left, which annihilate each other. Thus the ﬂux is zero as asserted. Lastly, suppose that x 1 is + − excited by x 2 but x is not excited by x 1. Then x is not excited at time t, so the right hand side − − of (60) equals 1. Indeed, no r particle is released from (x 1,x) and a l particle is released from + + + (x 1,x 2) at time t, so either this incoming l particle annihilates the bottom r particle on (x,x 1) + + − if any, or occupies the empty queue at (x,x 1); in both cases, the ﬂux on (x,x 1) is 1. This shows the assertion. The previous observation immediately yields that the tournament expansion for FCA dynamics does follow a tournament-like time evolution where local maxima affect their neighbors only when they blink: 20 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Proof.

text: The

text: second

text: part

text: of

text: the

text: assertion

text: follows

text: immediately

text: from

text: the

text: ﬁrst

text: part,

text: deﬁnition

text: of

text: rank

text: of

text: the

text: origin,

text: and

text: the

text: following

text: identity

text: x

text: x

text: rkt

text: rkt(x)

text: [rkt

text: dXt

text: dXt

text: Now

text: we

text: show

text: the

text: ﬁrst

text: part.

text: We

text: may

text: assume

text: x

text: y

text: since

text: both

text: hand

text: sides

text: in

text: are

text: anti-symmetric

text: under

text: exchanging

text: x

text: and

text: y.

text: Observe

text: that

text: it

text: sufﬁces

text: to

text: show

text: the

text: assertion

text: for

text: y

text: x

text: since

text: then

text: y

text: k

text: dXt)(i,i

text: is

text: excited

text: at

text: time

text: t)

text: is

text: excited

text: at

text: time

text: t)

text: i

text: x

text: i

text: is

text: excited

text: at

text: time

text: t)

text: is

text: excited

text: at

text: time

text: t),

text: where

text: the

text: left

text: hand

text: side

text: equals

text: that

text: of

text: It

text: remains

text: to

text: verify

text: that

text: for

text: any

text: x

text: (dXt

text: dXt)(x,x

text: is

text: excited

text: at

text: time

text: t)

text: is

text: excited

text: at

text: time

text: t)

text: for

text: any

text: x

text: The

text: argument

text: is

text: based

text: on

text: the

text: particle

text: system

text: expansion

text: and

text: Lemma

text: namely,

text: the

text: left

text: hand

text: side

text: of

text: equals

text: the

text: “ﬂux”

text: of

text: particles,

text: which

text: we

text: deﬁne

text: it

text: to

text: be

text: the

text: net

text: change

text: in

text: the

text: number

text: of

text: r

text: particles

text: minus

text: l

text: particles

text: on

text: edge

text: (x,x

text: from

text: time

text: t

text: to

text: t

text: First

text: assume

text: that

text: x

text: excites

text: x

text: at

text: time

text: t,

text: so

text: x

text: blinks

text: at

text: time

text: t

text: and

text: is

text: not

text: excited

text: at

text: the

text: same

text: time,

text: so

text: the

text: right

text: hand

text: side

text: of

text: equals

text: The

text: assumption

text: yields

text: that

text: edge

text: (x,x

text: has

text: only

text: r

text: particles,

text: and

text: its

text: bottom

text: r

text: particle

text: is

text: released

text: at

text: time

text: t;

text: since

text: x

text: is

text: not

text: excited

text: at

text: time

text: t,

text: there

text: is

text: no

text: r

text: particle

text: released

text: from

text: (x

text: so

text: (x,x

text: loses

text: one

text: r

text: particle

text: during

text: the

text: transition

text: X

text: X

text: Then

text: t

text: t

text: by

text: Lemma

text: the

text: left

text: hand

text: side

text: of

text: also

text: equals

text: as

text: desired.

text: Second,

text: suppose

text: that

text: x

text: does

text: not

text: excite

text: x

text: but

text: x

text: is

text: excited

text: by

text: x

text: at

text: time

text: t.

text: If

text: x

text: is

text: also

text: excited

text: by

text: x

text: at

text: time

text: t,

text: then

text: no

text: particle

text: leaves

text: the

text: edge

text: (x,x

text: but

text: there

text: is

text: both

text: an

text: incoming

text: l

text: particle

text: from

text: the

text: right

text: and

text: an

text: r

text: particle

text: from

text: the

text: left,

text: which

text: annihilate

text: each

text: other.

text: Thus

text: the

text: ﬂux

text: is

text: zero

text: as

text: asserted.

text: Lastly,

text: suppose

text: that

text: x

text: is

text: excited

text: by

text: x

text: but

text: x

text: is

text: not

text: excited

text: by

text: x

text: Then

text: x

text: is

text: not

text: excited

text: at

text: time

text: t,

text: so

text: the

text: right

text: hand

text: side

text: of

text: equals

text: Indeed,

text: no

text: r

text: particle

text: is

text: released

text: from

text: (x

text: and

text: a

text: l

text: particle

text: is

text: released

text: from

text: (x

text: at

text: time

text: t,

text: so

text: either

text: this

text: incoming

text: l

text: particle

text: annihilates

text: the

text: bottom

text: r

text: particle

text: on

text: (x,x

text: if

text: any,

text: or

text: occupies

text: the

text: empty

text: queue

text: at

text: (x,x

text: in

text: both

text: cases,

text: the

text: ﬂux

text: on

text: (x,x

text: is

text: This

text: shows

text: the

text: assertion.

text: The

text: previous

text: observation

text: immediately

text: yields

text: that

text: the

text: tournament

text: expansion

text: for

text: FCA

text: dynamics

text: does

text: follow

text: a

text: tournament-like

text: time

text: evolution

text: where

text: local

text: maxima

text: affect

text: their

text: neighbors

text: only

text: when

text: they

text: blink:

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: = ≥ Proposition 4.2. ≥Let (Xt)t≥0∈and (rkt)t≥0 be as before, and suppose no particle ﬂips after time t t0 0. Then for any t t and(cid:40)x (cid:90), we have 0 + ∃ ∈ = > + = rkt(x) 1 if y N(x) s.t. Xt(y) b(κ) and rkt(y) rkt(x) rkt 1(x) (61) rkt(x) otherwise ∈ > Proof. Recall that x is excited at time t iff there exists a blinking neighbor y N(x) with dX (y,x) 0, = + t and by construction rkt(y) rkt(x) dXt(y,x). Hence the assertion follows from Proposition 4.1. = Now we are ready to prove the key lemma in this section. Recall that the quantity rkt(0) net(0) ≥ is a “temporal” quantity in the sense that it depends on the history of trajectory (X ) upto time − t t 0 t 1. Deﬁne a “spatial” quantity M (r) by the maximum rank at time t in the r-ball centered at the t origin, i.e., = | | ≤ Mt(r) max{rkt(x) : x r}. (62) The next observation relates these two quantities. = ≥ Lemma 4.3. Le≥t (Xt)t≥0 and (rkt)t≥0 be as before, and suppose no particle ﬂips after time t t0 0. Then for each t 0, we have (cid:98) (cid:99) + ≤ ≤ Mt (t/ κ/2 (κ 1)) net+t (0) Mt (t/κ). (63) 0 0 0 = Moreover, if κ 3, we have − ≤ ≤ + Mt (t 1) ne3t t (0) Mt (t). (64) 0 0 0 = ≥ Proof. Recall that net(0) rkt(0) for all t 0 by construction. By Proposition 4.2, each site increases its rank only when in contact with blinking neighbors with higher rank. This happens if and only if a particle passes through each site. By Lemma 2.3 (i), this happens at most once in every κ seconds. + In other words, the speed of information propagation is upper bounded by 1/κ; by time t t , the 0 origin can adopt the highest rank within radius at most t/κ, which is M (t/κ). This gives the second t 0 inequalities in (63) and (64). ≥ ∈ To show the ﬁrst inequality in (63), we ﬁrst claim that for any t 0, x (cid:90), we have ≥ | = ± +(cid:98) (cid:99) + rkt κ/2 (κ 1)(x) max{rkt(y) y x 1}. (65) 21 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

font: LVRXUO+Fourier-Math-Symbols

text: Proposition

font: VPHQXA+Utopia-Bold

text: ≥Let

font: GIRVSK+Utopia-Italic

font: TVTNZO+Utopia-Regular

text: be

text: as

text: before,

text: and

text: suppose

text: no

text: particle

text: ﬂips

text: after

text: time

text: t

text: Then

text: for

text: any

text: t

text: t

label: equation

font: DEWUCV+Fourier-Math-BlackBoard

text: we

text: have

text: rkt(x)

text: if

text: y

text: N(x)

text: s.t.

text: Xt(y)

text: b(κ)

text: and

text: rkt(y)

text: rkt(x)

text: rkt

text: rkt(x)

text: otherwise

text: Proof.

text: Recall

text: that

text: x

text: is

text: excited

text: at

text: time

text: t

text: iff

text: there

text: exists

text: a

text: blinking

text: neighbor

text: y

text: N(x)

text: with

text: dX

text: (y,x)

text: t

text: and

text: by

text: construction

text: rkt(y)

text: rkt(x)

text: dXt(y,x).

text: Hence

text: the

text: assertion

text: follows

text: from

text: Proposition

text: Now

text: we

text: are

text: ready

text: to

text: prove

text: the

text: key

text: lemma

text: in

text: this

text: section.

text: Recall

text: that

text: the

text: quantity

text: is

text: a

text: “temporal”

text: quantity

text: in

text: the

text: sense

text: that

text: it

text: depends

text: on

text: the

text: history

text: of

text: trajectory

text: (X

text: upto

text: time

text: t

text: t

text: t

text: Deﬁne

text: a

text: “spatial”

text: quantity

text: M

text: (r)

text: by

text: the

text: maximum

text: rank

text: at

text: time

text: t

text: in

text: the

text: r-ball

text: centered

text: at

text: the

text: t

text: origin,

text: i.e.,

text: Mt(r)

text: max{rkt(x)

text: x

text: r}.

text: The

text: next

text: observation

text: relates

text: these

text: two

text: quantities.

text: Lemma

text: Le≥t

text: and

text: be

text: as

text: before,

text: and

text: suppose

text: no

text: particle

text: ﬂips

text: after

text: time

text: t

text: Then

text: for

text: each

text: t

text: we

text: have

text: Mt

text: (t/

text: (κ

text: net+t

text: Mt

text: (t/κ).

text: Moreover,

text: if

text: κ

text: we

text: have

text: Mt

text: (t

text: t

text: Mt

text: (t).

text: Proof.

text: Recall

text: that

text: for

text: all

text: t

text: by

text: construction.

text: By

text: Proposition

text: each

text: site

text: increases

text: its

text: rank

text: only

text: when

text: in

text: contact

text: with

text: blinking

text: neighbors

text: with

text: higher

text: rank.

text: This

text: happens

text: if

text: and

text: only

text: if

text: a

text: particle

text: passes

text: through

text: each

text: site.

text: By

text: Lemma

text: (i),

text: this

text: happens

text: at

text: most

text: once

text: in

text: every

text: κ

text: seconds.

text: In

text: other

text: words,

text: the

text: speed

text: of

text: information

text: propagation

text: is

text: upper

text: bounded

text: by

text: by

text: time

text: t

text: t

text: the

text: origin

text: can

text: adopt

text: the

text: highest

text: rank

text: within

text: radius

text: at

text: most

text: t/κ,

text: which

text: is

text: M

text: (t/κ).

text: This

text: gives

text: the

text: second

text: t

text: inequalities

text: in

text: and

text: To

text: show

text: the

text: ﬁrst

text: inequality

text: in

text: we

text: ﬁrst

text: claim

text: that

text: for

text: any

text: t

text: x

text: we

text: have

text: rkt

text: (κ

text: max{rkt(y)

text: y

text: x

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: A. Appendix: Proof of Lemma 6.1. In this appendix we prove Lemma 6.1. To obtain asympotics of the survival probabilities deﬁned in (82), we analyze their generating functions (cid:88) = Fi j(cid:101)(q,u) (cid:88)≥ qxutQi j(x,t) x,t 0 = Qi j(u) utQi j(l,t). l ≥ t 0 An inspiring analysis was given by Rajesh and Majumdar [15] for the ‘one dimensional’ case when the generating functions do not depend on indices i and j. Our analysis extends their arguments to multi-dimensional cases. − First note that Fi j’s converge on the box [0,1)2 and Q˜i j’s converge on ( 1,1). The survival prob- abilities satisfy recursion relations, which then lead to linear relations of generating functions Fi j’s and Q˜i j’s with boundary conditions on Q˜i j’s. This gives us a matrix equation involving the generat- l l ing functions Fi j’s and Q˜i j’s. Using Cramer’s rule, we can ﬁnd an explicit expression for Q˜i j’s. Then l → − l we investigate the asymptotic behavior when u 1 , which in turn translates into the asymptotic behavior of Qi j(0,t) by a standard Tauberian theorem. From a ﬁrst step analysis and Proposition 6.2 (iii), the survival probabilities satisfy the following recursive equations  (cid:80)    (cid:80) = + − ≥ 3Qi j(x,t) =(cid:80)2k=0Q jk(+x g(i, j,k≥),t · 1) + − for x ∈ 2 3Qi j(x,t) 2= 1{x g(i, j,k) 0} Q jk(x g(i, j,k),t 1) for x {0,1} ( A.1) = k 0 ≥ · − + ≥ − 3Qi0(0,t) 2= 1{g(i,0,k) 0} Q0k(g(i,0,k),t 1) 1{t 2}1Q21(1,t 2) k 0 3 ∈ ≥ (cid:54)= for all i, j (cid:90) and t 1. Since g(i, j,k) does not depend on i if j 2, in this case the right hand 3 sides of the above recursive relations are independent of i. It follows that Qi0 and Qi1 do not depend on i. Thus we only need to consider ﬁve different survival probabilities. Their recursive relations are explicitly given as below:       • = • + − + • + − + − −  3Q 0(x,t) Q 0(x 0,t 1) Q 1(x 1,t 1) Q02(x 1,t 1) • = • − − + • + − + + − 3Q 1(x,t) Q 0(x 1,t 1) Q 1(x 0,t 1) Q12(x 1,t 1)  = • + − + • + − + + − 3Q02(x,t) Q 0(x 1,t 1) Q 1(x 2,t 1) Q22(x 0,t 1) ( A.2)  = • − − + • − − + + − 3Q12(x,t) Q 0(x 2,t 1) Q 1(x 1,t 1) Q22(x 0,t 1) = • + − + • − − + + − 3Q22(x,t) Q 0(x 1,t 1) Q 1(x 1,t 1) Q22(x 0,t 1) 29 ##LTLine##

text: A.

label: section

text: Appendix:

text: Proof

text: of

text: Lemma

text: In

text: this

text: appendix

text: we

text: prove

text: Lemma

text: To

text: obtain

text: asympotics

text: of

text: the

text: survival

text: probabilities

text: deﬁned

text: in

text: we

text: analyze

text: their

text: generating

text: functions

font: ILXBYS+Fourier-Math-Extension

text: Fi

text: qxutQi

text: j(x,t)

text: x,t

text: Qi

text: j(u)

text: utQi

text: j(l,t).

text: l

text: t

text: An

text: inspiring

text: analysis

text: was

text: given

text: by

text: Rajesh

text: and

text: Majumdar

text: for

text: the

text: ‘one

text: dimensional’

text: case

text: when

text: the

text: generating

text: functions

text: do

text: not

text: depend

text: on

text: indices

text: i

text: and

text: j.

text: Our

text: analysis

text: extends

text: their

text: arguments

text: to

text: multi-dimensional

text: cases.

text: First

text: note

text: that

text: Fi

text: j’s

text: converge

text: on

text: the

text: box

text: and

text: Q˜i

text: j’s

text: converge

text: on

text: The

text: survival

text: prob-

text: abilities

text: satisfy

text: recursion

text: relations,

text: which

text: then

text: lead

text: to

text: linear

text: relations

text: of

text: generating

text: functions

text: Fi

text: j’s

text: and

text: Q˜i

text: j’s

text: with

text: boundary

text: conditions

text: on

text: Q˜i

text: j’s.

text: This

text: gives

text: us

text: a

text: matrix

text: equation

text: involving

text: the

text: generat-

text: l

text: l

text: ing

text: functions

text: Fi

text: j’s

text: and

text: Q˜i

text: j’s.

text: Using

text: Cramer’s

text: rule,

text: we

text: can

text: ﬁnd

text: an

text: explicit

text: expression

text: for

text: Q˜i

text: j’s.

text: Then

text: l

text: l

text: we

text: investigate

text: the

text: asymptotic

text: behavior

text: when

text: u

text: which

text: in

text: turn

text: translates

text: into

text: the

text: asymptotic

text: behavior

text: of

text: Qi

text: by

text: a

text: standard

text: Tauberian

text: theorem.

text: From

text: a

text: ﬁrst

text: step

text: analysis

text: and

text: Proposition

text: (iii),

text: the

text: survival

text: probabilities

text: satisfy

text: the

text: following

text: recursive

text: equations

text: 3Qi

text: j(x,t)

text: jk(+x

text: g(i,

text: j,k≥),t

text: for

text: x

text: j(x,t)

text: g(i,

text: j,k)

text: Q

text: jk(x

text: g(i,

text: j,k),t

text: for

text: x

text: k

text: k

text: for

text: all

text: i,

text: j

text: and

text: t

text: Since

text: g(i,

text: j,k)

text: does

text: not

text: depend

text: on

text: i

text: if

text: j

text: in

text: this

text: case

text: the

text: right

text: hand

text: sides

text: of

text: the

text: above

text: recursive

text: relations

text: are

text: independent

text: of

text: i.

text: It

text: follows

text: that

text: and

text: do

text: not

text: depend

text: on

text: i.

text: Thus

text: we

text: only

text: need

text: to

text: consider

text: ﬁve

text: different

text: survival

text: probabilities.

text: Their

text: recursive

text: relations

text: are

text: explicitly

text: given

text: as

text: below:

text: Q

text: Q

text: 3Q

text: Q

text: Q

text: Q

text: Q

text: Q

text: Q

text: Q

text: Q

text: ##LTLine##


text: ≥ = for all x 2, and for x 1 and 0, we have       • = • − + • − + −  3Q 0(1,t) Q 0(1,t 1) Q 1(2,t 1) Q02(0,t 1) • = • − + • − + − 3Q 1(1,t) Q 0(0,t 1) Q 1(0,t 1) Q12(1,t 1)  = • − + • − + − 3Q02(1,t) Q 0(2,t 1) Q 1(3,t 1) Q22(1,t 1) ( A.3)  = • − + − 3Q12(1,t) Q 1(0,t 1) Q22(0,t 1) = • − + • − + − 3Q22(1,t) Q 0(1,t 1) Q 1(0,t 1) Q22(1,t 1) and       • = • − + • − + ≥ • −  3Q 0(0,t) Q 0(0,t 1) Q 1(1,t 1) 1{t 2}1Q 1(1,t 2) • = • − + − 3 3Q 1(0,t) Q 1(0,t 1) Q12(1,t 1)  = • − + • − + − 3Q02(0,t) Q 0(1,t 1) Q 1(2,t 1) Q22(0,t 1) ( A.4)  = − 3Q12(0,t) Q22(0,t 1) = • − + − 3Q22(0,t) Q 0(1,t 1) Q22(0,t 1). To turn these systems of linear equations into relations between generating functions, we ﬁrst ≥ ≥ multiply each equation in ( A.2) by qxut and take summation on x 1 and t 1, noting that ( A.3) − and ( A.4) coincide except that the last term Q22(1,t 1) in the fourth equation in ( A.4) is missing. •• This Legandre transform applied to Q (x,t) terms above is as follows: (cid:181) (cid:182) (cid:88) (cid:88) •• = •• − •• + •• − •• qxutQ (x,t) F (q,u) Q˜ (u) qxQ (x,0) Q (0,0) ≥ 0 ≥ x,t 1 x 0 = •• − •• − q F (q,u) Q˜ (u) − 0 1 q •• = ≥ where we have used the fact that Q (x,0) 1 for any x 0. Similarly, 30 ##LTLine## ##LTLine##

text: for

text: all

text: x

text: and

text: for

text: x

text: and

text: we

text: have

text: Q

text: Q

text: 3Q

text: Q

text: Q

text: Q

text: Q

text: Q

text: Q

text: Q

text: and

text: Q

text: Q

text: 3Q

text: Q

text: Q

text: Q

text: Q

text: To

text: turn

text: these

text: systems

text: of

text: linear

text: equations

text: into

text: relations

text: between

text: generating

text: functions,

text: we

text: ﬁrst

text: multiply

text: each

text: equation

text: in

text: by

text: qxut

text: and

text: take

text: summation

text: on

text: x

text: and

text: t

text: noting

text: that

text: and

text: coincide

text: except

text: that

text: the

text: last

text: term

text: in

text: the

text: fourth

text: equation

text: in

text: is

text: missing.

text: This

text: Legandre

text: transform

text: applied

text: to

text: Q

text: (x,t)

text: terms

text: above

text: is

text: as

text: follows:

text: qxutQ

text: (x,t)

text: F

text: (q,u)

text: Q˜

text: (u)

text: qxQ

text: Q

text: x,t

text: x

text: q

text: F

text: (q,u)

text: Q˜

text: (u)

text: q

text: where

text: we

text: have

text: used

text: the

text: fact

text: that

text: Q

text: for

text: any

text: x

text: Similarly,

text: ##LTLine##

text: ##LTLine##


text: (cid:101) (cid:101) (cid:101) ∼ ∼ 4Q02(u) 7Q22(u) 21Q12(u). ( A.14) 0 0 0 Using this in the ﬁfth and sixth relations gives (cid:101) (cid:101) (cid:101) (cid:101) • ∼ − ∼ 9 Q 1(u) 4Q22(u) Q02(u) Q22(u). ( A.15) 2 0 0 4 0 This veriﬁes the ﬁrst three asympotitics in the assertion. With the ﬁrst, ﬁfth, and last relation in ( A.13) in mind, it now sufﬁces to show that (cid:101) (cid:101) (cid:101) 1 • ∼ • ∼ Q 0(u) Q 1(u) Q12(u). ( A.16) 2 0 0 0 To this end, we need another set of recursive relations which come from a ‘last step analysis’, similar to the proof of Lemma 3.2. Namely, we break the event that our random walk S starting at = − = • n height S 1 with triple X(cid:126) ( 1) ( ,i, j) surviving through t steps according to the ﬁrst hitting time 0 0 − of height 0. If it hits level 0 at sth step, then it has to survive the next t s steps starting from height 0. − = • • − (cid:126) By Proposition 6.2 (iii), the following excursion is initialized with triple X (s 1) ( , , j 1). 0 ∈ ≤ ≤ For each (i, j) ((cid:90) )2 an(cid:179)d 1 s t, denote (cid:175) (cid:180) 3 (cid:175) (cid:175) = ≥ ··· ≥ = = − = • ai j(j) (cid:80) S 1, ,S − 1, S 0 S 1, X(cid:126) ( 1) ( ,i, j) . ( A.17) 1 s 1 s 0 0 (cid:54)= Fix j 0. Then by Proposition 6.2 (iii) we have (cid:88) (cid:179) (cid:175) (cid:180) (cid:175) (cid:175) 1− t ai j(s) = (cid:80)(cid:179)S ≥ 1, ··· ,S ≥ 1(cid:175)(cid:175)S = 1, X(cid:126) (−1) = (•,i, j)(cid:180) ( A.18) = 1 t (cid:175) 0 0 s 1 = ≥ ··· ≥ = − = • = (cid:80) S 0, ,S 0 S 0, X(cid:126) ( 1) ( ,i, j) Qi j(0,t). ( A.19) 1 t 0 0 Hence by partitioning, we can write (cid:88) = + t • − − Qi j(1,t) Qi j(0,t) ai j(s)Q (j 1)(0,t s). ( A.20) = s 1 ≥ By multiplying ut to the recursion ( A.20) and summing over all t 0, we obtain 34 ##LTLine## ##LTLine##

text: Using

text: this

text: in

text: the

text: ﬁfth

text: and

text: sixth

text: relations

text: gives

text: Q

text: This

text: veriﬁes

text: the

text: ﬁrst

text: three

text: asympotitics

text: in

text: the

text: assertion.

text: With

text: the

text: ﬁrst,

text: ﬁfth,

text: and

text: last

text: relation

text: in

text: in

text: mind,

text: it

text: now

text: sufﬁces

text: to

text: show

text: that

text: Q

text: Q

text: To

text: this

text: end,

text: we

text: need

text: another

text: set

text: of

text: recursive

text: relations

text: which

text: come

text: from

text: a

text: ‘last

text: step

text: analysis’,

text: similar

text: to

text: the

text: proof

text: of

text: Lemma

text: Namely,

text: we

text: break

text: the

text: event

text: that

text: our

text: random

text: walk

text: S

text: starting

text: at

text: n

text: height

text: S

text: with

text: triple

text: ,i,

text: j)

text: surviving

text: through

text: t

text: steps

text: according

text: to

text: the

text: ﬁrst

text: hitting

text: time

text: of

text: height

text: If

text: it

text: hits

text: level

text: at

text: sth

text: step,

text: then

text: it

text: has

text: to

text: survive

text: the

text: next

text: t

text: s

text: steps

text: starting

text: from

text: height

text: By

text: Proposition

text: (iii),

text: the

text: following

text: excursion

text: is

text: initialized

text: with

text: triple

text: X

text: (s

text: j

text: For

text: each

text: (i,

text: j)

text: s

text: t,

text: denote

text: ai

text: j(j)

text: S

text: ,S

text: S

text: S

text: ,i,

text: j)

text: s

text: s

text: Fix

text: j

text: Then

text: by

text: Proposition

text: (iii)

text: we

text: have

text: 1−

text: t

text: ai

text: j(s)

text: ,S

text: (•,i,

text: t

text: s

text: S

text: ,S

text: S

text: ,i,

text: j)

text: Qi

text: t

text: Hence

text: by

text: partitioning,

text: we

text: can

text: write

text: t

text: Qi

text: Qi

text: ai

text: j(s)Q

text: (j

text: s).

text: s

text: By

text: multiplying

text: ut

text: to

text: the

text: recursion

text: and

text: summing

text: over

text: all

text: t

text: we

text: obtain

text: ##LTLine##

text: ##LTLine##


text: developed by the authors and Gravner in a recent work [10] to study 3-color CCA and GHM on arbi- trary graphs. We develop a similar technique for FCA on (cid:90), by which we are able relate the maximum of an associated random walk to the number of excitations. Applying a functional central limit theo- rem for random walks with correlated increments, we obtain our second main result: = ≥ Theorem 3. Let G (cid:90) be the integer lattice with nearest-neighbor edges, ﬁx κ 3, and let X be drawn ∼ 0 from the uniform product measure (cid:80) on (cid:90)(cid:90). Let Z N(0,1) be a standard normal random variable. κ Then we have the followings: ≥ = > ∈ ≥ (i) For each κ 3, there exists a constan(cid:161)t σ σ(κ) 0 su(cid:162)ch that for any x (cid:90) and r 0, we have (cid:112) ≥ ≥ ≥ ≤ lim→∞inf (cid:80) net(x) r tσ 4(cid:80)(Z r)(cid:80)(Z r). (9) t = (ii) For κ 3, we have (cid:179) (cid:180) (cid:112) ≥ = ≥ ≤ l→im∞ (cid:80) net(x) r 8t/81 4(cid:80)(Z r)(cid:80)(Z r). (10) t ∈ ≥ for any x (cid:90) and r 0. (cid:112) (cid:112) In words, it tells us that all sites must excite at least about t times in the ﬁrst t seconds, which agrees with the probability of disagreement at time t decaying like 1/ t. This paper is organized as follows. In Section 2 we carefully deﬁne the embedded particles sys- tem for FCA, and establish combinatorial lemmas that relate the survival of random walks arising from counting initial particles to the event of having local disagreement on a particular edge at a par- ticular time. In Section 3 we coarse grain the correlated increments of associated random walk into i.i.d. chunks and prove the Theorem 2 (i), using a classic theorem of Sparre Anderson about survival of random walks with i.i.d. increments. To obtain the complimentary result in Theorem 3, in Sec- tion 4, we introduce a new notion of tournament expansion on top of the embedded particle system which we will have developed in Section 2. By using a functional CLT for Markovian increments, we then prove Theorem 3 in Section 5. In Section 6, we prove Theorem 2 (ii) by using a generating func- tion method to compute the survival probability of a walk with Markovian increments. The detailed computations for generating functions are given in the appendix. 2. Particle system expansion of FCA on (cid:90) = ≥ = (cid:98) (cid:99) Let G (V,E) be a (not necessarily ﬁnite) simple graph and ﬁx κ 3 and let m κ/2 . Let E be the set = | ∈ → of the ordered pairs of adjacent nodes, i.e., E {(u,v),(v,u) uv E}. For each κ-coloring X : V (cid:90) , → − κ we deﬁne an associated 1-form dX : E [ m,m] by 5 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: developed

text: by

text: the

text: authors

text: and

text: Gravner

text: in

text: a

text: recent

text: work

text: to

text: study

text: CCA

text: and

text: GHM

text: on

text: arbi-

text: trary

text: graphs.

text: We

text: develop

text: a

text: similar

text: technique

text: for

text: FCA

text: on

text: by

text: which

text: we

text: are

text: able

text: relate

text: the

text: maximum

text: of

text: an

text: associated

text: random

text: walk

text: to

text: the

text: number

text: of

text: excitations.

text: Applying

text: a

text: functional

text: central

text: limit

text: theo-

text: rem

text: for

text: random

text: walks

text: with

text: correlated

text: increments,

text: we

text: obtain

text: our

text: second

text: main

text: result:

text: Theorem

text: Let

text: G

text: be

text: the

text: integer

text: lattice

text: with

text: nearest-neighbor

text: edges,

text: ﬁx

text: κ

text: and

text: let

text: X

text: be

text: drawn

text: from

text: the

text: uniform

text: product

text: measure

text: on

text: Let

text: Z

text: be

text: a

text: standard

text: normal

text: random

text: variable.

text: κ

text: Then

text: we

text: have

text: the

text: followings:

text: (i)

text: For

text: each

text: κ

text: there

text: exists

text: a

text: σ

text: σ(κ)

text: that

text: for

text: any

text: x

text: and

text: r

text: we

text: have

text: lim→∞inf

text: net(x)

text: r

text: tσ

text: r).

text: t

text: (ii)

text: For

text: κ

text: we

text: have

text: l→im∞

text: net(x)

text: r

text: r).

text: t

text: for

text: any

text: x

text: and

text: r

text: In

text: words,

text: it

text: tells

text: us

text: that

text: all

text: sites

text: must

text: excite

text: at

text: least

text: about

text: t

text: times

text: in

text: the

text: ﬁrst

text: t

text: seconds,

text: which

text: agrees

text: with

text: the

text: probability

text: of

text: disagreement

text: at

text: time

text: t

text: decaying

text: like

text: t.

text: This

text: paper

text: is

text: organized

text: as

text: follows.

text: In

text: Section

text: we

text: carefully

text: deﬁne

text: the

text: embedded

text: particles

text: sys-

text: tem

text: for

text: FCA,

text: and

text: establish

text: combinatorial

text: lemmas

text: that

text: relate

text: the

text: survival

text: of

text: random

text: walks

text: arising

text: from

text: counting

text: initial

text: particles

text: to

text: the

text: event

text: of

text: having

text: local

text: disagreement

text: on

text: a

text: particular

text: edge

text: at

text: a

text: par-

text: ticular

text: time.

text: In

text: Section

text: we

text: coarse

text: grain

text: the

text: correlated

text: increments

text: of

text: associated

text: random

text: walk

text: into

text: i.i.d.

text: chunks

text: and

text: prove

text: the

text: Theorem

text: (i),

text: using

text: a

text: classic

text: theorem

text: of

text: Sparre

text: Anderson

text: about

text: survival

text: of

text: random

text: walks

text: with

text: i.i.d.

text: increments.

text: To

text: obtain

text: the

text: complimentary

text: result

text: in

text: Theorem

text: in

text: Sec-

text: tion

text: we

text: introduce

text: a

text: new

text: notion

text: of

text: tournament

text: expansion

text: on

text: top

text: of

text: the

text: embedded

text: particle

text: system

text: which

text: we

text: will

text: have

text: developed

text: in

text: Section

text: By

text: using

text: a

text: functional

text: CLT

text: for

text: Markovian

text: increments,

text: we

text: then

text: prove

text: Theorem

text: in

text: Section

text: In

text: Section

text: we

text: prove

text: Theorem

text: (ii)

text: by

text: using

text: a

text: generating

text: func-

text: tion

text: method

text: to

text: compute

text: the

text: survival

text: probability

text: of

text: a

text: walk

text: with

text: Markovian

text: increments.

text: The

text: detailed

text: computations

text: for

text: generating

text: functions

text: are

text: given

text: in

text: the

text: appendix.

text: Particle

text: system

text: expansion

text: of

text: FCA

text: on

text: Let

text: G

text: (V,E)

text: be

text: a

text: (not

text: necessarily

text: ﬁnite)

text: simple

text: graph

text: and

text: ﬁx

text: κ

text: and

text: let

text: m

text: Let

text: E

text: be

text: the

text: set

text: of

text: the

text: ordered

text: pairs

text: of

text: adjacent

text: nodes,

text: i.e.,

text: E

text: {(u,v),(v,u)

text: uv

text: E}.

text: For

text: each

text: κ-coloring

text: X

text: V

text: κ

text: we

text: deﬁne

text: an

text: associated

text: dX

text: E

text: m,m]

text: by

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: to address the problem of old patents having less prior art and more a search corpus of ~7m USPTO patents. The authors, based on forward art than newer patents and vice versa. Results showed high the experimental results and through interviews with patent practi- correlation between assigned ranks and forward citations count. tioners, concluded that, a one-size-ﬁts-all semantic search approach Hido et al. [91] proposed a scoring model which assigned a patentabil- is incapable of capturing the highly nuanced relevance judgments ity score to each patent and thus can be utilized to determine whether made in the domain of patent litigation. Rather, the search work- it will be granted. First, the authors extracted textual features such ﬂow should be modeled as a multistage information seeking pro- as word frequency, word age, and syntactic complexity (e.g., num- cess, where users are presented with interactive elements to con- ber of sentences). Then, they trained a classiﬁer using previous trol the search space, and their feedback is incorporated iteratively patent ofﬁce decisions as ground truth. Though results showed the in the relevance ranking of retrieved results for enhanced perfor- model effectiveness, the utilized syntactic complexity features are mance. all extracted from the topic patent and thus could be good predic- Finally, There is much to be done in building predictive models tors for the writing quality not patentability potential. for patent litigation given the availability of prior case datasets that The correlation between patent claims novelty and patent value were not available few years ago (e.g., prosecution histories, court has been analyzed in [93,94] using lexical analysis of patent text. decisions, and PTAB decisions). In [94], Hasan et al. proposed an IR-based ranking tool which analyses patent claims for originality. The technique ﬁrst extracts 6Pa.t3entsTreepcrehsennot loonge yofLthiecmenosstivnagluable assets in today’s enter- key terms and phrases from the claims text using syntactic patterns prises which, if leveraged effectively, guarantee not only compet- and then looks for usage patterns backward to determine their nov- itive superiority, but also huge licensing revenues [93]. The tech- elty, and forward to determine their inﬂuence. The method con- nology licensing task is three sided. First, patent owners would siders usage patterns only through user deﬁned time window. It be interested in ﬁnding potential licensees with reasonable effort. is also keyword-based and hence will fail to capture key phrases Second, licensees would like to ﬁnd relevant inventions to their that are semantically similar and subsequently might give inaccu- businesses. Third, owners and businesses would be interested in rate scores. gauging the strategic and protection values of a patent in order to Along the efforts of using patent legal data for quality assessment support their pricing and offering decisions. Mann and Underweiser [95] utilized prosecution histories, court While there is no much research focusing on the task of automat- decisions, and patent textual features to analyze patent quality. The ically recommending potential licensees. The task of recommend- analysis suggested that patent examination records would be very ing patents to be licensed was relatively more considered. Chen et helpful in better discriminating high from low quality patents and al. [93] proposed a platform called SIMPLE which is used at IBM possibly improve the examination process as a whole. to identify target patents for licensing. Given a set of topic patents, SIMPLE uses nearest neighbor similarity to ﬁnd other patents that 6Li.t2igatioPnaitnegnetneLrailt,iagnadtpioatnent litigation speciﬁcally have been are most similar to the given topic set. Then, all the patents are and still a topic of interest to legal professionals. With the in- grouped and proposed as one licensing package to interested party. creased amounts of digitized data available and the need for tech- The platform was extended in [101] to allow retrieving target patents nology support in analyzing and mining these huge datasets, litiga- using free text search. We can notice that current trends for iden- tion became of more interest to computational science researchers. tifying potential patents for licensing model the problem as a PR Patent litigation can take many forms, the most common is patent task. More elaboration on the SIMPLE platform was introduced infringement litigation where a patent owner (plaintiff) accuses an- by Spangler et al. [102] using interactive visualization. First, port- other party (defendant) of using his/her invention without license folios of two companies are contrasted to ﬁnd content overlap be- or permission. Because litigation is very expensive, the most com- tween both of them using proximal search. Then, the closest patents mon defensive action for the defendant is to establish invalidity of to the overlap area are recommended as candidates for licensing. the plaintiff invention by issuing a post grant proceeding such as 7. CONCLUDING REMARKS PGR or IPR. Now the problem becomes a PR task, i.e. invalidity In this paper we presented a comprehensive review of PR methods search, where one of the aforementioned methods can be utilized and approaches. It is clear that, the well-performing IR techniques with wider scope to cover not only patent literature but also other in areas like Web search can not be utilized directly in PR with- published material. out deliberate domain adaptation and customization. Furthermore, The task of automatically establishing patent infringement is not state-of-the-art performance in automatic PR is still low (<0.2 MAP). addressed in literature. Such task requires extensive human exper- Several proposed techniques for query expansion, query reduction tise and reasoning to build correspondences between product fea- and pseudo relevance feedback require tuning of various parame- tures and patent claims. On the other hand, statistical and visual ters. Search professional practices suggest that effective prior art analytics of previous court decisions have shown some degree of search requires multiple iterations of searching, reviewing, and re- success in helping lawyers to better understand possible outcomes ﬁning. On the other hand, examiners’ query formulation practices and better plan on defense strategies [96–98]. (few keywords and Boolean search) are different from those of For example, Allison et al. [99] provided a statistical study on automatic methods (many keywords and free-text search). These patent cases ﬁled from 2008 to 2009 and decisions made between observations motivate the need for interactive search tools which (2009-2013). The study showed that, there is a strong correlation provide cognitive assistance to search professionals with minimal between court decision, and patent-speciﬁc, litigation-speciﬁc, and effort. These tools must also be developed in hand with patent pro- industry-speciﬁc variables such as industry and technology type, fessionals considering their practices and expectations. inventors foreign status, number of claims, number of forward and Unexplored patent-related data sources might be an opportunity for backward citations, and number of defendants sued. breakthrough improvements over the current modest state-of-the- Rajshekhar et al. [100] studied the potential of concept-based se- art in PR. For example, utilizing reexamination records, PTAB de- mantic search in patent litigation. The authors designed an exper- cisions, differences between the patent application and the granted iment in order to retrieve invalidating patents to a given litigated version, examiner/applicant correspondences, and prosecution his- patent using a subset of PTAB’s ﬁnal decisions as ground truth and tories. All these resources are not yet fully explored in the literature

text: to

text: address

text: the

text: problem

text: of

text: old

text: patents

text: having

text: less

text: prior

text: art

text: and

text: more

text: a

text: search

text: corpus

text: of

text: USPTO

text: patents.

text: The

text: authors,

text: based

text: on

text: forward

text: art

text: than

text: newer

text: patents

text: and

text: vice

text: versa.

text: Results

text: showed

text: high

text: the

text: experimental

text: results

text: and

text: through

text: interviews

text: with

text: patent

text: practi-

text: correlation

text: between

text: assigned

text: ranks

text: and

text: forward

text: citations

text: count.

text: tioners,

text: concluded

text: that,

text: a

text: one-size-ﬁts-all

text: semantic

text: search

text: approach

text: Hido

text: et

text: al.

text: proposed

text: a

text: scoring

text: model

text: which

text: assigned

text: a

text: patentabil-

text: is

text: incapable

text: of

text: capturing

text: the

text: highly

text: nuanced

text: relevance

text: judgments

text: ity

text: score

text: to

text: each

text: patent

text: and

text: thus

text: can

text: be

text: utilized

text: to

text: determine

text: whether

text: made

text: in

text: the

text: domain

text: of

text: patent

text: litigation.

text: Rather,

text: the

text: search

text: work-

text: it

text: will

text: be

text: granted.

text: First,

text: the

text: authors

text: extracted

text: textual

text: features

text: such

text: ﬂow

text: should

text: be

text: modeled

text: as

text: a

text: multistage

text: information

text: seeking

text: pro-

text: as

text: word

text: frequency,

text: word

text: age,

text: and

text: syntactic

text: complexity

text: (e.g.,

text: num-

text: cess,

text: where

text: users

text: are

text: presented

text: with

text: interactive

text: elements

text: to

text: con-

text: ber

text: of

text: sentences).

text: Then,

text: they

text: trained

text: a

text: classiﬁer

text: using

text: previous

text: trol

text: the

text: search

text: space,

text: and

text: their

text: feedback

text: is

text: incorporated

text: iteratively

text: patent

text: ofﬁce

text: decisions

text: as

text: ground

text: truth.

text: Though

text: results

text: showed

text: the

text: in

text: the

text: relevance

text: ranking

text: of

text: retrieved

text: results

text: for

text: enhanced

text: perfor-

text: model

text: effectiveness,

text: the

text: utilized

text: syntactic

text: complexity

text: features

text: are

text: mance.

text: all

text: extracted

text: from

text: the

text: topic

text: patent

text: and

text: thus

text: could

text: be

text: good

text: predic-

text: Finally,

text: There

text: is

text: much

text: to

text: be

text: done

text: in

text: building

text: predictive

text: models

text: tors

text: for

text: the

text: writing

text: quality

text: not

text: patentability

text: potential.

text: for

text: patent

text: litigation

text: given

text: the

text: availability

text: of

text: prior

text: case

text: datasets

text: that

text: The

text: correlation

text: between

text: patent

text: claims

text: novelty

text: and

text: patent

text: value

text: were

text: not

text: available

text: few

text: years

text: ago

text: (e.g.,

text: prosecution

text: histories,

text: court

text: has

text: been

text: analyzed

text: in

text: using

text: lexical

text: analysis

text: of

text: patent

text: text.

text: decisions,

text: and

text: PTAB

text: decisions).

text: In

text: Hasan

text: et

text: al.

text: proposed

text: an

text: IR-based

text: ranking

text: tool

text: which

text: analyses

text: patent

text: claims

text: for

text: originality.

text: The

text: technique

text: ﬁrst

text: extracts

text: loonge

text: yofLthiecmenosstivnagluable

text: assets

text: in

text: today’s

text: enter-

text: key

text: terms

text: and

text: phrases

text: from

text: the

text: claims

text: text

text: using

text: syntactic

text: patterns

text: prises

text: which,

text: if

text: leveraged

text: effectively,

text: guarantee

text: not

text: only

text: compet-

text: and

text: then

text: looks

text: for

text: usage

text: patterns

text: backward

text: to

text: determine

text: their

text: nov-

text: itive

text: superiority,

text: but

text: also

text: huge

text: licensing

text: revenues

text: The

text: tech-

text: elty,

text: and

text: forward

text: to

text: determine

text: their

text: inﬂuence.

text: The

text: method

text: con-

text: nology

text: licensing

text: task

text: is

text: three

text: sided.

text: First,

text: patent

text: owners

text: would

text: siders

text: usage

text: patterns

text: only

text: through

text: user

text: deﬁned

text: time

text: window.

text: It

text: be

text: interested

text: in

text: ﬁnding

text: potential

text: licensees

text: with

text: reasonable

text: effort.

text: is

text: also

text: keyword-based

text: and

text: hence

text: will

text: fail

text: to

text: capture

text: key

text: phrases

text: Second,

text: licensees

text: would

text: like

text: to

text: ﬁnd

text: relevant

text: inventions

text: to

text: their

text: that

text: are

text: semantically

text: similar

text: and

text: subsequently

text: might

text: give

text: inaccu-

text: businesses.

text: Third,

text: owners

text: and

text: businesses

text: would

text: be

text: interested

text: in

text: rate

text: scores.

text: gauging

text: the

text: strategic

text: and

text: protection

text: values

text: of

text: a

text: patent

text: in

text: order

text: to

text: Along

text: the

text: efforts

text: of

text: using

text: patent

text: legal

text: data

text: for

text: quality

text: assessment

text: support

text: their

text: pricing

text: and

text: offering

text: decisions.

text: Mann

text: and

text: Underweiser

text: utilized

text: prosecution

text: histories,

text: court

text: While

text: there

text: is

text: no

text: much

text: research

text: focusing

text: on

text: the

text: task

text: of

text: automat-

text: decisions,

text: and

text: patent

text: textual

text: features

text: to

text: analyze

text: patent

text: quality.

text: The

text: ically

text: recommending

text: potential

text: licensees.

text: The

text: task

text: of

text: recommend-

text: analysis

text: suggested

text: that

text: patent

text: examination

text: records

text: would

text: be

text: very

text: ing

text: patents

text: to

text: be

text: licensed

text: was

text: relatively

text: more

text: considered.

text: Chen

text: et

text: helpful

text: in

text: better

text: discriminating

text: high

text: from

text: low

text: quality

text: patents

text: and

text: al.

text: proposed

text: a

text: platform

text: called

text: SIMPLE

text: which

text: is

text: used

text: at

text: IBM

text: possibly

text: improve

text: the

text: examination

text: process

text: as

text: a

text: whole.

text: to

text: identify

text: target

text: patents

text: for

text: licensing.

text: Given

text: a

text: set

text: of

text: topic

text: patents,

text: SIMPLE

text: uses

text: nearest

text: neighbor

text: similarity

text: to

text: ﬁnd

text: other

text: patents

text: that

text: litigation

text: speciﬁcally

text: have

text: been

text: are

text: most

text: similar

text: to

text: the

text: given

text: topic

text: set.

text: Then,

text: all

text: the

text: patents

text: are

text: and

text: still

text: a

text: topic

text: of

text: interest

text: to

text: legal

text: professionals.

text: With

text: the

text: in-

text: grouped

text: and

text: proposed

text: as

text: one

text: licensing

text: package

text: to

text: interested

text: party.

text: creased

text: amounts

text: of

text: digitized

text: data

text: available

text: and

text: the

text: need

text: for

text: tech-

text: The

text: platform

text: was

text: extended

text: in

text: to

text: allow

text: retrieving

text: target

text: patents

text: nology

text: support

text: in

text: analyzing

text: and

text: mining

text: these

text: huge

text: datasets,

text: litiga-

text: using

text: free

text: text

text: search.

text: We

text: can

text: notice

text: that

text: current

text: trends

text: for

text: iden-

text: tion

text: became

text: of

text: more

text: interest

text: to

text: computational

text: science

text: researchers.

text: tifying

text: potential

text: patents

text: for

text: licensing

text: model

text: the

text: problem

text: as

text: a

text: PR

text: Patent

text: litigation

text: can

text: take

text: many

text: forms,

text: the

text: most

text: common

text: is

text: patent

text: task.

text: More

text: elaboration

text: on

text: the

text: SIMPLE

text: platform

text: was

text: introduced

text: infringement

text: litigation

text: where

text: a

text: patent

text: owner

text: (plaintiff)

text: accuses

text: an-

text: by

text: Spangler

text: et

text: al.

text: using

text: interactive

text: visualization.

text: First,

text: port-

text: other

text: party

text: (defendant)

text: of

text: using

text: his/her

text: invention

text: without

text: license

text: folios

text: of

text: two

text: companies

text: are

text: contrasted

text: to

text: ﬁnd

text: content

text: overlap

text: be-

text: or

text: permission.

text: Because

text: litigation

text: is

text: very

text: expensive,

text: the

text: most

text: com-

text: tween

text: both

text: of

text: them

text: using

text: proximal

text: search.

text: Then,

text: the

text: closest

text: patents

text: mon

text: defensive

text: action

text: for

text: the

text: defendant

text: is

text: to

text: establish

text: invalidity

text: of

text: to

text: the

text: overlap

text: area

text: are

text: recommended

text: as

text: candidates

text: for

text: licensing.

text: the

text: plaintiff

text: invention

text: by

text: issuing

text: a

text: post

text: grant

text: proceeding

text: such

text: as

text: CONCLUDING

text: REMARKS

text: PGR

text: or

text: IPR.

text: Now

text: the

text: problem

text: becomes

text: a

text: PR

text: task,

text: i.e.

text: invalidity

text: In

text: this

text: paper

text: we

text: presented

text: a

text: comprehensive

text: review

text: of

text: PR

text: methods

text: search,

text: where

text: one

text: of

text: the

text: aforementioned

text: methods

text: can

text: be

text: utilized

text: and

text: approaches.

text: It

text: is

text: clear

text: that,

text: the

text: well-performing

text: IR

text: techniques

text: with

text: wider

text: scope

text: to

text: cover

text: not

text: only

text: patent

text: literature

text: but

text: also

text: other

text: in

text: areas

text: like

text: Web

text: search

text: can

text: not

text: be

text: utilized

text: directly

text: in

text: PR

text: with-

text: published

text: material.

text: out

text: deliberate

text: domain

text: adaptation

text: and

text: customization.

text: Furthermore,

text: The

text: task

text: of

text: automatically

text: establishing

text: patent

text: infringement

text: is

text: not

text: state-of-the-art

text: performance

text: in

text: automatic

text: PR

text: is

text: still

text: low

text: MAP).

text: addressed

text: in

text: literature.

text: Such

text: task

text: requires

text: extensive

text: human

text: exper-

text: Several

text: proposed

text: techniques

text: for

text: query

text: expansion,

text: query

text: reduction

text: tise

text: and

text: reasoning

text: to

text: build

text: correspondences

text: between

text: product

text: fea-

text: and

text: pseudo

text: relevance

text: feedback

text: require

text: tuning

text: of

text: various

text: parame-

text: tures

text: and

text: patent

text: claims.

text: On

text: the

text: other

text: hand,

text: statistical

text: and

text: visual

text: ters.

text: Search

text: professional

text: practices

text: suggest

text: that

text: effective

text: prior

text: art

text: analytics

text: of

text: previous

text: court

text: decisions

text: have

text: shown

text: some

text: degree

text: of

text: search

text: requires

text: multiple

text: iterations

text: of

text: searching,

text: reviewing,

text: and

text: re-

text: success

text: in

text: helping

text: lawyers

text: to

text: better

text: understand

text: possible

text: outcomes

text: ﬁning.

text: On

text: the

text: other

text: hand,

text: examiners’

text: query

text: formulation

text: practices

text: and

text: better

text: plan

text: on

text: defense

text: strategies

text: (few

text: keywords

text: and

text: Boolean

text: search)

text: are

text: different

text: from

text: those

text: of

text: For

text: example,

text: Allison

text: et

text: al.

text: provided

text: a

text: statistical

text: study

text: on

text: automatic

text: methods

text: (many

text: keywords

text: and

text: free-text

text: search).

text: These

text: patent

text: cases

text: ﬁled

text: from

text: to

text: and

text: decisions

text: made

text: between

text: observations

text: motivate

text: the

text: need

text: for

text: interactive

text: search

text: tools

text: which

text: The

text: study

text: showed

text: that,

text: there

text: is

text: a

text: strong

text: correlation

text: provide

text: cognitive

text: assistance

text: to

text: search

text: professionals

text: with

text: minimal

text: between

text: court

text: decision,

text: and

text: patent-speciﬁc,

text: litigation-speciﬁc,

text: and

text: effort.

text: These

text: tools

text: must

text: also

text: be

text: developed

text: in

text: hand

text: with

text: patent

text: pro-

text: industry-speciﬁc

text: variables

text: such

text: as

text: industry

text: and

text: technology

text: type,

text: fessionals

text: considering

text: their

text: practices

text: and

text: expectations.

text: inventors

text: foreign

text: status,

text: number

text: of

text: claims,

text: number

text: of

text: forward

text: and

text: Unexplored

text: patent-related

text: data

text: sources

text: might

text: be

text: an

text: opportunity

text: for

text: backward

text: citations,

text: and

text: number

text: of

text: defendants

text: sued.

text: breakthrough

text: improvements

text: over

text: the

text: current

text: modest

text: state-of-the-

text: Rajshekhar

text: et

text: al.

text: studied

text: the

text: potential

text: of

text: concept-based

text: se-

text: art

text: in

text: PR.

text: For

text: example,

text: utilizing

text: reexamination

text: records,

text: PTAB

text: de-

text: mantic

text: search

text: in

text: patent

text: litigation.

text: The

text: authors

text: designed

text: an

text: exper-

text: cisions,

text: differences

text: between

text: the

text: patent

text: application

text: and

text: the

text: granted

text: iment

text: in

text: order

text: to

text: retrieve

text: invalidating

text: patents

text: to

text: a

text: given

text: litigated

text: version,

text: examiner/applicant

text: correspondences,

text: and

text: prosecution

text: his-

text: patent

text: using

text: a

text: subset

text: of

text: PTAB’s

text: ﬁnal

text: decisions

text: as

text: ground

text: truth

text: and

text: tories.

text: All

text: these

text: resources

text: are

text: not

text: yet

text: fully

text: explored

text: in

text: the

text: literature


text: Table 4: Pseudo Relevance Feedback Methods Method Description Dataset MAP PRES • • • • Bouadjenek et al. [27] use different methods of QE and QR from the PRF set CLEF-IP 2010 0.13 0.55 • • • • use Ricchio, MMR, LM CLEF-IP 2011 0.10 0.45 • Magdy et al. [19] naive PRF CLEF-IP 2009 0.05 - • remove stop-words • use most frequent terms • Mahdabi & Crestani [28] build regression model using relevance score, RF sim- CLEF-IP 2010 0.16 0.56 ilarities...etc • use the model to estimate the effectiveness of RF • use top 100 RF and maximize AP • Ganguly et al. [29] perform query segmentation CLEF-IP 2010 0.14 0.47 • retain segments highly to be generated using RF LM • Golestan Far et al. [30] manually annotate one relevant RF result CLEF-IP 2010 0.2915 - • add terms in the annotated result to the query • Golestan Far et al. [30] assume relevant RF results are known CLEF-IP 2010 0.4816 - • add terms more frequent in relevant than irrelevant RF to query which part(s) of the retrieved results should be used as the source PRF results based on their similarity with the query patent over of expansion and/or reduction?, 3) what is the best length of the speciﬁc terms. These terms are learned by building a classiﬁcation expansion list in case of QE, or the best threshold for removing model that classiﬁes whether a term would be useful for QE or not terms in case of QR?, 4) which pseudo-relevant results are really according to some proximity features between the original query relevant and how many of them should be used?, and 5) what is the terms and pseudo-relevant terms. The authors, through experiments best relevance scoring model for the search task (e.g., BM25 [39], on a subset of USPTO patents, showed the ability of this model to the vector space model with tf-idf weighting...etc). introduce more relevant QE terms and subsequently increasing the Bouadjenek et al. [27] provided a thorough evaluation on the CLEF- retrievability of individual patents. However, the authors did not IP 2010/2011 collections to address some of the above challenges. evaluate this model on a any of the available test collections. More- The authors explored the scenario when only partial patent appli- over, extracting similarity features and computing similarities with cation is available for prior art search (e.g., title, abstract, extended PRF results during query execution is computationally expensive abstract, or description). The authors tested different QE and QR and time consuming. general methods such as Rocchio [40] and a variant of the Maximal Along the same efforts, Mahdabi and Crestani [28] proposed a Marginal Relevance (MMR) [41]. They also tested patent-speciﬁc framework for identifying effective PRF documents at runtime and methods utilizing synonym sets [42], language models [29], and then performing QE using terms from these relevant documents. IPC-based lexicon [43]. After experimenting various sections as The authors ﬁrst proposed patent-speciﬁc features and then used sources for the initial query terms as well as expansion/reduction them to build a regression model which calculates a relevancy score sources, the results showed that, the description section among of each PRF document. Though results on the CLEF-IP 2010 col- other sections is the best to use as the initial query in case of both lection were encouraging, several challenges still exist. For ex- QE and QR. QE was not beneﬁcial for the long description queries ample, the computational complexity of calculating the regression as it already contains good coverage of relevant terms. However, model features at runtime. And PRF parameters tuning (e.g., num- QR on description queries was useful as it removed many of the ber of PRF documents to use). noisy terms. Generally, QR outperformed QE on description and In [29], Ganguly et al. proposed a PRF approach which utilizes a extended abstract queries which indicates that, with long queries, language model for QR of long queries composed of full patent ap- QR is effective for better retrieval performance. The results also plications. The authors argued that, naive application of PRF to ex- showed that generic QE methods such as Ricchio works generally pand query terms could add noisy terms causing query-topic drift. better for QE than patent-speciﬁc QE methods. Finally, the results Moreover, naive removal of terms that has unit term frequency in showed that BM25 scoring works better than the TF-IDF scoring the query could cause removal of useful terms and thus hurt re- on the long description queries for both QR and QE, while TF- trieval effectiveness. Instead, the authors proposed a PRF-based IDF works better than BM25 on short and medium-length title or QR technique which generates language model similarity scores abstract queries. Through this comprehensive experimental study, between query segments (sentences or n-grams) and top ranked the authors did not evaluate the impact of using multiple sections results. Segments with top scores are kept and all others are re- in combination as sources for QE or QR. More importantly, the moved. Results on the English subset of the CLEF-IP 2010 col- study does not provide any insights about the respective values of lection showed that the proposed approach outperforms the base- number of expansion terms or term removal threshold and whether lines. Parameter tuning is still the main downside of this technique. these values are somewhat deterministic or vary widely calling for The performance of the proposed approach was unstable compared interactive setting. to the baselines with different parameter values. Speciﬁcally, the To address the problem of poor PRF results in PR compared to tra- window size, the number of pseudo-relevant documents, and the ditional IR, Bashir and Rauber [44] proposed a novel approach for fraction of terms to retain. PRF-based QE which builds a model that learns to identify better In [30], Golestan Far et al. provided a study on hybrid QRE which ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Table

text: Pseudo

label: caption

text: Relevance

text: Feedback

text: Methods

text: Method

label: table

text: Description

text: Dataset

text: MAP

text: PRES

label: list

text: Bouadjenek

text: et

text: al.

text: use

text: different

text: methods

text: of

text: QE

text: and

text: QR

text: from

text: the

text: PRF

text: set

text: CLEF-IP

text: use

text: Ricchio,

text: MMR,

text: LM

text: CLEF-IP

text: Magdy

text: et

text: al.

text: naive

text: PRF

text: CLEF-IP

text: remove

text: stop-words

text: use

text: most

text: frequent

text: terms

text: Mahdabi

text: Crestani

text: build

text: regression

text: model

text: using

text: relevance

text: score,

text: RF

text: sim-

text: CLEF-IP

text: ilarities...etc

text: use

text: the

text: model

text: to

text: estimate

text: the

text: effectiveness

text: of

text: RF

text: use

text: top

text: RF

text: and

text: maximize

text: AP

text: Ganguly

text: et

text: al.

text: perform

text: query

text: segmentation

text: CLEF-IP

text: retain

text: segments

text: highly

text: to

text: be

text: generated

text: using

text: RF

text: LM

text: Golestan

text: Far

text: et

text: al.

text: manually

text: annotate

text: one

text: relevant

text: RF

text: result

text: CLEF-IP

text: add

text: terms

text: in

text: the

text: annotated

text: result

text: to

text: the

text: query

text: Golestan

text: Far

text: et

text: al.

text: assume

text: relevant

text: RF

text: results

text: are

text: known

text: CLEF-IP

text: add

text: terms

text: more

text: frequent

text: in

text: relevant

text: than

text: irrelevant

text: RF

text: to

text: query

text: which

text: part(s)

text: of

text: the

text: retrieved

text: results

text: should

text: be

text: used

text: as

text: the

text: source

text: PRF

text: results

text: based

text: on

text: their

text: similarity

text: with

text: the

text: query

text: patent

text: over

text: of

text: expansion

text: and/or

text: reduction?,

text: what

text: is

text: the

text: best

text: length

text: of

text: the

text: speciﬁc

text: terms.

text: These

text: terms

text: are

text: learned

text: by

text: building

text: a

text: classiﬁcation

text: expansion

text: list

text: in

text: case

text: of

text: QE,

text: or

text: the

text: best

text: threshold

text: for

text: removing

text: model

text: that

text: classiﬁes

text: whether

text: a

text: term

text: would

text: be

text: useful

text: for

text: QE

text: or

text: not

text: terms

text: in

text: case

text: of

text: QR?,

text: which

text: pseudo-relevant

text: results

text: are

text: really

text: according

text: to

text: some

text: proximity

text: features

text: between

text: the

text: original

text: query

text: relevant

text: and

text: how

text: many

text: of

text: them

text: should

text: be

text: used?,

text: and

text: what

text: is

text: the

text: terms

text: and

text: pseudo-relevant

text: terms.

text: The

text: authors,

text: through

text: experiments

text: best

text: relevance

text: scoring

text: model

text: for

text: the

text: search

text: task

text: (e.g.,

text: on

text: a

text: subset

text: of

text: USPTO

text: patents,

text: showed

text: the

text: ability

text: of

text: this

text: model

text: to

text: the

text: vector

text: space

text: model

text: with

text: tf-idf

text: weighting...etc).

text: introduce

text: more

text: relevant

text: QE

text: terms

text: and

text: subsequently

text: increasing

text: the

text: Bouadjenek

text: et

text: al.

text: provided

text: a

text: thorough

text: evaluation

text: on

text: the

text: CLEF-

text: retrievability

text: of

text: individual

text: patents.

text: However,

text: the

text: authors

text: did

text: not

text: IP

text: collections

text: to

text: address

text: some

text: of

text: the

text: above

text: challenges.

text: evaluate

text: this

text: model

text: on

text: a

text: any

text: of

text: the

text: available

text: test

text: collections.

text: More-

text: The

text: authors

text: explored

text: the

text: scenario

text: when

text: only

text: partial

text: patent

text: appli-

text: over,

text: extracting

text: similarity

text: features

text: and

text: computing

text: similarities

text: with

text: cation

text: is

text: available

text: for

text: prior

text: art

text: search

text: (e.g.,

text: title,

text: abstract,

text: extended

text: PRF

text: results

text: during

text: query

text: execution

text: is

text: computationally

text: expensive

text: abstract,

text: or

text: description).

text: The

text: authors

text: tested

text: different

text: QE

text: and

text: QR

text: and

text: time

text: consuming.

text: general

text: methods

text: such

text: as

text: Rocchio

text: and

text: a

text: variant

text: of

text: the

text: Maximal

text: Along

text: the

text: same

text: efforts,

text: Mahdabi

text: and

text: Crestani

text: proposed

text: a

text: Marginal

text: Relevance

text: (MMR)

text: They

text: also

text: tested

text: patent-speciﬁc

text: framework

text: for

text: identifying

text: effective

text: PRF

text: documents

text: at

text: runtime

text: and

text: methods

text: utilizing

text: synonym

text: sets

text: language

text: models

text: and

text: then

text: performing

text: QE

text: using

text: terms

text: from

text: these

text: relevant

text: documents.

text: IPC-based

text: lexicon

text: After

text: experimenting

text: various

text: sections

text: as

text: The

text: authors

text: ﬁrst

text: proposed

text: patent-speciﬁc

text: features

text: and

text: then

text: used

text: sources

text: for

text: the

text: initial

text: query

text: terms

text: as

text: well

text: as

text: expansion/reduction

text: them

text: to

text: build

text: a

text: regression

text: model

text: which

text: calculates

text: a

text: relevancy

text: score

text: sources,

text: the

text: results

text: showed

text: that,

text: the

text: description

text: section

text: among

text: of

text: each

text: PRF

text: document.

text: Though

text: results

text: on

text: the

text: CLEF-IP

text: col-

text: other

text: sections

text: is

text: the

text: best

text: to

text: use

text: as

text: the

text: initial

text: query

text: in

text: case

text: of

text: both

text: lection

text: were

text: encouraging,

text: several

text: challenges

text: still

text: exist.

text: For

text: ex-

text: QE

text: and

text: QR.

text: QE

text: was

text: not

text: beneﬁcial

text: for

text: the

text: long

text: description

text: queries

text: ample,

text: the

text: computational

text: complexity

text: of

text: calculating

text: the

text: regression

text: as

text: it

text: already

text: contains

text: good

text: coverage

text: of

text: relevant

text: terms.

text: However,

text: model

text: features

text: at

text: runtime.

text: And

text: PRF

text: parameters

text: tuning

text: (e.g.,

text: num-

text: QR

text: on

text: description

text: queries

text: was

text: useful

text: as

text: it

text: removed

text: many

text: of

text: the

text: ber

text: of

text: PRF

text: documents

text: to

text: use).

text: noisy

text: terms.

text: Generally,

text: QR

text: outperformed

text: QE

text: on

text: description

text: and

text: In

text: Ganguly

text: et

text: al.

text: proposed

text: a

text: PRF

text: approach

text: which

text: utilizes

text: a

text: extended

text: abstract

text: queries

text: which

text: indicates

text: that,

text: with

text: long

text: queries,

text: language

text: model

text: for

text: QR

text: of

text: long

text: queries

text: composed

text: of

text: full

text: patent

text: ap-

text: QR

text: is

text: effective

text: for

text: better

text: retrieval

text: performance.

text: The

text: results

text: also

text: plications.

text: The

text: authors

text: argued

text: that,

text: naive

text: application

text: of

text: PRF

text: to

text: ex-

text: showed

text: that

text: generic

text: QE

text: methods

text: such

text: as

text: Ricchio

text: works

text: generally

text: pand

text: query

text: terms

text: could

text: add

text: noisy

text: terms

text: causing

text: query-topic

text: drift.

text: better

text: for

text: QE

text: than

text: patent-speciﬁc

text: QE

text: methods.

text: Finally,

text: the

text: results

text: Moreover,

text: naive

text: removal

text: of

text: terms

text: that

text: has

text: unit

text: term

text: frequency

text: in

text: showed

text: that

text: scoring

text: works

text: better

text: than

text: the

text: TF-IDF

text: scoring

text: the

text: query

text: could

text: cause

text: removal

text: of

text: useful

text: terms

text: and

text: thus

text: hurt

text: re-

text: on

text: the

text: long

text: description

text: queries

text: for

text: both

text: QR

text: and

text: QE,

text: while

text: TF-

text: trieval

text: effectiveness.

text: Instead,

text: the

text: authors

text: proposed

text: a

text: PRF-based

text: IDF

text: works

text: better

text: than

text: on

text: short

text: and

text: medium-length

text: title

text: or

text: QR

text: technique

text: which

text: generates

text: language

text: model

text: similarity

text: scores

text: abstract

text: queries.

text: Through

text: this

text: comprehensive

text: experimental

text: study,

text: between

text: query

text: segments

text: (sentences

text: or

text: n-grams)

text: and

text: top

text: ranked

text: the

text: authors

text: did

text: not

text: evaluate

text: the

text: impact

text: of

text: using

text: multiple

text: sections

text: results.

text: Segments

text: with

text: top

text: scores

text: are

text: kept

text: and

text: all

text: others

text: are

text: re-

text: in

text: combination

text: as

text: sources

text: for

text: QE

text: or

text: QR.

text: More

text: importantly,

text: the

text: moved.

text: Results

text: on

text: the

text: English

text: subset

text: of

text: the

text: CLEF-IP

text: col-

text: study

text: does

text: not

text: provide

text: any

text: insights

text: about

text: the

text: respective

text: values

text: of

text: lection

text: showed

text: that

text: the

text: proposed

text: approach

text: outperforms

text: the

text: base-

text: number

text: of

text: expansion

text: terms

text: or

text: term

text: removal

text: threshold

text: and

text: whether

text: lines.

text: Parameter

text: tuning

text: is

text: still

text: the

text: main

text: downside

text: of

text: this

text: technique.

text: these

text: values

text: are

text: somewhat

text: deterministic

text: or

text: vary

text: widely

text: calling

text: for

text: The

text: performance

text: of

text: the

text: proposed

text: approach

text: was

text: unstable

text: compared

text: interactive

text: setting.

text: to

text: the

text: baselines

text: with

text: different

text: parameter

text: values.

text: Speciﬁcally,

text: the

text: To

text: address

text: the

text: problem

text: of

text: poor

text: PRF

text: results

text: in

text: PR

text: compared

text: to

text: tra-

text: window

text: size,

text: the

text: number

text: of

text: pseudo-relevant

text: documents,

text: and

text: the

text: ditional

text: IR,

text: Bashir

text: and

text: Rauber

text: proposed

text: a

text: novel

text: approach

text: for

text: fraction

text: of

text: terms

text: to

text: retain.

text: PRF-based

text: QE

text: which

text: builds

text: a

text: model

text: that

text: learns

text: to

text: identify

text: better

text: In

text: Golestan

text: Far

text: et

text: al.

text: provided

text: a

text: study

text: on

text: hybrid

text: QRE

text: which

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:48) the LHC would not be valid if the Z boson couples very weakly with the leptons, and thus one has to rely on the hadronic channels. The paper is organized as follows. In section II, we discuss the possible hints of new physics from B meson decays and extract the constraints on the lepton ﬂavor violating → new NP parameters in the charged lepton sector from the from the decay mode B d ± ∓ τ e . These parameters are in general related to the corresponding NP parameters in the neutrino sector by the SU(2) gauge symmetry. The basic formalism of neutrino oscillation L including NSI eﬀects are brieﬂy discussed in section III. In section IV, we study the eﬀect of NSI parameters on ν appearance oscillation probability and the search for the new CP e violating signals at long-baseline experiments is presented in section V. Section VI contains the summary and conclusions. I. NEW PHYSICS EFFECTS FROM B MESON DECAYS In this section, we would like to see the possible interplay of new physics in the τ-lepton sector considering the decay channels of B meson. For this purpose, we ﬁrst − → − consider the leptonic decay channel B τ ν¯. During the last few years, there has been a systematic disagreement betwe(cid:16)en the e(cid:17)xperimental and SM predicted value for → − → the branching ratio of B τν mode. The branching ratio for B τν is given as τ Br(B− → τν¯ ) = G2F |V |2τ −f2 m m2 1 − m2τ 2 .T hismodeisverycleanandtheonlynon − τ 8π ub B B B τ m2 B perturbativequantityinvolvedintheexpressionforbranchingratio()isthedecayconstantofBmeson.However, thereisstillatensionbetweentheexclusiveandinclusivevalueofV ub at the level of 3σ. This mode has been precisely mea- − → − ± × sured [11] with a value Br(B τ ν¯ ) = (1.14 0.27) τ − − → − ± ± × 10 4 .T helatestresultfromBelleCollaboration[16]Br(B τ ν¯ ) = (1.25 0.28 0.27) τ − | 10 4 , alsointhelineofthepreviousmeasurements.Sincethereisanuncertaintybetweenthe—V ub values extracted from exclusive and inclusive modes, we use the SM ﬁtted value of its − → − ± × branching ratio from UTﬁt collaboration [17] Br(B τ ν¯ ) = (0.84 0.07) τ − 10 4 .T hisvalueagreeswellwiththeexperimentalvalue().However, thecentralvaluesofthesetworesultsdiffersignificantly.OnecaneliminatetheV ub −→ − dependence completely by introducing the LFU probing ratio Rπ = τB0 Br(B → τ −ν¯τ) = τ/l τ − Br(B0 π0l ν¯ ) ± B l 0.73 0.15 , whichhasaround2.6σ deviation from its SM prediction of Rπ,SM = 0.31(6) τ/l [18]. Thus, these deviations may be considered as the smoking gun signal of new physics associated with the tauonic sector. We then proceed to obtain the bound on the lepton 2 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: the

text: LHC

text: would

text: not

text: be

text: valid

text: if

text: the

text: Z

text: boson

text: couples

text: very

text: weakly

text: with

text: the

text: leptons,

text: and

text: thus

text: one

text: has

text: to

text: rely

text: on

text: the

text: hadronic

text: channels.

text: The

text: paper

text: is

text: organized

text: as

text: follows.

text: In

text: section

text: II,

text: we

text: discuss

text: the

text: possible

text: hints

text: of

text: new

text: physics

text: from

text: B

text: meson

text: decays

text: and

text: extract

text: the

text: constraints

text: on

text: the

text: lepton

text: ﬂavor

text: violating

text: new

text: NP

text: parameters

text: in

text: the

text: charged

text: lepton

text: sector

text: from

text: the

text: from

text: the

text: decay

text: mode

text: B

text: d

text: τ

text: e

text: These

text: parameters

text: are

text: in

text: general

text: related

text: to

text: the

text: corresponding

text: NP

text: parameters

text: in

text: the

text: neutrino

text: sector

text: by

text: the

text: gauge

text: symmetry.

text: The

text: basic

text: formalism

text: of

text: neutrino

text: oscillation

text: L

text: including

text: NSI

text: eﬀects

text: are

text: brieﬂy

text: discussed

text: in

text: section

text: III.

text: In

text: section

text: IV,

text: we

text: study

text: the

text: eﬀect

text: of

text: NSI

text: parameters

text: on

text: ν

text: appearance

text: oscillation

text: probability

text: and

text: the

text: search

text: for

text: the

text: new

text: CP

text: e

text: violating

text: signals

text: at

text: long-baseline

text: experiments

text: is

text: presented

text: in

text: section

text: V.

text: Section

text: VI

text: contains

text: the

text: summary

text: and

text: conclusions.

text: I.

text: NEW

text: PHYSICS

text: EFFECTS

text: FROM

text: B

text: MESON

text: DECAYS

text: In

text: this

text: section,

text: we

text: would

text: like

text: to

text: see

text: the

text: possible

text: interplay

text: of

text: new

text: physics

text: in

text: the

text: τ-lepton

text: sector

text: considering

text: the

text: decay

text: channels

text: of

text: B

text: meson.

text: For

text: this

text: purpose,

text: we

text: ﬁrst

text: consider

text: the

text: leptonic

text: decay

text: channel

text: B

text: τ

text: ν¯.

text: During

text: the

text: last

text: few

text: years,

text: there

text: has

text: been

text: a

text: systematic

text: disagreement

text: the

text: and

text: SM

text: predicted

text: value

text: for

text: the

text: branching

text: ratio

text: of

text: B

text: τν

text: mode.

text: The

text: branching

text: ratio

text: for

text: B

text: τν

text: is

text: given

text: as

text: τ

text: Br(B−

text: τν¯

text: |V

text: m

text: .T

text: hismodeisverycleanandtheonlynon

text: τ

text: 8π

text: ub

text: B

text: B

text: B

text: τ

text: B

text: ub

text: at

text: the

text: level

text: of

text: This

text: mode

text: has

text: been

text: precisely

text: mea-

text: sured

text: with

text: a

text: value

text: Br(B

text: τ

text: ν¯

text: τ

text: .T

text: τ

text: ν¯

text: τ

text: ub

text: values

text: extracted

text: from

text: exclusive

text: and

text: inclusive

text: modes,

text: we

text: use

text: the

text: SM

text: ﬁtted

text: value

text: of

text: its

text: branching

text: ratio

text: from

text: UTﬁt

text: collaboration

text: Br(B

text: τ

text: ν¯

text: τ

text: .T

text: ub

text: dependence

text: completely

text: by

text: introducing

text: the

text: LFU

text: probing

text: ratio

text: Rπ

text: Br(B

text: τ

text: −ν¯τ)

text: τ/l

text: τ

text: ν¯

text: B

text: l

text: deviation

text: from

text: its

text: SM

text: prediction

text: of

text: Rπ,SM

text: τ/l

text: Thus,

text: these

text: deviations

text: may

text: be

text: considered

text: as

text: the

text: smoking

text: gun

text: signal

text: of

text: new

text: physics

text: associated

text: with

text: the

text: tauonic

text: sector.

text: We

text: then

text: proceed

text: to

text: obtain

text: the

text: bound

text: on

text: the

text: lepton

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: NH, δCP = 0 NH, δCP = 90 NH, δCP = -90 25 25 20 εeτ = 0.3 εeτ = 0.3 εeτ = 0.3 20 εeτ = 0.0 20 εeτ = 0.0 εeτ = 0.0 15 15 15 10 10 10 5 5 5 0 0 0 0.5 1 1.5 2 2.5 3 3.5 4 0.5 1 1.5 2 2.5 3 3.5 4 0.5 1 1.5 2 2.5 3 3.5 4 Energy (GeV) Energy (GeV) Energy (GeV) IH, δCP = 0 IH, δCP = 90 IH, δCP = -90 20 20 20 εeτ = 0.3 εeτ = 0.3 εeτ = 0.3 εeτ = 0.0 εeτ = 0.0 εeτ = 0.0 15 15 15 10 10 10 5 5 5 0 0 0 0.5 1 1.5 2 2.5 3 3.5 4 0.5 1 1.5 2 2.5 3 3.5 4 0.5 1 1.5 2 2.5 3 3.5 4 Energy (GeV) Energy (GeV) Energy (GeV) ◦ FIG. 4: The event spectra of NOνA for diﬀerent values of CP violating phase, i.e, δ = 0 (left CP ◦ − ◦ panel), δ = 90 (middle panel), and δ = 90 (right panel) . CP CP − if NSIs exists in nature. The CP-violation sensitivity (χ2 = χ2(δtrue) χ2(δtest = 0, 180)) CP CP as a function of δ for NOνA (DUNE) is given in the top (bottom) panel of Fig. 7. The CP dark solid curve in the ﬁgure corresponds to CPV sensitivity in presence of NSI, whereas the dark dashed curve in the ﬁgure corresponds to CPV sensitivity in SO. From the ﬁgure, we can see that NSI can signiﬁcantly aﬀect CPV sensitivity of both experiments. Though there is signiﬁcant enhancement in the CPV sensitivity in presence of NSI for NOνA, it should be noted that the δ coverage for CPV sensitivity above 1σ is reduced in presence of NSI CP while comparing with that of SO. Whereas for DUNE, the CPV sensitivity is enhanced in the presence of NSI and it is above 5σ for more than 50% allowed values of δ in the case CP of both NH and IH. IV. SUMMARY AND CONCLUSIONS Conservation of lepton ﬂavour universality is one of the unique feature of the SM. How- ever, recently there are a series of experimental results in B physics pointing towards possible violations of LFU, both in the charged and neutral current mediated semileptonic decays. 11 sry3 ni nib VeG 521.0 rep tnevE sry3 ni nib VeG 521.0 rep tnevE sry3 ni nib VeG 521.0 rep tnevE sry3 ni nib VeG 521.0 rep tnevE sry3 ni nib VeG 521.0 rep tnevE sry3 ni nib VeG 521.0 rep tnevE ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

text: NH,

font: default

text: δCP

text: NH,

text: δCP

text: NH,

text: δCP

text: εeτ

text: εeτ

text: εeτ

text: εeτ

text: εeτ

text: εeτ

text: Energy

text: (GeV)

text: Energy

text: (GeV)

text: Energy

text: (GeV)

text: IH,

text: δCP

text: IH,

text: δCP

text: IH,

text: δCP

text: εeτ

text: εeτ

text: εeτ

text: εeτ

text: εeτ

text: εeτ

text: Energy

text: (GeV)

text: Energy

text: (GeV)

text: Energy

text: (GeV)

text: FIG.

text: The

text: event

text: spectra

text: of

text: NOνA

text: for

text: diﬀerent

text: values

text: of

text: CP

text: violating

text: phase,

text: i.e,

text: δ

text: (left

text: CP

text: panel),

text: δ

text: (middle

text: panel),

text: and

text: δ

text: (right

text: panel)

text: CP

text: CP

text: if

text: NSIs

text: exists

text: in

text: nature.

text: The

text: CP-violation

text: sensitivity

text: CP

text: CP

text: as

text: a

text: function

text: of

text: δ

text: for

text: NOνA

text: (DUNE)

text: is

text: given

text: in

text: the

text: top

text: (bottom)

text: panel

text: of

text: Fig.

text: The

text: CP

text: dark

text: solid

text: curve

text: in

text: the

text: ﬁgure

text: corresponds

text: to

text: CPV

text: sensitivity

text: in

text: presence

text: of

text: NSI,

text: whereas

text: the

text: dark

text: dashed

text: curve

text: in

text: the

text: ﬁgure

text: corresponds

text: to

text: CPV

text: sensitivity

text: in

text: SO.

text: From

text: the

text: ﬁgure,

text: we

text: can

text: see

text: that

text: NSI

text: can

text: signiﬁcantly

text: aﬀect

text: CPV

text: sensitivity

text: of

text: both

text: experiments.

text: Though

text: there

text: is

text: signiﬁcant

text: enhancement

text: in

text: the

text: CPV

text: sensitivity

text: in

text: presence

text: of

text: NSI

text: for

text: NOνA,

text: it

text: should

text: be

text: noted

text: that

text: the

text: δ

text: coverage

text: for

text: CPV

text: sensitivity

text: above

text: 1σ

text: is

text: reduced

text: in

text: presence

text: of

text: NSI

text: CP

text: while

text: comparing

text: with

text: that

text: of

text: SO.

text: Whereas

text: for

text: DUNE,

text: the

text: CPV

text: sensitivity

text: is

text: enhanced

text: in

text: the

text: presence

text: of

text: NSI

text: and

text: it

text: is

text: above

text: 5σ

text: for

text: more

text: than

text: allowed

text: values

text: of

text: δ

text: in

text: the

text: case

text: CP

text: of

text: both

text: NH

text: and

text: IH.

text: IV.

text: SUMMARY

text: AND

text: CONCLUSIONS

text: Conservation

text: of

text: lepton

text: ﬂavour

text: universality

text: is

text: one

text: of

text: the

text: unique

text: feature

text: of

text: the

text: SM.

text: How-

text: ever,

text: recently

text: there

text: are

text: a

text: series

text: of

text: experimental

text: results

text: in

text: B

text: physics

text: pointing

text: towards

text: possible

text: violations

text: of

text: LFU,

text: both

text: in

text: the

text: charged

text: and

text: neutral

text: current

text: mediated

text: semileptonic

text: decays.

text: ni

text: nib

text: VeG

text: rep

text: tnevE

text: ni

text: nib

text: VeG

text: rep

text: tnevE

text: ni

text: nib

text: VeG

text: rep

text: tnevE

text: ni

text: nib

text: VeG

text: rep

text: tnevE

text: ni

text: nib

text: VeG

text: rep

text: tnevE

text: ni

text: nib

text: VeG

text: rep

text: tnevE

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##