Scott N Armstrong
email: armstrong@math.lsu.edu

Boyan Sirakov
email: sirakov@ehess.fr

SHARP LIOUVILLE RESULTS FOR FULLY NONLINEAR EQUATIONS WITH POWER-GROWTH NONLINEARITIES

Keywords: Mathematics Subject Classification. Primary 35B53, 35J60 fully nonlinear elliptic equation, Bellman-Isaacs equation, Liouville theorem

We study fully nonlinear elliptic equations such as

in R n or in exterior domains, where F is any uniformly elliptic, positively homogeneous operator. We show that there exists a critical exponent, depending on the homogeneity of the fundamental solution of F , that sharply characterizes the range of p > 1 for which there exist positive supersolutions or solutions in any exterior domain. Our result generalizes theorems of as well as Cutri and Leoni [11], who found critical exponents for supersolutions in the whole space R n , in case -F is Laplace's operator and Pucci's operator, respectively. The arguments we present are new and rely only on the scaling properties of the equation and the maximum principle.

Introduction and main results

Elliptic equations and systems with power-like zero order terms have been the focus of great attention for many years. A model is the Emden-Fowler equation

(1.1)
-∆u = u p , p > 1, which has important applications in physics and geometry as well as a rich mathematical structure. In this paper, we study the more general equation

(1.2) F (D 2 u) = f (x, u)
where F is a uniformly elliptic operator and f has power-like dependence in u. In particular, we study the existence of positive solutions and supersolutions of (1.2) in unbounded domains of R n , n ≥ 2. The only hypotheses on the nonlinear operator F are uniform ellipticity and positive homogeneity; precisely, we require: (H1) for some constants 0 < λ ≤ Λ and all real symmetric matrices M and N , with N nonnegative definite, we have λ trace(N ) ≤ F (M -N ) -F (M ) ≤ Λ trace(N ), and (H2) F (tM ) = tF (M ) for every t ≥ 0 and each symmetric matrix M . An operator F satisfying (H1)-(H2) is called an Isaacs operator. If in addition F is concave or convex, then F is often called a Hamilton-Jacobi-Bellman operator. See the references in the next section for more on the the theory and applications of Isaacs operators.

The question we are concerned with has been extensively studied in the special case F (D 2 u) = -∆u (when (H1) holds with λ = Λ = 1, and (H2) holds for all t ∈ R), by using energy methods and the divergence-form structure of the Laplacian. The following Liouville-type theorem is a particular case of results obtained by Bidaut-Véron [START_REF] Bidaut-Véron | Local and global behavior of solutions of quasilinear equations of Emden-Fowler type[END_REF], and sharply characterizes the range of p > 1 for which there exist positive (super)solutions of (1.1) in exterior domains, as well as positive supersolutions in the whole space R n . An exterior domain is a domain Ω ⊂ R n for which R n \ B R ⊆ Ω ⊆ R n \ {0} for some R > 0, where B R denotes the open ball of radius R centered at the origin.

Theorem 1.1 ([6]). Denote 2 * := n/(n -2) if n ≥ 3, and 2 * := ∞ if n = 2. Let p > 1. Then the Emden-Fowler equation (1.1) has no nontrivial nonnegative weak supersolutions in any exterior domain of R n , provided that p ≤ 2 * .

Note that it can be checked by a straightforward calculation the functions v(x) := c p |x| -2/(p-1) and u(x) := cp 1 + |x| 2 -1/(p-1) are respectively a solution of (1.1) in R n \{0} and a supersolution of (1.1) in the whole space R n , provided that p > 2 * and the constants c p , cp > 0 are chosen appropriately. Thus the previous theorem states that 2 * is the critical exponent for both the existence of positive solutions or supersolutions of (1.1) in any exterior domain, and positive supersolutions of (1.1) in the whole space R n . Recall that the famous result of Gidas and Spruck [START_REF] Gidas | Global and local behavior of positive solutions of nonlinear elliptic equations[END_REF] states that the critical exponent for existence of positive solutions of (1.1) in R n is different, namely 2 * := (n + 2)/(n -2). The delicate proof of this deep fact relies on special geometric properties and symmetries of the Laplacian. Theorem 1.1 has been extended to various quasilinear equations in divergence form, like -∆ m u = u p , see [START_REF] Bidaut-Véron | Local and global behavior of solutions of quasilinear equations of Emden-Fowler type[END_REF], as well as to more general divergence form equations such as -div(A(Du, u, x)) = 0, provided that A possesses the appropriate growth in u and Du. For more results in this direction, see [START_REF] Guedda | Local and global properties of solutions of quasilinear elliptic equations[END_REF][START_REF] Mitidieri | A priori estimates and the absence of solutions of nonlinear partial differential equations and inequalities[END_REF][START_REF] Bidaut-Véron | Nonexistence results and estimates for some nonlinear elliptic problems[END_REF][START_REF] Serrin | Cauchy-Liouville and universal boundedness theorems for quasilinear elliptic equations and inequalities[END_REF].

In this paper, we study the corresponding problem for certain fully nonlinear elliptic equations. Consequently, all differential (in)equations appearing here are to be interpreted in the viscosity sense, which is the appropriate notion of weak solution for elliptic equations in nondivergence form. Our model equation is

(1.3) F (D 2 u) = u p ,
where p > 1 and F satisfies (H1) and (H2). The arguments we give are completely different from the ones in the above quoted works, since energy methods are obviously inapplicable to the study of (1.3). Instead, our approach relies on the maximum principle, and makes essential use of the following result we recently obtained with Smart [START_REF] Armstrong | Fundamental solutions of homogeneous fully nonlinear elliptic equations[END_REF] on the existence and properties of fundamental solutions of fully nonlinear equations.

Theorem 1.2 ([3]

). Assume F satisfies (H1) and (H2). The equation

F (D 2 u) = 0 in R n \ {0} has a non-constant solution that is bounded below in B 1 and bounded above in R n \ B 1 . Moreover, the set of all such solutions is {aΦ + b | a > 0, b ∈ R}, where Φ ∈ C 1,δ loc (R n \ {0}
) can be chosen to satisfy one of the following homogeneity relations: for all σ > 0,

(1.4) Φ(x) = Φ(σx) + log σ or Φ(x) = σ α * Φ(σx) α * Φ(x) > 0 for x ∈ R n \ {0},
for some unique number α * = α * (F ) ∈ (-1, ∞) \ {0} which depends only on F and n (we set α * (F ) = 0 in case the first alterantive in (1.4) occurs). We call α * (F ) the scaling exponent of F , and we call Φ the fundamental solution of F .

Remark 1.3. Of course, the fundamental solution of the Laplacian is Φ

(x) = |x| 2-n , if n ≥ 3, and Φ(x) = -log |x|, if n = 2, so the scaling exponent of -∆ is α * (-∆) = n -2.
For a general F satisfying (H1) and (H2), the scaling exponent can be any number between λ Λ (n-1)-1 and Λ λ (n-1)-1. For more on fundamental solutions and scaling exponents, we refer to [START_REF] Armstrong | Fundamental solutions of homogeneous fully nonlinear elliptic equations[END_REF].

Equation (1.3) has another "scaling exponent", given by the interplay between the 1-homogeneity of the elliptic operator and the p-homogeneity of the right-hand side in (1.3). If u is a (sub/super)solution of (1.3) in the exterior domain R n \ B R , then it is easy to check that the rescaled function u σ , defined for each σ > 0 by

u σ (x) := σ β * u(σx), β * = β * (p) := 2 p -1 ,
is also a (sub/super)solution of (1.3) in the domain R n \ B R/σ . In order to compare with (1.4), note that Φ σ ≡ Φ when α * = β * .

Put briefly, our main result for (1.3) asserts that the answer to the question of whether there exists a positive (super)solution in exterior domains, or a positive supersolution in the whole space R n , is determined by which of the numbers α * (F ) and β * (p) is greater. This result extends Theorem 1.1 to arbitrary Isaacs operators, and provides a new perspective on this theorem by embedding the Laplacian in the family of positively homogeneous, uniformly elliptic operators. From our point of view, the condition p ≤ n/(n -2) is better written as n -2 ≤ 2/(p -1), which emphasizes the competition between the homogeneity of the fundamental solution of the Laplacian and the scaling exponent β * (p) = 2/(p -1) for equation (1.1). Of course, we may also write the inequality α * (F ) ≤ β * (p) in terms of p as

(1.5) p ≤ 2 * (F ) := α * (F )+2 α * (F ) if α * (F ) > 0, ∞ if α * (F ) ≤ 0.
To our knowledge, there are no previous results concerning the nonexistence of positive solutions of fully nonlinear equations and inequalities in exterior domains. Theorem 1.4 implies (1.3) has no positive singular supersolutions, with singularities contained in a bounded set, provided that α * ≤ β * .

In the special case that (1.3) is posed in the whole space R n , and F is a Pucci extremal operator (see Section 2 for a definition of these operators), problem (1.3) was studied and Theorem 1.4 was proved by Cutri and Leoni [START_REF] Cutrì | On the Liouville property for fully nonlinear equations[END_REF]. Their result was extended to a class of rotationally invariant operators 1 in a recent paper by Felmer and Quaas [START_REF] Felmer | Fundamental solutions and two properties of elliptic maximal and minimal operators[END_REF]. Note that for rotationally invariant operators the existence statements (ii) and (iii) in Theorem 1.4 are trivial. For such operators, just as for (1.1), it can be checked by a direct computation that if α * > β * , then the functions v(x) := c|x| -2/(p-1) and u(x) := c 1 + |x| 2 -1/(p-1) are respectively a solution of (1.3) in R n \ {0} and a supersolution of (1.3) in the whole space R n , for suitably chosen constants c, c > 0. The proofs of the nonexistence statements in [START_REF] Cutrì | On the Liouville property for fully nonlinear equations[END_REF] and [START_REF] Felmer | Fundamental solutions and two properties of elliptic maximal and minimal operators[END_REF] depend heavily on the rotational invariance of F , in particular on the existence of radial fundamental solutions for F . Theorem 1.4 generalizes these results first by dropping the assumption of rotational invariance and considering an arbitrary fully nonlinear operator satisfying (H1) and (H2), and second by requiring only that the equation hold in an exterior domain, which yields a Liouville statement for singular solutions. Our proof of Theorem 1.4 is (necessarily) accomplished through a different argument than the one given in both [START_REF] Cutrì | On the Liouville property for fully nonlinear equations[END_REF] and [START_REF] Felmer | Fundamental solutions and two properties of elliptic maximal and minimal operators[END_REF]. The proof of part (i) makes use of the scaling properties of the equation and of the maximum principle to compare a positive supersolution of (1.3) with the fundamental solution Φ of F . To prove part (ii), we show that the ellipticity estimates imply that some power of the fundamental solution of F is a supersolution of (1.3), which permits us to construct a solution of (1.3) in the whole space by a truncation-type argument.

