Video 5-7: Cell-Probe Lower Bounds 2

0:02 So, I will show a lower bound on this dynamic rank parity problem. And to do that, we started with yet another problem, namely the which side problem, which now is really a questionable data structure. You have a a set operation that sets a certain value, and you only store this value, and I can have ask queries where um I can find out whether the number is smaller or larger that I'm storing. Now, clearly uh with log U search uh ask queries, I can answer um I can nail down what value I have stored. Right? And I can also solve this problem um by storing uh Y explicitly, and then log U bit probes, that's the length of the number, so I can set with that many bits, I can store Y explicitly, and I can read Y explicitly, and then I can do whatever. For example, I can compare it. So, um this is this is a trivial upper bound how you could realize this data structure problem on this uh um bit probe model.

1:11 That's not very interesting. I mean, for two reasons. First of all, the data structure is not interesting, it doesn't do anything special, and also the uh for three reasons, I guess. Um the data structure is not very interesting, the model is not very interesting because we're not charged for anything but storing touching these bits, and the problem itself is also not interesting. A an upper bound for this problem is really not what we came for. What we're after is a lower bound. And for that uh we started last time, but I wanted to go over this this lemma briefly, it's to do with the proper computation. And I want to zoom out at at this point a bit again. Um if you think what we were what we're trying to show is that we need this at least log U of a log log U bit probes per operation in the worst case. So, we need that many bits for each operation, say.

2:05 To both implement set and ask. That's reasonably close to this upper bound we have. Also, notes um if I have a running time T that I don't know yet, some upper bound for the number of bits that both the update and the query are allowed to look at or change. Then, clearly if I call um one time this this set operation, it only changes T bits. And so, uh if I start with the all zero vector, there's not so many different states the memory could be in. Because I'm only changing up to T bits. Which T bits I change may depend on the input, and what I change them to may depend on the input. So, it's not entirely clear what the data looks like. And also with these ask queries, I can also just look at T bits, but which ones I might make uh an an adaptive choice depending on what the bits I previously read gave me as a result, and what this parameter is.

3:09 So, in a way it feels like um the data structure just from not touching that many bits can only be in a very small number of different states. But, it's a bit hard to get our handle on uh what we can conclude from that. And there's a cute trick, that's the whole point why I'm um doing this lemma with this this proof with you, but allows you to get um a proper statement from from these vague observations.

3:36 Okay. Uh the part we were looking at is this lemma, the which side any which side algorithm any algorithm for this problem needs omega log U over log log U bit probes in the worst case per operation. We'll prove this specifically for the set of uh operations where we have one set call and then only ask queries afterwards. And we say the solution space is S bits, so the algorithm uses S bits in total and T bit probes per operation. Then let's call the state of the memory if we um update uh if we set I if the parameter to the set operation is I and then let X I be the state of the memory which is some bit vector in 0 1 to the S. But note, it's not an arbitrary bit vector. It has to be Hamming weight has to have Hamming weight at most T. Because we start with all zeros initially in the machine by definition and then the update operation can only spend T bit probes.

4:41 So it can only flip at most T bits, maybe less, but certainly not more. Okay. Moreover, we can use log U ask calls to find out what the original number here was which means all these X I are distinguishable with log U ask calls. So in a way there's not a lot that each of these has to be different. Right? If two states X I X J were the same then clearly the algorithm could be fooled to answer the wrong thing. I can ask uh the same set of queries but with a different I I should get a different answer at some point. So they need to be all different. However, um they're just these arbitrary bit vectors and the ask queries may touch different bits. So how do we make progress from that?

5:44 And uh what what we can say for sure is that the queries are essentially following some uh binary decision diagram binary decision tree in the following sense. There will be some first cell of memory that they are reading. This cell of memory that they read may depend on their parameter. It's ask why, right? Compare the stored number with some number. It may depend on this parameter and it may depend on I guess only that for the first bit probe. So, it touches some first bit. The outcome of that bit probe will either be zero or one. And then after that it might touch a few more bits. But the bits that it touches um must be such that when I do these log U's calls in total, I can distinguish all these X's. Now, each of these uh queries has only time T to touch bits. So, it can only touch T bits in a row.

6:45 Um we can always represent this as some sort of um for each for each query there's some decision diagram where each of these nodes means read some state of the memory.

