Next week at this time, you will be having our exam. The midterm will be starting at 9. Again, this board marketing. Well, imagine I'm riding on the board. It's 09009. 9 a.m. sharp. We'll start the midterm exam in this room. Okay, thank you. So it will be one hour and a half. Exams of 90 minutes will be more than necessary for those who have studied it, for those who are familiar with the subjects. So if you haven't studied it already, at least some of the most recent issues, I mean, like the national thread perceptions in the Middle East, I strongly recommend you to go over this book. I mean, this is already available in the reserve section of the library. So it is essential that you make your readings before examination, the midterm exam. Let me ask you a question. Which issue or what are the issues that attract your attention the most with respect to the Middle East security topics? Well, I mean anything. While you were taking this course, what did you have in mind in terms of learning about Middle East security? What was it that attracted you to this course in terms of Middle East security? Because Middle East and security always go together. I mean, these are two names that go very well. Like Michel Mabel, Son Limo Kivon, Très bien ensemble. Yes, Pishra. Yeah, Israeli-Palestinian problem, we have covered a lot of issues here in the class. And this is at the cracks of, I mean, at the very core of the overall problematic that we have in front of us. The Middle East is very much characterized. As you will remember, we have noted certain things on the board about the characteristics of the Middle East. And one major, one particular issue was the Palestinian problem. What else? Yeah, the peace process. Actually, the peace process is something relatively new when compared to the Middle East history. Because the roots of the conflict, actually you can go as far back as you like in terms of centuries, even millennia. But the peace process is something that has started right after the Iraq war, the first war in 1991, which was started officially in front of the public's eye in Madrid. That was called the Madrid peace process. But there was also another process which was going behind the doors. And in Oslo, that was also called the Oslo peace process, which paved the way to the peace process, actually the peace between Jordan and Israel. And Jordan became the second country in the Middle East which recognized the state of Israel, which was in 1994, October 1994, September 1994. So, and of course, the invasion of Iraq is something even more new, which took place in 2003. And this is something that we also touched upon a lot. And something that we will cover when we will talk about, I mean, Turkey's relations with some of the Middle East countries, because Turkey cannot be dissociated from the Middle East entirely. We are not anymore in the Cold War period, during which Turkey was more or less, I mean, part of the West, and of course part of the West with respect to its defense issues and political issues. But also, due to some reasons that we try to talk about a little bit, not so much, Turkey had turned its attention to the West or to the north-eastern border which was the Soviet border. Now, of course, Turkey is much more involved in Middle Eastern politics and maybe, according to some people, more than necessary. Well, we'll talk about it, whether it is more than necessary or whether it is less than necessary. So, we'll talk about this in the coming weeks, probably after the by-ramp. So, what else? Yes? Iranian Revolution. Iranian Revolution and its nuclear program, actually, nuclear program precedes the revolution, which also something that was started during the Shah period. And still has a lot of implications for the region, which definitely should be covered. What else? Because I'm trying to figure out, I mean, which topic we should go ahead with. This is important in the sense that we not only understand what has happened in the past, but also what is happening today and what is likely to happen in the future. And this is important. And, of course, I would like to figure out as to which subject would be more attractive for you, because, I mean, many things are happening around the world, and more specifically in the Middle East. And I believe at least some of you follow from the news and try to understand what is behind all this development, such as the missile defense of Turkey's reservation not to name any country when it comes to a NATO project, where the Turkey should lift its reservation with respect to naming specific doors, citing specifically Iran as a threat or not. And people are confused as to why Turkey is behaving that way and things like that. So all of these issues are somewhat interlinked. Ibrahim? Yeah, I mean, because there is a perceived rapprochement at least over the last several years between Turkey and Iran. Well, Turkey and Iran have been more or less good neighbors, not so much of confrontational relations over the last several centuries. At least the way we perceive it, because when you talk with experts on Iran and they say, well, there is this rhetoric of no conflict with Iran since the Qasseh Shireen Treaty 1639 and between the Safavids, Iran and Ottoman Turks. But this is not true. There have been so many fighting and so many conflictual issues. And even the border which we claim not to have been changed significantly has changed time and again. So, well, this is an issue that most people would like to understand, of course, what lies behind as to whether there is a rapprochement between Turkey and Iran. Is it something new? Is it something that is stemming from the conjunctural developments most recently? Is it a deliberate policy of Turkey to contain Iran or to balance Iran? Or is it something that is just out of ideological stance of the current government party in Turkey? This is something that we should talk about more or less. Yes, other topics that, I mean, at least from your perspective are the ones that you should be more familiar with. Chala. The Niktur Non-proliferation Treaty is something that, of course, is becoming more and more... who is calling it this?  I'm sorry for that. So, this is an important treaty and this year there was another review conference which takes place in every five-year intervals. And this time the MPT is of greater importance, not only for the world, but also more specifically for the region. Because there have been many references made to the MPT when it comes to Iran's obligations. And whether Iran is violating some of its obligations or does it fully comply with the MPT requirements and principles and norms? Well, these are things that we should definitely cover. I think we can talk about the Iranian program and Iran's Niktur program and its implications for the rest of the world, for the Middle East, and of course for Turkey. So, you being the... okay, students here and since this issue is being very much articulated here and there in the media on TV channels among scholarly debates in universities or elsewhere. And by the way, for those who are interested, Mr. Hans Plix. Remember who he was? Hans Plix. A name that I've mentioned here several times. Actually, Hans Plix was formerly the head of the IAEA, International Atomic Energy Agency for so many years. And then he was succeeded by Mohamed El-Barde. And then he was appointed as the director of ANMOVIC. At least you should remember ANMOVIC, right? What was it? Can someone spell it out? What does ANMOVIC stand for?  Should I? No, no, no. I mean, just spell out. I mean, United Nations Monitoring Verification Inspection Commission. All right, so, Doctor, actually, Hans Plix Those who are a PhD are very sensitive about being cited here. Doctor. When you say Mr. or Doctor, well, that's something that is really taking so much time and it's painstaking process for those who do really perform it properly. Anyway, Mr. Hans Plix, Doctor Hans Plix, sorry. I will be given a lecture at CETA. Actually, I've never been to their place. It's on Rashid Khalib Chattesi, I think, something like that. You can find from the website and it's at 16 hours in the afternoon and Doctor Hans Plix, I think this CETA meeting is open to your participation. I don't think you need to make reservations or to get permission. So, I would strongly recommend to those who are interested in what happened back then in Iraq and why was it that ANMOVIC not quote-unquote successful in finding the secret weapons, allegedly secret weapons of Iraq. So, well, I'm going there at least and I have some place in my car if you like. Just stop by at 3.30 after my class. I can take you there. All right, let's talk about the Iranian nuclear program. And today, in the afternoon, I think I can use this PowerPoint which is, sorry, available on my website and therefore you don't need to take detailed notes. Just visit my website whenever you can and you go to the PowerPoints. Where is it? Well, this is actually something, this is a presentation I made at the NATO school in Germany, well, 2nd of November already. So, almost exactly for years. Yeah, here we go. This is a presentation which was found to be the best among some 30 presentations for your information as a commercial. Yeah, Iran's nuclear ambitions and emerging crisis, sorry, in 2006. And by that time, the crisis was still emerging and therefore I have to update some of the slides towards the end and these slides, well, they'll still apply, they'll still make sense, but some information may need to be updated maybe with some new developments but in the overall, actually this presentation still makes sense. We need to turn off some of the lights, so is it okay like this? All right, so first of all, it is a very complex issue. So it is not something that you can understand in a straightforward manner. I mean, Ciala just mentioned the MPT. Without proper understanding of the MPT, it may not be possible to understand or to distinguish between who says what and why that country's position is such because there are different interpretation of some of the article, some of the terms of the MPT and therefore, according to Iran, it is something else but according to the United States, it is something else and therefore we should maybe at some point I should be giving some information about the literal issues, I mean, literal issues because without proper understanding of other issues which also have direct bearings, direct consequences on the problem, it may not be possible to fully understand where we stand here today, I mean, why we stand here today and actually what is likely to happen in the future. Of course any discussion on Iranian nuclear ambitions must start with the background information and some of which I share with you already when we were talking about the post-Yom Kippur period and the implications of the Yom Kippur for the region, for the world and it was, I mean, the war between Israel and Arab states in 1973 which was a surprise attack by Syria, Egypt, well on Israel, of course. So the background information, I will try to identify what the puzzle is. It is a puzzle because there is substantial difficulty locating the problem properly understanding the problem because not everyone agrees on the nature of the problem. Some people's interpretation is different than some other people and of course there are major actors who are influential and at some point I will be talking about Turkey's position. Back in 2006 when I gave this presentation in November at the NATO school Turkey was not necessarily an active party to this debate and there were some attempts but not so powerful attempts or not permitted sort of behavior from Turkey's part but then especially since 2008 and onwards we have seen Turkey more on the or featuring on this problem and here it says in the emerging crisis the crisis still emerging. Actually we don't know how it will proceed how it will, or what kind of shape it will take but still it is at the crisis situation, crisis level but yet at least things have still at least as I can see or as much as we can see things have not gone out of hand there are still rooms for containing the problem and maybe who knows solving the problem if of course provided that the parties really commit themselves to the solution of the conflict and as I said there are different perspectives and therefore these different perspectives make it all the more difficult to solve the problem because the conditions that are presented by the parties, if not all of the parties but some of the parties Iran being on the one hand the United States on the other hand their prerequisites or their sine qua non type conditions I mean conditions that they put forward before everything else do not match, are not compatible and therefore they do not necessarily come to a common ground which would facilitate finding any solution. Then what are the problems and what are the prospects? Well back then I suggested certain things which I still stand behind them and because these are long term prospects and this is not an issue that you can single handedly solve overnight by cutting a deal with one or two of the parties it is something that has far reaching consequences for every country involved for the region and of course for the world. I mean nothing happens here or everything happens that happened here has far reaching consequences for the rest of the world same applies to for instance the situation in Afghanistan or Pakistan, India the security situation in some parts of the world actually has some consequences far reaching consequences for other parts of the world so you cannot just look at the problem by only looking at the regional consequences. Let's move forward the background. The background you should be familiar with because we talk time and again maybe not in a in such a coherent manner but not so much exposure on the very specifics of the Iranian nuclear program but it all goes back to the 1950s and it is not only peculiar to Iran because the 1940s and 50s certain developments had also some implications for some countries in terms of thinking at least about embarking on a nuclear program the Atoms for Peace which was a famous speech by the US president before the United Nations General Assembly on December 8, 1953 so he said actually basically let's benefit from the merits of peaceful exploitation of nuclear energy for everyone but since nuclear energy just like any other source of energy or any other scientific discovery has two faces one is benign, peaceful in terms of generating electricity or developing or producing isotopes for some treatments, medical treatments or healthcare curing some illnesses etc and also improving or increasing fertility in agriculture so nuclear energy is something that is good, that is beneficial so let's use this part, let's exploit that part but not go ahead with metric exploitation because with pretty much the same or similar physical infrastructure plus almost the same scientific accumulation, scientific knowledge you may do both I mean if you like but what I now emphasize was to advance the peaceful application and also put a cap or at least put some conditions on the exploitation of nuclear energy well that was of course not a speech coming out of the blue just one day he woke up and he wanted to deliver a speech no, this is of course not the case there is much history to this and it is something that actually he is a fan himself almost obligated in a position to make to deliver such a speech because he was under the pressure of his country's nuclear lobby because as you know and everybody knows the United States was the first and hopefully the last country which has used nuclear weapons actually used against people against humanity in war time which was back in 6th and 9th August 1945 in Hiroshima Nagasaki well of course the scientists might have had prior knowledge about the possible effects of nuclear explosion but still they couldn't keep from advancing that weapon and finally they produced that weapon and they tested first in a desert in New Mexico and then used against people well some people's explanation is that it was a sort of weapon which put an end to the war war 2 and therefore at least yes they are sorry for those who lost their lives hundreds of tons of people but still maybe they prevented others maybe millions from losing their lives because had this not happened the war might have prolonged for so many years in the Pacific against Japan and that many more people well these are all hypothetical issues that we cannot deal with because we don't have any factual data that would substantiate any of these arguments for or against anyway but what that I mean this usage this actual use of nuclear weapons in Hiroshima and Nagasaki and the consequences that they have seen put political pressure on the United States administration well of course it is not an easy decision and not only using it against people civilians but also as to whether this capability should be further advanced or should somehow be you know consolidated which the United States took the decision not to go ahead with weapons or development first I mean this is the very immediate reaction of the United States and but and then they proposed to the Soviet Union to take such measures not to develop the imitry dimensions of the of nuclear weapons but the Soviet Union's reaction was well you have developed that weapon so you have the knowledge and knowledge cannot be disinvented so you cannot put the genie back to the bottle and therefore not that you have this knowledge as to how to do it as to how to detonate a nuclear device we don't know it so even though you propose not to go ahead with further advancement further development of nuclear capability how can we make sure that you will not use this knowledge science or technological capabilities that you have accumulated so far against us in the future so the Soviet Union did not agree to the proposal put forward by the United States not to exploit nuclear energy for meter purpose any further then Soviets disagreed with the United States and they of course developed their own nuclear weapon nuclear device at least in 1949 soon after I mean four years not a long time in this kind of process so having seen the impossibility of preventing the spread of this this technology the United States at least for doing its own part for some reasons of course and I will not go into the details there is a sort of a big chunk of writings, books, articles on the United States decision to limit the transfer of technology to other countries so there was this so-called MacMahon Act and the nuclear energy act or atomic energy act in 1947 which prevented the US companies and the government of course from sharing this technology with even the closest allies and well the United States during this Manhattan project which paved the way to the nuclear weapons under the leadership of Robert Oppenheimer and although the United States benefited from the scientific accumulation of many scientists from around the world especially from European countries they in turn did not want to share this technology with their wartime allies the United Kingdom being the closest so that was something which also created frictions between the United States and the United Kingdom which of course in due course paved the way to United Kingdom's independent nuclear weapons capability and eventually to French nuclear weapons capability well anyway what the decision was not to share this technology with anybody else not to let other countries, other firms benefit from the accumulation the US scientific circles but of course that was the US decision which was at the time the most advanced country in the world in terms of nuclear capabilities and that was a decision of the United States alone but other countries especially European countries like Sweden and also Canada of course Sweden, Belgium well they were also scientifically advanced countries and United Kingdom as well France Germany so they were all developing these capabilities and not only that they were developing for themselves but they were also selling technology for instance Canadian firms sold technology in Pakistan over time so the companies which were large big companies in the United States which were developing technology were in a disadvantage position in the international market because they were not allowed to sell technology which at the time of course let them earn large sums of money so nuclear technology or technology something new something highly advanced of course you could sell at a very high price and make a lot of profit but because of the Atomic Energy Act of 1947 US companies were prevented from doing so and while other Europeans and Canadian firms were selling this technology of course under some maybe conditions but still they were capable of selling technology so therefore the United States having seen the impossibility of stopping the spread of this technology instead of preventing US companies anymore from selling this technology the United States sort of came out with a proposal which is known as Atoms for Peace proposal was to okay let's since this spread of this technology is not is going to gain some pace that we will not be able to control fully so why not why shouldn't we control the spread of this technology the United States being part of the game so that was it and the United States the US President by delivering this speech actually wanted to take the advantage and the upper hand in the nuclear market Ibrahim Germany started before the United States in Nazi period in that time isn't Germany has well actually Germany I mean Nazi Germany during the war was working on nuclear weapons and many of the scientists especially Jewish scientists from European countries who were either kidnapped or hijacked to the United States or by themselves by their own free will have gone to the United States before the war or during the war so that was a huge issue because while on the one hand there was this war between the military but there was also a war between the secret services and the US secret services and or the British secret service they were all after scientists rocket scientists nuclear scientists, other scientists whose knowledge would be of significance for some metro applications for the United States or the United Kingdom or if they were not in the hands of the Western countries they fear that they would help Nazi Germany advance its military capabilities and it is a well known fact that Nazi Germany had of course advanced nuclear program, nuclear weapons program and some scientists I think I don't know if I mentioned his name here Joseph Rothblatt he he was the only scientist who quit the Manhattan project before the bomb was fully assembled when Nazi Germany lost war and he said there is no more reason for me to contribute to this project because my purpose was to build the bomb before the Nazis did because some scientists were really concerned and of course some countries were really concerned about whether the Nazi Germany would produce the weapons before the United States so they instead of staying in Europe and or helping the Nazi Germans developing this weapon they fled to the United States or they were as I said with the help of the secret services they have gone to the United States and helped the Manhattan project so that was one motivation or one explanation for some scientists for having contributed to the development of nuclear weapons because many people felt really sorry about the extent of their contribution to the bomb after having seen the effects in Hiroshima and Nagasaki and there is a documentary actually I would like to share this with you and it's in my office and maybe we can share some time about the development of the first nuclear weapon and some scientists were really looking at the issue from a very scientific perspective but then as I said after having seen the pictures probably and since there was no precedent there was no prior example as to what would be the actual consequence of such a nuclear explosion they say they could somehow imagine as to how big the destructive impact or effects of weapon would be but they have only seen after having seen the Hiroshima and Nagasaki pictures so you're right the nuclear science was not unique to the United States I mean the United States and if you go back to the 19th century the last sort of quarter of 19th century you see in Tsar's period in Russia scientists, Russian scientists working on at least of course theoretically whether atom could be split so because atom was known for so many centuries as the smallest unit of any sort of material which could not be split but theoretical physics suggested that and they work on it and then eventually I mean starting from the 1860s 1870s onwards Russian scientists have done a significant theoretical breakthroughs which of course paved the way to work of Einstein and other scientists so Germany, Sweden, Belgium, they were all sort of countries which were capable of developing a certain level of technology but of course it took maybe much more concentrated work just like the one in during the Manhattan project which of course required the concerted efforts of many scientists and a lot of physical financial contributions, material contributions was coming from the US government so without the Manhattan project the bomb might not have been developed so fast it might have taken maybe another decade or maybe even longer we don't know I mean at least scientists, nuclear physicists or nuclear engineers might comment on this but what we know was that in Europe in some countries when I mean in the 1950s for instance and 60s of course and onwards the level of nuclear science and technology was significant and that was of course also the time when especially for quick economic recovery from the damages of the World War II Germany and other countries I mean some of them were physically totally destroyed, some of them were maybe not so much destroyed physically but of course suffered the consequences of the war in economic terms so energy generation is or was back then was very very important and nuclear energy as has been the case until major accidents that took place in the 70s and 80s was seen as a panacea especially after the OPEC crisis in 1974 so therefore technology or at the technological level nuclear science was and nuclear energy was developed in a number of European countries which eventually started to sell this technology at a very significant price while the United States firms were not allowed to do so so that was the reason I mean why the United States after some time decided to change this attitude, this policy and to let the U.S. firms to sell technology provided they of course impose some conditions on the buyers because nuclear technology is not a technology that can be left to itself I mean this is this is not again unique to the United States or unique to nuclear technology sometimes I mean especially at this time for instance we talk more or less state of the art or some groundbreaking technological advances in electronics for instance in the field of electronics and when you go to the producer of some major product and if you want to buy the know-how I mean you may not be given this know-how even if you offer a large sums of money a big price the money that you pay will be relatively speaking not so much significant with respect to the money that they can gain over time in long term if they keep this secrets or the technology or scientific knowledge secrets for themselves so that was the situation making the 50s and some countries of course were trying to keep some of the technology for themselves but also let others benefit from it at a very high price and again for reasons that we will be discussing later on again the United States decided to change its course of action and change its policy and pave the way to the atoms for peace and that is using the merits of nuclear technology for peaceful purposes and will continue with the rest of this power point and I would strongly recommend it to have a look at it I mean because now you have weekend I know you have exam maybe other exams next week including our our exam here and this is available on my website and just go ahead and have a look at it and familiarize yourself with the issues that we will be covering next Tuesday