Finally, Theorem 1.4(iii) is proved with the help of Krasnoselskii degree theory (see Theorem 3.5 in Section 3), a tool which became popular in elliptic PDE with the well-known works of Amann (see e.g. [START_REF] Amann | Fixed point equations and nonlinear eigenvalue problems in ordered Banach spaces[END_REF]). An essential step in the application of degree theoretic results lies in estabishing a priori bounds. The classical blowup argument, introduced by Gidas and Spruck [START_REF] Gidas | A priori bounds for positive solutions of nonlinear elliptic equations[END_REF] and de Figueiredo, Lions and Nussbaum [START_REF] De Figueiredo | A priori estimates and existence of positive solutions of semilinear elliptic equations[END_REF], has been employed many times in the last thirty years to obtain a priori bounds and hence existence results for nonlinear problems in bounded domains. In the fully nonlinear setting this approach was first used in [START_REF] Quaas | Existence results for nonproper elliptic equations involving the Pucci operator[END_REF].

It is less typical for a priori estimates and degree theory to be used to establish existence results in unbounded domains, and their application hides some specificities. In particular, we deduce an a priori estimate by an argument which is different than the one typically used in the literature (for example in [START_REF] De Figueiredo | A priori estimates and existence of positive solutions of semilinear elliptic equations[END_REF][START_REF] Gidas | A priori bounds for positive solutions of nonlinear elliptic equations[END_REF]). In fact, we will prove the following result, which implies Theorem 1.4(iii) and deserves to be stated separately.

Theorem 1.5. Assume β * (p) < α * (F ). Then at least one of the following holds:

(i) equation (1.3) has a bounded positive solution in the whole space R n , or (ii) equation (1.3) has a positive solution u in the domain R n \ {0} which is (-β * (p))-homogeneous, that is, u σ ≡ u for all σ > 0.
In Section 3 we give an extended discussion of our arguments and compare them to those of previous papers on the subject. Let us mention here another advantage of our approach, which is that it easily adapts to more general nonlinearities f = f (x, u) as in (1.2). An extension of our results to equation (1.2) is given in Theorem 3.1, which roughly states that analogous conclusions as in Theorem 1.4 (i)-(ii) hold for (1.2), provided f is positive, behaves like |x| -γ u p for large |x| and small u, and satisfies a mild global hypothesis.

It remains an interesting open question whether the result of Gidas and Spruck [START_REF] Gidas | Global and local behavior of positive solutions of nonlinear elliptic equations[END_REF] can be extended to fully nonlinear equations. For more details on this question, we refer to Felmer and Quaas [START_REF] Felmer | On critical exponents for the Pucci's extremal operators[END_REF], who used ODE techniques to study the existence and nonexistence of radial solutions in R n for rotationally invariant operators.

In the next section, we very briefly describe some notation and results from the theory of viscosity solutions of fully nonlinear equations. Our main result is proved in Section 3.

Some notations and results on viscosity solutions of elliptic PDE

This short section is meant for readers who are not familiar with the theory of fully nonlinear equations and the concept of viscosity solutions.

We denote the set of n-by-n real symmetric matrices by S n , and I n ∈ S n is the identity matrix. If x, y ∈ R n , we denote by x ⊗ y the symmetric matrix with entries 1 2 (x i y j + x j y i ). For M, N ∈ S n , we write M ≥ N if M -N has nonnegative eigenvalues. The Pucci extremal operators are defined by

P + λ,Λ (M ) := sup A∈ λ,Λ [-trace(AM )] and P - λ,Λ (M ) := inf A∈ λ,Λ [-trace(AM )] ,
for each M ∈ S n and 0 < λ ≤ Λ, where λ, Λ ⊆ S n is the subset of S n consisting of the matrices A for which λI n ≤ A ≤ ΛI n . The following equivalent definition of the Pucci extremal operators is often more convenient for calculations:

(2.1)

P + λ,Λ (M ) = -λ µj >0 µ j -Λ µj <0 µ j and P - λ,Λ (M ) = -Λ µj >0 µ j -λ µj <0 µ j ,
where µ 1 , . . . , µ n are the eigenvalues of M . See Caffarelli and Cabre [START_REF] Caffarelli | Fully nonlinear elliptic equations[END_REF] for more on these operators (to avoid confusion with the notations in [START_REF] Caffarelli | Fully nonlinear elliptic equations[END_REF], note that

P + λ,Λ (M ) = -M -(M, λ, Λ) and P - λ,Λ (M ) = -M + (M, λ, Λ)
, where M ± are as in [START_REF] Caffarelli | Fully nonlinear elliptic equations[END_REF]). An equivalent way of writing (H1) is (H1) there exist 0 < λ ≤ Λ such that for every M, N ∈ S n ,

P - λ,Λ (M -N ) ≤ F (M ) -F (N ) ≤ P + λ,Λ (M -N ).
Observe that (H1) and (H2) are satisfied for both F = P - λ,Λ and F = P + λ,Λ , and these hypotheses imply P - λ,Λ (M ) ≤ F (M ) ≤ P + λ,Λ (M ) for each M ∈ S n . Furthermore, an equivalent way of stating (H1) and (H2) is to assume F is of the form

(2.2) F (D 2 u) = sup α∈A inf β∈B -a α,β ij ∂ ij u or F (D 2 u) = inf α∈A sup β∈B -a α,β ij ∂ ij u ,
where α, β are indices that belong to some sets A and B, and the symmetric matrices A α,β = (a α,β ij ) satisfy the inequality λI ≤ A α,β ≤ ΛI. This is the form of general Isaacs operators, which are fundamental in the theory of two-player zerosum stochastic differential games. In the particular case card(B) = 1, the operator F in (2.2) is called a Hamilton-Jacobi-Bellman operator -these have many uses in applied mathematics, and arise in the theory of stochastic optimal control. We refer to Cabre [START_REF] Cabré | Elliptic PDE's in probability and geometry: symmetry and regularity of solutions[END_REF] as well as Fleming and Soner [START_REF] Fleming | Controlled Markov processes and viscosity solutions[END_REF] for references and more on Hamilton-Jacobi-Bellman and Isaacs equations.

Suppose that Ω is an open subset of R n , F satisfies (H1), and f ∈ C(Ω). A continuous function u ∈ C(Ω) is a viscosity subsolution (resp. supersolution) of the equation

(2.3) F (D 2 u) = f (x) in Ω, if, for every point x 0 ∈ Ω and test function ϕ ∈ C 2 (Ω) such that x → u(x) -ϕ(x)
has a local maximum (resp. minimum) at x 0 , we have

F (D 2 ϕ(x 0 )) ≤ (resp. ≥) f (x 0 ).
We say that u is a viscosity solution of (2.3) if it is both a viscosity subsolution and supersolution of (2.3). Below we mention some standard results from the theory of viscosity solutions which will be used in this article. All differential operators F , G, H, appearing below are assumed to satisfy only (H1).