7:05 Say an address K. And then we have two outcomes depending on whether the bit read there was zero or one. And then of course at the next point, this could be K prime, this could be read K double prime. They don't need to be the same. They can depend on uh what the outcome of the previous was. But the height of these needs to be at most T because that's the running time the bit probes.

7:32 So, that's the setup of this lemma. It says if I have U different bit vectors all of length S and all of bounded Hamming weight at most T ones and I know that there's a binary decision tree of depth T that can distinguish all of them somehow. And the cleverness here is we don't need to know what these trees do as long as there is some way um for binary decision trees of depth D to distinguish them, we get an a bound on in this case the number of different bit vectors, and we can uh calculate around to get a bound in terms of the other parameters.

8:17 So, uh how do we get to this lemma? First of all, um it may read various different parts of the memory, but certainly um every X I That's what we mean by distinguishing. And so, uh and the the thing you have to keep in mind here is the decision tree will be formed by all the ask queries combined. It's not a single ask query. It's um the combination of these log U ask queries combined.

9:22 At the end of this decision tree, I will have figured out which number was written in my set query in my set update. So, the each leads to each lead to a different leaf in this large um This is for a single query. And maybe I should uh move that out of the way because it's not going to be exactly the tree we apply this lemma on.

9:54 For a single query, the tree may depend on the parameter Y. But the tree we get from all the queries together doesn't depend on those because we set the queries. Okay. Haha. Because they correspond to different leaves in this decision tree, no matter which bits were actually read from my memory, I can re-encode each leaf with the bit string I read along the uh decision tree. So, again, my decision tree here, um height D here, at some point here, I will have leaves for my different X's.

10:35 And I'm just going to re-encode or associate each of these leaves with a path from the root down to this leaf. That's a bit sequence of length at most D.

11:12 Now, this bit sequence has to be different for each of the X's. Otherwise, they wouldn't be distinguished by the decision tree. And the bit sequences are of length D, plus they have Hamming weight at most T. Because that was the assumption here. And these uh these decision trees can only query bits from the strings that we look at, that we want to distinguish.

11:53 Um, let's maybe give these names so that it's uh So, in other words, each YI is a subsequence of XI or not even subsequence, it's formed from checking some bits of XI in some order, but I don't know in which order and I don't know which bits. May be different for each, but it's it's a subset of the bits of XI. So, it can't have more ones. Well, that just means um that I can upper bound the number of different Ys I have. And that's precisely this bound, that's what's stated here. It's the number of bit strings of a certain length, namely D, that have at most T ones. And I get this by summing up, well, how many options do I have to put uh no one. Well, just one, everything zero. How many options do I have to put a single one? Well, D, right? I can put at each of the D positions I could put the one. How many options do I have if I allow two ones precisely? Well, D choose two. I pick a subset of two positions.

13:17 And so on, I sum these up up to T. That's all the bit strings that have Hamming weight at most T. Okay, we apply the lemma here. I mean, this is this is the end of the proof. The formula is uh is precisely this number of bit strings, and we've associated each of these xi that are found in this decision tree with uh a shorter bit string formed from some of its own bits. That's all that's happening here. The cleverness lies in reducing the memory size. Previously, these xi were formed of the entire memory of the data structure, and we don't know how big that is. It could be very long. But it turns out because the data structure is so constrained in how many bits it can look at, the whole memory doesn't even use the doesn't help you. Uh you can't really look at it, so you might as well not have it.

14:30 So, for us, the xi are the memory contents of the data structure. So, the depth of this decision tree, the number of bits I can touch, is going to be log U * T at most. After at least after at most that many bit probes, I have identified which of the xi I have. They need to be different. So, I'm in the setup of the lemma with this D. And so, the rest is just a computation.

15:30 From the lemma we get that U is upper bounded by the sum I from zero up to um The T here is the number of one bits. So that's our T. There's two There's two notions of what T means, right? If you notice. The T here is how many bits can the update operation set to one. And uh we treat one uniform bound on the number of bits that the update touches and the number of bits that the query reads. We'd say it's just one bound to keep it simple. This T is how many bits I can have written. And this T is how many bits I can have read during the queries. Okay. Uh so here we get the D which is log U times T choose I.