Okay, so what I will be talking about is a popular framework for dealing with uncertainty in optimization called online framework and in particular, I want to focus on a central problem in this area called the case-server problem and to present to you a new algorithm for this problem and this algorithm is joined work with Nikhil Banzal, Nifbukhbinda and Sefinawah. Okay, so the point of start of this talk is the classical view of optimization, okay? So according to this classical view, the way the optimization happens is that, you know, if you have some problems you want to solve, then we are presented with an instance, well, an input instance of this problem. We put this instance in our computer, we run some algorithm on that and, well, this produces some answer. It might be an optimal answer or maybe only approximately optimal answer, okay? So, you know, this is the way we think about optimization nowadays and sort of this point of view was, you know, it's extremely influential in literature science and beyond it, but, well, the point I want to make today is that, you know, despite all of its success and, you know, and its influence, there is one aspect of, you know, quite a fraction of real-world problems that this framework, you know, completely misses, that it's not present in this view and, you know, this aspect is the fact that, you know, uncertainty is a part of life and then as a result is a part of many optimization problems. So to give you an example, you know, imagine that you are a, you know, trader at Wall Street and, you know, and if you, well, and so, you know, so your task is to sell and buy stocks, to maximize profit and, you know, and if you look at the stock quotes from last month, it's very easy for you to see, you know, well, to see, you know, how should you, well, which stocks you should sell and which one you should buy to maximize your profit? But that's not the core of the problem because the core of the problem is that you have to do it for the next month.  So in particular, you know, the common, the common characteristic of the problem we try to capture here is that, you know, we don't know the whole input in advance, we only learn it gradually, but still, you know, as we learn this input, we already have to make some irrevocable decisions, well, along the way. So, you know, we have to make decisions even though sometimes we cannot really evaluate what will be the impact on the performance of the final solution. Okay? So this is clearly an aspect of optimization that, well, classical model, classical view does not capture. So, you know, the question is, you know, how can we capture this kind of challenges? How can we deal with that? Okay? So as you might imagine, you know, this is not, this is not a new question and there are already some well-known answers. In particular, there are two prevailing frameworks to kind of settle this kind of questions. So the first one is called, you know, stochastic optimization and what this framework tells us is, you know, the following that, you know, okay, well, you don't know what your input will be, really, but you at least know that it will be coming from some, you know, underlying distribution.  So, you know, all you have to do is just to devise a procedure that, you know, will leverage this knowledge of this distribution to make sure that you will try to well optimize your expected cost with respect to the distribution. Okay? So this is, this is the, well, so this is the framework and, you know, and the nice thing about this framework is that, you know, quite often it allows you to get a positive result that, you know, but give you a performance guarantee that it's very close to what you will be able to do if you, there was no uncertainty involved at all. Okay? So that's a nice thing, but the problem is that, you know, well, it's not really clear how meaningful this kind of positive results are because if you have your problem, you know, how do you know that, you know, the input you are seeing comes from some fixed distribution? And even if this distribution exists, you know, how can you access it?  So this is the, well, this is the problem and, you know, and this problem brings us to the second framework for dealing with entertaining optimization called online optimization. So what this framework does, well, it takes exactly the opposite stance. So what it tells you is that, you know, you make absolutely no assumptions on, you know, how your input will look like. Yes, it can be even adversarial and, you know, really it can be as bad as possible.  So there is no notion of expectation because you don't know what, what is the distribution.  So, you know, so clearly, you know, the problem here is that, you know, once you are in such a restrictive setting, then, you know, more often than not, than not, you will end up having not a positive result, but negative results and pretty strong at that. But, you know, on the flip side of this is, you know, if you are able to get some positive result, then this is an extremely meaningful statement. Yes, because it just holds without any assumptions and you don't have to worry about, you know, how it's applicable to your particular problem. So as you might guess from the title of the talk, you know, the framework I want to focus on today is online optimization framework. And in particular, let's start by discussing one of the classical problems in the area, namely the caching problem. Okay? So the caching problem tries to, you know, tries to capture the difficulty of maintaining a cache in a situation where the data access, well, data access patterns are unknown to us. So, you know, probably all of you know, but caching is a very popular technique for speeding up memory access in a situation when the memory has very large latency. So what you are trying to do, you know, whenever you fetch some data from the memory, you try to store it locally in your cache. So whenever you need it again, you can quickly access it. But of course, the catch here is that cache has only limited size and you cannot just afford to simply store everything you ever, you ever fetch. So you have just to, well, to make sure that you keep the most important stuff. But now, if you don't know what the data access memory pattern is, well, it's hard for you to assess what is the important, important stuff really. So there is some difficulty coming in and, you know, this problem tries to capture exactly that. So formally, the way we do it is as follows. So the setup here is that, you know, we have our, you know, we have a universe of N pages. So this is the, you know, we have, we can at most see N different pages throughout the execution of the algorithm. And we have the cache, which can hold, you know, at any given time at most K pages. And to make this interesting, we assume that K is strictly smaller than N. Okay? So this is the setup and now we are playing the following game. So in each round, we get the page request coming in. Okay? And now two things can happen. So either we have already, well, we already have this page in the cache and then we are happy because we can fetch it quickly and we don't have to do anything. Or, well, we are slightly more unlucky and the page that is requested actually is not in our cache.  And also now we want to, you know, to put it in our cache and, you know, if we have a room in this cache to put this page and that's all we have to do. But sometimes, you know, the cache might be full already. So we have to decide which page to evict to make room for this new page. Okay? So this is the game we are playing and this, you know, this keeps repeating. And, you know, know that the only decision that you are making in this, you know, in this model is just, you know, which page to evict whenever we have to evict the page. Okay? So everything else is already predefined by the input. So now our goal is, you know, to devise an addiction policy that will lead to the minimal, you know, total number of cache misses over the sequence that we are presented with. Okay? So this is the problem.  Okay? So what are the good algorithms we are looking for here? So, you know, clearly, you know, if we knew all the future requests in advance, then it's very easy to get an optimal solution. It's like, it's a very simple, there is a very simple policy that allows you to do that. But of course, you know, the point here is, you know, well, like the point here is that it's not, that's not what we are after here. So we are after here, we are trying to do well despite the fact that we have no idea what the future will be. So this is the online setting. And in particular, once you have no idea what is the future, then there is no hope really for always be able to match the offline optimum. So offline optimum is the best solution when you know the whole sequence of requests in advance. So, you know, so we cannot hope to match the offline optimum. So what we are after here is to, well, what we are after here is, you know, to design an online algorithm that tries to never do much worse than offline optimum. OK, so we don't hope to be always able to be optimal, but at least we want to be always sure that we are not far from the optimal solution. And, you know, to make it precise, you know, we introduce a notion of competitiveness and we say that the algorithm is, you know, C-competitive for some value C, if on every request sequence, the number of cache misses that we suffer is never bigger than C times the optimal number of cache misses that we could have here. OK, and, you know, what we will be after, we will be trying to find an algorithm who have, you know, minimal competitiveness. OK, so now, you know, once we know, you know, OK, I should also mention that, you know, competitiveness is only one measure of performance of the algorithm. There are also other measures that I will not talk about, you know, in particular, there is so-called, you know, minimal regret measurement, but I will not go into that in this talk. So, OK, so now we know what we do, what we mean by, you know, by a good algorithm. So, you know, so what is known about, so how can you get some, you know, some nice algorithm for this problem?  OK, and indeed, Citer and Tarjanin, in their seminar paper, they analyzed this policy and they prove that it is K-competitive. OK, so the thing is that this is a K-competitive is an interesting statement, because, you know, note that the competitiveness does not depend on the length of the sequence, OK? So the sequence can be very long, but this, you know, this sort of this competitiveness ratio depends only on the size of the cache, so that's very interesting. On the other hand, you know, if your cache has like 10,000 lines, then it's not, you know, it's not the most satisfying performance ever, so, you know, so the obvious question is, you know, can we do better than that?  Sort of the, you know, the key reason why this is the case is that actually, deterministic algorithms are completely predictable.  At every given time step, OK, so everything is uniquely defined, so as a result, it is not hard to design a sequence that causes this algorithm to have a cache miss every single run. And then when you do, you know, appropriate math, you will notice that, you know, you can make the sequence that, you know, it will, it will cause the algorithm to have a cache miss every single time, but the optimal solution will only have a cache miss at most every, every Kth run, so this will lead to this K lower bound, OK? So this is, you know, so this is, this is a result, but of course the natural question now is, you know, so how about randomness, can randomness help you? And well, it turns out that it indeed can, so, you know, so what you would like here, what we are considering here is, you know, we are thinking about eviction policies that can use, well, can make random choices, yes? So, so what we do, well, our algorithm can, you know, can, can toss random coins, and what we are measuring for a given sequence is the expected number of cache misses, OK? And once we look at this model and we give more power to our algorithm, then we could, then we could do much better, actually, actually exponentially better. In fact, you know, there is a very, you know, very simple algorithm that allows you to obtain O of log K competitiveness, and you can prove that this O of log K is actually the best possible here. So clearly for, you know, for caching problem, we essentially know everything, so we know the best competitiveness for, you know, for a randomized model and for the termistic model. So probably this is time to move to a slightly more challenging problem, namely the case-server problem, which will be the focus of the reminder of the stock, OK? So, yeah, so probably, you know, the easiest way to think about what, you know, what the case-server problem is, is to view it as a, you know, as a task of, you know, that fire track dispatcher is facing, OK? So the setup here is that we have n locations over some metric, so, you know, there might be different distances between any two points. OK? And we have case-servers of, or fire tracks here, OK? So, and we want the number of servers to be, well, strictly smaller than the number of locations to make it interesting again. And now, you know, we are playing the following game. So in each round, we have a request or a fire appearing at one of the locations. And once again, one of two things can happen.  Or actually, you know, we don't have a, we don't have a fire at this location. And then what has to happen is, well, we have to decide, you know, which of the servers or fire tracks to move to this location, well, to take care of this, of the fire. OK? So here is the fire, and we move this track, and there is another fire, and we move this track. So, you know, so, so this is the game. And now, you know, our task is to devise a way of, you know, moving the servers around that will, you know, lead to the minimum total distance traveled by the, by this fire track. You know, while serving the, while serving the request. And of course, we want to do all of this in online settings. So in a setting when we don't know where the future fire will be. OK? So this is the problem.  OK, so what is the motivation for starting this kind of problem? And, well, there are a couple of reasons for that. So, one reason is that actually, you know, this problem captures, well, even though it's very artificial and sort of, and sort of very, very simple. Or maybe, well, maybe because of that, it captures quite a variety of online scenarios. So you can imagine, you know, fire, well, the service to be like technicians, service trucks, well, copies of frequently changing data, et cetera, et cetera. And, you know, and each of these institutions will, you know, will yield some interesting online scenario, and they all will be captured by this case-server problem. And in particular, you can view caching as a special case of the case-server problem. So essentially, caching is the case-server problem on your uniform metric.  And then it's easy to see that whenever you have a request, you know, it corresponds to, well, you can see it as a fire or as a request to a page, and, you know, this, you know, this operation of moving the servers corresponds exactly to, you know, eviction and fetching, fetching procedure. And since the metric is uniform, you know, every such a move counts the same. So this will just count the number of cache misses while you are serving the request. Okay. So, so this is one type of reasons why we care about this problem. But also, you know, the second type of reason that, that makes this problem interesting, at least to me as a theoretician, is that, you know, despite the very simple formulation, this problem has extremely rich structure.  So that's another reason why we really want to understand what's going on in this problem. Okay.  So clearly, you know, as caching is a special case of the case error problem, then all the lower bounds, you know, transfer over. So we know that we cannot hope for a better than K-competitive, you know, deterministic algorithm and better than overflow K-competitive randomized algorithm. Okay. And the interesting thing is that, you know, despite the fact that the case error problem seems to be much, much, much more general than that, we don't know any single better lower bound. So all the lower bounds for this problem come directly from the lower bounds for the caching problem. Okay. So this is, you know, these people were quite surprised by that and, you know, they couldn't believe it first. But then, you know, well, this set of the affairs made them, you know, put quite a bold conjecture. So, okay, so if we cannot prove better lower bounds than we have for caching, so well, maybe, you know, maybe, you know, maybe this is actually the right bounds here.  So one is deterministic case error conjecture, which asks about exactly K-competitive deterministic algorithm and the other is, you know, the randomized case error conjecture that asks about, you know, overflow K-competitive algorithm. So these are the big questions that we are after here, too.  So, you know, so let me give me just a very brief history of what's going on because, as you might imagine, there is actually a multitude of work on this problem and I don't have time to really, you know, present in any meaningful manner. So, you know, in terms of deterministic case error problem, then the conjecture, well, that you can hope for, you know, K-competitiveness was already put forward in the paper by Manasseh et al. in 88. But they didn't provide any general case error algorithm. They only had some indications to believe that this is the right answer.  And as you can see, you know, this competitiveness is quite large. It's actually exponential in K. So it seems to be very far off from, you know, what we hope is right, is correct. But shortly thereafter, there was a breakthrough paper by Kustupets and Papadimitriou, who showed that actually you can get an deterministic algorithm whose competitiveness is 2K-1 only. So, clearly, you know, here we are done up to a factor of 2, and in fact, you know, for some special cases of the problem, for instance, when the metric comes from a tree metric, we know that K is actually the right answer. So, you know, we are, the state of affairs is pretty good here already. So, how about the, you know, the randomized case error problem? So, you know, in case of the randomized algorithm, there was really a lot of work on various special variants of this problem. In particular now, quite recently, we learned that you can get an O of log K competitive algorithm for an extension of the caching problem called weight-weighting paging problem. And this is the result of BANZAL at all. But, you know, if you ask about the, you know, the BANZ for general metric, then the best-known result is just, you know, the deterministic algorithm of Kustupets and Papadimitriou. So, essentially, you know, despite, well, it's intuitively obvious that we know how that randomization should help here, we have no idea how to take advantage of it. We don't understand how to use it here.  So, really, you know, despite a lot of effort, the state of the affairs is not very promising here.  So maybe, you know, maybe actually K is the bound here.  Well, there is no good reason, but we are.  So what we do, well, we present an algorithm for the general K server problem, the randomized algorithm for the general K server problem that is, you know, poly-log competitiveness, well, poly-log competitive, but, of course, the catch here is that this poly-log depends on K and N, so the number of points. So as long as the number of points is, you know, sub-exponential in K, then we are improving over this 2K minus 1 bound, but, you know, in general, these two points are incomparable, okay? So there is this dependence on R. So, you know, this is the result, so let me just, you know, proceed to explaining to you while giving you some idea how this kind of result can be obtained. So, well, clearly, you know, when you look at the, you know, state of the affairs, well, the history of the problem and what people struggled with, then it's pretty clear to everyone that sort of the hard part here seems to be dealing with an arbitrary, you know, arbitrary metric, okay? Because, well, if metric is uniform, we know what to do. We know exactly what to do. So, sort of the guiding principle of what you will be doing here is, well, we will try to trade the complexity of the underlying metric, well, we will, for the complexity of the problem we are solving. So what do I mean by that? Well, what we will try to do, we will try to reduce the K server problem over an arbitrary metric to a different, more difficult problem, but over a very simple metric, namely the uniform one, okay? So how can we do this kind of reduction? So how, well, how can we go about that? Well, it, you know, well, this reduction comes essentially in two big steps. So the first step, you know, has something to do with so-called HST metric. So what is an alpha HST metric is? Well, it is a metric that is induced on the list of the following, well, type of a tree. So this tree is a level, it's a level three, and, you know, and all the edges on the first level have, you know, have length one. All the edges on the second level have length alpha. All the edges on the third level have length alpha squared. And we have this kind of, you know, and we have this kind of exponential growth as a rate of alpha, you know, for each of this level. So, you know, so any metric that is induced, well, on the list of such a tree will be an alpha HST metric.  So, essentially, if you want to, you know, if you want to, well, get an algorithm for the case in a problem for general metrics and you are willing to pay this, this, this, well, alpha log n factor in our competitiveness, then we can just constrain ourselves from now on just to alpha HST metrics, okay? So, because whenever we get an algorithm for this kind of metrics, it will immediately give us an algorithm for general metric here, okay? So, that's the first step, and so, from now on, we just look at, you know, at alpha HST metrics.  So, clearly, by definition of the metric, you know, you know, we have, you know, that both requests and servers reside in the leaves of this tree. And, you know, if you observe a case server solution, then, you know, like the, and if you look just at the trees, then, you know, the, well, when you, the process that we'll imagine there, like, sort of the way the servers are moving around here might be very difficult and not really, well, easy to grasp. So, what we will try to do instead to sort of understand what's going on a bit better, well, we will try, you know, we will try to, you know, view this, you know, complicated process on leaves as a process that is generated by relatively simple processes or, well, on happening for each of the internal nodes, okay? So, we will just try to break down this complicated process into simple processes that are happening for every internal node. So, you know, so this might be a bit mysterious, what do I mean by that? So, let's, well, let's try it slowly here. So, in particular, you know, so let's focus our attention on one particular internal node. Let's say the root, okay? And let's look at, you know, what does this root see when he just, you know, constraints himself to his local neighborhood?  So, it particularly doesn't see the leaves. And, you know, what's going on there from his point of view? So, well, he doesn't see where the requests arrive, to which leaves the request arrive. He just sees to which, you know, subtree corresponding to his children, well, this request shows up. So, if there is a request, well, somewhere in the, you know, in the subtree corresponding to the child, he only knows that, you know, there is a request corresponding to this child. And that's all that he sees.  All it sees is just, you know, how many servers are in each of the respective subtree. So, from his local point of view, he only sees this, you know, configurations when, you know, just assign number of servers to each of his child's subtree. And, well, in particular, you know, whenever there is a movement of servers around, well, he doesn't see anything of this movement, as long as, you know, this movement does not, you know, move servers, well, between different, different subtree. This is the local view of the route. And now we wonder, you know, what does this route see when he observes an optimal solution on the K server? Well, what it will see is that, you know, there will be some dynamic emerging from, you know, from these configurations he's seeing. Namely, there will be like sort of two conflicting processes happening. So, on one hand, you know, what will be happening is that the trees that tend to get a lot of requests will also tend to get more servers there, because it will make, you know, taking care of this request easier. But on the other hand, of course, you know, the number of servers is fixed, so it kind of doesn't, you know, give a lot of servers to every tree and also moving servers around is expensive.  So we see that, you know, we will have these two conflicting goals and now when we want to actually recover a good, you know, a good solution to the K server problem, we will try to, you know, set up an algorithm that will try to guess what would be the best assignment of servers throughout the time. So we will try to, you know, to capture this kind of, well, algorithmic task as an algorithm, as an algorithmic problem. And when you try to do that, then, you know, the problem you are likely to, the problem you are likely to end up with is so-called the allocation problem, which is the third and last of the problems I want to introduce today. Okay? And by the way, I should mention that, you know, that, you know, like this general approach was pioneered here by, you know, Kota and Myersen and Poplowski, and in particular, they were the first to introduce this allocation problem in the context of the K server problem. Okay? So what is the allocation problem? So in the allocation problem, well, you can think that this is a job of some manager that oversees, you know, while taking care of some projects, you know, well, by some team of, you know, workers in a couple of offices. So the setup here is that we have a delocations over a uniform metric now. So the metric is uniform again. And now, you know, well, we have K servers or workers. And now it will actually make sense to have more than one worker at a given location. Okay? And now, you know, the game it displays is as follows. So in each round, we get a request. So the request is just, you know, what it consists of. Well, it consists of a location to which it corresponds to. And also, you know, together with this location, we are presented with K plus one values that are non-increasing. So there is no ST0 up to STK. And the meaning of these numbers is, you know, STJ is just the cost of completing the project that's happening at this, you know, requested location if we have exactly J workers there. Okay? So essentially, you know, what's going on in each round. So, you know, the manager, whenever he sees the, you know, the request and the corresponding service costs, he has to decide, you know, whether I want to move some workers around and, you know, any moving of workers will cause a move cost. And then once he says, okay, I'm done now, then, you know, we just look at the location that was, you know, that was requested and we pay the service cost given by the respective value of STJ. Okay? So here, you know, maybe seeing this request at first location, he decides to, well, to move, you know, to move two workers there. And now he says, I'm done. And he pays the cost of ST3 as a service cost here. Okay? And also he paid the move cost of moving two servers. So this is the game that we are playing once again in online setting. And our goal now is to play this game in such a way that we will minimize the sum of the move cost at the service cost here. Okay? So this is the problem. And note, you know, that I mentioned that, well, that, well, at some point I mentioned that, you know, the problem we'll end up working with will be, you know, will be a generalization of case error problem. And indeed it is. So it's easy to see that if we just consider a special case of this problem in which, you know, the request or of the form will pay infinity service cost. If there is no server at the location and zero service cost will never there's at least one server at the location, then what we will recover here is exactly, you know, caching problem, which is the case error on the uniform metric. But of course, you know, we see that allocation problem is much more than that. And sort of, that will be the price we will repay. And just one, just one thing to note. So one thing that I ignored here that actually, you know, to make this problem useful to us, I'm sorry, namely we also, you know, well, in addition to all of, you know, the service costs and the request, we also should allow the number of available workers to change over time. So like in each round, we also are told, okay, this round, we have only this many workers, you know, available to you. So if you have more than that, you have to return some of them back to the headquarters. Or, you know, if you have less than that, then you will get some free workers here. Okay? But I will ignore this. I will ignore this part in this talk. So this is the problem we are, you know, we are interested in.  Well, and the reason why we care about this is the problem because like Kota, at all, showed that if you are able to get a good enough algorithm for this allocation problem, then it allows you to get, you know, well, what we are looking for. I mean a poly-algorithmic competitive algorithm for the case error problem over general metric. So note here that this poly-log depends on K and N as we expect. But also it depends on delta, which is the aspect ratio of the underlying metric. So, well, this is the theorem. And essentially, you know, what it means is that, you know, from now on, all we really need to care about is just, you know, finding the good enough algorithm for the allocation problem. So note that now we have a problem over uniform metric. But, well, it seems to be slightly more difficult than the original problem we were dealing with. And so this is the theorem that, you know, Kota had all proved. And also they sort of, they sort of made the first step.  So D is equal to two. And this, you know, doesn't really give us anything in general case. It only gives us some, well, algorithm for very special type of metrics. But this is the first step. So, well, all we have to do is just, you know, make the next step and just get, you know, the good enough algorithm for, you know, for the general case. So that's, you know, that's what we set out to do. And that's exactly what we failed. Because, you know, after quite a lot of effort, we realize that we don't know how to do that. Like, it seems to us that the problem, well, in the, well, in the course of this reduction, the problem that we ended up with just becomes too hard. We just don't know how to get this good enough guarantee for this, you know, for the problem that I just stated to you. So that's, that's not good, yes? Because, well, essentially it seems that this is a dead end. So because we reduce a problem to another problem that we don't know how to solve, so that means, you know, that all the effort is wasted here. But, well, maybe it's not that bad. So let's try to recover. And so, so let's try to, you know, sort of to, yeah, to prolong the agony here. And let's try to, you know, okay, we don't know how to solve, you know, the actual problem. So let's just try to look at some fractional relaxation of it, okay, and see what we can do there. So what kind of fractional relaxation can we consider here? Well, it's probably, you know, the simplest possible fractional relaxation you could imagine. So what we will be doing, so, well, instead of keeping track of the actual integral configuration of the, of the servers, what we will do, we'll just keep track of, you know, of some marginals. So we'll just keep track of marginal probabilities xij for any i and j, well, which is the probability that we have exactly j servers at location i, okay? So what kind of constraints you want to enforce here? Well, one type of constraints we'll just say that for any location i, this is indeed a probability distribution. So this xij is for fx i sum up to 1. And the second constraint we'll just say that, you know, if we sample independently the number of servers from each of these configurations, then the expected number of servers that we will get with this procedure will be exactly what it should be, namely k, okay? And once, now, once we are dealing with a more general configuration, we have to extend the notion of service cost and move cost, and we do it in an absolutely, well, natural manner. So we just look at the expected service cost, and we look at some, well, earth mover distance between configurations as they change. So now we have this fractional relaxation, you know, and the good news here is that, whoa, actually for this relaxation, we know how to get this good enough algorithm. So, so far, so good. But, well, the problem is that this fractional relaxation actually, well, we can't really use it to get the good solution for the integral case because the problem is that this fractional relaxation actually has very bad integrality gap. So it has an integrality gap of omega of k, so, you know, there is no hope that we will be able to get a running procedure that will always, well, give us a good enough solution for the integral case. So, well, we tried to do something, and we got stuck again. So what to do now? So do we abandon this whole approach? Well, not really. So now, you know, the key observation that we have to make is that actually, you know, why do we even care about this allocation problem? It's like, we don't really want to solve this allocation problem. This is just some kind of proxy for what we really want to solve, namely the case-server problem. So we want to get an integral solution for the case-server problem, not necessarily the integral solution for the fractional problem, for the allocation problem. So, once we realize that, then what we do, and this is the outline of our algorithm, what we do, well, we start from the solution for the fractional allocation problem, and then we, you know, extended the reduction of quota at all on the HST. So we get a solution that is fractional for case-server problem. But now, we show that once you are, no, once you are dealing with a case-server problem, like fractional case-server problem on HST, actually there is a simple rounding procedure that will give you, you know, the integral solution to the case-server problem on the HST, and will just incur some, you know, some acceptable overhead. So, well, so this is the way the algorithm works, and you know, and it seems to work, and then we did the integrity gap go. Well, essentially what happened here is that, you know, once we were able to defer the rounding step to the moment when we deal with case-server problem and not the general allocation problem, then, you know, then for the, for the configuration corresponding to the case-server problem, actually this integrity gap, well, it's not present. It only is present for some configurations for the allocation problem. So, in this way, you know, by being able to defer this step, we just, you know, got around this integrity gap, and we could get what we wanted. And let me just know that one thing that I omitted here is that, you know, as probably you noted, you know, the reduction of COTA at all, it introduced also a dependency on the aspect ratio of the metric, and actually we had a way of getting rid of that. So we were able to not, well, to get rid of this dependence, but I will not talk about this here. So this is the way the algorithm works, and, you know, and the remaining time I just want to spend on, you know, on giving you some glimpse of how this fractional allocation problem actually works like. Yes, because maybe it wasn't clear from the way I was explaining things, but actually this is the heart of our algorithm. Yes, like this is actually where the most integral things, you know, are happening. So let me try to give you a glimpse of that here. So, well, I will do it, you know, I will give you these glimpse, well, just for a special case of the problem. So in the special case, you know, well, I will just assume that all the service cost vectors are of the form that you either have to pay while some cost CT for not having a server at the location, and, you know, once we have at least one server at the location, we just pay zero. So this special case corresponds to caching with renting, where we have a caching problem in which, you know, whenever we have a request and we don't have a server there, we have an option of paying CT for just taking care of this particular request and not have to move the server. So not having to move the server. So this is the special case we will focus on here, but really, once we are in the special case, then really it doesn't make sense to put more than one server at any given location. So we can assume that, you know, that all xijs for, you know, for j bigger than one are just zero. And essentially, you know, once we are in the special case, you know, we can, you know, the complete description of the configuration is just given by saying, for instance, you know, what is the value of x i zero for every location, and x i zero is the probability of having no servers and what is the probability of having one server at location i. So we know everything we want to know. Okay? So this is the special case we will focus on and also, well, just to get rid of corner cases, let me also assume that, you know, even though these probabilities x i zero are numbers between zero and one, they actually never are exactly zero or are never exactly one. They are always, you know, between, strictly between these two boundaries. Okay? So this is the special case we will be dealing with here. I just reproduced it over here. And, you know, so the picture we should look at is something like this, so this, you know, this brown, well, this brown volume corresponds to the volume of the server that we have at every given location and x i zero are just the gaps that we have, you know, in each of the locations. So now, you know, so how the algorithm works now? Well, so, so how do we describe what our algorithm works? So in each round t, it is presented as some, you know, that corresponds to a location and some service cost vector. And well, usually what I should just tell you is that, you know, if our old state was this, then our new state will be this. But that's not what I will do. What I will do instead, you know, the way our algorithm is defined is just it provides a way of evolving the old state into a new state via some, well, continuous process that depends on the request. So this, so what will be just happening, you know, whenever we see, you know, the new request, then, you know, we will just set up some evolution of the current state that, you know, that along which our state will evolve for some period of time. And, you know, whatever it evolves into will be our new state. So this evolution will be, you know, so this infinitesimal evolution will be a two-step process. So what we will be doing is, you know, as a first step, we will have well, so-called rising step in which we will just decrease the value of XIT0 by, well, the following quantity. So just to decipher what this quantity is. So know that, you know, XIT0 is just the probability that we have zero servers at the requested location and CT is just the penalty that we pay for not having a server at the location. So essentially what this expression is, it's proportional to the expected service cost that we will pay in current configuration. So what we are doing, well, we are trying to decrease, well, decrease the value of XIT0 quantity. So essentially, we will try to reduce the service cost that we will incur and we will do it professionally to the service cost that we are actually well, are likely to incur at this moment. So this is sort of like a gradient descent step here. So that's good because, you know, reducing the service cost is something we definitely want to do. But, of course, the problem is that, you know, that this will make the state infeasible, yes, because we just will decrease the, we just put more volume into our system, but, you know, now we have to withdraw to make the solution feasible again. And the way we do it, well, we do it in the fixing state. And the way we do it is by increasing each of XIT0s proportionally to the value of XIT0 plus some additive factor. So we just do it, you know, we just do it infeasibly as long as, you know, the volume, we have too much volume in the system. So sort of, you know, so sort of clearly, you know, by doing that we will make the system, the state feasible again. And this, you know, fixing step is that sort of like we do this withdrawal proportionally to the XIT0 because, you know, whenever we have a location that has, you know, almost full server there, we want to be very conservative with withdrawing volume from there. We are much, much more happy to, you know, to be more, you know, to be more courageous. We draw out from a location that already have not that much server already.  So this is the algorithm. So we just keep repeating this, you know, the steps for some period of time.  So how to prove some competitiveness here. So, well, so, well, so I will, I want you to give you an example. Actually, the competitive analysis of this problem is quite simple.  So it's a potential based argument. So what our potential is, well, our potential is this expression written over there. So this expression depends on two things. On the configuration of the algorithm and the configuration of some fixed optimal solution. So we don't know, our algorithm doesn't know what the solution is, but, you know, there is some fixed optimal solution and we just want to measure some, you know, configuration from the configuration of this optimal solution.  So all, at all locations that, you know, that the optimal solution has a server, the contribution of this location to the potential is always zero, no matter what is, whether we have server there or not. And now, on the other hand, if, you know, if optimal solution does not have a server at the location, then this, you know, then this contribution is logarithmic, you know, given by this expression. So just to decipher what this expression is, yes. So it's over there. So this is, well, an example, an example graph of it. So what will happen is that, you know, so this expression, well, well, decreases as x i zero grows. So if x i zero is one, then, well, this logarithm just evaluates to zero. And, you know, if x i zero is zero, which corresponds to having a server at location i, then this expression is, well, it's as something that is all of log k. Okay? And no, and we have everything in between for fractional values of x i zero as logarithm function dictates. Okay? So, you know, for those, for a few that are sort of familiar, there is some similarity here between, you know, relative entropy and, you know, this potential, this symmetry is not exact, but sort of the feeling is sort of the same. Okay? So this is our potential, and now, you know, how can we use it to prove the competitiveness? So assume we want to establish all of log k competitiveness of our algorithm. And so, you know, as the potential based argument, well, as potential based arguments go, all we have to show is that, you know, at every given, like, throughout the whole execution of the algorithm, the following inequality is, you know, differential inequality is preserved. And, you know, just to get rid of some, you know, of too much of expressions, let me just, you know, prove to you that this inequality holds in a special case where this corresponds to caching when all the, you know, all the costs for not having a server are actually infinity. So we essentially, what happens there, that we never want to pay any service cost. So we always make sure that we don't pay any service cost at all. So then, you know, this inequality that we have to show, it just simplifies to the following thing. And, you know, whatever we show, we just, this will be a proof of log k competitiveness for caching problem. Okay? So how can we show this inequality here? Well, what do we do? Well, so we will just fix some round of our algorithm that corresponds to, you know, to a request being at location I.T. And we will just divide, you know, to hold this around the way what algorithm and optimal solution does into three stages. So in the first stage, you know, we just look, you know, whether opt moves or not. So opt only moves if he doesn't have a server at I.T. already. And, you know, if he doesn't have a server at I.T. already, then he will move one server there from some location I.T. So how does this move affect our inequality? Well, clearly, you know, our algorithm doesn't move. So the change of the movement of algorithm is zero. And clearly, well, just optimal solution just moved one server. So delta move opt is just one. And now what is the change in the potential? Well, in the worst case, what will happen is that, like, once we draw a server from location I.T. then these locations will start to contribute something to the potential. But, you know, no matter what the value of X I.T. is, in the worst case, it will be just some, you know, of log k factor. So we know that in the worst case, you know, from which location the optimal will draw the servers, this will be at most a factor. So we see that, you know, on the right we have O of log k and on the left we have O of log k, so everything works out. Okay? So this step is okay. Now, for the second step, well, what happens is that the algorithm tries to increase, well, decrease the value of X I.T. zero. And since it wants to have a zero service constant, essentially it sets X I.T. zero to zero. Okay? So that's what it does. So how does it reflect in our inequality? So, well, clearly optimum doesn't move, so we don't have to worry about that. Also, the potential also doesn't change, because we know that opt has to have a server to location I.T. And we know that locations that opt have a server, they don't contribute anything to the potential. So nothing changes here. The only thing that changes is sort of the move, because we, you know, we brought some volume to the location I.T. But, well, we can actually charge this increase in the volume to the withdrawal step, because, you know, whatever we bring here, we will have to withdraw in the next step. So we will just, you know, we will just charge this increase to the withdrawal in the next step. So we don't have to worry about this here. Okay? So this stage is okay. And now there is only one stage left, in which the algorithm withdraws the volume from the locations. And remember, the way it happens is that like, as long as the state is infeasible, so it has too much volume, we just increase each XI0 proportionally to the XI0 plus 1 over K. Okay? So what's happening? So once again, opt doesn't move. So we don't have to care about it. So what is the move cost of the algorithm? Well, each location contributes, you know, this factor of XI0 plus 1K times the proportionality factor d tau. And now when we sum it up, then we will see that, you know, this 1 over K will sum up to n over K, clearly.  And why is it so? Well, it is so because we know that if state is infeasible, what does it mean that the state is infeasible? It means that, you know, the sum of XI0 is too small. So it's actually strictly smaller than n minus K. So we use here to upper bound our move cost by this quantity. And now all that remains to do is just, you know, to estimate what is the change in the potential once we withdraw. So what is the potential, what the change in the potential is? Well, so we just sum over all the locations. And, you know, and what we have here, we just look at the derivative of our potential and, you know, times the change in each of the variables. And, you know, when you do the math, when you take this derivative, then the magic happens and actually each of the terms will be exactly what equal to 1. Because, of course, this is the way it was chosen to. But sort of a nice fact. So we see that the change in the potential is just the sum. Well, we will get some minus.  So this just describes the configuration of the optimal solution. And, well, we know what this has to sum up to. It has to sum up to exactly n minus K. So we see that, you know, the change in the potential has been minus 2, well, times n minus K. And now, you know, once we want to compare this to, well, these two things, the move cost and the change in the potential. And, you know, it's a easy, it's an easy exercise to see that indeed, you know, this quantities work the way we want them. So essentially that the sum of change in the potential and the change in the move cost is, you know, at most 0. So the inequality is preserved. And what we use here is the fact, so to have this inequality hold, we have to use the fact that n is at least K plus 1. Because if it's exactly K, then the problem is not interesting anymore, so we assume that n is always strictly bigger than K. Okay? So that's all. That's the whole analysis. And, you know, just extending this analysis to the, you know, to the case when the CT can be actually arbitrary or when xi 0s can be exactly 0 or exactly 1 is very easy. What is not that easy is actually, you know, extending this algorithm to be able to handle the general cost vectors. So there is some natural way of extending the general cost vectors, but, you know, the first natural extension will not work. There will be some difficulties. So you have to get some further ideas to make everything work, but it can't be done and please see the paper for details. So, yeah, so this is it. So let me just conclude and state some open problems. So, well, what happened here is like we provide the first polylog-competitive algorithm for the case-server problem.   It would be very interesting. And, you know, and maybe a less ambitious challenge but still very interesting would be just, you know, to decide whether, you know, we'll either get rid of the dependence on n or actually maybe prove that it's necessary, yes? So, you know, having a lower bound that tells you that, you know, that you have to have some, you know, well, log star and dependence on the, well, on n in your competitive test, it would be very interesting because I think the general belief is that there should be no dependence on n at all. So, that would be very interesting. So, this is, these are questions regarding the case-server problem, but in general, sort of, you know, the one thing that I think is very important in the grand deem of dealing with uncertainty optimization is that actually I'm not exactly sure whether, you know, stochastic model or online model are the right models to begin with. So, I think that still, you know, sometimes these models work out, but I think they're not the ultimate best models that we could have. And, you know, the big open problem here is actually, like, to find some, you know, meaningful model that will on one hand allow us to get, you know, allow us to get any future results, but then it will also correspond quite well to what's happening in the reality. Okay, thank you.