• Maximum principle and strong maximum principle ([9, Proposition 4.9, Theorem 5.3] and Theorem 3.3 in [START_REF] Michael | User's guide to viscosity solutions of second order partial differential equations[END_REF] together with the remarks in Example 3.6 and section 5.C in that paper). Suppose that Ω is bounded and

u, v ∈ C( Ω), f ∈ C(Ω) satisfy F (D 2 u) ≤ f ≤ F (D 2 v) in Ω and u ≤ v on ∂Ω . Then u ≤ v in Ω. If u(x 0 ) = v(x 0 ) at some point x 0 ∈ Ω, then u ≡ v in Ω. • Transitivity of inequalities in the viscosity sense ([9, Theorem 5.3] and [2, Lemma 3.6]). Assume F (M ) + G(N ) ≥ H(M + N ) for each M, N ∈ S n . If u, v, f, g ∈ C(Ω) are such that F (D 2 u) ≤ f and G(D 2 v) ≤ g in Ω, then the function w := u + v satisfies H(D 2 w) ≤ f + g in Ω. • Local Hölder estimates ([9, Theorem 4.10]). Suppose that u, f ∈ C(Ω) satisfy the inequalities P - λ,Λ (D 2 u) ≤ |f | and P + λ,Λ (D 2 u) ≥ -|f | in Ω. Then there is a constant 0 < γ < 1, γ = γ(n, λ, Λ), such that for each compact subset K ⊆ Ω we can find C = C(n, Λ, λ, K, Ω) for which u C γ (K) ≤ C u L ∞ (Ω) + f L n (Ω) .
• The infimum of a family of supersolutions which is uniformly bounded below is a supersolution. ([9, Proposition 2.7]).

The book [START_REF] Caffarelli | Fully nonlinear elliptic equations[END_REF] is a nice introduction to the theory of viscosity solutions of fully nonlinear, uniformly elliptic equations. See also Crandall, Ishii, and Lions [START_REF] Michael | User's guide to viscosity solutions of second order partial differential equations[END_REF].

Further remarks and proofs

3.1. Discussion and more general results. To put our main result and its proof in a proper context, we begin this section with a discussion. First, all earlier results concerning linear and quasilinear operators in divergence form use the weak formulation of the equation in terms of integrals, a feature which operators in nondivergence form do not have. For example, a simple way to prove a nonexistence result for (1.1) is to replace u by its spherical mean, which is a supersolution too, by Jensen's inequality. It is then enough to study radial supersolutions, which can be reduced to an ODE problem (see for example Guedda and Véron [START_REF] Guedda | Local and global properties of solutions of quasilinear elliptic equations[END_REF]).

A different approach is required in the nondivergence setting. It was noticed by Labutin [START_REF] Labutin | Isolated singularities for fully nonlinear elliptic equations[END_REF] as well as in [START_REF] Cutrì | On the Liouville property for fully nonlinear equations[END_REF] and [START_REF] Felmer | Fundamental solutions and two properties of elliptic maximal and minimal operators[END_REF] that for certain rotationally invariant fully nonlinear operators F , such as the Pucci extremal operators, there exists a unique number α = α * (F ) ∈ (-1, ∞) for which the function ξ α defined by

(3.1) ξ α (x) :=    |x| -α if α > 0, -log |x| if α = 0, -|x| -α if α < 0, is a smooth solution of F (D 2 ξ α ) = 0 in R n \ {0}
. This is easy to verify by a direct computation. For the Pucci maximal operator P + λ,Λ we have α * (P + λ,Λ ) = Λ λ (n-1)-1, while the Pucci minimal operator P - λ,Λ has scaling exponent α * (P - λ,Λ ) = λ Λ (n-1)-1. It is then shown in [START_REF] Cutrì | On the Liouville property for fully nonlinear equations[END_REF][START_REF] Felmer | Fundamental solutions and two properties of elliptic maximal and minimal operators[END_REF] that (1.3) has no positive supersolutions in the whole space R n if and only if (1.5) holds. The argument used in these papers relies on the fact that any solution of F (D 2 u) ≥ 0 in R n satisfies min ∂Br u = min Br u by the maximum principle, so the function r → m(r) = min ∂Br u is decreasing. Together with the radial symmetry of the fundamental solution, this permits one to prove an analogue of Hadamard's three spheres theorem, which in turn implies that the function r α * (F ) m(r) is increasing. Finally, with the help of a judiciously chosen test function, one obtains the inequality m(r) p ≤ Cr 2 m(r/2), which contradicts properties of m(r). This approach cannot be used if the operator is not rotationally invariant, or if the domain is not R n .

In addition to being more general, our proof of the corresponding Liouvilletype result, Theorem 1.4(i), is actually simpler. It has two central ideas. First, we observe that a nontrivial solution of F (D 2 u) ≥ 0 in an exterior domain must be greater than a constant multiple of the fundamental solution, according to the maximum principle. Second, thanks to the scaling properties of (1.3), we will see that in the case α * (F ) ≤ β * (p) the existence of a nontrivial solution of (1.3) contradicts the finiteness of the first half-eigenvalue of F in an annular domain.

The existence statement (ii) in Theorem 1.4 is obtained by "bending" the fundamental solution, that is, by showing that some power of Φ is a supersolution in R n \ {0} of the inequality we want to solve. Then a supersolution in R n is obtained by truncating this function around the origin in a suitable way.

The proof of Theorem 1.4(iii) is based on a well-known theorem by Krasnoselskii, which asserts the existence of a nonzero fixed point of any compact map which sends a convex cone into itself, under some conditions on its behavior on two distinct spheres. The precise statement of this theorem is given in Theorem 3.5 below. To apply it, we show that an appropriate map can be defined on the cone of nonnegative (-β * )-homogeneous functions whenever β * < α * . We verify that its fixed points are solutions of (1.3), and that it satisfies the conditions of Krasnoselskii's theorem under the assumption that (1.3) does not have bounded positive solutions in the whole space R n . On the other hand, if (1.3) has a positive solution in R n , then of course this solution is also a solution in R n \ {0}, so we have nothing to prove.

As we noted in the introduction, we can easily extend our results to more general nonlinearities f (x, u). The next theorem generalizes our statements on supersolutions, that is, Theorem 1.4 (i) and (ii). We denote

β * = β * (p, γ) := 2 -γ p -1 ,
for each γ < 2 and p > 1.

Theorem 3.1. Assume that the operator F satisfies (H1) and (H2), R 0 > 0, and f : (R n \ B R0 ) × (0, ∞) → (0, ∞) is a continuous function (note f needs not be defined at u = 0).

(i) Suppose there exist ε 0 , c 0 , C 0 > 0, p > 1, γ < 2 such that α * (F ) ≤ β * (p, γ),

(3.2) f (x, s) ≥ c 0 |x| -γ s p in (R n \ B R0 ) × (0, ε 0 ), and
(3.3) f (x, s) s ≤ C 0 f (x, t) t for all t > 0, s ∈ (0, min{t, ε 0 }), |x| ≥ R 0 .
Then (1.2) has no positive supersolution in any exterior domain. (ii) Suppose that there exist constants ε 0 , C 0 > 0, p > 1 and γ < 2 such that α * (F ) > β * (p, γ) and

(3.4) f (x, s) ≤ C 0 |x| -γ s p in (R n \ B R0 ) × (0, ε 0 ).
Then there exists a positive supersolution of

(1.2) in R n \ B R0 . If in addition γ ≤ 0 and (3.4) holds in R n × (0, ε 0 ), then (1.
2) has a positive supersolution in the whole space R n .

Remark 3.2. The number β * (p, γ) defined in this theorem is the scaling exponent of the equation

(3.5) F (D 2 u) = |x| -γ u p .
That is, if u is a (sub/super)solution of (3.5) in R n \ B R , then the rescaled function

(3.6) u σ (x) := σ β * u(σx), β * = 2 -γ p -1 , is also a (sub/super)solution of (3.5) in R n \ B R/σ .
Remark 3.3. In the case f = f (s) does not depend on x, conditions (3.2) and (3.4) in Theorem 3.1 suggest that it is the behaviour of f (s) near s = 0 that determines whether there exist positive supersolutions of (1.2) in exterior domains. While condition (3.3) is a global hypothesis, it is not very restrictive. In fact, hypothesis (3.3) turns out to be necessary only for the method of proof we employ.

We have recently discovered another approach which permits us to replace (3.3) by an optimal hypothesis, and yields nonexistence results for sublinear equations (p < 1) as well as for systems of Lane-Emden type. This alternative method, based on some results from the regularity theory of Krylov and Safonov (c.f. [START_REF] Krylov | Nonlinear elliptic and parabolic equations of the second order, volume 7 of Mathematics and its Applications[END_REF]), will be described in a forthcoming article.

3.2.

Proof of the nonexistence result. The existence of fundamental solutions of quasilinear equations provides a lower bound on positive supersolutions, as observed for example in [START_REF] Serrin | Cauchy-Liouville and universal boundedness theorems for quasilinear elliptic equations and inequalities[END_REF]Lemma 2.3] and [START_REF] Bidaut-Véron | Nonexistence results and estimates for some nonlinear elliptic problems[END_REF]Proposition 2.6]. The following lemma states that the same is valid for uniformly elliptic operators of Isaacs type. Its simple proof needs only Theorem 1.2 and the maximum principle.

Lemma 3.4. Suppose that R 1 > 0 and u ∈ C(R n \ B R1 ) is a positive solution of F (D 2 u) ≥ 0 in R n \ BR1 . Then for some c > 0, (3.7) u(x) ≥ c|x| -α in R n \ B R1 ,
where α := max{0, α * (F )}.

Proof. We first consider the case α * (F ) > 0. By Theorem 1.2, the fundamental solution Φ of F is such that Φ > 0 and Φ(x) → 0 as |x| → ∞. Select c > 0 so small that u ≥ cΦ on ∂B R1 . Then for each ε > 0, there exists R = R(ε

) > R 1 such that u + ε ≥ ε ≥ Φ in R n \ B R.
Applying the maximum principle to

F (D 2 (u + ε)) ≥ 0 = F (D 2 Φ) in B R \ B R1 , for each R > R(ε), we conclude that u + ε ≥ Φ in R n \ B R1 . Letting ε → 0 we obtain u ≥ Φ in R n \ B R1
. This implies (3.7) by the homogeneity of Φ, since Φ(x) = |x| -α * (F ) Φ(x/|x|) for every x ∈ R n \ {0}.

In the case α * (F ) ≤ 0, we have Φ(x) → -∞ as |x| → ∞. Setting

c := (1/2) min ∂B R 1 u > 0,
we observe that u ≥ εΦ + c on ∂(B R \ B R1 ), for each 0 < ε < c/(max ∂B R 1 Φ), and each R > R(ε) sufficiently large. By the maximum principle, we have u ≥ εΦ + c in R n \ B R1 . By passing to the limit ε → 0, we deduce that u ≥ c.

Proof of Theorem 3.1 (i). Assume first that there exists u > 0 which is a supersolution of (1.2) with f (x, u) = |x| -γ u p , that is,

(3.8) F (D 2 u) ≥ |x| -γ u p
in some exterior domain R n \ B R1 . We can assume R 1 > 1. We will argue that the number β * defined in (3.6) is such that

β * < α * (F ).
In what follows c, C denote positive constants which may change from line to line, and depend only on F and n.

By Remark 3.2, for each σ ≥ R 1 the function u σ given by (3.6) is a supersolution of (3.8) in R n \ B 1 , and hence

(3.9) F (D 2 u σ ) ≥ |x| -γ u p σ ≥ min{1, 2 -γ } u p σ in B 2 \ B 1 .
By applying Lemma 3.4 to u and expressing (3.7) in terms of u σ , we obtain

(3.10) u σ (x) = σ β * u(σx) ≥ cσ β * -α |x| -α for every σ ≥ 1 and |x| ≥ R 1 /σ,
where α := max{0, α * (F )}. Thus for every σ ≥ R 1 , we have

u σ (x) ≥ cσ β * -α in B 2 \ B 1 .
Hence by (3.9), (3.11)

F (D 2 u σ ) ≥ cσ (β * -α)(p-1) u σ in B 2 \ B 1 .
The existence of a positive function u σ satisfying this inequality implies that the first eigenvalue of F in the bounded regular domain B 2 \ B 1 is bounded below by cσ (β * -α)(p-1) , for every σ ≥ R 1 . This is of course a contradiction if β * > α and σ ≥ 2R 1 is taken large enough, since the first eigenvalue λ + 1 (F, B 2 \ B 1 ) is finite. For a simple proof 2 of a finite upper bound on the first eigenvalue, which requires only the maximum principle, see the definition of λ + 1 (F, Ω) as well as Lemma 3.7 in [START_REF] Scott | Principal eigenvalues and an anti-maximum principle for homogeneous fully nonlinear elliptic equations[END_REF]. For more on first eigenvalues of fully nonlinear equations of Isaacs type, see [START_REF] Quaas | Principal eigenvalues and the Dirichlet problem for fully nonlinear elliptic operators[END_REF][START_REF] Scott | Principal eigenvalues and an anti-maximum principle for homogeneous fully nonlinear elliptic equations[END_REF] and the references therein.

We have left to rule out the critical case α = α * (F ) = β * > 0. We first show that in this case we can improve (3.10). Define w(x) := Φ(x) (log |x|) and observe that by (H1) and (H2),

F (D 2 w) ≤ log |x|F (D 2 Φ) + 2P + λ,Λ (D log |x| ⊗ DΦ) + ΦP + λ,Λ (D 2 log |x|) = 2|x| -2 P + λ,Λ (x ⊗ DΦ(x)) + Φ(x)P + λ,Λ |x| -2 I n -2|x| -4 x ⊗ x in R n \ B R1 , provided that Φ ∈ C 2 (R n \ B R1
). We remark that differentiating the equality Φ(x) = t α Φ(tx) with respect to x yields that the matrix

H(x) = x⊗DΦ(x) Φ(x) satisfies H(tx) = H(x) for all t > 0. Thus P + λ,Λ (H(x)) ≤ C = max ∂B2 P + λ,Λ (H(x)) in R n \ B 1 .
The latter is rigorous, since Φ is locally uniformly bounded in C 1 , 2 In view of possible applications of this method to other problems, we note that this argument does not depend on the existence of an eigenfunction.

depending only on the constants λ, Λ, and n. Thus P + λ,Λ (x ⊗ DΦ(x)) ≤ CΦ(x), and since the eigenvalues of x ⊗ x are 0 and |x| 2 , we obtain (3.12)

