text:
Tight Lower Bounds for Selection in Randomly Ordered Streams (Extended Abstract) Amit Chakrabarti∗ T. S. Jayram Mihai Pˇ trascu∗ a ¸ firstname.lastname@example.com firstname.lastname@example.com firstname.lastname@example.com Abstract selection, where given a rank r one must return a value of We show that any algorithm computing the median of a rank r ± ∆. stream presented in random order, using polylog(n) space, The random order model is highlighted in the conclu- requires an optimal Ω(log log n) passes, resolving an open sion of [MP80] as an important challenge for future re- question from the seminal paper on streaming by Munro search. Munro and Paterson conjecture that selection with and Paterson, from FOCS 1978. polylog(n) space requires Θ(log log n) passes. In PODS 2006, Guha and McGregor [GM06] show the upper-bound 1 Introduction side of this conjecture. In general, they show that an al- gorithm using p passes can return an element with rank Finding order statistics in a data stream has been studied 2−p since the classic work of Munro and Paterson from FOCS r ± O(n ). It follows immediately that with O(p) passes 2−p 1978 [MP80], which is often cited as a paper introducing one can perform exact selection using space O(n ). the streaming model. Since then, much ink has been spilled The only lower bound for random order comes from it over this problem [MRL98, MRL99, GK01, GKMS02, [GM07], where √ is shown that a one pass algorithm re- GZ03, CM05, SBAS04, CKMS06, GM06, GM07]. In- quires space Ω( n). The nature of this proof prevents it deed, this is likely one of the most studied problems in the from generalizing to more than one pass, due to fundamen- streaming model, comparable only to the question of esti- tal technical reasons; see the discussion on technical con- mating frequency moments. Order statistics (a.k.a. quan- tributions below. tiles, percentiles, median) are one of the most natural In this paper, we show the following tight lower and frequently used summaries of a data set, making the bounds, addressing the 30-year-old question of Munro and streaming problem arise constantly in practical settings, Paterson: such as large databases. (Indeed, most of the works ref- erenced have appeared in "practical" conferences.) T HEOREM 1.1. Consider a stream of n numbers, chosen Munro and Paterson [MP80] study the problem under from [2n] uniformly at random, without replacement, and two assumptions about the stream order: adversarial and ordered uniformly at random. If an algorithm uses memory −p random order. In the case of random order, any permuta- O(n2 ) and can, with error probability 1/3, approximate tion of the input values is equally likely to appear in the the median by outputting a value with rank n ± n2−p , then 2 stream. However, multiple passes through the stream read the algorithm must use Ω(p) passes. In particular, finding items in the same order. They give algorithms that make the median with polylog(n) space requires Ω(log log n) p passes, and require O(n1/p ) memory1 for adversarial or- passes. der, and O(n1/2p ) memory for random order. They also prove some lower bounds under assumptions about what 1.1 The Random-Order, Multipass Model. Histori- the algorithm can store in its internal memory. In the adver- cally, the model that we are considering has found a place sarial model, an unrestricted tight lower bound of Ω(n1/p ) in both the theoretical and practical worlds; see the sem- was shown by Guha and McGregor [GM07]. Their bounds inal paper of Munro and Paterson [MP80], as well as the are also tight for the well-studied problem of approximate very thorough justification in [GM06]. However, we find it worthwhile to reiterate why the model is appealing. ∗ Part of this work was done while the authors were visiting IBM Streaming algorithms are designed with two classes Almaden Research Center. The first author is supported in part by NSF of applications in mind: scenarios where data passes by CAREER Award CCF-0448277 and a Dartmouth College Junior Faculty and one cannot remember it all (e.g. in a network router), Fellowship. 1 We let O(·) ignore polylog(n) factors. For simplicity, we assume e and scenarios where the data is on secondary storage and the universe [U ] = {1, . . . , U } for the numbers in the stream satisfies a memory-limited algorithm examines it sequentially. The U = poly(n), so that items in the stream can be stored in O(log n) bits. second application allows multiple passes and is common in very large databases; this is the case where our lower 1.2 Technical Contribution. For simplicity, define bound is relevant. S T A T (i, S) to be the ith order statistic of the set S. While streaming is the only possible model for a Then, M E D I A N (S) = S T A T 1 |S| , S . Also define 2 router, any doubts as to whether it is a model worth study- R A N K (x, S) = |{y ∈ S : y ≤ x}|, where it is not nec- ing for large databases have been erased by recent pro- essary that x ∈ S. gramming platforms like Google's Map-Reduce [DG04]. We first explain a very high-level intuition for the Forced by the massive, hugely distributed nature of data, lower bound. When proving a lower bound for p passes, we these platforms essentially define streaming as the primi- break the stream into p + 1 parts. We assign each part to a tive for accessing data. player and consider a communication game between these We now switch our attention to the random-order players. For example, we can say Player 1 receives the last √ assumption of our model. Though worst-case order is the n items, Player 2 the preceding n7/8 items, Player 3 the model of choice for theory, we believe the random-order preceding n31/32 and so on, up to player p+1 who receives model is an important link to the practical world which the remaining Ω(n) items at the beginning. Let Ti be the cannot be marginalized. The following are common cases elements of player i, and T≥i = j≥i Tj . in which random order is realized. While pondering these Assume the median occurs in Tp+1 , i.e. the first part of cases, the reader may want to consider a realistic example the stream, which happens with constant probability. Then, of a database query like "find quantiles for the salary of let ri = R A N K (M E D I A N (T ), T≥i+1 ). After learning ri , people hired between 2001 and 2004, and with the work players i + 1, . . . , p + 1 actually want to solve the ri order location being India". statistic problem on their common input T≥i+1 . The hardness of the problem comes from the fact that • random by assumption: if the values in the data ri depends quite heavily on Ti . For example, if Player √ set are assumed to come from some random source 1 sees the last n elements of the stream, an expected √ (e.g. salaries obey a distribution), the stream will have n/2 of these elements are below the median. However, uniform ordering. This is an instance of average- the number of elements below is actually a binomially dis- case analysis, which is quite common in the realm of tributed random variable with standard deviation O(n1/4 ). databases. Then, Player 1's input can shift r1 anywhere in a O(n1/4 ) range with roughly uniform probability. In this uncertainty • random by heuristic: if the records in the database are range, Player 2 has an expected |T2 |/Θ(n3/4 ) = n1/8 el- ordered by some other keys (say, last name), then the ements. Even when r1 is known, these elements shift r2 order in which we read the interesting values (salary) around by a binomial with standard deviation Θ(n1/16 ), is sufficiently arbitrary to be assumed random. This etc. assumption is well-known in databases, as it is usually The intuition for the hardness of tracing this sequence made by query optimizers. of r1 , r2 , . . . , is a standard pointer chasing intuition. Re- • random by design: if we do not know enough about the member that in each pass, the players speak in the order 1/4 query to build a useful data structure, we can decide to p + 1, p, . . . , 1. If r1 has an uncertainty range of O(n ), store records in a random order, hoping to avert worst- it means players p + 1, . . . , 2 must prepare to solve on the 1/4 case behavior. This is the common playground for order of n different order statistic problems, without theory, which assumes worst-case data, but looks at the having any idea which one until Player 1 speaks. Then, if expected behavior over the algorithm's randomness. they only communicate polylog(n) bits each, they cannot in expectation gain significant knowledge about the order- The perspective of lower bounds. We believe the statistic problem that turns out to be relevant. Then, in the value of the random-order model for lower bounds is second round we have the same intuition, with Player 2's strictly higher that for upper bounds. A rather common input deciding r2 , and so on. objection to lower bounds in adversarial models are claims that they are irrelevant in real life, where heuristics do Problem structure. The hardness intuition presented better since "data is never so bad in practice". Based on above presumably dates back to Munro and Paterson, who the real-world examples above, one may not be fully con- conjectured that Θ(log log n) was the correct bound with- vinced that streams are truly random-ordered. However, out having an upper bound. However, there are significant the examples cast serious doubt that a very intricate worst- obstacles in the road to a lower bound, which accounts for case order constructed by a lower bound is sufficiently why the conjecture has remained unresolved despite very plausible to mean anything in practice. The relevance of significant progress in streaming lower bounds. our lower bound is much harder to question, since it shows The challenges faced by the proof fall in two broad that even under the nicest assumptions about the data, an categories: understanding the structure of the problem algorithm cannot do better. correctly, and developing the right ideas in communication complexity to show that this structure is hard. With regard which we need lower bounds. For example, in FOCS to the former, it should be noted that the intuition is shaky 2004, Chakrabarti and Regev [CR04] study a variant tai- in many regards. For example, while it is true that players lored for approximate nearest neighbor; in SODA 2006, ≥ 2 are trying to compute S T A T (r1 , T≥2 ), the value of Adler et al. [ADHP06] study a variant tailored for dis- r1 cannot be defined without reference to M E D I A N (T ). tributed source coding and sensor networks; in STOC This defeats the purpose, since knowing r1 may reveal a ¸ 2006 and SODA 2007 Pˇ trascu and Thorup [PT06, PT07] significant information about the median. study a variant tailored for predecessor search; Chakrabarti We circumvent problems of this nature by identifying in CCC 2007 [Cha07] and Viola and Wigderson in a more subtle and loose structure that makes the problem FOCS 2007 [VW07] study variants tailored for multiparty hard, while not deviating too far from the pointer chasing number-on-the-forehead pointer chasing. intuition. To demonstrate the obstacles that need to be sur- These papers, as well as the present one, push the mounted, we mention that at a crucial point, our argument theory of round elimination in very different directions, needs to invoke a nondeterministic prover that helps the making it applicable to natural and interesting problems. players see the hard structure, while allowing the prover to Since round elimination has become a staple of modern communicate little enough to not make the problem easier. communication complexity, one cannot help but compare this line of work to another well-developed area: the study Communication complexity. Still, the challenges re- of PCPs with different properties, giving inapproximability garding communication complexity are the more serious results for various problems. ones. At a high level, our proofs have the same flavor as the round elimination lemma [MNSW98, Sen03]. In the 2 Preliminaries simplest incarnation of this lemma, Alice has a vector of In this section, we boil down the task of proving our B inputs (x1 , . . . , xB ), and Bob has an input y and an in- streaming lower bound to that of lower bounding the dex i ∈ [B]. The players are trying to determine some communication complexity of a related problem under a f (xi , y). Alice speaks first, sending a message of S B specific product distribution on its inputs. bits. Then, this message is essentially worthless and can be eliminated, because it is communicating almost no in- 2.1 Hard Instance. formation about the useful xi , for random i. Our situation is similar: ri selects the next problem D EFINITION 2.1. The stream problem R A N D M E D I A N is among nΩ(1) choices, and players ≥ i+1 don't know what defined as follows. The input is a stream of n integers in to communicate that would be useful to the ri problem. [2n] ordered uniformly at random. The desired output is However, our setting is much more difficult because the any integer from the stream with rank between n − ∆ and 2 n random order of the stream forces a very particular distri- 2 + ∆. bution on the problem. Not only is the index ri not uniform D EFINITION 2.2. For a permutation π ∈ S2n , we define in its range (rather, it obeys a binomial distribution), but the the stream problem M E D π as follows. The input is a set problems xi are heavily correlated. To see that, note for T ⊂ [2n] with |T | = n that is presented as follows. example the strong correlation between S T A T (ri , T≥i+1 ) Let x ∈ {0, 1}2n be the characteristic vector of T . The and S T A T (ri + 1, T≥i+1 ). input stream is xπ(1) , xπ(2) , . . . , xπ(2n) , i.e., the bits of x The usual proofs of round elimination, based on man- ordered according to π. The desired output is any value A ufacturing inputs to match a random message, cannot work such that |R A N K (A, T ) − n | ≤ ∆, i.e., a ∆-approximate 2 here because of these correlations. At a technical level, median of T . A random instance of M E D π is defined to be note that round elimination normally imposes a nonprod- one where T is chosen uniformly at random amongst all uct distribution on the problem, whereas we will need to subsets of size n. Note that π continues to be fixed a priori have a product distribution. and parametrizes the problem. By contrast, the only previous lower bound for our problem [GM07] was not based on understanding this We will construct a family F ⊂ S2n of permutations unusual setting for round elimination, but on reducing a that consists of almost all of S2n (F is to be thought of simple case of round elimination (indexing) to finding the as a family of "typical permutations"). We shall then median with one pass. While this is possible (with a lot of show a lower bound for M E D π for any π ∈ F. Then, technical effort) for one pass, it fails entirely for multiple by contradiction with following lemma, we obtain a lower passes. bound for R A N D M E D I A N . Our effort is part of a larger trend in recent litera- ture. While the basic round elimination lemma is under- L EMMA 2.3. Let F ⊂ S2n be a family of permutations stood, many variants with peculiar requirements are stud- with |F| ≥ (1 − o(1)) · (2n)!. If R A N D M E D I A N admits ied, motivated by fundamental algorithmic questions for an ε-error p-pass streaming algorithm with space s, then there exists π ∈ F such that a random instance of M E D π L EMMA 2.6. Suppose is such that i = Ω(log n) for all admits a p-pass streaming algorithm with distributional i. If, for a particular π, a random instance of M E D π has error ε + o(1) and space s + O(log n). an ε-error p-pass streaming algorithm with space s, then there exists a suitable t satisfying conditions (2.1) such that Proof. Let A be the algorithm for R A N D M E D I A N in the a random instance of M E D C O M M π, ,t has an (ε + o(1))- hypothesis. We propose the following algorithm B π for error p-round communication protocol with message size M E D π : the input stream of bits xπ(1) , . . . , xπ(2n) is s. transformed into the stream of integers π(i) : xπ(i) = 1 , using O(log n) additional space, and fed to A as input. Proof. A streaming algorithm for M E D π translates in The output of B π is the same as that of A. Clearly, B π an elementary way into a communication protocol for is correct whenever A is. The key observation is that if π M E D C O M M π, ,t : the players simulate the streaming algo- is distributed uniformly at random in S2n , then the input to rithm on their respective portions of the input, with each A constructed by B π is ordered uniformly at random. (This pass being simulated by one round of communication. holds for every fixed x ∈ {0, 1}2n and hence for a random They ensure continuity by communicating the memory x.) Therefore, the expected distributional error of B π for contents of the streaming algorithm. This transformation such random π is at most ε. An averaging argument now incurs no additional error, but it only gives low expected shows that there exists π ∈ F such that the distributional distributional error for a suitably random t. To be precise, error of B π is at most ε|S2n |/|F| = ε + o(1). suppose x ∼ U , where U denotes the uniform distribu- tion on weight-n bitvectors in {0, 1}2n . Let yi be as in 2.2 Communication Complexity. We now transform Definition 2.4. Define the random variables ti (x) = |yi | ˆ π ˆ(x) = (t1 (x), . . . , tp (x)). For a ˆ ˆe M E D into a multiparty number-in-hand communication and the random vector t game M E D C O M M π, ,t that is additionally parametrized by vector t in the support of t(x), let ρ(t) be the distribu- ˆ t an integer p, a vector = ( 1 , . . . , p ) ∈ N and a vector tional error of the above protocol for a random instance of e t = (t1 , . . . , tp ) ∈ Nt . These parameters are required to M E D C O M M π, ,t . Then, by the correctness guarantee of the e satisfy: ˆ streaming algorithm, we have Ex∼U [ρ(t(x))] ≤ ε. (The p e p e reader may want to carefully compare the definition of a p ≥ 2, random instance of M E D π with that of M E D C O M M π, ,t .) i = 2n , ti = n , i=1 i=1 To prove the lemma, we must show the existence of (2.1) a vector t such that t satisfies the conditions (2.1) and i 2i and ∀ i ∈ [p] : ≥ 2 . ρ(t) ≤ ε + o(1). Let us call a particular t in the support of ti n ˆ t(x) good if it satisfies the final condition in (2.1) and bad Recall that the input to the stream problem is a bitvec- otherwise. Let U be the uniform distribution on {0, 1}2n . tor x ∈ {0, 1}2n ordered according to π. In the com- Then, munication game, there are p players and Player i re- ˆ ˆ Pr [t(x) is bad] = Pr [t(z) is bad | |z| = n] ceives i of the bits of x. Player 1 receives the last 1 x∼U z∼U bits of x according to π, Player 2 the 2 bits before that, ˆ Prz∼U [t(z) is bad] √ ≤ ˆ = Pr [t(z) is bad] · O( n) . etc. In other words, Player i receives the bits xk for Prz∼U [|z| = n] z∼U π k ∈ Piπ , where P1 := {π(n − 1 + 1), . . . , π(n)}, π P2 := {π(n − 1 − 2 + 1), . . . , π(n − 1 )}, etc. ˆ For i ∈ [p] and z ∼ U, ti (z) is the weight of a uniformly The players communicate by writing s-bit messages random bitvector in {0, 1} i . Define the sets Ii := t ∈ on a blackboard, i.e. all messages are visible to all players. {0, 1, . . . , i } : i < 2 2 . Then, by a union bound, i t n The games consists of p rounds. In each round, the players p communicate in the fixed order p, (p − 1), . . . , 2, 1. The e π desired output is the same as that for M E D and must be ˆ Pr [t(z) is bad] ≤ ˆ Pr[ti (z) = t] z∼U written by Player 1 at the end of round p. i=1 t∈Ii p p 2 e e D EFINITION 2.4. For an input x ∈ {0, 1}2n to = 2− i i ≤ i = . M E D C O M M π, ,t , define yi ∈ {0, 1} i to be Player i's in- i=1 t∈Ii t i=1 n2 n put, i.e., the projection of x on to the co-ordinates in Piπ . Define the sets Ti := {k ∈ Piπ : xk = 1}, T := i Ti and ˆ Ex∼U [ρ(t(x))] ˆ ˆ So, E [ρ(t(x)) | t(x) is good] ≤ T≥i := j≥i Tj . x∼U ˆ(x) is good] Prx∼U [t ε D EFINITION 2.5. A random instance of M E D C O M M π, ,t is ≤ 1 √ = ε + o(1) . 1 − n · O( n) one where, for each i, yi is chosen uniformly at random from the set Xi := {y ∈ {0, 1} i : |y| = ti }. Thus, there exists a good t such that ρ(t) ≤ ε + o(1). 2.3 The Permutation Family. We are now ready to vary T1 (Lemma 3.5). It then follows that we can find a √ define the permutation family F for which we prove the large number, B = Ω( 1 /∆2 ), of instantiations of T1 lower bound. Informally, F is the set of all permutations such that the corresponding r1 values are Ω(∆2 ) apart. Us- π for which each Piπ is rather uniformly distributed in ing the estimator property of r1 (T1 ), we then show that the the range [2n]. Specifically, we break the range [2n] into corresponding values of A must also be Ω(∆2 ) apart. This i equal-sized buckets and insist that any k consecutive gap is large enough that if B s, the corresponding ran- buckets contain Θ(k) elements of Piπ for k = Ω(log n). dom variables R A N K (A, T2 ) are "nearly independent" and Formally: have sufficient variance that they are unlikely to be con- fined within intervals of length at most 2∆; the precise ver- F = π ∈ S2n : ∀ i ∈ [p], k = Ω(log n), j ≤ i − k, sion of this statement is a key probabilistic fact that we call the Dispersed Ranks Lemma (Lemma 4.1). However, by k n n we have ≤ Piπ ∩ j · , (j + k) · ≤ 2k the correctness guarantees, it is quite likely that the values 2 i i of R A N K (A, T2 ) are so confined. This contradiction shows L EMMA 2.7. Suppose i = Ω(log n) for all i. Then that B = O(s), yielding the desired lower bound. Prπ∈Sn [π ∈ F] = 1 − o(1). We now fill in the details, starting with the precise definition of r1 . Proof. Pick π ∈ Sn uniformly at random, so that Piπ is n a random subset of [n] of size i . Let Aijk = Piπ ∩ D EFINITION 3.1. For S ⊂ [2n], define r1 (S) := 2 − n [jn/ i , (j + k)n/ i ]. Clearly, for all (i, j, k), we have |{x ∈ S : x ≤ n}| = 2 − R A N K (n, S). Note that E[|Aijk |] = k. Applying a Chernoff-Hoeffding bound for n = E[M E D I A N (T )]. the hypergeometric distribution, we have L EMMA 3.2. If s ≥ log n, there exists X2 ⊂ X2 such αijk := Pr[|Aijk | ∈ [k/2, 2k]] < e−Ω(k) ≤ n−4 , / that the message sent by Player 2 is constant over X2 , |X2 | ≥ |X2 |/22s , and Pr[|R A N K (A, T ) − n | > ∆ | T2 ∈ 2 where the latter inequality holds for k = Ω(log n). A X2 ] ≤ 1 + 1 . 2 3 3 n union bound over all O(n p) = O(n ) triples (i, j, k) shows that Pr[π ∈ F] ≤ i j k αijk = o(1). / Proof. Since Player 2's message is s bits long, it partitions (1) (2s ) X2 into 2s subsets X2 , . . . , X2 such that the message 3 Warm-up: One Pass (i) is constant on each X2 . Define In this section, we show that a one-pass algorithm for R A N D M E D I A N either uses space Ω(n1/12 ), or requires n (i) pi := Pr R A N K (A, T ) − > ∆ | T2 ∈ X 2 . approximation ∆ = Ω(n1/12 ). While this result is weaker 2 than the previous lower bound for one pass [GM07], it 2s (i) demonstrates the basic structure of our argument in a The protocol's guarantee implies i=1 pi |X2 |/|X2 | ≤ 1 s 1 1 simple case, and introduces some lemmas that will be 3 . Call an integer i ∈ [2 ] good if pi ≤ 3 + n and bad required later. otherwise. By Markov's inequality, By Lemmas 2.3 and 2.6, and Yao's minimax princi- (i) 1 ple [Yao77], it suffices to show the following for some |X2 | 3 1 p ≤ 1 3 1 = 1− ≤ 1− ; choice of p and : for all π ∈ F and t ∈ N satisfying e |X2 | 3 +n n+3 n 1 i bad condition (2.1), a 3 -error 1-round deterministic commu- (i) nication protocol for M E D C O M M π, ,t with message size s |X2 | 1 whence ≥ . must have s = Ω(n 1/12 ). For the rest of this section, let us |X2 | n i good fix such a protocol. We also fix p = 2. Let T and Ti be as in Definition 2.4 and chosen at random as in Definition 2.5. (i) Therefore, there exists a good i such that |X2 |/|X2 | ≥ Let A be the random variable indicating the output of the −s 1 −s 2 · n ≥ 4 , where we used s ≥ log n. Setting X2 to be protocol (which is an element of T ). (i) Here is an outline of our proof. The protocol's guar- this particular X2 completes the proof. antee is that Pr[|R A N K (A, T ) − n | > ∆] ≤ 1 . We first 2 3 fix Player 2's message, thereby restricting T2 within some For the rest of this section, we fix an X2 with the properties large subset X2 ⊂ X2 , and adding o(1) error (Lemma 3.2). guaranteed by the above lemma. At this point A is a function of T1 alone. Next, we define √ a quantity r1 (T1 ) that estimates R A N K (A, T2 ) to within L EMMA 3.3. If s ≥ log n and 1 ≤ n, then about ±∆, provided s is small (Corollary 3.4) and that Pr |R A N K (M E D I A N (T ), T2 ) − r1 (T1 )| > 10s | T2 ∈ √ 1 takes on a large number Ω( 1 ) of distinct values as we X2 ≤ n . 1 Proof. Note that |R A N K (M E D I A N (T ), T2 ) − r1 (T1 )| = Proof. By Corollary 3.4, ET1 [e(T1 )] ≤ 3 + o(1). So, by |R A N K (M E D I A N (T ), T2 ) + R A N K (n, T1 ) − n |2 = a Markov bound, PrT1 [r1 (T1 ) ∈ R] ≥ 0.01. To obtain |R A N K (n, T1 ) − R A N K (M E D I A N (T ), T1 )| = |T1 ∩ I|, the conclusion, we now show that Pr[r1 (T1 ) ∈ R] = √ where I is the interval between n and M E D I A N (T ). We O(|R|/ 1 ). now study the quantity pλ := Pr[|n − M E D I A N (T )| > √ As before, it is sufficient to perform an analysis under π λ n | T2 ∈ X2 ], where λ > 0 is a real parameter. the assumption that T1 ⊂ P1 is chosen by including every To this end, let U be a uniform random subset of element with probability 1/2, independently. Examining [2n]. Then, a simple Chernoff bound shows that Pr[|n − Definition 3.1, we see that √ 2 M E D I A N (U )| > λ n] ≤ e−λ /20 . Note that the distri- n n π r1 (T1 ) = − R A N K (n, T1 ) = − |P1 ∩ [n]| . bution of T is the same as that of U conditioned on the 2 2 event E := "∀ i ∈ {1, 2} : |U ∩ Piπ | = ti ." Clearly π By the defining property of F, we have |P1 ∩[n]| = Θ( 1 ), 2 Pr[E] = i=1 2− i ti ≥ n−4 , where we used the fact i r1 so √ has a binomial distribution with standard deviation that the vector (t1 , t2 ) satisfies condition (2.1). Further- Θ( √). It follows that, for any x, Pr[r1 (T1 ) = x] ≤ 1 √ more, Pr[T2 ∈ X2 ] ≥ 2−2s , by Lemma 3.2. Therefore O(1/ 1 ). Therefore Pr[r1 (T1 ) ∈ R] = O(|R|/ 1 ), as √ desired. pλ = Pr |n − M E D I A N (U )| > λ n | E, T2 ∈ X2 2 We can now prove the one-pass lower bound as fol- e−λ /20 lows. Define ∆1 := ∆ + 10s. For any N ≥ 1, we ≤ −4 −2s . n 2 can clearly find |R|/N elements in R such that any two √ are at least N apart. Combining this simple observa- Now, set λ = 10 s. This gives pλ ≤ n4 22s e−5s ≤ tion with Lemma 3.5, we see that there exist instantia- n4 2−5s ≤ n , for s ≥ log n. Therefore, except √ 1 with (1) (B) 1 tions T1 , . . . , T1 √ of the random set T1 , with B ≥ probability n , the interval I has length at most 10 sn. 2 |R|/(100∆1 ) = Ω( 1 /∆2 ), such that 1 If we break the range [2n] into 1 equal-sized buckets, the √ (i) interval I will fit into a union of at most 10 sn· 1 /(2n) ≤ 1. for all i ∈ [B] , e T1 ≤ 0.35, and √ 5 s ≤ 5s consecutive buckets. By the defining property (i+1) (i) of F, this means |P1 ∩ I| ≤ 10s. Since T1 ⊂ P1 , we are 2. for all i ∈ [B − 1] , r1 T1 π π − r1 T 1 ≥ 100∆2 1 (1) done. and r1 T1 ≥ 100∆2 .1 Recall that X2 has been fixed, so A is a function of C OROLLARY 3.4. Pr |R A N K (A, T2 ) − r1 (T1 )| > ∆ + 1 T1 alone. Let A(i) be the output of the protocol when 10s | T2 ∈ X2 ≤ 3 + o(1). (i) T1 = T1 and, for convenience, define A(0) = 0. Define (i) (i) Proof. Suppose |R A N K (A, T ) − n | 2 ≤ ∆ and the intervals Ri := r1 T1 − ∆1 , r1 T1 + ∆1 . Pick |R A N K (M E D I A N (T ), T2 ) − r1 (T1 )| ≤ 10s. By Lem- any i ∈ [B − 1]. By condition 1 above, mas 3.2 and 3.3, it suffices to show that these conditions (i) (i+1) imply |R A N K (A, T2 ) − r1 (T1 )| ≤ ∆ + 10s. To do so, note Pr R A N K A , T2 ∈ Ri R A N K A , T2 ∈ Ri+1 that the former condition is saying that there are at most ∆ (i) ≥ 1 − e T1 − e T1 (i+1) > 0. values in T between A and M E D I A N (T ). Since T2 ⊂ T , ∗ we have |R A N K (A, T2 ) − R A N K (M E D I A N (T ), T2 )| ≤ ∆. Therefore, by condition 2, there exists an instantiation T2 ∗ ∗ Now we simply apply a triangle inequality. of T2 such that R A N K A(i+1) , T2 − R A N K A(i) , T2 ≥ 100∆2 − 2∆1 ≥ 99∆2 . Thus, A(i+1) − A(i) ≥ 99∆2 . 1 1 1 The above lemma establishes the "estimator property" Similar reasoning shows that this inequality in fact holds of r1 (T1 ) mentioned earlier. We now show that r1 has high for i = 0 as well. In summary, the values A(0) , . . . , A(i) variability even when restricted to inputs T1 on which the are seen to be well dispersed. protocol does not err much. For sets S ⊂ [2n], define On the other hand, condition 1 above can be written as e(S) := Pr |R A N K (A, T2 ) − r1 (T1 )| > ∆ + 10s ∀ i ∈ [B] : Pr R A N K A(i) , U ∈ Ri U ∈ X2 ≥ 0.65 , U | T2 ∈ X 2 , T 1 = S , where U denotes a uniform random subset of [ 2 ]. Let E ∗ denote the event i ∈ [B] : R A N K A(i) , U ∈ Ri ≥ i.e, the error probability of the protocol when Player 1's in- 0.6B. A Markov bound gives us Pr[E ∗ | U ∈ X2 ] ≥ 1/8. put is S and Player 2 sends his fixed message correspond- Furthermore, ing to X2 . Pr[U ∈ X2 ] = 2− 2 |X2 | ≥ 2− 2 −2s |X2 | L EMMA 3.5. Define R := {r1 (T1 ) : e(T1 ) ≤ 0.35}. √ 2 −2s 2 Then |R| = Ω( 1 ). = 2− 2 −2s ≥ , t2 n2 where the final inequality used (2.1). Therefore, Pr[E ∗ ] ≥ qi − qk independent Bernoulli random variables. By the (1/8) · 2−2s n−2 . well-separated property of the qj 's we have qi − qk ≥ At this point we invoke a key probabilistic fact — the 99∆2 . Using the property of the binomial distribution, the √ Dispersed Ranks Lemma — which says that for such well probability that Zi attains any value is√ most 1/ 99∆2 . at √ dispersed A(i) values, we must have Pr[E ∗ ] ≤ 2−Ω(B) . Therefore, Pr[Zi ∈ Ri | E] ≤ |Ri |/ 99∆2 ≤ 2/ 99. Combined with the above lower bound on Pr[E ∗ ], this im- √ Using this bound in (4.2), it follows that plies s ≥ Ω(B) − O(log n) = Ω( 1 /(∆ + 10s)2 ) − √ √ O(log n). Setting 1 = n (the maximum allowed Pr (Zi ∈ Ri ) ≤ (2/ 99)|S| = 2−c B , by Lemma 3.3) and rearranging gives max{s, ∆} = i∈S Ω(n1/12 ), the desired lower bound. where c > 1. 4 The Dispersed Ranks Lemma 5 Two Passes We now introduce a key technical probabilistic fact that In this section, we show that a 2-pass algorithm requires lies at the heart of our lower bound argument and captures max{s, ∆} = Ω(n3/80 ). This proof contains all the ideas the intuition behind round elimination in our setting. The needed for the general lower bound for p passes. However, theorem was used in the above proof of the lower bound in this extended abstract, we choose to present the lower for one-pass algorithms. Later, it will be used repeatedly bound for p = 2, which allows for much more transparent for the multipass lower bound. notation and discussion. A proof of the general lower bound is deferred to the full version of the paper. L EMMA 4.1. (D ISPERSED R ANKS L EMMA ) Let and B We fix the number of players p = 3, for the commu- be large enough integers and let U denote a uniform nication problem M E D C O M M π, ,t . In general, for a p-pass random subset of [ ]. Let q0 = 0 and let q1 , q2 , . . . , qB ∈ algorithm, we would fix p = p + 1. Assume we have a 1 - 3 [ ] be such that ∀ i : qi+1 − qi ≥ 99∆2 . Let Ri := error 2-round deterministic protocol for the problem with [qi − ∆, qi + ∆] for i ∈ [B], and let E ∗ denote the message size s. event i ∈ [B] : R A N K (qi , U ) ∈ Ri ≥ 0.6B. Then We begin by fixing the first round of communication Pr[E ∗ ] = 2−cB , for some constant c > 0. in essentially the same way as in the one-pass lower bound. First, we fix the messages of Players 3 and 2 as Proof. Let Zi denote the random variable R A N K (qi , U ) for in Lemma 3.2. Now define r1 (T1 ) as before, and conclude all i ∈ [B]. By the union bound, √ that there exist Ω( 1 ) settings of T1 , leading to distinct r1 values, where the protocol's error is at most 0.35. To Pr[E ∗ ] ≤ Pr (Zi ∈ Ri ) , 1 B maximize hardness, pick B choices r1 , . . . , r1 for r1 that S i∈S k+1 k are√ far away as possible, i.e. for all k, r1 − r1 = as Ω( 1 /B). where S ranges over all subsets of [B] containing exactly We now consider B simulations for the second round, 0.6B indices. We will show that each probability within depending on the B picked choices of T1 (more precisely, the sum is at most 2−c B for some constant c > 1. Since depending on the messages output by Player 1 given the B the number of choices of S is at most 2B , the proof of the choices of T1 ). Let A1 , . . . , AB be the algorithm's output lemma follows. in all these simulations. Now, Player 3 sends B messages Fix a set S ⊆ [B] of size 0.6B. For each i ∈ S, define of s bits, effectively a Bs-bit message, which we fix as in Ji = {j ∈ S | j < i}. By the chain rule of probability, Lemma 3.2. At the end of all these steps, we have: Pr (Zi ∈ Ri ) (T3 , T2 ) ∈ X3 × X2 , |X3 | ≥ |X3 |/2O(Bs) , i∈S (5.3) (4.2) |X2 | ≥ |X2 |/2O(s) ; = Pr Zi ∈ Ri (Zj ∈ Rj ) i∈S j∈Ji i ∀ i : Pr R A N K (Ai , T≥2 ) − r1 ≥ ∆ + O(s) (5.4) Fix an i in the above product in (4.2) above. Also fix a set | (T3 , T2 ) ∈ X3 × X2 ≤ 0.35 + o(1) . of elements zj ∈ Rj for all j ∈ Ji . Let E denote the event As before, to show that the information about T3 j∈Ji (Zj = zj ). We will upper bound the probability is not enough, we must analyze what problem is being Pr[Zi ∈ Ri | E]. By averaging, this will also yield the solved from Player 3's perspective. That is, we want to same upper bound on the probability in (4.2). understand R A N K (Ai , T3 ). By (5.4), we must understand Let k denote the largest element in Ji . Conditioned i R A N K (S T A T (r1 , T≥2 ), T3 ). Let us define on the event E, Zi is the sum of zk and a binomially distributed random variable corresponding to a sum of (5.5) i ξ i := S T A T (r1 , T≥2 ) . i i−1 Intuitively speaking, r1 and r1 are √ separated by Note that there is a unique acceptable witness (proof) √ Ω( 1 /B), so there are on the order of n · B1 elements 2 for every problem instance. In other words, the nonde- in P2 between ξ i and ξ i−1 . This makes for a variance of π terministic protocol induces a partition of X2 × X3 into a √ R A N K (ξ i , T3 ) of roughly n · B1 2 1/2 . Since the variance certain number, NR , of rectangles. Let us discard all rect- needs to be high to make for a hard problem, we have angles with size less than |X2 × X3 |/(100NR ). At least imposed a lower bound for 2 /n. a 0.99 fraction of the space X2 × X3 survives, so the av- On the other hand, we need to show R A N K (ξ i , T3 ) erage error over this remainder of the space increases by has small variance conditioned on T2 . That is done by at most 0.01. Pick any remaining rectangle over which constructing a good estimator r2 based on T2 . Our ability the error increases by at most 0.01 and call it X2 × X3 . to do that depends on how well we can understand ξ i . Then, since |X2 × X3 | ≥ |X2 × X3 |/(100NR ), we have Specifically, if we understand it to within ±D, we have |X2 | ≥ |X2 |/(100NR ) and |X3 | ≥ |X3 |/(100NR ). Fi- D n values in P2 that cannot be compared reliably to 2 nally, observe that NR = 2O(log n) , since the nondetermin- ξ i , so the estimator for R A N K (ξ i , T3 ) suffers an additive istic protocol sends O(log n) bits. approximation of D n . To keep the approximation in 2 Henceforth, we shall fix the spaces X2 and X3 (and check, we must impose an upper bound on 2 /n. the constant M ) guaranteed by the above lemma and work Thus, we have forces upper bounding and lower within them. bounding 2 /n, and we must make sure that a good choice i Assume by symmetry that r1 ≥ (t2 + t3 )/2, that is actually exists. That is done by constructing an estimator i i ξ ≥ M . If we knew ξ , we could compute: with small enough D. To make better estimation possible, we need some more information about the stream. It turns i R A N K (ξ i , T3 ) = r1 − |{y ∈ T2 | y ≤ ξ i }| out that if we find out M E D I A N (T≥2 ), we reduce the uncer- tainty range of ξ i enough to get a good D. This is intuitive, = r1 − R A N K (M, T2 ) − T2 ∩ [M, ξ i ] . i i √ since r1 is only O( 1 ) away from M E D I A N (T≥2 ). How- ever, obtaining M E D I A N (T≥2 ) is hard in our model (that Since ξ i is not known, we can proceed in the same way, is essentially what we are trying to prove). To circumvent using E[ξ i ] instead. Unfortunately, a priori ξ i is not con- that, we note that it is an easy computation based on non- centrated too tightly, and this uncertainty would introduce determinism. On the other hand, a small intervention by a too large an approximation in the estimate of |T2 ∩[M, ξ i ]|. i nondeterministic prover cannot help solve all r1 problems, However, this is precisely why we want to fix M : condi- so we still get a lower bound even if we allow nondeter- tioned on M E D I A N (T≥2 ) = M , ξ i is much more tightly minism in a brief part of the communication game. concentrated, and 5.1 Constructing an Estimator r2 . We now attempt to Ξi := E[ξ i | M E D I A N (T≥2 ) = M ] i construct a good estimator r2 (r1 , T2 ) for the interesting i is a good enough replacement for the real ξ i . We thus quantity R A N K (ξ , T3 ). In general, T2 does not give define: enough information to construct a very good estimator r2 . However, we restrict the problem to a subset of i i r2 (r1 , T2 ) = r1 − R A N K (Ξi , T2 ) the inputs where such an estimator exists. It turns out i = r1 − R A N K (M, T2 ) − T2 ∩ [M, Ξi ] . that the one critical piece of information that we need is M E D I A N (T2 ∪ T3 ), so we work in a set of the inputs where L EMMA 5.2. For λ ≥ Ω(B), we have: Pr ξ i − Ξi ≥ it is fixed. √ 2 λ 4 1 | (T3 , T2 ) ∈ X3 × X2 ≤ 2−Ω(λ ) . L EMMA 5.1. Let X2 ⊂ X2 , X3 ⊂ X3 be arbitrary. There exist X2 ⊂ X2 , X3 ⊂ X3 and a constant M such that: Proof. The following random walk defines ξi = i • |X2 |/|X2 | ≥ 2 −O(log n) and |X3 |/|X3 | ≥ 2 −O(log n) ; S T A T (r1 , T≥2 ): start with M E D I A N (T≥2 ) and go up on elements of P2 ∪ P3 , until you find r1 − t2 +t3 elements π π i 2 i i • Pr R A N K (A , T≥2 ) − r1 ≥ ∆ + O(s) ≤ 0.37; that are in T≥2 . The length of this walk is an approximate bound for ξ i − M E D I A N (T≥2 ). The only discrepancy is • M E D I A N (T2 ∪ T3 ) = M for all (T2 , T3 ) ∈ X2 × X3 . π π π the number of elements in [2n] \ (P2 ∪ P3 ) = P1 that Proof. Consider the following nondeterministic commu- are skipped. However, we will only be interested in walks nication protocol for finding M E D I A N (T2 ∪ T3 ) with whose length does not deviate too much from its expecta- √ O(log n) communication. The prover proposes the median tion. Thus, the length is O(r1 − t2 +t3 ) ≤ O( 1 ). By the i 2 x and R A N K (x, T2 ). Player 2 accepts iff this rank is cor- defining property of F, there are only O(log n) elements π rect. Player 3 accepts iff R A N K (x, T3 ) + R A N K (x, T2 ) = of P1 in the relevant range, so the length of the walk is an (|T2 | + |T3 |)/2. O(log n) additive approximation to ξ i − M E D I A N (T≥2 ). π π Now assume T≥2 is selected from P2 ∪ P3 by in- (T2 , T1 ) which don't lead to error above 0.47. By √ Markov, k+1 k cluding every element independently and uniformly. Then Pr[r2 ∈ G] ≥ 1/10. √ Note that r1 − r1 = Ω( 1 /B) π the length of the walk deviates from its expectation by and there are Ω( n · 2 1 /B) values of P2 in this range. √ √ λ r1 − t2 +t3 ≤ λ 4 1 with probability 2−Ω(λ ) . The i 2 With 1 = n, 2 = n15/16 , this gives Ω(n3/16 /B) val- √ 2 O(log n) approximation is a lower order term compared ues. So the lemma is applied with ∆ = Ω(n3/32 / B). √ The conclusion will be that an event of the form E ∗ is expo- to λ 4 1 (affecting constant factors in λ), so this is a bound √ on the deviation of ξ i − M E D I A N (T≥2 ) from its mean. nentially unlikely unless |G| = Ω(B∆) = Ω( B · n3/32 ). √ Now to obtain the real process of selecting T≥2 , all Therefore, we have Ω( B · n3/32 ) possible values for r2 . we have to do is condition on |T2 | = t2 , |T3 | = t3 . The proof is completed as before, using the dispersed These events have probability 1/ poly(n) by (2.1), so the ranks property for the last player. We need B 2 choices i+1 2 i i of r2 , so √ can guarantee r2 − r2 = Ω(B∆/B 2 ) = we probability of the bad event is ≤ 2−Ω(λ ) · poly(n). Since 3/32 2 2 Ω(n / √B). Then the new ∆ for the lemma is λ = Ω(B) > log n, we have 2−Ω(λ ) ·poly(n) = 2−Ω(λ ) . Ω(n3/64 /√ B), and we thus obtain an inapproximability 4 Now we condition on (T3 , T2 ) ∈ X3 × X2 . By (5.3) of n 3/64 4 / B. On the other hand, we have an upper bound and Lemma 5.1, we have Pr[(T3 , T2 ) ∈ X3 × X2 ] ≥ for the approximation of O(∆ + B), so this is impossible 2−O(Bs)−O(log n) ≥ 2−O(Bs) . So in the universe X3 × X2 , if ∆ = B and B 5/4 < n3/64 , if B < n3/80 . That means 2 the probability of a deviation is at most 2−Ω(λ ) /2−O(Bs) . s + ∆ = Ω(n3/80 ). 2 If λ ≥ Ω(B), this is 2−Ω(λ ) . Finally, note that in X3 × X2 , M E D I A N (T≥2 ) is fixed. Acknowledgments Then, the event that ξ i − M E D I A N (T≥2 ) doesn't deviate We are grateful to Sudipto Guha for suggesting to us the from the expectation is the same as the event that ξ i problem studied here, and for inspiring and motivating doesn't. conversations in the early stages of this work. √ C OROLLARY 5.3. If 2 < n/ 4 1 , then ∀ i ∈ [B], Pr R A N K (ξ i , T3 ) − r2 (r1 , T2 ) > Ω(B) | (T3 , T2 ) ∈ i References X3 × X2 = o(1). [ADHP06] Micah Adler, Erik D. Demaine, Nicholas J. A. Har- Proof. Inspecting the definition of r2 , we observe that a ¸ vey, and Mihai Pˇ trascu. Lower bounds for asymmetric i i i i R A N K (ξ , T3 ) − r2 (r1 , T2 ) ≤ T2 ∩ [ξ , Ξ ] . Setting communication channels and distributed source coding. In √ Proc. 17th Annual ACM-SIAM Symposium on Discrete Al- λ = Θ(B) in Lemma 5.2, |ξ i − Ξi | ≤ O(B) · 4 1 entails √ i i π i i 4 gorithms, pages 251–260, 2006. T2 ∩ [ξ , Ξ ] ≤ P2 ∩ [ξ , Ξ ] ≤ ( 2 /n) · O(B 1 ) = [Cha07] Amit Chakrabarti. Lower bounds for multi-player O(B), where the final inequality follows from the defining pointer jumping. In Proc. 22nd Annual IEEE Conference property of F. on Computational Complexity, pages 33–45, 2007. [CKMS06] Graham Cormode, Flip Korn, S. Muthukrishnan, and 5.2 The Variability of r2 . Putting the bounds on the Divesh Srivastava. Space- and time-efficient deterministic estimator r2 together, we obtain the following problem: algorithms for biased quantiles over data streams. In Proc. 25th ACM Symposium on Principles of Database Systems, (T3 , T2 ) ∈ X3 × X2 , |X3 | ≥ |X3 |/2O(Bs) , pages 263–272, 2006. [CM05] Graham Cormode and S. Muthukrishnan. An improved |X2 | ≥ |X2 |/2O(s) ; data stream summary: the count-min sketch and itsapplica- tions. J. Alg., 55(1):58–75, 2005. Preliminary version in i ∀ i : Pr R A N K (Ai , T3 ) − r2 (r1 , T2 ) ≥ ∆ + O(B) Proc. 6th Latin American Theoretical Informatics Sympo- sium, pages 29–38, 2004. | (T3 , T2 ) ∈ X3 × X2 ≤ 0.37 + o(1) . [CR04] Amit Chakrabarti and Oded Regev. An optimal ran- domised cell probe lower bound for approximate nearest Thus, we have identified the problem that the algo- neighbour searching. In Proc. 45th Annual IEEE Sympo- rithm is solving with small approximation. The only re- sium on Foundations of Computer Science, pages 473–482, maining question is how many choices of r2 exist, for pos- 2004. sible choices of T2 . These are distinct problems that the [DG04] Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Sim- messages from Player 3 must have answered. plified data processing on large clusters. In Proc. 6th Sym- posium on Operating System Design and Implementation, We now sketch the remainder of the analysis, defer- pages 137–150, 2004. ring a complete rigorous treatment to the full version of [GK01] Michael Greenwald and Sanjeev Khanna. Space- the paper. The analysis is completed by applying a ver- efficient online computation of quantile summaries. In sion of the Dispersed Ranks Lemma to Player 2. Let Proc. Annual ACM SIGMOD Conference, pages 58–66, G be the set of r2 values that get generated by settings 2001. [GKMS02] Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, [MRL99] Gurmeet Singh Manku, Sridhar Rajagopalan, and and Martin Strauss. How to summarize the universe: Dy- Bruce G. Lindsay. Random sampling techniques for space namic maintenance of quantiles. In Proc. 28th Interna- efficient online computation of order statistics of large tional Conference on Very Large Data Bases, pages 454– datasets. In Proc. Annual ACM SIGMOD Conference, 465, 2002. pages 251–262, 1999. [GM06] Sudipto Guha and Andrew McGregor. Approximate a ¸ [PT06] Mihai Pˇ trascu and Mikkel Thorup. Time-space trade- quantiles and the order of the stream. In Proc. 25th ACM offs for predecessor search. In Proc. 38th Annual ACM Symposium on Principles of Database Systems, pages 273– Symposium on the Theory of Computing, pages 232–240, 279, 2006. 2006. [GM07] Sudipto Guha and Andrew McGregor. Lower bounds a ¸ [PT07] Mihai Pˇ trascu and Mikkel Thorup. Randomization for quantile estimation in random-order and multi-pass does not help searching predecessors. In Proc. 18th An- streaming. In Proc. 34th International Colloquium on nual ACM-SIAM Symposium on Discrete Algorithms, pages Automata, Languages and Programming, pages 704–715, 555–564, 2007. 2007. [SBAS04] Nisheeth Shrivastava, Chiranjeeb Buragohain, Di- [GZ03] Anupam Gupta and Francis Zane. Counting inversions vyakant Agrawal, and Subhash Suri. Medians and beyond: in lists. In Proc. 14th Annual ACM-SIAM Symposium on new aggregation techniques for sensor networks. In Proc. Discrete Algorithms, pages 253–254, 2003. ACM SenSys, pages 239–249, 2004. [MNSW98] Peter Bro Miltersen, Noam Nisan, Shmuel Safra, [Sen03] Pranab Sen. Lower bounds for predecessor searching and Avi Wigderson. On data structures and asymmet- in the cell probe model. In Proc. 18th Annual IEEE ric communication complexity. J. Comput. Syst. Sci., Conference on Computational Complexity, pages 73–83, 57(1):37–49, 1998. Preliminary version in Proc. 27th An- 2003. nual ACM Symposium on the Theory of Computing, pages [VW07] Emanuele Viola and Avi Wigderson. One-way multi- 103–111, 1995. party communication lower bound for pointer jumping with [MP80] J. Ian Munro and Mike Paterson. Selection and sorting applications. In Proc. 48th Annual IEEE Symposium on with limited storage. TCS, 12:315–323, 1980. Preliminary Foundations of Computer Science, 2007. to appear. version in Proc. 19th Annual IEEE Symposium on Founda- [Yao77] Andrew C. Yao. Probabilistic computations: Towards a tions of Computer Science, pages 253–258, 1978. unified measure of complexity. In Proc. 18th Annual IEEE [MRL98] Gurmeet Singh Manku, Sridhar Rajagopalan, and Symposium on Foundations of Computer Science, pages Bruce G. Lindsay. Approximate medians and other quan- 222–227, 1977. tiles in one pass and with limited memory. In Proc. Annual ACM SIGMOD Conference, pages 426–435, 1998.
Pages to are hidden for
"median"Please download to view full document


text:
Order Megace
Here's a taste of what TheBody.com has to offer on this topic:
Ask the Experts
megace to gain weighti am a healthy person weighing 80 but height 6 feet so i want to use megace to gain body weight please do tell me the way to achieve my goal
Response from Nelson Vergel, B.S.Ch.E., M.B.A.
Program for Wellness Restoration...individuals, even those with advanced cancer. It is also used to boost appetite in individuals with other cancers or HIV/AIDS.Megace us the worst drug to use for weight gain. It increases mostly fat mass, hyperglycemia, risks of blood clots and... Read more »
Megace treatmentI have been offered to start treatment with Megace. I have now read the side effects and I was not... Read more »
Megace, androgel, and testosterone levelsHello..I have been taking Megace to help bolster my appetite, but recently I read that Megace can... Read more »
An Overview of Megestrol Acetate (Megace)... me-JES-trole Brand Name: Megace ES, Megace Oral Suspension Other Name(s): Acetato de megestrol, Megestrol Drug Class: Opportunistic Infection and Other Drugs Read more »
Wasting Syndrome...the causes mentioned above. Reducing nausea and vomiting helps increase food intake. Also, appetite stimulants including Megace and Marinol have been used. Megace, unfortunately, is associated with increases in body fat. Marinol (dronabinol)... Read more »
Caring for Your Gut: Dealing With Diarrhea, Nausea and Other Stomach Problems if You Have HIV/AIDS...you are taking (including over-the-counter, prescription, street drugs, and herbs), even if you only use them occasionally. Megace (a hormone) and Marinol (a synthetic version of marijuana) may increase appetite. Marijuana may be effective for... Read more »
Getting HIV DrugsTable of Contents Health Insurance AIDS Drugs Assistance Program Medicaid Drug Company Programs Clinical Trials Buyers' Club Seeking Help Health Insurance Health insurance usually covers most of the cost of your... Read more »
Connect With Others
Two weeks down and a life time to live
Posted by trulife, 2 RepliesWell folks...it's the end of two weeks on Atripla and so far things are going well. Side effects have been limited and are now subsiding. My biggest problem so far is swallowing the pill. I have always had trouble swallowing pills...go figure...a... Read more »
What foolish and senseless behavior. Please Help!
Posted by brainshom, 1 ReplyAbout 2 months ago, I did something that was completely out of my character and now I am scared as hell. I was new in the neighborhood and had a one night stand with a girl whom I later found out was/is a prostitute. Had I known she was a sex... Read more »
hello everyone...
Posted by Anonymous, 2 Replies...seem to be keeping the diahreah in check, so long as I don't stop taking either of them, and we've recently added megace, 20 ml once a day as an appetite stimulant. I am also taking some of the more usual... Read more »
Wasting---help me
Posted by Anonymous, 4 RepliesI'm sorry to come on board, but I need help. My husband is wasting away. He's newly on meds, but not gaining. It seems as though his buttcheeks are completely gone. I don't know what to do. I'm afraid. He's down to 120 and losing despite putting... Read more »
Resource Centers
Guides for People With HIV

subset: commoncrawl


text:
Hi! I am 31 years old and live in Hamilton, New Zealand. I am a lawyer and specialise in environmental and employment law. I love to travel and have lived in London and travelled around Europe previously. My partner, Kieran is also a lawyer and is looking forward to travelling to Europe for the first time later this year.
When I'm not working I like to exercise/run, hang out with friends, bake, watch movies and spend time with our two cats.


text:
Genome 2.0: mountains of new data are challenging old views.
Only 6 years later, the landscape of the genome is already proving to be dramatically different than most scientists had expected.
The established view of the genome began to take shape in 1958, just 5 years after Francis Crick and James D. Watson worked out the structure of DNA. In that year, Crick expounded what he called the "central dogma" of molecular biology: DNA's genetic information flows strictly one way, from a gene through a series of steps that ends in the creation of a protein. That principle developed into a modern orthodoxy, according to which a genome is a collection of discrete genes located at specific spots along a strand of DNA. This old view got the basics right: that genes encode proteins and that proteins do the myriad work necessary to keep an organism alive.
Researchers slowly realized, however, that genes occupy only about 1.5 percent of the genome. The other 98.5 percent, dubbed "junk DNA," was regarded as useless scraps left over from billions of years of random genetic mutations. As geneticists' knowledge progressed, this basic picture remained largely unquestioned. "At one time, people said, 'Why even bother to sequence the whole genome? Why not just sequence the [protein-coding part]?'" says Anindya Dutta, a geneticist at the University of Virginia in Charlottesville.
Closer examination of the full human genome is now causing scientists to return to some questions they thought they had settled. For one, they're revisiting the very notion of what a gene is. Rather than being distinct segments of code amid otherwise empty stretches of DNA--like houses along a barren country road--single genes are proving to be fragmented, intertwined with other genes, and scattered across the whole genome.
Even more surprisingly, the junk DNA may not be junk after all. Most of this supposedly useless DNA now appears to produce transcriptions of its genetic code, boosting the raw information output of the genome to about 62 times what genes alone would produce. If these active nongene regions don't carry code for making proteins, just what does their activity accomplish?
"What we thought was important before was really just the tip of the iceberg," says Hui Ge of the Whitehead Institute for Biomedical Research in Cambridge, Mass.
With the genome sequence in hand, exploration has moved at a brisk pace during the past 6 years. A milestone was reached in June, when a project called the Encyclopedia of DNA Elements (ENCODE) thoroughly mapped the functional regions in 1 percent of the human genome. The effort involved was staggering: Thirty-five teams of scientists from around the world worked for 4 years and compiled more than 600 million data points, the consortium reported in the June 14 Nature.
From the accumulating mountains of data, scientists are building a new picture of how the genome works as a whole. They have found mutations in nongene regions of DNA that are linked to common diseases such as diabetes and forms of cancer. And some researchers propose that DNA once labeled junk could have spawned the complex bodies of higher organisms--even the complexities of the human brain.
SECOND FIDDLE TO SUPERSTAR In the emerging picture of the genome's functioning, many of the key elements identified so far are molecules of RNA, a chemical cousin of DNA.
In the old central dogma, RNA had a strictly subservient role in the all-important task of making proteins. An RNA molecule is made from units of genetic code strung together, much like DNA. But while DNA has two strands twisted together into a double helix, RNA usually has only a single strand.
Protein synthesis begins when the two strands of a section of DNA unzip. Units of RNA then pair up with their counterparts on one of the DNA strands, forming a complementary messenger RNA (mRNA) molecule. The mRNA detaches and floats off to other parts of the cell, where it hooks up with machinery that transcribes its coded message into a protein.
If RNA's only job were making proteins, then nearly all the RNAs produced in cells should be transcripts of protein-coding genes. (A small fraction of RNAs serve in the protein-transcription machinery.) But in 2005, Jill Cheng and her colleagues at Affymetrix, a genomics company in Santa Clara, Calif., showed that less than half of the RNA produced by 10 of the chromosomes in human cells represented transcripts of traditional genes. In the team's experiments, 57 percent of the RNA was transcribed from noncoding, "junk" regions.
The results from ENCODE were even more striking. In the slice of DNA studied in that project, between 74 percent and 93 percent of the genome produced RNA transcripts. What becomes of this tremendous output is uncertain. John M. Greally of the Albert Einstein College of Medicine in New York says it's likely that some portion of it is made accidentally and simply discarded. But the discovery that so much of the genome is being transcribed into RNA underscores how out-of-date the central dogma has become.
Indeed, the closer researchers look, the more functions they find that RNA transcripts perform. An alphabet soup of new acronyms describes the newfound roles of RNAs. First there were short nuclear RNAs (snRNAs) and short nucleolar RNAs (snoRNAs), both of which reside inside the nucleus and help control production of other RNAs. These were joined by microRNAs (miRNAs) and short interfering RNAs (siRNAs), which can modulate the activity of protein-coding genes. In mice, about 34,000 of the RNA transcripts produced by the genome are non-protein-coding, outnumbering the roughly 32,000 transcripts that code for proteins, according to a 2005 study by an international group of scientists called the Functional Annotation of Mouse Consortium.
These new families of RNAs add a layer of regulation that fine-tunes the production of proteins. While scientists already knew that some proteins influence the activity of other genes, "there are many more RNAs than proteins that play a regulatory role," Ge says.
Gene regulation may not sound sexy, but it's a powerful way for a cell to evolve complex behaviors using the tools--proteins--that it already has. Consider the difference between a one-bedroom bungalow and an ornate, three-story McMansion. Both are made from roughly the same materials--lumber, drywall, wiring, plumbing--and are put together with the same tools--hammers, saws, nails, and screws. what makes the mansion more complex is the way that its construction is orchestrated by rules that specify when and where each tool and material must be used.
In cells, regulation controls when and where proteins spring into action. If the traditional genome is a set of blueprints for an organism, RNA regulatory networks are the assembly instructions. In fact, some scientists think that these additional layers of complexity in genome regulation could be the answer to a long-standing puzzle.
GENOME AS NETWORK The biggest surprise in the first sequence of the human genome was how few protein-coding genes it contained.
"We humans do not have that many more genes than simpler organisms like flies or mice," Ge says. Earlier guesses of the number of genes in humans ran as high as 100,000, but the published sequence in fact contained only about 23,000. That's not much more than the roughly 21,000 genes possessed by the roundworm, a microscopic creature without a brain. If protein-coding genes are the only functional elements in an organism's DNA, where does the extra information come from that's needed to assemble and operate the complex bodies and brains of people, as compared with the simplicity of roundworms? "If we just look at the number of genes, it doesn't make sense," Ge says.
While the number of genes isn't much different in roundworms and people, the human genome is 30 times the size of the roundworms'. People have a much larger quantity of DNA beyond what codes for proteins. Since much of this "junk" DNA is being transcribed into RNA, perhaps it's responsible for much of the complexity of human bodies and brains. In fact, organisms simpler than roundworms, such as single-celled bacteria, carry little non-coding DNA and may have no regulatory RNA at all.
"Scientists have been suspecting that it is the regulatory networks that lead to this amazing complexity" in higher organisms, Ge says.
John S. Mattick of the University of Queensland in Brisbane, Australia, points to a known example of the importance of regulatory RNAs: their crucial role in fetal development. For example, most multicellular animals possess a gene called Notch that helps guide neural development, while the gene itself has much the same form in both simple and complex animals, its activity is regulated by miRNAs that are highly variable from one animal to another. Such miRNAs also influence a gene called Hox, which acts in many animals to define a fetus' body axis and the placement of its limbs.
What's more, the changes that distinguish human brains from those of chimpanzees and other apes could be due in part to evolutionary changes in RNAs that don't encode proteins. A group led by Katherine S. Pollard of the University of California, Davis identified DNA sequences shared by people and chimpanzees, but with large differences, meaning that they have evolved rapidly since the two species shared a common ancestor.
The researchers found that one of these sequences is a non-coding region of DNA that's related to brain function, they reported in the Sept. 14, 2006 Nature. Pollard and her colleagues speculate that this region produces a regulatory RNA and that changes in this RNA contributed to the evolution of the human brain.
With regulatory RNAs appearing to play such an instrumental role in animal development, it's no surprise that scientists are finding disease-associated mutations in regions of the genome formerly regarded as junk.
David Altshuler of the Broad Institute in Cambridge, Mass., and his colleagues looked for DNA mutations in 1,464 patients with type 2 diabetes. Three of the mutations that correlated with the disease were in DNA segments that don't code for proteins, the team reported in the June 1 Science. Other scientists have found mutations in noncoding DNA that link to diseases such as autism, breast cancer, lung cancer, prostate cancer, and schizophrenia.
To be sure, the specific functions of most of the noncoding DNA remain unknown. Projects such as ENCODE have focused on identifying the broad functional categories for active regions of the genome without working out the specific cellular function of each transcript, a task that will take biologists years, if not decades.
In fact, scientists debate whether some fraction of the genome's copious RNA Output might do nothing at all. It may simply be that once the cellular machinery that transcribes DNA into RNA gets started, it sometimes doesn't know when to stop. On the other hand, making lots of RNA that does nothing would be a waste of a cell's energy. That's something that natural systems tend to avoid, so the fact of its production argues for at least some of this RNA being biologically active.
THE GENE IS DEAD In the old view, each gene sat in splendid isolation on its segment of the genome. Other genes might be nearby, but scientists assumed that they didn't overlap each other.
Now it's clear that a single length of DNA can be transcribed in multiple ways to produce many different RNAs, some coding for proteins and others constituting regulatory RNAs. By starting and stopping in different places, the transcription machinery can generate a regulatory RNA from a length of DNA that overlaps a protein-coding gene. Moreover, the code for another regulatory RNA might run in the opposite direction on the facing strand of DNA. According to the ENCODE project results, up to 72 percent of known genes have transcripts on the facing DNA strand as well as the main strand.
"The same sequences are being used for multiple functions," says Thomas R. Gingeras of Affymetrix. That introduces complications into the evolution of the genome, which had until recently been assumed to act through single DNA mutations affecting single genes. Now, "a mutation in one of those sequences has to be interpreted not only in terms of [one gene], but [of] all the other transcripts going through the region," Gingeras explains.
The implications of this single mutation-multiple consequence model are still a matter of debate. In some cases, the RNA transcripts from DNA that overlaps a protein-coding gene regulate that same gene, so a mutation could affect both the structure and the regulation of a protein. But often, those transcripts regulate genes that are far away, or even on different chromosomes. This complex interweaving of genes, transcripts, and regulation makes the net effect of a single mutation on an organism much more difficult to predict, Gingeras says.
More fundamentally, it muddies scientists' conception of just what constitutes a gene. In the established definition, a gene is a discrete region of DNA that produces a single, identifiable protein in a cell. But the functioning of a protein often depends on a host of RNAs that control its activity. If a stretch of DNA known to be a protein-coding gene also produces regulatory RNAs essential for several other genes, is it somehow a part of all those other genes as well?
To make things even messier, the genetic code for a protein can be scattered far and wide around the genome. The ENCODE project revealed that about 90 percent of protein-coding genes possessed previously unknown coding fragments that were located far from the main gene, sometimes on other chromosomes. Many scientists now argue that this overlapping and dispersal of genes, along with the swelling ranks of functional RNAs, renders the standard gene concept of the central dogma obsolete.
LONG LIVE THE GENE Offering a radical new conception of the genome, Gingeras proposes shifting the focus away from protein-coding genes. Instead, he suggests that the fundamental units of the genome could be defined as functional RNA transcripts.
Since some of these transcripts ferry code for proteins as dutiful mRNAs, this new perspective would encompass traditional genes. But it would also accommodate new classes of functional RNAs as they're discovered, while avoiding the confusion caused by several overlapping genes laying claim to a single stretch of DNA. The emerging picture of the genome "definitely shifts the emphasis from genes to transcripts," agrees Mark B. Gerstein, a bioinformaticist at Yale University.
Scientists' definition of a gene has evolved several times since Gregor Mendel first deduced the idea in the 1860s from his work with pea plants. Now, about 50 years after its last major revision, the gene concept is once again being called into question.
Reader Opinion
|Printer friendly Cite/link Email Feedback
|Barry, Patrick
|Science News
|Sep 8, 2007
|Previous Article:
|What goes up: big-city air pollution moves to the burbs and beyond.
|Next Article:
|A different view of Uranus' rings.


text:
Donate Today!
Become a Member
Become a Member
Thank you for contacting the Association.
Use this form to report technical problems with diabetes.org, such as broken hyperlinks.
Please fill out this form so we can properly assist you. We will respond within three business days.
Your Name (required)
Your Email Address (required)We need your email address so that we can respond to your question.
Subject (required)Choose from the list below or select "Other"
Broken link (provide page URL in next question)Incorrect information on web page (provide page URL in next question)Can't find informationGeneral questionOther
Page URL If you are reporting a broken link, a problem with a form, or an error on a page, providing the page URL helps us pinpoint the problem. For example: http://www.diabetes.org/food-and-fitness/food/
Device Your are Using This helps us determine if the problem is related to your particular device.
Desktop computerLaptop computerTabletSmart phone
Operating System You are Using This helps us determine if the problem is related to the system you are using.
Web Browser You are Using This helps us determine if the problem is related to the browser you are using.
ChromeFirefoxInternet Explorer (version 9 or later)Internext Explorer (version 8 or earlier)SafariOpera
The problem you are experiencing (required) (please be as specific and complete as possible so we can better answer your question)
Give hope to millions with diabetes wishing for cure.
March 24 is Alert Day. Take the Diabetes Risk to find out your risk for type 2 diabetes.
Get your go-to resource for healthy meals in any restaurant.
Check out the Drive to Stop Diabetes 2015 NASCAR Schedule.
Help Stop Diabetes by Taking Part in these Promotions.
Receive your personalized action plan with My Health Advisor.
Washington Redskins Pro Bowler Trent Williams Takes Control.
Organize and send your diabetes data with Diabetes 24/7.


text:
Greater Bemidji Area Joint Planning Board: Building gets approval by JPB for Voyageurs High School relocation
Voyageurs Expeditionary High School is getting closer to relocating its school across town.
The Greater Bemidji Area Joint Planning Board voted unanimously Wednesday to approve a Conditional Use Permit for the former Kobilka's Sporting Goods building at 3724 Bemidji Ave. N. to operate as a school.
Get the full story
Subscribe or Log In
Are you a newspaper subscriber but you don't have a Digital Access account yet? Activate your account.
You will need your subscription account number and phone number. Not sure if you have an account? Email us or call (218) 333-9200 and we can help you.


text:
Sale Price $
You Save $
This adidas Stella McCartney barricade dress unites a stylish slimming look with sporty performance. It features adjustable elastic tank straps, built-in shelf bra, mesh panels on sides and back, zig-zag top stitching, slimming colorblocking, and a heat transfer adidas by Stella McCartney logo at center chest. Coordinating compression short is included.
- Fit: We find the dress is very fitted throughout.
- Content: 86% Nylon, 14% Spandex
- Colors: Fresh Blue w/Legend Blue/White & Running Yellow
CLIMALITE: Light, breathable fabrics conduct heat and sweat away from the body to keep you comfortable and dry in warm conditions.
|Pros Wearing This Item
Caroline Wozniacki
|Other items in Discount adidas Apparel
adidas Women's Stella McCartney Spring Tank
adidas Women's Stella McCartney Spring Cap Sleeve Top
adidas Women's Summer Powerluxe Live it Up Tank
|Check out all adidas Women's Tennis Apparel


text:
Investigation on the polymerization of an unsaturated polyester system by a resistivity technique
Article first published online: 9 MAR 2003
DOI: 10.1002/app.1965.070090511
Copyright © 1965 John Wiley & Sons, Inc.
Journal of Applied Polymer Science
Volume 9, Issue 5, pages 1743–1755, May 1965
Additional Information
How to Cite
Judd, N. C. W. (1965), Investigation on the polymerization of an unsaturated polyester system by a resistivity technique. J. Appl. Polym. Sci., 9: 1743–1755. doi: 10.1002/app.1965.070090511
Publication History
- Issue published online: 9 MAR 2003
- Article first published online: 9 MAR 2003
- Manuscript Received: 11 SEP 1964
Options for accessing this content:
- If you have access to this content through a society membership, please first log in to your society website.
- If you would like institutional access to this content, please recommend the title to your librarian.
- Login via other institutional login options http://onlinelibrary.wiley.com/login-options.
- You can purchase online access to this Article for a 24-hour period (price varies by title)
- If you already have a Wiley Online Library or Wiley InterScience user account: login above and proceed to purchase the article.
- New Users: Please register, then proceed to purchase the article.
Login via OpenAthens
Search for your institution's name below to login via Shibboleth.
Registered Users please login:
- Access your saved publications, articles and searches
- Manage your email alerts, orders and subscriptions
- Change your contact information, including your password
Please register to:
- Save publications, articles and searches
- Get email alerts
- Get all the benefits mentioned below!


text:
RED BULLS: Supporting the drawdown: Making room
CAMP VIRGINIA, Kuwait - Before the drawdown from Iraq was announced, the 134 Brigade Support Battalion at Camp Virginia, Kuwait, was at work preparing to house the soldiers and units coming out of Iraq. "We're expecting tens of thousands to come through Camp Virginia in a matter of a few months," said Lt. Col. Brian Bobo, battalion commander.
Get the full story
Subscribe or Log In
Are you a newspaper subscriber but you don't have a Digital Access account yet? Activate your account.
You will need your subscription account number and phone number. Not sure if you have an account? Call 218-855-5897 and we can help you.


text:
Where can I get good wood to make some grips like cherry wood and others?
Join FirearmsTalk.com Today - It's Free!
Are you a firearms enthusiast? Then we hope you will join the community. You will gain access to post, create threads, private message, upload images, join groups and more.
Firearms Talk is owned and operated by fellow firearms enthusiasts. We strive to offer a non-commercial community to learn and share information.
Join FirearmsTalk.com Today! - Click Here
a small time tool store in your area
Suppose you were an idiot. And suppose you were a member of Congress....
But then I repeat myself.
-Mark Twain


text:
Waratahs face a non-stop journey to finals
Rupert Guinness It is probably a good thing for the Waratahs if their playing ranks are "brain washed to try and think week-to-week".
Tahs scrum strength a good sign: Kepu
Georgina Robinson It was a project marked by twice-daily scrummaging sessions in the midsummer heat but the Waratahs are starting to reap the benefits and the Wallabies could be next.
Tahs overcome Blues to post fourth win
Georgina Robinson The Waratahs put a week of controversy behind them with an emphatic 23-11 victory over Super Rugby cellar dwellers the Blues in Sydney on Saturday.
Lacklustre affair highlights value of passion
Rupert Guinness What a difference a week makes ... even if the Waratahs again walked away winners against the Blues at home in Sydney on Saturday night.
Eales: Leadership calls for taking a stand
Rupert Guinness and Georgina Robinson It was a stand-out moment in the Wallabies captaincy of John Eales when, with 25 minutes left in the 1999 World Cup final against France at Millennium Stadium in Cardiff, he approached the referee and threatened to lead his team off the field in opposition to the dirty play of Les Bleus.
ARU should have given more details
Spiro Zavos Transparency is the key for the ARU in dealing with Jacques Potgieter's homophobic slur.
Waratahs won't risk Tatafu Polota-Nau after head knock
Georgina Robinson Michael Cheika has defended the intentions of coaches and team medicos after withdrawing Test hooker Tatafu Polota-Nau from the Waratahs' clash with the Blues on Saturday.
Kirwan predicts 'fireworks' in physical battle with Waratahs
Georgina Robinson John Kirwan has predicted "fireworks" and a physically explosive clash between the Blues and Waratahs in Sydney on Saturday.
Waratahs wary of underdog Blues
Georgina Robinson The Waratahs have underestimated the Blues once before and second rower Will Skelton says they will not be burnt that way again.
Tahs kick less than majority of NRL
Paul Cully Issac Luke alone kicks almost as much as the Waratahs, so why is rugby still struggling to get traction?
Little risk of Wallabies rift: Dwyer
Rupert Guinness Any risk of a rift between the Waratahs and Brumbies in the Wallabies squad after fiery derby should be contained by wise heads, says former coach.
Latu unaware of standing ovation after yellow card
Rupert Guinness It is rare that you see a yellow carded player get a standing ovation from their home crowd when they leave the field as Waratahs hooker Tolu Latu did last Sunday.
Brumbies park hostilities to team up with Tahs
Chris Dutton The ACT Brumbies will shelve Super Rugby hostilities to join forces with the NSW Waratahs in camp this weekend, adamant the fire and controversy of a heated battle in Sydney will be buried to focus on the Wallabies.
Moore and Cheika back Pocock on homophobia stance
Georgina Robinson Senior Waratahs, Wallabies and Brumbies figures have backed David Pocock for condemning homophobic slurs in the Brumbies' spiteful derby clash with the Waratahs.
Gibson to be named NSW coach this week
Georgina Robinson Daryl Gibson is expected to be appointed Waratahs head coach this week after rival Nick Scrivener withdrew from the race to take up an offer in Japan.
Pocock stands up when others wouldn't and he's not the villain
Chris Dutton David Pocock and the ACT Brumbies stood tall on the rugby field to do their bit in taking up the fight against homophobia.
Potgieter fined after homophobic slur in Brumbies clash
Chris Dutton ACT Brumbies players quizzed as Jacques Potgieter fined $20,000 for homophobic slur.
Potgieter fined $20,000 for homophobic slurs against Brumbies
Rupert Guinness The Waratahs' marquee international, Jacques Potgieter, has been fined $20,000 – with $10,000 suspended – for using homophobic slurs during his side's Super Rugby derby against the Brumbies at Allianz Stadium in Sydney on Sunday afternoon.
Homophobia not an issue at Waratahs: Folau
Rupert Guinness Star Waratah back Israel Folau has defended his side against the suggestion that there are homophobic views within the camp of the Super Rugby champions or even the game of rugby itself.
Potgieter fined by ARU
Chris Dutton NSW Waratahs forward Jaques Potgieter has apologised for using homophobic slurs in the match against the ACT Brumbies, describing the incident as an "offhand remark" after being fined $20,000 by the ARU.


text:
hyde st. pier posters, hyde posters, street posters, ferry posters, terminal posters, san francisco posters, harbor posters, boats posters, ships posters, victorian posters
All prints ship in durable cardboard tubes.
Fine Art America is one of the largest, most-respected giclee printing companies in the world with over 40 years of experience producing museum-quality posters and prints. All of our posters are produced on state-of-the-art, professional-grade Epson printers.
We use acid-free paper with archival inks to guarantee that your posters last a lifetime without fading or loss of color. All posters include a 1" white border around the image to allow for future framing and matting, if desired.
Posters ship within 3 - 4 business days in durable cardboard tubes.
The Hyde St. Pier was an historic ferry terminal on San Francisco's waterfront. Before the Bay and Golden Gate Bridges, U.S. HWY 101 and 40 diverted onto ferries at this pier. Untold thousands of people and early automobiles plyed this route to destinations north and east. Today it is a part of San Francisco's Maritime National Historic Park. Several historic vessels are moored here and from the left in the photo are the 1886 square rigger BALCLUTHA, the 1914 double paddle-wheeled tugboat EPPLETON HALL, the hull of the 1895 schooner C.A. Thayer, and (behind the C.A. Thayer) the 1890 steam Ferry Boat EUREKA. All of these ships are rare representatives of the few ships of their class, if any, that are still in existence today....
MODIFICATIONS and CUSTOM Orders WELCOME! As a youth, I was constantly drawing, painting, and experimenting in fine arts. Also, I had a strong interest in architecture. Today, I enjoy photography, history, drawing and painting. I labored over 25 years in a pre-World War II aluminum mill, some of the time on catwalks above two-thousand degree, electrically charged molten metal. At the height of my career the plug was pulled when various globalist financiers ravaged the company. In my mid-40s, I returned to college and re-educated as a computer network engineer. I currently work for local government. As a computer expert, I am proficient in most of the digital imaging software out there. As you browse offerings . . . keep in mind...
Our return policy is very simple:
If you're not happy with a purchase that you made on FineArtAmerica.com, for any reason, you can return it to us within 30 days of the order date. As soon as it arrives, we'll issue a full refund for the entire purchase price. Please note - Fine Art America does not reimburse the outgoing or return shipping charges unless the return is due to a defect in quality.
Fine Art America sells thousands of pieces of artwork each month - all with a 100% money-back guarantee.
If you've hesitated to purchase artwork online in the past, why not give us a try? You have nothing to lose!
We take great pride in the fact that 301,834 artists have chosen Fine Art America to fulfill their orders, and we look forward to helping you select your next piece!
Customer Service: 877-807-5901
(Call Any Time - 24 Hours Per Day)
All posters ship from our production facility within 24 hours of your order.


text:
Supporting Student Transformation Phil and Andrea
College provides intellectual stimulation and social experience that shape students' futures, personally and professionally. For some BU graduates, the college years are especially powerful, and they are driven to give back to the university that changed their lives.
Giving Never Grows Old
Today, Frances Young '36 turns 100 years old. To mark the occasion, there is a celebration at a restaurant in downtown La Crosse, Wisconsin, with family and friends, treats, cake and a photo in the Sunday paper. And of course, in a nod to St. Patrick's Day, "there is the wearing of the green," says Frances.
Accountant Pays It Forward
Al Fisher '69 first heard of BU during his senior year of high school, when his bookkeeping instructor suggested he attend either here or Shippensburg to study accounting. He chose BU and says the education he received set him up for professional success.
BU Foundation Makes Greenly Center Home
Main Street has a new resident – actually, several new residents – with the opening of the Greenly Center, the BU Foundation's new home, on March 12. Construction on the $8.25 million building was made possible thanks to a generous $1 million gift from Duane R. and Susan Basar Greenly, both members of the Class of 1972.


text:
We hate to see her go, but we love to watch her walk away.
Glitter Rocks
Get in the mood for love with sexy-sweet clothing and accessories; from jewel-trim headbands and leather clutches to embellished dresses and skiy-high platform sandals.
Julie Haus, spring 2009
Hoop earrings, Sequin, $28, at Girly NYC, NYC


text:
Christian Bale30 January 1974, Haverfordwest, Pembrokeshire, Wales
41 years
Sibi Blazic
Handsome actor Christian Bale is most known for his role in The Batman-movies and in American Psycho. He has one child with his wife Sibi Blazic.
RSS feed with Christian Bale
Picture special
Thursday 8:36 PM, 24/02/2011
Tags: Oscars / Hollywood celebrity
Its Oscars Time!
Tuesday 8:36 PM, 25/01/2011
The Oscar nominations are out and there were some obvious choices and some little surprises! Natalie Portman of course is nominated for her perform...READ MORE ▶
Tags: Oscars
Picture special
The Best of the Golden Globe Awards Red Carpet!
Monday 1:23 PM, 17/01/2011
You didn't think we would give you just the news from the Golden Globes last night and not the red carpet did you?! Here are all the...READ MORE ▶
Tags: Golden Globe / Red Carpet / Versace / Glee / Burberry / Calvin Klein / Valentino / Prada / Armani / Shoes / Marc Jacobs / Lanvin
Breaking News!
Last Night's Golden Globes - The Big Winners!
Monday 8:46 AM, 17/01/2011
Congratulations to "The Social Network! The movie walked away with a whopping 4 awards last night at the Golden Globes! Best Film, Best Director, B...READ MORE ▶
Tags: Golden Globe / Glee
Jessica Biel In the Next Batman Movie?!
Thursday 12:53 PM, 13/01/2011
The new Batman movie is in the works! Christian Bale will play Batman again in the next movie and its going to be called "The Dark Knight Rises". There are a lot of rumors flying around about who else will be starring and one of the biggest questions is - who will be Batman's love interest! We are hearing it could be Jessica Biel! Both Katie Holmes and Maggie Gyllenhaal have played opposite Christian, do you think Jessica would be a good choice? Vote or tell us in the comments who you think would be better as Vicki Vale?(Huffington Post)
Jessica Biel in the new Batman movie?
Tags: Celebrity rumors
Picture special
Wednesday 2:28 PM, 12/01/2011
Tags: Blake Lively / Red Carpet


text:
dark eggs.com- any good?
I am just exploring other possibilities regarding ordering baby chicks. I usually order from Mcmurray - I have nothing against them - have only had one problem with them and they corrected the situation.
just looking at other hatcheries for better quality and more variety. I looked at dark eggs.com and they seem to have a good variety.
anybody have any other suggestions besides these two and Ideal.com?
thanks alot everybody!
I have bought chicks from Townline in Zealand, MI. and they were not good quality show birds (they were not sold by them as 'Show' Quality)but were very good layers with production/feed ratios that were very good. Out of 104 chicks (pullets) received all 104 survived to adulthood and only 1 Roosters out of the batch. They started laying at between 16-18 weeks of age. They were a blend of heavy dual purpose meat/layers. They do allow you to go and pick them up.
Years back I ordered Silkies and Japs from Strombergs and they were to be 'show quality' birds. The Silkies were not even poor quality pet birds-many were crippled and the feathering look like they were crossbreeds-They were Silkies without the Silky feathers. The Japs were beautifully colored and had very good body shape but all were so long legged they looked like Jungle Fowl-for that reason were not the show 'Quality' promised. They treated me indifferently when these problems were brought to their attention. I could not give these poor quality 'Show' birds to the 4-H kids so ended up taking the whole lot to the auction.
I now try to buy all my new bloodlines from individual breeders who have a long history of QUALITY show birds.
I use Mt healthy hatcheries in Cincinnati. good selection plus they are close enough to my farm that I can drive down and pick up the chicks so they don't have to go through 2 to 3 days in the US postal system.
Here is a link that might be useful: Mt Healthy hatcheries


text:
Thanks for redeeming.{{else}}
Success! Thanks for repurchasing.{{/if}} {{else}} {{#if Expired}}
Increase my visibility!{{else}} {{#if IsMultiPack}}
{{#if HasMultiPack}} You have {{MultiPackCount}} top spot(s) left. Now loading you into the search listings... {{else}} You have used all top spots. Now loading you into the search listings... {{/if}}{{else}}
We are loading you into the search listing pages...{{/if}} {{/if}} {{/if}} {{/if}}
{{Current}} just saw you!{{/if}} {{#if LastTopSpotPurchaseIsMulti }} {{#if HasAnyTopSpot}}
{{#if HasFreeTopSpot }} {{ UnclaimedTopSpotFree }} Free {{/if}} {{#if HasPaidTopSpot }} {{#if HasFreeTopSpot }} & {{/if}} {{ MultiPackCount }} {{/if}} Top Spot{{#if Plural}}s{{/if}} Left{{else}}
0 Top Spot{{#if Plural}}s{{/if}} Left{{/if}} {{else}} {{#if HasFreeTopSpot }}
{{ UnclaimedTopSpotFree }} Top Spot{{#if Plural}}s{{/if}} Left{{/if}} {{/if}} {{else}} {{#if HasResults}}
{{Current}} see you now!{{else}} {{/if}} {{/if}}
You can now invite anyone to meet at your favorite Starbucks.
Limited-time feature
30 year old man | Pasadena, CA, USA | Seeking women 21-36 within 30 miles
All things in due time, all things in their own time.
I think self-realization and the quickly following opportunity to actualize yourself in the world is probably the greatest moment in anyone's life. It's a process, right? That ebb and flow and the journey from where socialization begins and then point where you make a stamp in the world. I think I've never loved who I am more than I do now, and while we all have old sorrows and all celebrate old joys, I know who I am against the tide of world. This gives me the opportunity to not only know who I am, but to also now know what it is I am looking for in a partner. I want someone like me, but not exactly like me. Someone who can push the boundaries a little bit when I don't and someone who can tell me that I have a home when we're in each others arms. I want someone I can share true and adventurous passion with and can feel safe with and who can feel safe, in turn, with me. Most of all, I want and need someone who is ready to grow through the next part of life together and is excited about the idea of me being their partner through that process. And I need a sense of humor, because life can really suck without laughter.
Basketball, Football, Swimming, Walking / Hiking, Yoga
I exercise 1-2 times per week.
I have Dogs
I like Birds, Cats, Fish
I have worked in a lot of really awesome locales, so I have a nice list of go-to's and must-do's. I love the Bottle Room in Whittier, the Bruery tasting room in Placentia, Seven Grand downtown, A.O.C. in Culver City, Congregation Ale House, and more
California School of Culinary Arts, Pasadena, CA
Silver Linings Playbook, Love Actually, The Dark Knight Rises, Emarosa, Reign of Kindo, City and Colour, Game of Thrones, Homeland, Thai food, Lebanese food.
On a day off, you're likely to catch me reading a book or getting a beer somewhere. I actually had a tradition of taking myself out to lunch of my days off, usually for sushi because happy hour is the best. Other than that, I'm just out and about.
I'm working on getting through 'A Song of Ice and Fire,' which has been a tremendously good read. I am in totally admiration of the author's ability to thread all those various storylines and such a vast world together.
Z{{Cta}} {{#if HasMoreInfo}} ?{{CtaSecondary}} {{/if}}
|What he is looking for
|5'10" (177cms)
|4'9" (144cms) to 5'9" (175cms)
|Body type:
|About average
|Slender, About average, Curvy, Athletic and toned
|No preference
|No preference
|No preference
|No preference
|Executive / Management
|No preference
|$50,001 to $75,000
|No preference
|Never Married
|No preference
|Have kids:
|No preference
|Wants kids:
|I'll tell you later
|No preference
|Asian, Latino / Hispanic
|Latino / Hispanic, White / Caucasian, Other
I am actually 3/4 Mexican, 1/4 Japanese, for the curious sorts.
|No preference
|English, Spanish
|Bachelors degree
|No preference


text:
Ft. Hood fire chief helped wounded officer
FORT HOOD, Texas — The call came over the radio. "Shots fired." And then, even worse: "Officer down."
Billy Rhoads, chief of the Fort Hood Fire Department, grabbed a radio and donned his flak jacket. He jumped into his SUV and tore down the road. A dozen or so blocks away, at the Soldier Readiness Center, a gunman had opened fire on soldiers.
Copyright © 2013 LexisNexis, a division of Reed Elsevier Inc. All rights reserved.
Terms and Conditions Privacy Policy
Full story: Ft. Hood fire chief helped wounded officer
Recommended Tactical EMS / TEMS
Join the discussion
Ft. Hood fire chief helped wounded officer
PoliceOne top 5
- 1 Video: Actress apologizes after dash cam refutes claim her son was racially profiled
- 2 Video: Knife-wielding man on rampage TASERed by UK cop
- 3 Video: Ariz. cop escapes death as gunman attempts to sneak up behind him
- 4 Rules for Texas police videos depend on who's holding the camera
- 5 The Dirty Dozen: Updating the '10 Deadly Errors' of policing


text:
Food File: the weekly food news round-up
- Food & Drink
- February 13, 2015, 07:00
Rooting for Ballymaloe It's hard to believe Ballymaloe Relish is 25 years-old, and now it has been joined on shop shelves by a sibling, Ballyma(...)
Nolan gets his 'Cork on' as Allen reveals her recipe for success
- Companies
- November 21, 2014, 01:30
The annual invasion of Dublin by the cream of Cork's business establishment took place on Tuesday night, with Cork Chamber's annual dinner at the Doub(...)
Hot reads for cooks
- It's Christmas
- November 20, 2014, 00:00
Nervous cooks Mary Berry Cooks The Perfect ... by Mary Berry (Dorling Kindersley, €30) She may be best known for her cakes and puddings, bu(...)
Cork entries sweeps the boards at food writers' awards
- Food & Drink
- March 12, 2014, 13:40
Cork has dominated this year's Irish Food Writers' Guild Food Awards, with six of the seven awards going to Cork producers, organisations or in(...)
Simon Coveney: 'A McDonald's burger isn't as unhealthy as some people suggest'
- Food & Drink
- November 18, 2013, 01:00
He spends his days talking about food – how to produce it, sell it and regulate it. But who knows what the Minister for Food really thinks about food?(...)
Ireland on a plate
- Irish Times
- November 2, 2013, 01:00
What is Irish cuisine? Have you ever fumbled for words when asked this question by a visitor to Ireland? Should you say bacon and cabbage? Potatoes? I(...)
Television: Belvedere, Ballymaloe and Brian Cowen's hard-neck life
- TV, Radio, Web
- September 7, 2013, 01:00
Many private schools offer scholarships. Most are based on academic or musical excellence, but Belvedere College, the all-boys Jesuit school in Dublin(...)
Inside Track: West Cork haven delivers success for Durrus
- Agribusiness & Food
- June 12, 2013, 01:00
Durrus is one of the original Irish farmhouse cheeses and is handmade in a remote part of the Sheep's Head peninsula in West Cork. What is special abo(...)
Simply Darina
- People
- April 20, 2013, 06:00
D arina Allen is moving at quite a pace. The 62-year-old is nimbly darting up steps, through gates, over walls and across muddy field(...)
Chef and writer who was at the frontier of Irish cuisine for more than four decades
- People
- March 30, 2013, 06:00
Gerry Galvin, who has died aged 70, was best known as one of the most creative chefs of Ireland's culinary development and also was an influent(...)


text:
- Presentation
- Answers_to_Possible_Questions.doc
- (57 KB, Microsoft Word)
Interview question & answer bank - PGCE
I prepared this document last year when I had my interview for primary PGCE at Nottm Trent Uni. It was then checked by a careers advisor after I had finished. I used these ideas to answer questions I was asked at interview, and gained a place on the course. They are in written format rather than bullet-point, because I believe they should be used as a guide ONLY and not used word-for-word so that you sound like a textbook! Hope this helps!
94 Reviews
Fab! Thanks.
Brilliant! Just the help I needed
Thank you :-)
Brilliant thank you. It gives a super introduction prior to interview.
thank you. very informative.


text:
- Gazprom work settlement railway starion
- Problem: to develop a new railway station concept for for the working settlement Gazprom's gas production in the wild far north.
In Russia, a sufficiently large number of gas fields are located in the far north - the area with severe weather conditions. The safest way to get to these places - the railroad. The task of the station - the meeting and distribution arriving workers. At the same time there may be about 1,000 people. There are a spacious lounge and recreation areas for workers wich waiting of departure. Station is located near a helipad, for sending people directly to the work settlement. Also nearly is the hotel where workers can sit in the case of long waiting times of departure.
Now about, the structure. Because in those places there is no soil (but is permafrost) - a common construction is not possible. All buildings are made on stilts at a distance from the ground - this reduces the heat emmision (so that the cost of heating) and prevents melting of ice under the constitution. Railway station shape dictated by the reduction in heat loss, by reducing the surface area of the object, a rectangular shape would have a large surface area. Also, this form is more streamlined and doesn't allow blizzards to cover station. We made a large area of glass (polycarbonate) to reduce the cost of lighting the station during the day and to make more transperent construction.
- Made in SLAVASAAKYAN design studio.


text:
Donegal driven by fear of failure
- Gaelic Football
- September 20, 2014, 06:00
Anthony Thompson is the most fascinating type of ball player of them all: so brilliant at what he does that nobody notices him.It was significant that(...)
Jim McGuinness brought potential to glorious reality
- Gaelic Football
- September 1, 2014, 01:00
The starting point is worth repeating. In the autumn of 2010, Jim McGuinness took charge of a Donegal team who had been beaten to the point of perpetu(...)
Goal rush seals stunning win for Donegal as champions Dublin crash out
- Gaelic Football
- August 31, 2014, 17:49
Donegal 3-14 Dublin 0-17 After a spectacular eruption of near volcanic proportions the All-Ireland champions are gone – Donegal taking out Dubl(...)
Donegal ready to end Armagh's rollercoaster ride
- Gaelic Football
- August 8, 2014, 23:00
The absolute drizzling pity of Armagh's strop with the scribbling nibs of the press room has nothing to do with column inches devoted to them or what(...)
Donegal determined to wrestle back their crown
- Gaelic Football
- July 18, 2014, 23:00
They might be giants. In what seems like the blink of an eye, Malachy O'Rourke has transformed a Monaghan team with a great future behind it into a s(...)
McGuinnes bringing Donegal back in through the out door
- Gaelic Games
- May 27, 2014, 12:00
Everything we'll watch between now and the first week of August in the football championship will be processed through the prism of Dublin - they're t(...)
Karl Lacey's spirit of adventure helps drive Donegal forward
- Gaelic Football
- May 27, 2014, 01:00
A small group of youngsters stood around Karl Lacey at Celtic Park in the minutes after Sunday's absorbing Ulster quarter-final against Derry. It w(...)
Donegal rearguard proves the difference
- Gaelic Football
- May 26, 2014, 01:00
Donegal 1-11 Derry 0-11 They haven't gone away, you know. Donegal shook off the final vestiges of last summer's weariness and muted a loudening(...)
Donegal's scoring burst sees off Derry at Celtic Park
- Gaelic Football
- May 25, 2014, 17:01
Donegal 1-11 Derry 0-11: Donegal reaffirmed their Ulster credentials with a powerful second-half display at Celtic Park against Derry which was, in pl(...)
Donegal's accuracy and discipline enough to see them to a third Ulster title in a row
- Sport
- July 20, 2013, 01:00
It was a Benny Coulter goal deep into injury-time on May 30th, 2010, that last beat Donegal in the Ulster Championship. Or if you want to get really t(...)