Video 5-7: Cell-Probe Lower Bounds

0:01 In the last section, let's look a bit at lower bounds. Um we've already mentioned one, namely that you cannot hope to do dynamic sets with rank and select, actually one of them is enough uh in in much better time than for binary search trees.

0:20 And I want to give you uh first the formal statements and uh a hint at how these things might be proved. It turns out the proofs uh for the for the uh kind of state-of-the-arts theorems are very technical and seems uh it would need a lot of a lot of extra time to go through this, so we won't. Um but I'll give you a kind of a toy version of one of the bounds. And I want to state the full things though, because I think this is very useful to keep keep in mind that some things are just not possible. Very powerful in not designing data structures with that goal. These kind of lower bounds need a different model of computation. The standard lower bounds that we've also previously in this module could could use were were easier because we were looking at comparison-based algorithms. And there you could just use information theory arguments to say I need a certain number of comparisons.

1:14 Otherwise, I don't learn enough about my uh input. Uh here for integers, it seems we have too much freedom in our algorithms to do anything like this. So, instead um people came up with um in a way a much much more powerful model of computation, powerful in the sense that almost all computation is for free and cheap. And that's the the cell probe model. Um this is the most powerful lower bounds that you get from this because the model doesn't charge you for much. Uh it's assuming like in a word RAM that you have memory that is chunked up into words of size W. And you can do uh essentially whatever whatever you want. Um you only pay for touching memory. And you do this in units of whole words, which you can read or write. And you count the number of such cell probes. So, a cell would be a word, right? And a probe is you look at that cell, but reading and writing is kind of treated the same way.

2:25 Which means all computation is really free. What a stupid model, right? This is completely unrealistic, but remember for lower bounds, this is a good thing. The more unrealistic the model is in that it gives you uh much much more power than you you think you should have, it means that it lower bounds you derive there are also valid for any other models that are more realistic. In particular, any word RAM algorithm clearly needs as much time in terms of steps of operations than it needs to probe cells, because that is one special type of operation. Uh that's that's all there is to it. Now, this model is is easy to define, but it's much more beastly to prove anything in it, because what do you have at hand? What is a a cell probe algorithm? All you really have is that it somehow touches memory. That's not very restrictive. Uh let me sketch only at a very high level one opera- one type of argument you can make that shows that certain cell probe algorithms are impossible.

3:44 And one one such uh strategy is to use something called communication complexity. >> And there you have two players, Alice and Bob. And they jointly try to solve some computational task. The trouble is that they only have part of the input each. So, Alice has some part of the input, Bob has some other part of the input. And they can send messages across, maybe several times. Uh you can look at various various special cases of that. And at the end, one of them needs to compute some function f of x and y and output that.

4:35 That's the general setup. And then you can try to bound the minimal number of bits that need to be transmitted. That's why it's called communication complexity. How much information do you need to communicate to solve a certain problem? And in this world of data structures, the way you use this is that Bob is the memory, the memory controller. And Alice is the actual algorithm, or the CPU if you like. And so, whenever Alice wants to answer some query, so here Alice gets all the input and Bob gets the pre-processing result, the data structure.

5:21 Now, of course, answering a query on a data structure is exactly of such a form. It's a computation that depends on two things, the data you stored and the query parameters. And so, the goal is to compute data structure dot query x. Let me just sketch it like this. And so, then Alice sends to Bob a memory address.

5:48 And Bob replies the contents of that address. So, if you can bound the amount of information that needs to flow back and forth, and by the way, these is each W bits, right? Uh that's W bits, that's W bits. So, if you only um you've reduced the problem to this communication question. How many rounds do you need of sending W bits back and forth? Then you've proved the lower bound. On a high level of abstraction, that's uh fine. It turns out this is not gen- not in general easy. Uh but it's um one strategy that that um these lower bounds come from. Um but I didn't want to make the course into an introduction to complex communication complexity.

6:46 The first this is two main lower bounds that I want to present uh that I think you should roughly know about because they're classic results and they're powerful in what they what they imply. The first one is the one that I informally sketched earlier. Uh it's due to Fredman and Fredman and Saks. And it's about dynamic rank. So, it says if I want to maintain a dynamic set of integers again from some universe U um here I'm not really talking about word size but uh for for the computation time but rather um for the size of the cells that uh you probe. So, if you want to maintain a dynamic set of n integers um with a word size that can even be a bit larger than the universe size.