F (D 2 w) ≤ C|x| -2 Φ(x) ≤ C|x| -α-2 in R n \ B R1 .
By performing an analogous calculation with a smooth test function, we confirm that the differential inequality (3.12) holds rigorously in the viscosity sense, even when Φ is only in C 1,γ loc but not in C 2 (see for instance the proof of Lemma 3.3 in [START_REF] Armstrong | Fundamental solutions of homogeneous fully nonlinear elliptic equations[END_REF]). According to Lemma 3.4 and (3.8), we also have

(3.13) F (D 2 u) ≥ |x| -γ u p ≥ c|x| -γ-pα = c|x| -α-2 in R n \ B R1 , since α = β * . Note that Theorem 1.2 implies w = Φ(x) log |x| → 0 as |x| → ∞, since α * = β * > 0.
By (3.12), (3.13), and the maximum principle, we infer that

u + ε ≥ cw in B R \ B R1
for every ε > 0 and every R > R(ε) sufficiently large. Therefore by letting first R → ∞ and then ε → 0 we obtain

u ≥ c|x| -α log |x| in R n \ B R1 ,
by the definition of w and Theorem 1.2. Rescaling, we find that for σ ≥ R 1 ,

u σ ≥ c log σ in B 2 \ B 1 .
Thus for all σ ≥ R 1 ,

F (D 2 u σ ) ≥ |x| -γ u p σ ≥ c(log σ) p-1 u σ in B 2 \ B 1 .
As above, this shows that the first eigenvalue of F in B 2 \ B 1 is bounded below by c 3 (log σ) p-1 . Sending σ → ∞ yields a contradiction. This completes the proof of Theorem 3.1(i) in the case that f (x, u) = |x| -γ u p .

Finally, we remark that in the case of general nonlinearity f satisfying the hypotheses of Theorem 3.1 the problem can be reduced to the particular case we have just studied. Namely, with the help of Lemma 3.4 we obtain

(3.14) f (x, u) u p ≥ f (x, c|x| -α ) u p-1 c|x| -α ≥ c|x| -γ-α(p-1) u p-1 = c|x| -γ c|x| -α u p-1 ≥ c|x| -γ in R n \ B R1 .
The first inequality in (3.14) follows from Lemma 3.4 and (3.3) (if necessary, we take larger R 1 , so that R 1 ≥ R 0 and c|x| -α ≤ ε 0 in R n \ B R1 ), the second inequality is a consequence of (3.2), and the last inequality follows again from Lemma 3.4. Hence the nonexistence statement in Theorem 3.1 follows from what we already proved.

3.3. Proof of Theorem 3.1 (ii). We suppose 0 < (2 -γ)/(p -1) = β * < α * (F ). Define v := Φ τ where τ := β * /α * (F ) ∈ (0, 1). In the case Φ ∈ C 2 , we have

D 2 v = τ Φ τ -1 D 2 Φ -τ (1 -τ )Φ τ -2 (DΦ ⊗ DΦ) ,
so by (H1) and (H2) we obtain

F (D 2 v) ≥ τ Φ τ -1 F (D 2 Φ) + τ (1 -τ )Φ τ -2 P - λ,Λ (-DΦ ⊗ DΦ) = λτ (1 -τ )Φ τ -2 |DΦ| 2 in R n \ {0}
. This is routine to confirm in the viscosity sense in the case Φ ∈ C 2 . By differentiating Φ(x) = σ α Φ(σx) with respect to σ, we see that x • DΦ = -αΦ, hence |DΦ| ≥ α|x| -1 Φ. Therefore,

F (D 2 v) ≥ c|x| -2 Φ τ ≥ c|x| -τ α * -2 in R n \ {0}. Since 0 < c|x| -β * ≤ v(x) ≤ C|x| -β * and -β * p -γ = -τ α * -2, we deduce that (3.15) F (D 2 v) ≥ c|x| -γ v p in R n \ {0}.
Suppose in addition that γ ≤ 0. For a > 0, let w ∈ C( B1 ) be the unique solution of the Dirichlet problem

F (D 2 w) = a in B 1 , w = 0 on ∂B 1 .
The ABP inequality ([9, Theorem 3.6]) provides us the estimate 0 < w ≤ Ca. Thus if a > 0 is sufficiently small, the function w satisfies

(3.16) F (D 2 w) ≥ |x| -γ w p in B 1 .
By multiplying v = Φ τ by a small constant, if necessary, we may assume without loss of generality that v satisfies (3.15) and v < w in B 1/2 \ B 1/4 . Since v(x) → ∞ as |x| → 0, there exists δ > 0 such that w < v in B 2δ . Now define the function

u(x) :=      w(x) x ∈ B δ , min{v(x), w(x)} x ∈ B 1/3 \ B δ , v(x) x ∈ R n \ B 1/3 .
By construction, u is a supersolution of (3.5) in the whole space R n , since the minimum of two supersolutions is also a supersolution. This completes the proof of Theorem 3.1 (ii), in the special case f (x, u) = |x| -γ u p . Moreover, inequalities (3.15) and (3.16) continue to hold if we replace v (resp. w) by av (resp. aw), for any a ≤ 1. Since we can find a so small that av ≤ ε 0 in R n \ {B 1/3 } (resp. aw ≤ ε 0 in B 1 ), Theorem 3.1 (ii) follows from the existence result we just established.

3.4.

Proof of Theorem 1.5. It is convenient to define the space

X α := {u ∈ C(R n \ {0}) : u(x) = σ α u(σx) for every x ∈ R n \ {0}, σ > 0}
for every α > 0, as well as

H α := {x ∈ X α : u ≥ 0} and H + α := {u ∈ X α : u > 0} .
Observe that X α is a Banach space under the norm u Xα = max ∂B1 |u|, and H α is a closed convex cone in X α with interior H + α . Our argument is based on the following well-known fixed point theorem, due to Krasnoselskii (see [START_REF] Krasnosel | of Grundlehren der Mathematischen Wissenschaften[END_REF]). It also appears in the appendix of Benjamin [START_REF] Benjamin | A unified theory of conjugate flows[END_REF], and is applied to semilinear elliptic equations in [START_REF] De Figueiredo | A priori estimates and existence of positive solutions of semilinear elliptic equations[END_REF]. Theorem 3.5 (Krasnoselskii). Let X be a Banach space, and C a closed convex cone in X with vertex at the origin. Consider a compact map A : C → C which satisfies A(0) = 0. Suppose there exist 0 < r < R and ξ ∈ C \ {0} such that:

(i) u = tA(u) for every 0 ≤ t ≤ 1 and u X = r, and (ii) u = A(u) + tξ for every t ≥ 0 and u X = R. Then there exists u ∈ C satisfying A(u) = u and r < u X < R.

In this subsection we set β = β * (p), where p > 1 is fixed such that β < α * (F ). We are going to apply Theorem 3.5 using the nonlinear map A : H β → H β which is defined for each v ∈ H β by A(v) := u, where u ∈ H β is the unique solution of the equation

F (D 2 u) = v p in R n \ {0}.
That A is well-defined is a consequence of [3, Lemma 3.8], our assumption that 0 < β < α * (F ), and the relation between β and p. Precisely, the number β has the property that if βp = β + 2, and therefore if v ∈ H β , then v p ∈ H β+2 . Now [3, Lemma 3.8] asserts that if 0 < α < α * (F ) and f ∈ H α , then the equation

F (D 2 u) = f in R n \ {0} has a unique solution u ∈ H α . It follows that A : H β → H β is well-defined.
Clearly A(0) = 0, while the strong maximum principle implies that A(v) ∈ H + α for every v ∈ H α \{0}. By the Hölder regularity result which we quoted in the previous section, and since viscosity solutions are stable under local uniform convergence (see for example [8, Theorem 3.8]), the map A is compact and continuous.

In the next lemma we verify that hypothesis (i) in Theorem 3.5 holds for A, that is, we find our inner radius r > 0.

Lemma 3.6. Suppose that u ∈ H β , u ≡ 0, is a solution of u = tA(u) for some 0 ≤ t ≤ 1. Then there exists a constant r > 0, which does not depend on u, such that

(3.17) u X β > r.
Proof. The equation u = tA(u) means that u ∈ H β is a solution of the equation

F (D 2 u) = tu p in R n \ {0}.
Note that t = 0, that is, F (D 2 u) = 0 in R n \ {0} is excluded by Theorem 1.2 and our assumptions u ≡ 0 and β < α * (F ). Hence u ∈ H + β by the strong maximum principle.

By [START_REF] Armstrong | Fundamental solutions of homogeneous fully nonlinear elliptic equations[END_REF]Lemma 3.8] there exists a function v ∈ H + β satisfying

F (D 2 v) = |x| -β-2 in R n \ {0}.
Since -β -2 = -βp, we may set w := av for some small 0 < a < 1 to discover that

F (D 2 w) ≥ 2w p in R n \ {0}.
Set r := min ∂B1 w and suppose that (3.17) fails. Then w ≥ u, and so by multiplying w by a positive constant at most 1, we may assume that min ∂B1 (w -u) = 0, which by the homogeneity of u and w means that min R n \{0} (w -u) = 0. By the strong maximum principle, we deduce that w ≡ u, which is impossible since t ≤ 1.

In the next lemma, we find the outer radius R > 0 in Theorem 3.5. Here we set

ξ = ξ β = |x| -β ∈ H + β . Lemma 3.7. Assume that equation (1.
3) has no bounded positive solutions. Suppose that u ∈ H β satisfies u = A(u) + tξ for some t ≥ 0. Then there exists a constant R > 0, which does not depend on u and t, such that

(3.18) u X β < R.
Proof. We can assume that u ≡ 0. The equation

(3.19) u = A(u) + tξ
means that the function w := u -tξ is in H β and satisfies the equation

F (D 2 w) = u p in R n \ {0}.
In particular w = u -tξ ≥ 0. By the strong maximum principle w ∈ H + β and hence u ∈ H + β . Put m := min ∂B1 u > 0. We first claim that there exists T > 0, which does not depend on u and t, such that t ≤ m ≤ T . Notice u ≥ tξ ≥ 0 implies t ≤ m.

Recall βp = β + 2. Let v ∈ H + β be the solution of

F (D 2 v) = ξ p .
Set a = min ∂B1 v > 0 and notice that a depends only on F and n.

F (D 2 v k (z) -t k D 2 ξ(y k + z)) = v p k in R n \ {-y k } ⊇ B R k (0).
Observe that D 2 ξ(z) = β(β + 2)|z| -β-4 z ⊗ z -β|z| -β-2 I n .