16:21 Now this formula in principle relates U and T. What we'd really like is a lower bound in terms of T and not this nonsense. Uh it turns out you can from this it follows that T is omega log U over log log U. All that's needed is creative rewriting of this term. But to convince you, let me show you this trick. And it really needs a little little trick, that's all. Um So what is behind this this arrow is a clever upper bound for the kind of sums that we have here. Uh this is a more general thing I think um is is useful to know. So essentially what we're summing up here is binomial coefficients where we change the lower index. And uh if we sum this up to N, that would be just the number of all subsets of of n elements, two to the n. But we stop summing at at some threshold k. So in a way, this is precisely the number of sets of n element subsets of n elements of at most k elements.

17:32 Okay? Number of subsets of set of the first n integers of size less or equal k. That's literally what it is. And you can show this is always upper bounded by e times n divided k to the k.

18:00 I'll show you in a sec where this comes from. Appears just out of thin air as the previous one. Um but if you plug that in here, then what we get is that this this guy is upper bounded by e times t log u divided t to the power of t. Okay? Uh then I'm I'm taking logs on both sides and rearrange. And then I get this. So here I have um log u less or equal t times log of this guy.

19:31 Now, of course, the log t cancels. That's what I was missing. So, it's actually a much easier term now. And now you divide all by this. And you got the log u divided um Somehow this log u was already inside here a log. So, this is a double log.

20:02 And you have this plus log e, but uh for lower bound in terms of omega, this is fine. Now, how do you get this lovely upper bound?

20:19 That was following from this part. For this one, um we do a bit of creative rewriting from the binomial theorem. Which is, for example, you can say 1 + x to the power n is the sum from i from 0 up to n n choose i. And then 1 to the power i x to the say x to the power i 1 to the power n minus i, which of course is just it's just 1.

21:01 Now, this is clearly um upper bounded by the sum where I stop at k instead of going all the way up to n. And then if I make my X less or equal 1, X is a parameter I can choose. This formula is true for kind of all X's particular uh small X where this um uh is well-defined. Um I can make I can choose my X to be less than 1. That means a higher power is even smaller. So, I can replace the power I here by power K.

21:43 Which means I can pull it out of the sum. And then we have our sum on the left-hand side re- uh established here. But, we have this annoying factor in these things on the other side. Uh and we can set X to a convenient value. And it turns out a convenient value is K divided n.

22:15 And magically, if you do that, we get our sum less or equal this 1 + K over n to the power n divided uh or times the inverse uh K over n to the minus K.

22:46 And uh now we're using this standard upper bounds. This one converges to e to the um to the K. That's exactly the this limit of of the e function. It's always uh smaller than e to the K. That's for this first part. Um and for the second part, which is uh leave it and rewrite it to this.

23:14 And that's the bound that we claimed. Okay. So, this is um a general little trick. I mean, this has nothing to do with advanced data structures. I just found it clever enough, and I struggled with this at some point, so I thought it's it's useful if you don't need to struggle. And now I've seen it once. But, the the gist of the problem was you to apply this lemma with a decision tree argument, and then you get this lower bound with a little bit of uh arithmetic.

23:46 Um So, we've now found that we can solve uh we cannot solve this which side problem with less than log U of log log U bit probes. Um I think we have yet to con- connect how this which side problem has anything to do with our prefix parity problem.

24:07 Um we just said consider this other problem and then blah blah blah blah blah. Okay, so that's the end of of that proof. Um but let's briefly connect these two problems again. How can I use this which side prob- How can I solve the which side problem using a prefix rank?

25:07 >> Well, when someone says you should set I, you set your Ith position in your bit vector to one. And if someone later asks, is the value you stored less or equal to J?

25:28 We output Well, we have to do something with the prefix query. But luckily, we can just take the the XOR sum of all these first I entries.

25:43 The invariant is there's only going to be a single one in our bit vector. So, this whole notion of parity, this is all a bit of a uh kind of a a red herring here. It does exactly nothing. This is one exactly if the position Oh, sorry. This is a J.

26:03 I'm I'm summing up the first J positions. The modulo doesn't do anything if there's a single one in total. Uh and so, either this is zero if I is further to the right, or it's one if I is at most J. And so, I can maybe I need to invert this and say one minus, but that's all. I I can simulate the which side problem using my dynamic prefix parity problem. So, if this is hard to solve with a certain runtime, this also needs to be hard to solve with that runtime because I can use this problem to simulate the other. Oof. Okay. Um let me say very briefly where now we have um say a logarithmic word size.