7:40 And you want to do either insert, delete, and rank or insert, delete, and select. In both cases, you need amortized log U over log log U cell probes to answer these these questions per operation.

7:55 So, let me comment on on two things. First of all, you get this if either you just want rank or either you just want select. For both of these, this impossibility result already applies.

8:07 Second, um N is never going to be larger than U, the universe. So, if you have a lower bound in terms of U, you have the same bound in terms of N because N is only smaller. So, this is this is the higher lower bound. But, it's a bit more intuitive to think about the number of integers instead of the universe.

8:28 That's the one bound. That's the one we used before to argue there's not that much hope in improving uh binary search trees uh even if the keys are integers. Just this log log N factor is there to potentially exploit.

8:47 And um the general proof of this statement is um is too much to really go into. So, instead, let me prove a special case of that. Um it's essentially the same statement except that I'm looking at word size one. So, I can only probe individual bits. It turns out that makes life a bit easier. It also means the statement is much less powerful. Because uh probing individual bits, of course, gives me much less information than probing log N bits at a time. Whereas, the bound for the number of probes is the same. Okay, so it's the same bound as as for the other theorem. Uh same log U over log log U. But, here each cell probe is a single bit. Previously, it was W bits. Um I'm also just looking at worst case operation, not amortized as we have the full statement. And uh let's forget about select. Let's focus on rank. Okay? So, that's the three three senses in which this is weaker.

9:53 It's worst case, it's for tiny words, and only rank. So, let's try to prove this. And as often with lower bounds, is in a way a sequence of reductions. So, we'll prove a lower bound for an entirely different problem, and then show that this reduces uh to the um problem that we have here. So, if we had any algorithm for solving dynamic rank, then that would imply solving this other problem, for which we have the impossibility result. The first problem Uh the first problem is is called uh dynamic prefix parity.

11:03 So, uh you can think of this as being the same problem, but when I ask for rank, we really only get um kind of uh a modulo-2 answer, and all my elements are are bits. So, uh I guess more formally, um we maintain a bit vector of the um entire universe.

11:48 Which just sets a certain position to a new value. And I can do um a rank query in the sense uh I can ask for the parity of the prefix sum. Oh, the car. There we are.

12:13 So, I get the uh for I And the output is you take the first I things and you XOR them all together. In other words, um sum from I I went from zero up to including I uh These details don't matter.

13:04 Let's first see why this is um is easier than the original problem. So, to reduce to the original dynamic rank we uh assume we have a dynamic rank data structure and we try to solve this dynamic prefix parity problem with it. And for that, you just maintain the set of positions where the bit is one.

13:56 And so, if you think about it, if you now ask a rank query in this set, it tells you how many ones are to the left of the position you ask about. That's the same as this sum. So, rank and prefix sum are essentially uh equivalent in this sense. And of course, you can compute modulo two, fine, right?

14:38 Okay? So, instead of uh storing a set of integers and answering rank queries, I can think for my lower bound of maintaining a bit vector, a huge bit vector, right? The entire universe. I'm not I'm not going to want to really touch this. But, again, remember cell probe lower bound. We don't care at this point, we don't care at all how big the data structure is. It doesn't matter. Uh for dynamic data structures, the point is fine, use as much space as you want, but upon the updates, you can only touch a few locations, otherwise you're slow. So, you have this huge memory that you never have time to look at. Go have fun with it, right? It's not going to help. And same for the queries, uh you're also only going to touch few queries if you have small cell probe bound. So, space is kind of not useful. Uh so, it's fine to have this gigantic bit vector essentially lying around untouched.

15:35 Uh so, we can focus on this problem. Now, uh we'll show that for this problem dynamic prefix parity needs this omega log U divided log log U bit probes for operations in the worst case.

16:17 And uh to do that, we consider yet another problem. The chain of reductions, uh but I promise you this is the last one. And this one's even weirder. It's called the which side problem.