Since |y k | → ∞ and 0 ≤ t k ≤ T , we deduce that t k D 2 ξ(y k +z) → 0 locally uniformly in z ∈ R n as k → ∞. We also have R k → ∞ as k → ∞.

We will now argue that we may pass to limits in (3.22) in order to find a function v satisfying 0 ≤ v ≤ 2, v(0) = 1, and the equation Since v(0) = 1, the strong maximum principle implies that v > 0 in R n . We have obtained our desired contradiction, since we had assumed in our hypothesis that this equation has no bounded positive solutions.

F (D 2 v) = v p in R n .
Proof of Theorem 1.5. If equation (1.3) has a no bounded positive solution in R n , then Lemmas 3.6 and 3.7 assert that the map A : H β → H β satisfies the hypotheses of Theorem 3.5. Therefore there exists u ∈ H α \ {0} satisfying A(u) = u, that is, u is a solution of (1.3) in R n \ {0}. The strong maximum principle implies u > 0.

Theorem 1 . 4 .

 14 Assume that F satisfies (H1) and (H2), and p > 1. Then the generalized Emden-Fowler equation (1.3) (i) has no nontrivial nonnegative supersolution in any exterior domain of R n , if α * (F ) ≤ β * (p); (ii) has a positive supersolution in the whole R n , if α * (F ) > β * (p). (iii) has a positive solution in R n \ {0}, if α * (F ) > β * (p).

1 /β X β 1 - 2

 112 Then we haveF (D 2 w) = u p ≥ m p ξ p = F (m p v) in R n \ {0}, so that [3, Proposition 3.2(iii)] implies w ≥ m p v in R n \ {0}. In particular, u -t = w ≥ am p on ∂B 1 . Thus m ≥ m -t ≥ am p > 0.Hence t ≤ m ≤ a -1/(p-1) =: T , and we have the claim. We now prove the bound (3.18) by contradiction. If it fails, then for each k ≥ 1 there exist 0 ≤ t k ≤ T and u k ∈ H + β such that the functionw k := u k -t k ξ satisfies F (D 2 w k ) = u p k in R n \ {0}, but u k X β = max ∂B1 u k ≥ k. For each k, select x k ∈ ∂B 1 such that u k (x k ) = u k X β .Observe that by the homogeneity of u,(3.20) u k (y k ) = 1, y k := u k 1/β X β x k . Moreover, (3.21) u k ≤ 2 in B R k (y k ), R k := u k -1/β . Define v k (z) := u k (y k + z), and observe that v k satisfies v k (0) = 1, 0 ≤ v k ≤ 2 in B R k (0), and the equation(3.22)

First, observe that 2 ≤

 2 using(3.22) and (H1), we have that for |z| ≤ R k ,P - λ,Λ (D 2 v k (z)) ≤ F (D 2 v k (z) -t k D 2 ξ(y k + z)) -F (-t k D 2 ξ(y k + z)) ≤ (v k (z)) p + CT |y k + z| -β-(v k (z)) p + CT (|y k | -|z|)using also that|y k | = u k 1/β X β .Similarly, we haveP + λ,Λ (D 2 v k ) ≥ -CT 1 2 u k X β -(β+2)/β in B R k (0).Applying local Hölder estimates quoted in the previous section and using thatu k X β → ∞ and R k → ∞ as k → ∞, we have the bound sup k≥1 v k C α (B R (0)) ≤ C(R) < ∞for every R > 0. Therefore, by passing to a subsequence we may assume thatv k → v ∈ C(R n ) locally uniformly in R n . It is clear from (3.20) and (3.21) that 0 ≤ v ≤ 2 and v(0) = 1.If we define the operatorF k (M, z) := F (M -t k D 2 ξ(y k + z)), then F k (M, z) → F (M )locally uniformly in S n × R n as k → ∞, since the matrix t k D 2 ξ(y k + z) tends to 0 locally uniformly in z ∈ R n . Thus we may use [8, Theorem 3.8] to pass to limits in (3.22) and obtain F (D 2 v) = v p in R n .

rotationally invariant means that F (M ) depends only on the eigenvalues of M .


Ho-Leung L Chan
email: hlchan@cs.hku.hk

Tak-Wah W Lam
email: twlam@cs.hku.hk

Lap-Kei K Lee
email: lklee@mpi-inf.mpg.de

Hing-Fung F Ting
email: hfting@cs.hku.hk

CONTINUOUS MONITORING OF DISTRIBUTED DATA STREAMS OVER A TIME-BASED SLIDING WINDOW

Keywords: 1998 ACM Subject Classification: F.2.2 [Analysis of algorithms and problem complexity]: Nonnumerical algorithms and problems Algorithms, distributed data streams, communication efficiency, frequent items. T

The past decade has witnessed many interesting algorithms for maintaining statistics over a data stream. This paper initiates a theoretical study of algorithms for monitoring distributed data streams over a time-based sliding window (which contains a variable number of items and possibly out-of-order items). The concern is how to minimize the communication between individual streams and the root, while allowing the root, at any time, to be able to report the global statistics of all streams within a given error bound. This paper presents communication-efficient algorithms for three classical statistics, namely, basic counting, frequent items and quantiles. The worst-case communication cost over a window is O( k ε log εN k ) bits for basic counting and O( k ε log N k ) words for the remainings, where k is the number of distributed data streams, N is the total number of items in the streams that arrive or expire in the window, and ε < 1 is the desired error bound. Matching and nearly matching lower bounds are also obtained.

Introduction

The problems studied in this paper are best illustrated by the following puzzle. John and Mary work in different laboratories and communicate by telephone only. In a foreverrunning experiment, John records which devices have an exceptional signal in every 10 seconds. To adjust her devices, Mary at any time needs to keep track of the number of exceptional signals generated by each device of John in the last one hour. John can call Mary every 10 seconds to report the exceptional signals, yet this requires too many calls in an hour and the total message size per hour is linear to the total number N of exceptional signals in an hour. Mary's devices actually allow some small error. Can the number of calls and message size be reduced to o(N ), or even poly-log N if a small error (say, 0.1%) is allowed? It is important to note that the input is given online and Mary needs to know the answers continuously; this makes our problem different from those in other similar classical models, such as the Simultaneous Communication Complexity model [START_REF] Babai | Communication compleixty of simultaneous messages[END_REF], in which all inputs are given in advance and the parties need to compute an answer only once.

Motivation. The above problem appears in data stream applications, e.g., network monitoring or stock analysis. In the last decade, algorithms for continuous monitoring of a single massive data stream gained a lot of attention (see [START_REF] Ting | Data streams: models and algorithms[END_REF][START_REF] Muthukrishnan | Data streams: algorithms and applications[END_REF] for a survey), and the main challenge has been how to represent the massive data using limited space, while allowing certain statistics (e.g., item counts, quantiles) to be computed with sufficient accuracy.