27:12 And it turns out this is um the approach that we tried doesn't give any meaningful bounds in this case. There's there's too much power to the algorithm in a way. It can set a lot of bits. I think the the result we get from just this bound is is no longer interesting. Um here uh it uses um a trick that I'm only going to hand wave. Um it's called the chronogram method.

27:50 And what it's what it's basically trying to do um is look backward in time. Uh say here is a query up to some point. And uh in the analysis we look back in time in epochs that are essentially exponentially increasing.

28:16 Okay, I can't can't draw many exponentially increasing epochs without running out of space. Um where these are roughly uh the lengths of these are some curious number. What pops out is um this is log U to the third power then the next epoch starting from the same from now and goes back to log to the sixth power. And the next one is then log to the ninth.

28:53 Um if you do it like that, the the number of these epochs is well, such that the log to the three R of U um we set it to be roughly square root U. Yeah, say that is K. And so, um R from that is something like log U divided six times log log U.

29:37 So, this this looks familiar. That's like the lower bound we try to prove. Now, in this model we can read a full word of bits from uh each of these cell probes. Um What are the operations? Uh There's a specific way how you you sprinkle the Let's Let's maybe um I don't think this adds much to it. Basically, the the proof tries to come up with an operation sequence so that the prefix here um depends somehow on many updates. And for each epoch, it has to um read one cell from that that was written in that epoch. So, um because they're exponentially increasing, uh there's not enough time to write enough information about this epoch in the next epoch after it. Okay, that's uh uh If you can show that, then clearly with that lower bounds, you show that that many cell probes are necessary. And intuitively, lots of hand-waving, um how you can show this because the epochs are so much increasing there's so much going on in this epoch that cannot be captured in the few words that you could have written after that.

31:27 So, there will be some some write operations from that previous epoch left with crucial information from the updates in that epoch that still affect your prefix query that you cannot not read one of those words. But, uh a lot more calculation and combinatorial arguments are needed to make that rigorous. So, let's close the case here, and um it's not not anywhere close to a proof. Uh just wanted to give you a a rough flavor. Uh for the first version with the single bits, I think the proof is is is clean enough uh to follow through. Uh for this one, um I think I can't present it in good time to a level that's that is uh understandable. So, let's leave it like that. Uh and let me maybe zoom out again. Long uh proofs. Remember, rank and select in a dynamic set almost as bad as binary search trees, okay? You should This is I think um a good thing to keep in mind, and we'll come back to that.

32:32 Now, remember we've actually beaten this low this these runtimes with our Wi-Fast tries. There there we were able to get log log U running times. But clearly not for rank and select. That would contradict this. Rather we got it only for successor predecessor search insert delete. These all worked, but not rank and select. It's really specifically these two. Now you can also not do successor and predecessor arbitrarily well. And for this bound I'm not even going to try to prove anything because it's even more messy. And even the statement already is rather messy. Let me still um tease apart the statement a bit. And then we'll we'll confine ourselves with believing in the proof for this lecture. Here the lower bound is about a more restricted problem and it's it's stronger in two ways. Um it only looks at predecessor queries or floor queries as we called them previously. And it looks at a static set of numbers.

33:41 So there's not even any updates. But then uh it has to to make sense. In such a case you have to bound the space. So um if you have a static data set and you only want to bound this what queries take, you could precompute all queries. If you have infinite space, then that becomes boring. If you bound the space, not so boring. So here the setup is a static set and integers from a range of U, same as before. Um um here the number of bits is separate from the word size. So uh word size is W. Usually we we think of W and L being the same. The official statement even keeps those separate.

34:29 And the data structure is using n times L uh bits of space. Um that's just a lower bound. So, that is clearly I I just need to know the numbers. But, there's an an upper bound where the the space goes into the statement of the bound via this A, which is something like the the average space that you need per number. Right? This takes the total space of the data structure, divides it by the n integers that we have, and then takes the log of that. I mean, without the log, this is the number of bits per number.