16:48 I mean, this this prefix pi parity problem is at least a proper data structure, even though it's questionable whether the parity of the rank really helps you much. I think this is uh I don't know, whatever. A bit un-intuitive the name. Whereas this which side problem is really an uh not even a proper data structure. What you maintain is a single value X in the universe.

17:20 And you have two updates two operations. You have an a set operation which just overrides the value X by the new value. So, nothing else is kept about the history. And you have an ask query that tells you uh whether Y is less than X.

17:46 So, in a way this is a comparison and you can try to use the you can you can view this as a way of doing binary search over the universe. You can use set to set a certain value and then you can use several ask queries. The point here is I'm not interested in the overall time. I'm interested um per operation how many memory cells do I touch. So, because the problem is a bit weird.

18:19 Let's first think about an an obvious upper bound uh how you could solve this problem. Namely, if you allow me log U bit probes I'm just going to upon set I'm just going to store Y somewhere as the binary representation.

19:03 And upon ask, I'm going to read Y and compare the two numbers. Uh very boring and kind of trivial. So, I can solve this with log U bit probes by storing the number. Now, it sounds very unlikely that you can do better. Right? Somehow. Because how are you going to answer these ask queries if you don't even have time to read Y? But, it turns out the lower bound we can prove is again this log U over log log U.

20:14 Uh again, worst case per operation. Uh I might need 5 minutes to finish this, I think. Uh maybe we can we can skip the calculation trick um then that's uh a bit faster.

20:43 And we're only even in the proof, we get to choose we're proving a lower bound, so I get to choose what operation sequence I'm looking at. I can pick one that makes the data structure pay much, and that's fine. One example is good enough. So, we have um a sequence of operations has one set.

21:08 I'm going to call set I first and then followed only by ask queries. And the claim is for this, worst case per operation is this log U or log of U.

21:34 So, suppose we have a a solution and algorithm that uses S bits of space. Again, we're not trying to bound S, but there will be some space usage that it it has. And an operation time T. Some number of of bit probes that it does in the worst case over its operations. Again, worst case per operation.

22:06 That means after this single call to set, there's going to be some state of the memory depending on the parameter I that I I passed here. I have some state of the memory of this data structure. No matter what it does or what it looks like, this will be some set uh of bits.

22:34 And because it uses space S, it's going to be essentially a bit vector of uh dimension S. But, we know more. We know that the Hamming weight, fancy way of saying the number of ones, and I guess what's behind this is an assumption for the cell probe model that initially the memory is always zero. It's not a harsh restriction, but it's a standard assumption.

23:05 So, in other words, I can write for the Hamming weight like the the one norm of this vector happens to be the same for a binary vector. Uh that's at most T because this single set operation only has time T to mess with the memory. So, it can it can change T bits. It might change them back to zero if it's stupid, or it might put them to one. Clearly, it cannot touch more than T memory cells.

23:46 the the result will essentially follow from counting how many different ways this this memory can look like and contrasting that with the number of possibilities for I. Now, the problem is um intuitively, it should be so that every I leads to a different state in memory. But, we can't formally claim that because uh we have to live with some sort of sequence of asks. So, we have to pick a specific sequence of asks that makes it clear that all values of I need to lead to a different state of memory.

24:22 But, here um we can use log U calls to I. And so, if I can find out I using ask queries every value for I needs to have a different uh memory content. Right? So, if I is not equals J, X I is not equals X J.

24:57 Clear? Do we need to do something different. from that we can essentially derive that the T needs to have a certain minimal size. And to get there, we need a little combinatorial lemma.

25:26 Um So, the statement is precisely our situation. We have bit vectors X1 up to Xu. That's the different possible values for I. All of these are bit vectors of size of length S. But also with Hamming weights at most T. Okay? Now, we don't really know what these ask calls do. All we know is that they touch a certain number of bits.

26:18 What we do is that uh in some way, the only option is a binary decision tree. Lemma simply says there's these bit vectors and there's some binary decision tree of depth D that distinguishes all of these these strings. Uh then we can prove that the universe U is at most this cute sum I from zero to T D choose I.

27:11 And intuitively this is uh where the Hamming weight is at most uh T. Okay. Uh, maybe we'll do the proof next time. Uh, there's not that much left, but I I think uh already been overtime.