The space-accuracy tradeoff for representing a single stream has gradually been understood over the years (e.g., [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF][START_REF] Demaine | Frequency estimation of internet packet streams with limited space[END_REF][START_REF] Guha | Data-streams and histograms[END_REF][START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings and data stream computation[END_REF]). Recently, motivated by large scale networks, the database community is enthusiastic about communication-efficient algorithms for continuous monitoring of multiple, distributed data streams. In such applications, we have k ≥ 1 remote sites each monitoring a data stream, and there is a root (or coordinator) responsible for computing some global statistics. A remote site needs to maintain certain statistics itself, and has to communicate with the root often enough so that the root can compute, at any time, the statistics of the union of all data streams within a certain error. The objective is to minimize the communication. The communication aspects of data streams introduce several challenging theoretical questions such as what is the optimal communication-accuracy tradeoff for maintaining a particular statistic, and whether two-way communication is inherently more efficient than one-way communication.

Data stream models and ε-approximate queries. The data stream at each remote site is a sequence of items from a totally ordered set U . Each item is associated with an integral time-stamp recording its arrival time. Each remote site has limited space and hence it can only maintain the required statistics approximately. The statistics can be based on the whole data stream [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF][START_REF] Demaine | Frequency estimation of internet packet streams with limited space[END_REF][START_REF] Guha | Data-streams and histograms[END_REF][START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings and data stream computation[END_REF] or only the recent items [START_REF] Arasu | Approximate counts and quantiles over sliding windows[END_REF][START_REF] Datar | Estimating rarity and similarity over data stream windows[END_REF][START_REF] Lee | Maintaining significant stream statistics over sliding windows[END_REF]. Recent items can be modeled by two types of sliding windows [START_REF] Babcock | Sampling from a moving window over streaming data[END_REF][START_REF] Datar | Maintaining stream statistics over sliding windows[END_REF]. Let W be the window size, which is a positive integer. The count-based sliding window includes the last W items in the data stream, while the time-based sliding window includes items whose time-stamps are within the last W time units. The latter assumes that zero or more items can arrive at a time. Items in a sliding window will expire and are more difficult to handle than in the whole data stream. For example, counting the frequency of a certain item in the whole stream can be done easily by maintaining a single counter, yet the same problem requires space Θ( 1 ε log 2 (εW )) bits for a count-based sliding window even if we allow a relative error of at most ε [START_REF] Datar | Maintaining stream statistics over sliding windows[END_REF][START_REF] Gibbons | Distributed streams algorithms for sliding windows[END_REF]. In fact, the whole data stream model can be viewed as a special case of the sliding window model with window size being infinite. Also, a count-based window is a special case of a time-based window in which exactly one item arrives at a time. This paper focuses on time-based window, and the algorithms are applicable to the other two models.

We study algorithms that enable the root to answer three types of classical ε-approximate queries, defined as follows. Let 0 < ε < 1. For any stream σ, let c j,σ and c σ be the count of item j and all items whose timestamps are in the current window, respectively. Denote c j = σ c j,σ and c = σ c σ as the total count of item j and all items in all the data streams, respectively.

• Basic Counting. Return an estimate ĉ on the total count c such that |ĉ -c| ≤ εc.

(Note that this query can be generalized to count data items of a fixed subset X ⊆ U ; the literature often refers to the special case with U = {0, 1} and X = {1}.)

• Frequent Items. Given any 0 < φ < 1, return a set F ⊆ U which includes all items j with c j ≥ φc and possibly some items j ′ with c j ′ ≥ φc -εc. • Quantiles. Given any 0 < φ < 1, return an item whose rank is in φc -εc, φc + εc among the c items in the current sliding window. As in most previous works, we need to answer the following type of ε-approximate queries in order to answer queries on frequent items.

• Approximate Counting. Given any item j, return an estimate ĉj such that |ĉ j -c j | ≤ εc. (Note that this query gives estimate for any item, not just the frequent items. Also, the error bound is in term of c, which may be much larger than c j .) We need an algorithm to determine when and how the remote sites communicate with the root so that the root can answer the queries at any time. The objective is to minimize the worst-case communication cost within a window of W time units.

Previous works. Recently, the database literature has a flurry of results on continuous monitoring of distributed data streams, e.g. [START_REF] Babcock | Distributed top-k monitoring[END_REF][START_REF] Cormode | Sketching streams through the net: distributed approximate query tracking[END_REF][START_REF] Cormode | Holistic aggregates in a networked world: distributed tracking of approximate quantiles[END_REF][START_REF] Das | Distributed set-expression cardinality estimation[END_REF][START_REF] Greenwald | Power-conserving computation of order-statistics over sensor networks[END_REF][START_REF] Jain | Insight: A distributed monitoring system for tracking continuous queries[END_REF][START_REF] Manjhi | Finding (recently) frequent items in distributed data streams[END_REF][START_REF] Mouratidis | Continuous monitoring of top-k queries over sliding windows[END_REF][START_REF] Olston | Adaptive filters for continuous queries over distributed data streams[END_REF][START_REF] Sharfman | A geometric approach to monitoring threshold functions over distributed data streams[END_REF]. The algorithms studied can be classified into two types: one-way algorithms only allow messages sent from each remote site to the root, and two-way algorithms allow bi-directional communication between the root and each site. One-way algorithms are often very simple as a remote site has little information and all it can do is to update the root when its local statistics deviate significantly from those previously sent. On the other hand, most two-way algorithms are complicated and often involve non-trivial heuristics. It is commonly believed in the database community that two-way algorithms are more efficient; however, for most existing two-way algorithms, their worst-case communication costs are still waiting for rigorous mathematical analysis, and existing works often rely on experimental results when evaluating the communication cost.

The literature contains several results on the mathematical analysis of the worst-case performance of one-way algorithms. They are all for the whole data stream setting. Keralapura et al. [START_REF] Keralapura | Communication-efficient distributed monitoring of thresholded counts[END_REF] studied the thresholded-count problem, which leads to an algorithm for basic counting with communication cost O( k ε log N k ) words, where k and N are the number of streams and the number of items in these streams, respectively. Cormode et al. [START_REF] Cormode | Holistic aggregates in a networked world: distributed tracking of approximate quantiles[END_REF] gave an algorithm for quantiles with communication cost O( k ε 2 log N k ) words per stream. They also showed how to handle frequent items via a reduction to quantiles, so the communication cost remains the same. More recently, Yi and Zhang [START_REF] Yi | Optimal tracking of distributed heavy hitters and quantiles[END_REF] have reduced the communication cost for frequent items to O( k ε log N k ) words, and quantile to O( k ε log 2 ( 1 ε ) log N k ) words, using some two-way algorithms; these are the only analyses for two-way algorithms so far.

There have been attempts to devise heuristics to extend some whole-data-stream algorithms to sliding windows, yet not much has been known about their worst-case performance. For example, Cormode et al. [START_REF] Cormode | Holistic aggregates in a networked world: distributed tracking of approximate quantiles[END_REF] have extended their algorithms for quantiles and frequent items to sliding windows. They believed that the communication cost would only have a mild increase, but no supporting analysis has been given. The analysis of slidingwindow algorithms is more difficult because the expiry of items destroys some monotonic property that is important to the analysis for whole data stream. In fact, finding slidingwindow algorithms with efficient worst-case communication has been posed as an open problem in the latest work of Yi and Zhang [START_REF] Yi | Optimal tracking of distributed heavy hitters and quantiles[END_REF].

Our results. This paper gives the first mathematical analysis of the communication cost in the sliding window model. We derive lower bounds on the worst-case communication cost of any two-way algorithm (and hence any one-way algorithm) for answering the four

Basic Counting

Approximate Counting/ Quantiles (bits)

Frequent items (words) (words)

Whole data O( k ε log N k ) words [21] O( k ε log N k ) [29] O( k ε log 2 ( 1 ε ) log N k ) [29] stream Θ( k ε log εN k ) bits Ω( k ε log εN k ) [29, 30] Sliding window Θ( k ε log εN k ) O( k ε log N k ) O( k ε 2 log N k ) Ω( k ε log εN k ) Sliding window O(( W W -τ ) k ε log εN k ) O(( W W -τ ) k ε log N k ) O(( W W -τ ) k ε 2 log N k ) & out-of-order Ω(max{ W W -τ , k ε log εN k }) Ω(max{ W W -τ , k ε log εN k })
Table 1: Bounds on the communication costs. Note that the bounds are stated in bits for basic counting, and in words for the other problems.

types of ε-approximate queries. These lower bounds hold even when each remote site has unlimited space to maintain the local statistics exactly. More interestingly, we analyze some common-sense algorithms that use one-way communication only and prove that their communication costs match or nearly match the corresponding lower bounds. In our algorithms, each remote site only needs to maintain some Θ(ε)-approximate statistics for its local data, which actually adds more complication to the problem. These results demonstrate optimal or near optimal communication-accuracy tradeoffs for supporting these queries over the sliding window. Our work reveals that two-way algorithms could not be much better than one-way algorithms in the worst case.

Below we state the lower and upper bounds precisely. Recall that there are k remote sites and the sliding window contains W time units. We prove that within any window, the root and the remote sites need to communicate, in the worst case, Ω( k ε log εN k ) bits for basic counting and Ω( k ε log εN k ) words for the other three queries, where N is the total number of items arriving or expiring within that window. 1 For upper bounds, our analysis shows that basic counting requires O( k ε log εN k ) bits within any window, and approximate counting O( k ε log N k ) words. The estimates given by approximate counting are sufficient to find frequent items, hence the latter problem has the same communication cost. For quantiles, it takes O( k ε 2 log N k ) words. See the second row (sliding window) of Table 1 for a summary.

As mentioned before, sliding-window algorithms can be applied to handle the special case of whole data streams in which the window size W is infinite and N is the total number of arrived items. The first row of Table 1 shows the results on whole data streams. Our work has improved the communication cost for basic counting from O( k ε log N k ) words [START_REF] Keralapura | Communication-efficient distributed monitoring of thresholded counts[END_REF] to O( k ε log εN k ) bits. For approximate counting and frequent items, our work implies a one-way algorithm with communication cost of O( k ε log N k ) words; this matches the performance of the two-way algorithm by Yi and Zhang [START_REF] Yi | Optimal tracking of distributed heavy hitters and quantiles[END_REF]. In their algorithm, the root regularly updates every remote site about the global count of all items. In contrast, we use the idea that items with small count could be "turned off" for further updating. As a remark, our upper bound on quantiles is O( k ε 2 log N k ) words which is weaker than that of [START_REF] Yi | Optimal tracking of distributed heavy hitters and quantiles[END_REF]. Our algorithms can be readily applied to out-of-order streams [START_REF] Busch | A deterministic algorithm for summarizing asynchronous streams over a sliding window[END_REF][START_REF] Cormode | Time-decaying aggregates in out-of-order streams[END_REF]. In an out-oforder stream, each item is associated with an integral time-stamp recording its creation time, which may be different from its arrival time. We say that the stream has tardiness τ if any item with time-stamp t must arrive within τ time units from t, i.e., at any time in [t, t + τ ]. Without loss of generality, we assume that τ ∈ {0, 1, 2, . . . , W -1} (if an item time-stamped at t arrives after t + W -1, it has already expired and can be ignored). Note that for any data stream with tardiness greater than zero, the items may not be arriving in non-decreasing order of their time-stamps. Our previous discussion of data streams assumes tardiness equal to 0, and such data streams are called in-order data streams. The previous lower bounds for in-order streams are all valid in the out-of-order setting. In addition, we obtain lower bounds related to τ , namely, Ω( W W -τ ) bits for basic counting and Ω( W W -τ ) words for the other three problems. Regarding upper bounds, our algorithms when applied to out-of-order streams with tardiness τ will just increase the communication cost by a factor of W W -τ . The results are summarized in the last row of Table 1. The idea for basic counting is relatively simple. As the root does not require an exact total count, each data stream can communicate to the root only when its local count increases or decreases by a certain ratio ε > 0; we call such a communication step an up or down event, respectively. To answer the total count of all streams, the root simply sums up all the individual counts it has received. It is easy to prove that this answer is within some desired error bound. If each count is over the whole stream (i.e., window size = ∞ and N is the total number of arrived items), the count is increasing and there is no down event. A stream would have at most O(log 1+ε N ) up events and the communication cost is at most that many words. However, the analysis becomes non-trivial in a sliding time window. Now items can expire and down events can occur. An up event may be followed by some down events and the count is no longer increasing. The tricky part is to find a new measure of progress. We identify a "characteristic set" of each up event such that each up event must increase the size of this set by a factor of at least 1 + ε, hence bounding the number of up events to be O(log 1+ε N ). Down events are bounded using another characteristic set. Due to space limitation, the details can only be given in the full paper.

Approximate counting of all possible items is much more complicated, which will be covered in details in the rest of this paper. Assuming in-order streams, we derive and analyze two algorithms for approximate counting in Section 2. In Section 3, we discuss frequent items, quantiles, and finally out-of-order streams. The lower bound results are relatively simple and omitted due to space limitation.

Approximate Counting of all items

This section presents algorithms for the streams to communicate to the root so that the root at any time can approximate the count of each item. As a warm-up, we first consider the simple algorithm in which a stream will inform the root whenever its count of an item increases or decreases by a certain fraction of its total item count. We show in Section 2.1 that within any window of W time units, each data stream σ i (1 ≤ i ≤ k) needs to send at most O((∆ + 1 ε ) log n i ) words to the root, where ∆ is the number of distinct items and n i is the number of items of σ i that arrive or expire within the window. Then, the total communication cost within this window is 1≤i≤k (∆ + 1 ε ) log n i , which, by Jensen's inequality, is no greater than (∆ + 1 ε )k log( 1≤i≤k n i )/k = (∆ + 1 ε )k log N k where N = 1≤i≤k n i . We then modify the algorithm so that a stream can "turn off" items whose counts are too small, and we give a more complicated analysis to deal with the case when many such items increase their counts rapidly (Section 2.2). The communication cost is reduced to O( k ε log N k ) words, independent of ∆.

A simple algorithm

Consider any stream σ. At any time t, let c(t) and c j (t) be the number of all items and item j arriving at σ in [t -W + 1, t], respectively. Let λ < 1/11 be a positive constant (which will be set to ε/11). We maintain two λ-approximate data structures [START_REF] Datar | Maintaining stream statistics over sliding windows[END_REF][START_REF] Lee | A simpler and more efficient deterministic scheme for finding frequent items over sliding windows[END_REF] at σ locally, which can report estimates ĉ(t) and ĉj (t) for c(t) and c j (t), respectively, such that2

(1 -λ/6)c(t) ≤ ĉ(t) ≤ (1 + λ/6)c(t);
and c j (t) -λc(t) ≤ ĉj (t) ≤ c j (t) + λc(t).

Simple algorithm. At any time t, for any item j, let p < t be the last time ĉj (p) is sent to the root. The stream sends the estimate j, ĉj (t) to the root if the following event occurs.

• Up:

ĉj (t) > ĉj (p) + 9λĉ(t). • Down: ĉj (t) < ĉj (p) -9λĉ(t).
Root's perspective. At any time t, let r j,σ (t) be the last estimate received from a stream σ for item j (at or before t). The root can estimate the total count of item j over all streams by summing all r j,σ (t) received. More precisely, for any 0 < ε < 1, we set λ = ε/11 and let each stream use the simple algorithm. Then for each stream σ, the approximate data structures for ĉj (t) and ĉ(t) together with the simple algorithm guarantee that c j (t) -11λc(t) ≤ r j,σ (t) ≤ c j (t) + 11λc(t). Summing r j,σ (t) over all streams would give the root an estimate of the total count of item j within an error of ε of the total count of all items. Communication Complexity. At any time t, we denote the reference window as [t o , t], where t o = t -W + 1. Let n be the number of items of σ that arrive or expire in [t o , t]. Assume that there are at most ∆ distinct items. We first show that a stream σ encounters O(( 1 λ + ∆) log n) up events and sends O((

1 λ + ∆) log n) words within [t o , t].
The analysis of down events is similar and will be detailed later. For any time t 1 ≤ t 2 , it is useful to define σ [t 1 ,t 2 ] (resp. σ j,[t 1 ,t 2 ] ) as the multi-set of all items (resp. item j only) arriving at σ within [t 1 , t 2 ], and |σ [t 1 ,t 2 ] | as the size of this multi-set.