Welcome to the eighth session in the second module on signals and systems. Let me begin by answering the exercise that I had posed to you in the end of the previous session.  So, I made all of them quite free. There were two different frequencies, two different amplitudes and two different phases. And I said the system is linear and shift invariant, note it is linear. So, when I use the additivity part of linearity, I can recognize that the output is going to be the sum of the output to each of those sinusoid. So, let me put that down. So, answer, I have the system S, it is linear shift invariant stable. It has an impulse response h t and I can define the frequency response of the system. Let us call it h omega defined by minus infinity to plus infinity integral h lambda e raised to the power minus j omega lambda d lambda.   Simple enough, to each sinusoid its own point on the frequency response. For the angle of frequency omega 1, use the amplitude at omega 1 and the phase change at omega 1. For the angle of frequency omega 2, use the amplitude change at omega 2 and the phase change at omega 2 and make those changes and add those outputs and there you are. Now, in fact, look at this expression. Look at this expression again carefully. You see the beauty is you can predict what happens when you have 2 sinusoids to each its own so to speak. We could do this with more sinusoids. If you have 3 sinusoids, you would essentially have 3 term. If you have 10 sinusoids, you would have 10 terms and you can go on carrying that argument further. So, there is some attractiveness in decomposing an input if we could into sinusoidal component. That means, if I could think of any arbitrary input that I had as a linear combination of sinusoids, I am well placed as far as finding out the output is concerned. There is one convenient way in which the output could be found by looking at individual sinusoids comprising the input.  You will recall that this whole module was meant to introduce a change of paradigm, a change of the way in which we look at linear shift invariant systems when it is meaningful to do so. Now, you know recall we have been talking all the time about stable linear shift invariant systems and why stable? Because unless the system is stable, I am not guaranteed that the frequency response exists. So, the frequency response let me look at that frequency response clearly once again. Let me write down the expression for the frequency response and highlight where stability comes in. The frequency response H omega is minus to plus infinity H lambda e raised to power minus j omega lambda d lambda and the modulus of H omega is bounded is finite because of this because of the absolute integrity of the impulse response and that is why stability comes. Now, of course, you can see that stability is a sufficient conditions for the frequency response to exist and now I am going to put a big challenge before you. It is not an easy question and I do not even intend to answer this question immediately, but for some of you who are mathematically inclined you know who have done a course on real analysis or who have some exposure to functional spaces, advanced learners I might call them that. I have a challenge for you let me put that challenge down. Is stability a necessary condition for the existence of a frequency response? In fact, I will give you a hint it is not that means the integral may converge. So, it is very interesting later on we will see that even certain and see not all unstable linear shift invariant systems may not have a frequency response. There are a few linear shift invariant systems which are unstable, but which still do have a frequency response that is interesting. Now, what does that mean? That means that stability is of course a sufficient condition if a linear shift invariant system is stable a frequency response is guaranteed. If it is unstable it may or may not have a frequency response and the challenge before you is give examples of linear shift invariant system which are unstable some of which have a frequency response and give some examples of those which do not have a frequency response. Now, as I said this is a question for slightly advanced learners those who want to take a slightly difficult challenge if you do not want to do it at this stage do not worry. Implicitly you will find the answer will come in subsequent discussions in this course, but I wanted to just ignite your mind at this phase anyway. Now, as I was saying you could carry this argument to two synosoids you could carry this argument to 10 synosoids and then you could even think of a continuum of synosoids. So, for example, you could think of synosoids going all taking frequencies all the way from say 1 kilohertz to 2 kilohertz the whole continuum of frequencies from 1 to 2 kilohertz could have corresponding amplitudes and phases associated and you could think of combining all these synosoids and forming a waveform and you could query what happens when that waveform goes into a linear shift invariant system. Now, that is a slightly difficult situation to visualize. So, at least let us visualize something simpler. Suppose I could decompose one class of waveforms into a sum of discrete synosoids you know. So, you have a discrete collection of frequencies here I had to well we could have 3, 4, 10 or we could go to infinite, but discrete you know countably infinite. Now, in fact that is what is called a Fourier series expansion. So, many of us are familiar with what is called a Fourier series expansion of periodic waveforms. Now, when I have a Fourier series expansion of periodic waveforms I am essentially thinking of that periodic waveform as a combination of synosoids with frequencies which are multiples of the frequency of the periodic waveform. So, suppose I have a periodic waveform with a frequency of 1 kilohertz I am saying that periodic waveform has synosoids of frequency 1 kilohertz, 2 kilohertz, 3 kilohertz, 4 kilohertz and all multiples of 1 kilohertz. So, now I have a very convenient way of dealing with periodic waveforms going into a linear shift invariant system. In principle I could see what happens to each of these synosoil components of the periodic waveform and since the system is linear I could combine at the output the output corresponding to each of those components of the periodic waveform and thus generate the periodic waveform again at the output. So, let me complete one little detail here. I shall show you that if a periodic input goes into a shift invariant system the output has no choice but to be periodic. Let us prove that it is a simple proof and we can do it in a couple of minutes. Lemma a periodic input to a linear to a shift invariant we do not even need linearity produces a periodic output. Well, that is very easy. Let the input be x of t and let the period of the input be t, whereupon we have x of t plus capital T is equal to x of t for all t by definition. Now, let x t result in y t as the output of the linear shift invariant system. Now, from shifted variance what do we infer? x t plus capital T should result in y t plus capital T because of shift invariance and of course, x t results in y t and therefore, these two must be equal since these two are equal for all t, these two must be equal for all t. Therefore, we have proved the statement y t plus capital T must be equal to y t for all t and we have proved the lemma that the output is also periodic. In fact, the output is also periodic with the same period. So, now we have a clear situation that we deal with.  In fact, we are guaranteed the output is also periodic with the same period on account of shift invariance. And now on account of linearity, if I could take an arbitrary periodic input and decompose it into a combination of synosoids, then I could find the output periodic waveform by seeing what happens to each of the synosoids individually and we shall take this up in much greater depth in the next few sessions. By recapitulating the idea of a Fourier series decomposition and generalizing it to what we call a Fourier transform. Thank you.