35:05 And then, it turns out that the log of that enters these bounds. Um in that setup, predecessor queries need to have a certain running time. It's the minimum of these lovely four formulas. Uh let's try to analyze a bit what these mean. It turns out the last two terms, nobody has a really good intuition for, as far as I know. And they're also a bit of a uh theoretical corner case. An interesting range is this or this range. Let's look at the green one first, because that matches for the certain parameters that we should plug in, our Wi-Fast tries. Namely, A in our case, how much space did the Wi-Fast tries use? We said space n, but that was in words of space. So, in bits, it's n times w. So, here you should think of um I haven't I have put this here. So, in words of space, we should think of uh when we have n words of space, then that means S is n times 2 to the A, because that's the log.

36:23 And that also, if you solve for A, A is then log log n. Okay, if you plug that in here and assume that L is W and uh by and large this is log W divided log log n. Uh so you get uh this even kind of goes away, right? Um Yeah, W is that's right. Uh A is log W and W is log n or log U. And doesn't make a big difference here. So we get Wi fast tries with the log log um n from this upper part. Um because L is roughly log U. Um whether n or log U is dominates the depends on the choice of the parameters.

37:57 But this is essentially our uh log log U log log n time for the Wi fast tries. And this dominates the this this is the minimum of these other terms when W is fairly large.

38:14 Uh which you um again assuming L is W then then this term uh gives you the minimum because the overall term this double logarithmic is fairly low unless you have an extremely large W then this might be better. And these are somewhere in between. So for word sizes in the usual range that we think of, namely at most some power of logarithm of n, the true bound is what Wi-Fi's tries to achieve. So they are optimal in the in a whole sensible range of parameters. There's a different kind of data structure that can match this one. And they are interesting if somehow the word size is much much larger or conversely if um your n and l are much much smaller with respect to the word size.

39:07 Uh I decided not to really do much on this. Um in a way you should think of fusion trees as binary search trees or B-trees with a fan out of log n. More precisely log power of say a fourth root of W. I know this all sounds very ominous. So somehow you can branch out with W and do that in constant time.

40:11 Uh the trick to do that has to do with um So these are, you know, like in B-trees, there's um there's keys sitting separating these. It looks like a funny alien. Uh this is a a node a fat node that stores a whole bunch of uh keys. Then there's all there's a subtree with everything that's less than these then more subtrees.

40:35 And it looks even more like an alien. Okay. My drawing skills are deteriorating. Uh either way if you can branch out with this fourth root of W in each step you're going to have a tree that is of height log W to the fourth root of N.

41:04 And within this is you know this is log N divided log fourth root of W so the fourth root is within constant factors not not important.

41:26 So you essentially match this this red term. And what I'm completely skipping is how to do this magic step. Because this is not at all clear. There's way too many bits to even do it in one word. Uh the trick is that to decide which child branch you have to take you don't have to look at all the bits because these these bits these these keys will have to differ in a small number of bits. And you can check only those and then check once uh against the tree. So I'm this of course of course uh you don't need to know more than what I explained um at some point I had to cut things. Uh just to mention there is a data structure using trees that is like binary search trees except that you can you can bump up the fan out. It only works for integers. I still integer land. Um but you can do rank and select. You can do the full uh set of uh ordered um dictionary queries.

42:34 Okay, let's come to a close with this uh with this part. We've seen integer dictionaries upper bounds, namely uh hashing schemes that essentially fulfill all the dreams one might have in this in this area. Uh we've seen for sorted dictionaries essentially just standard binary search trees that use comparisons are almost optimal. And if you want fusion trees get you a little closer, but they're uh mostly theoretical data structure. If you can somehow come by with only um priority queue operations or only predecessor queries, then Wi-Fi tries are uh an an interesting alternative that doesn't exist outside the integer data structure world. There's no comparison-based uh on equivalent of that. Uh it seems to require randomization. I think this is uh from all we've seen for sure um we because we use hashing in between. Um seems hard to avoid in the dynamic case. And we've also seen a few more powerful lower bounds than what we've previously had.

43:36 Uh where unfortunately the results are the proofs are more complicated. Um The statements can also be complicated because of the many parameters. Uh but we've largely matching upper and lower bounds even in this area for um for dynamic rank where we need to use the fusion trees or for predecessors we've seen seen solutions as well. Um yeah, keep in mind that this this predecessor bound even applies to the static case that will be relevant for the upcoming chapters as well.

44:12 Um the other lower bound, the dynamic rank and select, is particularly powerful because it doesn't constrain the space at all, irrespective of how much space you use. Um and it's a much much higher bound, but it requires these two powerful queries uh to be true.