Consider an up event U j of some item j that occurs at time v ∈ [t o , t]. Define the previous event of U j to be the latest event (up or down) of item j that occurs at time p < v. We call p the previous-event time of U j . The number of up events with previous-event time before t o is at most ∆. To upper bound the number of up events with previous-event time p ≥ t o is, however, non-trivial; below we call such an up event a follow-up (event). Intuitively, a follow-up can be triggered by frequent arrivals of an item, or mainly the relative decrease of the total count. This motivates us to classify follow-ups into two types and analyze them differently. A follow-up U j is said to be absolute if c(p) ≤ 6 5 c(v), and relative otherwise. Define Recent-items(U j ) to be the multi-set of item j's that arrive after the previous event of U j , i.e., Recent-items(U j ) = σ j,[p+1,v] .

Absolute follow-ups. To obtain a tight bound of absolute follow-ups, we need a characteristic-set argument that can consider the growth of different items together. Let t 1 , t 2 , ..., t k be the times in [t o , t] when some absolute follow-ups (of one or more items) occur. Let x i be the number of items having an absolute follow-up at t i . Note that for all i, x i ≤ min{1/(7λ), ∆}, 3 and k i=1 x i is the number of absolute follow-ups in [t o , t]. We define the characteristic set S i at each t i as follows:

S i = the union of Recent-items(U j ) over all absolute follow-ups U j occurring at t 1 , t 2 , . . . , t i .

Recall that n is the number of items of σ that arrive or expire in

[t -W + 1, t]. Lemma 2.1. (i) For any 2 ≤ i ≤ k, |S i | > (1 + 6x i λ)|S i-1 |. (ii) There are k i=1 x i = O( 1 λ log n) absolute follow-ups within [t o , t].
Proof. For (i), consider an absolute follow-up U j of an item j, occurring at time t i with previous-event time p i . Note that the increase in the count of item j from p i to t i must be due to the recent items. We have

|Recent-items(U j )| ≥ c j (t i ) -c j (p i ) ≥ ĉj (t i ) -ĉj (p i ) -λc(t i ) -λc(p i ) (by σ's local data structures) > 9λĉ(t i ) -λc(t i ) -λc(p i )
(definition of an up event)

≥ (9λ(1 -λ 6 ) -λ -6 5 λ)c(t i ) ≥ 6λc(t i ) (U j is absolute)
There are x i absolute follow-ups at t i , so

|S i | > |S i-1 | + x i (6λc(t i )). Since S i ⊆ σ [to,t i ] , c(t i ) ≥ |S i | ≥ |S i-1 |. Therefore, we have |S i | > |S i-1 | + 6x i λ|S i | ≥ (1 + 6x i λ)|S i-1 |. For (ii), we note that n ≥ |S k | > k i=2 (1 + 6x i λ)|S 1 |, and |S 1 | ≥ 1. Thus, k i=2 (1 + 6x i λ) < n, or equivalently, ln n > k i=2 ln(1 + 6x i λ). The latter is at least k i=2 6x i λ 1+6x i λ ≥ λ k i=2 x i .
The last inequality follows from that x i ≤ 1/(7λ) for all i. Thus, k i=1

x i ≤ x 1 + 1 λ ln n = O( 1 λ log n).
Relative follow-ups. A relative follow-up occurs only when a lot of items expire, and relative follow-ups of the same item cannot occur too frequently. Below we define O(log n) time intervals and argue that no item can have two relative follow-ups within an interval. For an item with time-stamp t 1 , we define the first expiry time to be t 1 + W . At any time u in [t o , t], define H u to be the set of all items whose first expiry time is within

[u + 1, t], i.e., H u = σ [u-W +1,to-1] . |H u | is non-increasing as u increases. Consider the times t o = u 0 < u 1 < u 2 < • • • < u ℓ ≤ t such that for i ≥ 1, u i is the first time such that |H u i | < 5 6 |H u i-1 |. For convenience, let u ℓ+1 = t + 1. Note that |H u 0 | ≤ n and ℓ = O(log n). Lemma 2.

(i) Every item j has at most one relative follow-up U j within each interval

[u i , u i+1 -1]. (ii) There are at most O(∆ log n) relative follow-ups within [t o , t].
Proof. For (i), assume U j occurs at time v in [u i , u i+1 -1], and its previous event occurs at time p. By definition, c(p) > 6 5 c(v). Thus,

|H p | -|H v | = |σ [p-W +1,v-W ] | ≥ c(p) -c(v) > 1 5 c(v) ≥ 1 5 |σ [v-W +1,to-1] | = 1 5 |H v | , and |H v | < 5 6 |H p |. Since v < u i+1 and |H v | ≥ 5 6 |H u i |, we have |H p | > |H u i |
and p < u i . For (ii), there are ∆ distinct items, so there are at most ∆ relative follow-ups within each interval [u i , u i+1 -1], and at most O(∆ log n) relative follow-ups within [t o , t]. 3 If an up event of an item j occurs at time ti, then cj (ti) ≥ ĉj (ti) -λc(ti) > 9λĉ(ti) -λc(ti) ≥ 7λc(ti).

Thus the number of up events at time ti is at most c(ti)/(7λc(ti)) = 1/(7λ). Down events. The analysis is symmetric to that of up events. The only non-trivial thing is the definition of the characteristic set for bounding the absolute follow-downs D j , which is defined in an opposite sense: Assume D j occurs at time v and its previous event occurs at p ≥ t o . D j is said to be absolute if c(p) ≤ 6 5 c(v). Let Expire(D j ) be the multi-set of item j's whose first expiry time is within

[p + 1, v]. I.e., Expire(D j ) = σ j,[p-W +1,v-W ] .
It is perhaps a bit tricky that instead of defining the characteristic set of absolute follow-downs at the time they occur, we consider the times of the corresponding previous events of these follow-downs. Let p 1 , p 2 , ..., p k be the times in [t o , t] such that there is at least one event E j (up or down) at p i which is the previous event of an absolute follow-down D j occurring after p i . Let y i be the number of such previous events at p i , and let AD(p i ) be the set of corresponding absolute follow-downs. Note that y i (unlike x i ) only admits a trivial upper bound of ∆. We define the characteristic set T i for each p i as follows:

T i = the union of Expire(D j ) over all D j ∈ AD(p i ), AD(p i+1 ), . . . , AD(p k ).
Similar to Lemma 2.1, we can show that |T i | > (1 + 5y i λ)|T i+1 |. Owing to a weaker bound of individual y i , the number of absolute follow-downs, which equals k i=1 y i , is shown to be O((

1 λ + ∆) log n).
Combining the analyses on up and down events, and let λ = ε/11, we have the following.

Theorem 2.3. The simple algorithm sends at most O((

1 ε + ∆) log n) words to the root during window [t -W + 1, t].

The full algorithm

In this section, we extend the previous algorithm and give a new characteristic-set analysis that is based on future events (instead of the past events) to show that each stream's communication cost per window can be reduced to O( 1 ε log n) words. Then, by Jensen's inequality again, we conclude that the total communication cost per window is O( k ε log N k ). Intuitively, when the estimate ĉj (t) of an item j is too small, say, less than 3λĉ(t), the algorithm treats this estimate as 0 and set the off j flag of j to be true. This restricts the number of items with a positive estimate to O( 1 λ ). Initially, the off j flag is true for all items j. Given 0 < λ < ε/11, the stream communicates with the root as follows.

Algorithm AC. At any time t, for any item j, let p < t be the time the last estimate of j, i.e., ĉj (p), is sent to the root. The stream sends the estimate of j to the root if the following event occurs.

• Up: If ĉj (t) > ĉj (p) + 9λĉ(t), send j, ĉj (t) and set off j = false .

• Off:

If off j = false and ĉj (t) < 3λĉ(t), reset ĉj (t) to 0, send j, ĉj (t) and set off j = true. • Down: If off j = false and ĉj (t) < ĉj (p) -9λĉ(t), send j, ĉj (t) .

It is straightforward to check that the root can answer the approximate counting query for any item. We analyze the communication complexity of different events as follows. Fact 1. At any time v, the number of items j with off j = false is at most 1 λ . 4 4 For any item j, if off j = false, then ĉj (v) ≥ 3λĉ(v) and cj (v

) ≥ ĉj (v)-λc(v) ≥ (3λ(1-λ)-λ)c(v) ≥ λc(v).
Thus the number of items j with off j = false is at most c(v)/λc(v) = 1 λ .

Off events. Recall that we are considering the window [t o , t], and n is the number of items arriving or expiring within [t o , t]. By Fact 1, just before t o , there are at most 1 λ items with off j = false. Within [t o , t], only an up event can set the off flag to false. Thus the number of off events within [t o , t] is bounded by 1 λ plus the number of up events. Up and Down events. The assumption of ∆ gives a trivial bound on those events involving items with very small counts and in particular, those up events immediately following the off events. Such up events are called poor-up events or simply poor-ups. Using the off flag, we can easily adapt the analysis of the simple algorithm to bound all the down and up events of the full algorithm, but except the poor-ups. The following simple observations, derived from Fact 1, allow us to replace ∆ with 1/λ in the previous analysis to obtain a tighter upper bound of O( 1 λ log n). Let v be any time in [t o , t]. • There are at most 1/λ items whose first event after v is a down event.

• There are at most 1/λ non-poor-up events after v whose previous event is before v.

It remains to analyze the poor-ups. Consider a poor-up U j at time v in [t o , t]. By definition, off j = false at time v. The trick of analyzing U j 's is to consider when the corresponding items will be "off" again instead of what items constitute the up events. Then a characteristic set argument can be formulated easily. Specifically, we first observe that, by Fact 1, there are at most 1 λ poor-ups whose off flags remain false up to time t. Then it remains to consider those U j whose off flags will be set to true at some time d ≤ t. Below we refer to d as the first off time of U j . Poor-up with early off. Consider a poor-up U j that occurs at time v in [t o , t] and has its first off time at d in [v + 1, t]. Let F-Expire(U j ) be all the item j whose first expiry time is within [v + 1, d]. I.e., F-Expire(U j ) = σ j,[v+1-W,d-W ] . As an early off can be due to the expiry of many copies of item j or the arrival of a lot of items, it is natural to divide the poor-ups into two types: with an absolute off if c(d) ≤ 6 5 c(v), and relative off otherwise. For the case with absolute off, we consider the distinct times t 1 , t 2 , . . . , t k in [t o , t] when such poor-ups occur. Let x i be the number of such poor-ups at time t i . Note that x i ≤ 1/(7λ). For each time t i , we define the characteristic set F i = the union of F-Expire(U j ) over all U j occurring at t i , t i+1 , . . . , t k . Lemma 2.4. (i) For any

1 ≤ i ≤ k -1, |F i | > (1 + x i λ)|F i+1 |. (ii) Within [t o , t], there are k i=1 x i = O( 1
λ log n) poor-ups each with an absolute off. Proof. For (i), consider an item j and a poor-up U j with an absolute off that occurs at time t i and has its first off at time d i . The decrease in c j must be due to expiry of item j.

|F-Expire(U j )| ≥ c j (t i ) -c j (d i ) ≥ ĉj (t i ) -ĉj (d i ) -λc(t i ) -λc(d i ) > 9λĉ(t i ) -3λĉ(d i ) -λc(t i ) -λc(d i )
(definition of up and off)

≥ (9λ(1 -λ 6 ) -λ)c(t i ) -(3λ(1 + λ 6 ) + λ)c(d i ) ≥ 7λc(t i ) -5λc(d i ) ≥ (7 -5( 6 5 ))λc(t i ) = λc(t i ) (definition of absolute off) Thus, |F i | > |F i+1 | + x i (λc(t i )). Since F i ⊆ σ [t i -W +1,t-W ] , |F i | ≤ c(t i ). Therefore, |F i | > |F i+1 | + x i λ|F i | > (1 + x i λ)|F i+1 |.
By (i), we can prove (ii) similarly to Lemma 2.1 (ii).

Analyzing poor-ups with a relative off is again based on an isolating argument. We divide [t o , t] into O(log n) intervals according to how fast the total item count starting from t o grow; specifically, we want two consecutive time boundaries u i-1 and u i to satisfy

|σ [to,u i ] | > 6 5 |σ [to,u i-1 ] |.
Then we show that for any poor-up within [u i-1 , u i -1], its relative off, if exists, occurs at or after u i . Thus there are at most

| -|σ [to,v] | = |σ [v+1,d] | ≥ c(d) -c(v) > 1 6 c(d) ≥ 1 6 |σ [to,d] |. This implies |σ [to,d] | > 6 5 |σ [to,v] |. For (ii), consider the times t o = u 0 < u 1 < u 2 < • • • < u ℓ ≤ t such that for i ≥ 1, u i is the first time such that |σ [to,u i ] | > 6 5 |σ [to,u i-1 ] |. For convenience, let u ℓ+1 = t + 1. Note that |σ [to,t] | ≤ n and ℓ = O(log n). Furthermore, for any time v ∈ [u i-1 , u i -1], |σ [to,v] | ≤ 6 5 |σ [to,u i-1 ] |.
Therefore, by (i), for any poor-up of an item j within [u i-1 , u i -1], its relative off, if exists, occurs at or after u i , which implies at time u i -1, c j (u i -1) ≥ λc(u i -1). Then within each interval [u i-1 , u i -1], the number of such j as well as the number of poorups with a relative off are at most

Extensions

We extend the previous techniques to solve the problems of frequent items and quantiles and handle out-of-order streams. Below BC refers to our algorithm for basic counting.

Frequent items. Using the algorithms BC and AC, the root can answer the εapproximate frequent items as follows. Each stream σ communicates with the root using BC with error parameter ε/24 and AC with error parameter 11ε/24. At any time t, let r σ (t) and r j,σ (t) be the latest estimates of the numbers of all items and item j, respectively, received by the root from σ. To answer a query of frequent items with threshold φ ∈ (0, 1] at time t, the root can return all items j with σ r j,σ (t) ≥ (φ -ε 2 ) σ r σ (t) as the set of frequent items.

To see the correctness, let c σ (t) and c j,σ (t) be the number of all items and item j in σ at time t, respectively. Algorithm BC guarantees |r σ (t) -c σ (t)| ≤ ε 24 c σ (t), and algorithm AC guarantees |r j,σ (t) -c j,σ (t)| ≤ 11ε 24 c σ (t). Therefore, if an item j is returned by the root, then σ c j,σ (t) ≥ σ r j,σ (t) -11ε

σ c σ (t) ≥ (φ -ε 2 ) σ r σ (t) -11ε 24
σ c σ (t) ≥ (φ -ε 2 )(1 -ε 24 ) σ c σ (t) -11ε 24
σ c σ (t) ≥ (φ -ε 2 -φ ε 24 -11ε 24 ) σ c σ (t) 24
where the second inequality comes from the definition of the algorithm. The last term above is at least (φ -ε) σ c σ (t), so j is a frequent item. If an item j is not returned by the root, then σ r j,σ (t) < (φ -ε 2 ) σ r σ (t) and we can show similarly that σ c j,σ (t) < φ σ c σ (t). Quantiles. We give an algorithm for ε-approximate quantiles queries. Let λ = ε/20. For each stream, we keep track of the λ-approximate φ-quantiles for φ = 5λ, 10λ, 15λ, . . . , 1. We update the root for all these φ-quantiles when one of the following two events occurs: (i) for any k, the value of the (5kλ)-quantile is larger than the value of the (5(k + 1)λ)quantile last reported to the root, or (ii) for any k, the value of the (5kλ)-quantile is smaller than the value of the (5(k -1)λ)-quantile last reported to the root. The stream also communicates with the root using BC with error parameter λ. In the root's perspective, at any query time t, let φ ∈ (0, 1] be the query given and let r σ (t) be the last estimate sent by σ for the number of all items. The root sorts the quantiles last reported by all streams and for each stream σ, gives a weight of 5λr σ (t) to each quantile of σ. Then the root returns the smallest item j in the sorted sequence such that the sum of weights for all items no greater than j is at least ⌈φ σ r σ (t)⌉. Careful counting can show that j is an ε-approximate φ-quantile. To bound the communication cost, let n be the number of items of σ arriving or expiring during the window [t -W + 1, t]. We observe that when an event occurs, many items have either arrived or expired after the previous event. Using similar analysis as before, we can show that within a window, there are at most O( 1 ε log n) such events and thus each stream sends O( 1 ε 2 log n) words. By Jensen's inequality again, our algorithm's total communication cost per window is O( k ε 2 log N k ) where N is the number of items of the k streams that arrive or expire within the window. Note that the lower bound of O( 1ε log(εn)) words for approximate frequent items carries to approximate quantiles, as we can answer approximate frequent items using approximate quantiles as follows. The root poses ε-approximate φ-quantile queries for φ = ε, 2ε, . . . , 1. Given the threshold φ ′ for frequent items, the root returns all items that repeatedly occur as φ ′ ε -2 (or more) consecutive quantiles, and these items are (4ε)-approximate frequent items.

Out-of-order streams. All our algorithms can be extended to out-of-order stream with a communication cost increased by a factor of W W -τ , as follows. Each stream uses the data structures for out-of-order streams (e.g., [START_REF] Busch | A deterministic algorithm for summarizing asynchronous streams over a sliding window[END_REF][START_REF] Cormode | Time-decaying aggregates in out-of-order streams[END_REF]) to maintain the local estimates. Then each stream uses our communication algorithms for in-order streams. It is obvious the root can answer the corresponding queries. For the communication cost, consider any time interval P = [t -(W -τ ) + 1, t] of size W -τ . Items arriving in P must have time-stamps in [t -W + 1, t]. Using the same arguments as before, we can show the same communication cost of each algorithm, but only for a window of size W -τ instead of W . Equivalently, in any window of size W , the communication cost is increased by a factor of O( W W -τ ).

  1 λ such poor-ups within each interval and a total of O( 1 λ log n) within [t o , t]. Lemma 2.5. (i) Consider a poor-up U j with a relative off. Suppose it occurs at time v in [t o , t], and its first off time is at d in [v + 1, t]. Then |σ [to,d] | > 6 5 |σ [to,v] |. (ii) Within [t o , t], there are at most O( 1 λ log n) poor-ups each with a relative off. Proof. For (i), by the definition of a relative off, c(d) > 6 5 c(v). Thus, |σ [to,d]

  1 λ . Within [t o , t], there are ℓ = O(log n) intervals and hence O( 1 λ log n) poor-ups each with a relative off. Theorem 2.6. For approximate counting, each individual stream can use the algorithm AC with λ = ε/11 and it sends at most O( 1 ε log n) words to the root within a window. Memory usage of each remote site. Recall that we use two λ-approximate data structures [13, 23] for the total item count and individual item counts, which respectively require O( 1 λ log 2 (λn)) bits and O( 1 λ ) words. Note that O( 1 λ log 2 (λn)) bits is equivalent to O( 1 λ log(λn)) words. Furthermore, at any time, we only need to keep track of the last estimate sent to the root of all item j with off j = false, which by Fact 1, requires O( 1

	λ ) words. By setting λ = ε/11 (see Theorem 2.6), the total memory usage of a remote site is
	O( 1 λ log(λn)) = O( 1 ε log(εn)) words.

Note that the number of items arriving or expiring within window [t -W + 1, t] is no greater than the number of items arriving within [t -2W + 1, t].

The constant 6 in the inequality is arbitrary. It can be replaced with any number provided that other constants in the algorithm and analysis (e.g., the constant 9 in definition of up events) are adjusted accordingly.

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/3.0/.

W. Lam is partially supported by the GRF Grant HKU-713909E; H.F. Ting is partially supported by the GRF Grant HKU-716307E.