So, yeah, everybody knows the British Museum, but who knows Caldwell-Amtlauwek? I think not so many of you have ever heard of this museum. And so I want to introduce you to the museum and to a small special exhibition we have launched there this year. Also, I think about quite the same topic like you did, but I think on a completely different terrain, because it was in Germany, and in Germany we don't have this debate, like the scientific community in the Great Britain or on the British Isles has about, yeah, would we like to question our common opinion how the Calds or this Cald tribe moved and what they were doing? So it was quite risky for me as a scientist to do this. But, yeah, let's have a look at how we did it and what people say to it. First of all, I wanted to tell you a little bit about my background, as Phyllis already told. My PhD was on museums, and I did quite a similar thing on German museums ten years ago. And I also had some kind of form in which I visited 122 museums, and I did also literature and online research on another 250 museums. So I covered a large part of the German archaeological museums landscape in my survey that I did for my PhD. So you can see here the map where I mapped. I think I hope you can see all the dots of the museum that present archaeology, because I didn't only use or employ the archaeological museums, but also, of course, many museums like Small Heritage Museum who present a little bit of archaeology. I also tried to include those. There was a bit of statistic of what I was doing, how to separate different themes of the museum, or display, oh, that's the first one. How would I get that? Yeah, yeah. So, yeah, this is what I was doing. I also tried to have a look at the displays and, yeah, somehow categorize them and see what the difference of the various museums was. And what I was also doing was how one of my larger topics was how archaeology was presented in these museums, because mostly we show the nice exhibits, the nice objects, but a lot of museums don't talk about how archaeology is working. So this was one of my topics and what I also wanted to explore, or more intensively to explore was how do we engage with the present times, and these are just two examples from the Hamburg Museum above and the Museum at Nibra where this Bronze Age disc was found. There's a very nice museum as well and they tried to engage present times with the use of waste. The left picture above, the right picture above is modern waste and compared to ancient waste. And also the other museum is very much engaged with looting because the disc was found by looters and had to be retrieved from the antique market very spectacularly. This is what I'm normally doing. I'm a landscape archaeologist so it's completely different, but I'm engaged in British-ized archaeology and also in Iron Age archaeology in Germany and so I'm quite familiar with the debate and what's going on. And of course there's not only big, large exhibitions in Great Britain there's also a lot of Celtic exhibitions in Germany like for example the big exhibition in Stuttgart and there was also a larger exhibition in Verklinger-Hütte that's somewhere in the west of Germany and both exhibitions raised about 200,000 visitors each so it's some different things than we do at the Celtic event. So of course Julia always told and I think some of us like the quite similar there's a lot of literature, we know everything about the Celts and the public can read everything and all the things we want them to read and also the things we don't want them to read like for example the Celts and discoveries and there's covering the Middle-Earth or something like that and there's also of course this large community of modern Celts who find their identification by being Celts especially in the United States and in Canada and this quote I liked quite a lot that there are yeah I just read it, it's not that important at the moment so and of course all these modern recreations and it's not only happening the one image is familiar of the Celtic languages but it's also happening in Germany because in Germany and all the German speaking countries of Austria and Germany and Switzerland they have got a society that is called Ketten-Belten and this is all museums that deal mainly with Celtic archaeology or objects so and of course the Ketten-Belten is part of this Ketten-Belten Celtic worlds and so we are also they are quite in some kind of network about displaying Celts for the public so this is finally the Celtic world at the Glauberg and you see it quite well in the museum and it's based, you can see it here it's based a tiny bit, 40 kilometers in the northeast of Frankfurt so it's quite central in Germany but of course it's remote you have, even from Frankfurt you have to drive about an hour there and yeah just in the landscape and it's at the side, but of course wait a second, I'm going to show this one first of course it has got, the statue finds like the statue, the sandstone statue of this man that was found in the vicinity of one of two big burials and in these two burials were three burials with a lot of really really fantastic finds and people go there just because of these spectacular things and the very unique things at the Kettenberg it's all original, they don't have the copies but they, the community they argued a lot with the state of Hesse where they live and they finally were allowed to present everything at the place and that's quite unique and it's really a fantastic museum go there if you're in Germany and of course being in the countryside is different than being in a big city and they have to do a lot of commercials and I try to, I love this bag for bread actually I hope you get the notion if the kids from the Kettenberg had the bread from this special bakery they would be still alive and of course they also do a lot of promotion in other ways and you can already see that it's not always helping the case of being a bit more critical to what we display because of course equalizing what we find in the state or German state of Hesse with the Gauls in France is a complicated thing so this is the entrance to our exhibition that we launched in the Kettenberg and yeah, there is no reason actually for this museum to present an exhibition in this direction but they wanted to because visitors were asking them a lot of questions for example things like why don't you display things from Ireland we thought Ireland are the Celts and in Ireland are the Celts and how does this connect and all of these things so the guides in the museum were quite annoyed and wanted an exhibition about this and then I thought ok this is my hour this is my time and I can put all my things into this exhibition as well and so we did and yeah, of course we did have not as much room as the British Museum we were limited to 100 square meters so it's like one floor in another one family house or something and we had to reduce anything and of course the budget was much lower and so we could not borrow fancy things from anywhere but fortunately we had the Wermisch Germeister Zentral Museum in Mainz at our display and they have got copies of everything and for the fancy clients of the world they made copies and very very good copies couldn't tell the original from the copies in most cases so what we were doing the middle part was maybe about things that connected to the reverse of the Celtic notion in the 19th century a studio already referred to we had a lot of history resizing imagery in there to make this place and of course we had all these beautiful finds the talk of tristing I think most of the things were displayed at your places the hand from the tree and we didn't do much about the archaeological explanations like what the designs are we just displayed them and showed them to people and the outer space of the walls were covered with these kind of flanks and we divided them in four parts and they got all different cuts so that people would know different things start there we started with ancient sources and what the historians say about that of course in Germany we have two who had quite concrete ideas about what the Celtics were and that they would never have been able to build a nation that because they were only into war and into espy and things like that so that was quite interesting the designers reduced me to very very limited space of text and that was a really good thing because in the end with evaluation we would see that this was still too long but yeah the next part was about the languages and since I was studying Celtic studies I had a good idea so I could also capture this area as well and we covered the archaeogenetics and in the course the archaeology got a larger space and we were concentrating mainly on what archaeologists opinions of Celtics are and what we mostly wanted to display is what archaeologists know that they are not so much interested in the nationality of people or anything but they want to study things in their local surrounding in their environment so that's what we were doing with the things and of course in the end there was a larger part of the modern count because that's also something that interested people very much and then there was of course at the things we display there was always a short notion that there would be more explanation in other media stations so we had two media displays where people could explore very deeply into different topics and we were astonished that a lot of people would do oh I think I'm in the wrong presentation actually okay I don't have time anyway I wanted to tell you that we also did a small evaluation we evaluated 100 127 visitors and asked them about their opinion and I would skip all the part of the formal things and come mainly to what they think they thought our texts were much too long or still much too long or at least 30% of them thought they were too long and they also thought that we were that the objects were chosen quite well and that also the topic was very interesting to them and in the end I think that's a crucial thing is we asked them two questions which they could choose what they learned from the exhibition because we wanted to be very short and didn't want to disturb people to belong with this survey and we asked them I think it was something I have written it on the slide something like cats were people an ethnic group that covered large parts of Europe was one of the things and they nowadays present still present in the western parts of Europe and the other thing was that we said we don't know what cats are but because different disciplines have got different opinion of what they are and check 75% really check the second box so at least this goal was achieved with the exhibition and it got a lot of media in press and social media and of course there was a large framework program about it we destroyed all our nice things we taught people because we had a Celtic folk band so everything was right and the main thing that I learned from how to present this topic to people in a way that they can understand what we are talking about is that it also had a lot of people working at the museum because they now have a much better notion of what they are telling and really or in the brainstorming before the exhibition we really talked about everything and every misconception they had themselves because of course the guide they are not archaeologists or anything so we could really work out a lot for the museum itself this exhibition we got a lot of requests for the exhibition to go on trams and in parts of the exhibition we also go into the new exhibition at the flower sorry for the time


Bernard sat down for a nearly hour-long interview with Robert Costa of the Washington Post and I Thoroughly enjoyed this interview Bernie Sanders was really at his best and the entire thing was phenomenal I'll link to it down below if you want to watch it but I want to show you some highlights here and What I found to just be great because not only did he make some great points about the state of the 2020 race as well As what his presidency would look like But he didn't hesitate to take some some pretty bold shots at the venue itself, which I found the most entertaining Thanks so much for being here Bank of America really sponsoring this Let's just get into the interview The awkwardness that you can hear in The interviewer's voice Robert Costa it was palpable and I thoroughly enjoyed that This is why I love Bernard. He's at his best when he's outspoken when he doesn't hold back You can tell when Bernie is pulling punches, but when he just you know is himself It comes across as organic and it's just he shines and he really shined throughout this entire interview But I've got two more really short Less substantive clips here. So Bernie was asked about what Joe Biden said in the event he was the nominee and he went up against Donald Trump and His response was that he would consider challenging Donald Trump to a push-up competition or something along those lines in the event Donald Trump question if Joe Biden was weak or something along those lines Bernie's response here was perfect This president Biden said in terms of fighting president Trump beating president Trump on morning Joe this morning He may challenge the president to push-ups I'm no comment on that That was the best response ever. It was short but sweet But effective because look that level of stupidity It really shouldn't be dignified with a thoughtful response What Joe Biden is going to do if he becomes the nominee, which I hope he doesn't but in the event He's the nominee it's going to be a gigantic pissing contest between him and Donald Trump Whereas if Bernie Sanders was the nominee, we know that it would be about the policy substance Donald Trump would inevitably call him crazy Bernie tweet about him attack him But Bernie Sanders would remain glued to the policy agenda and that's how you win So you can't really dignify these things that Joe Biden says because he also has this kind of I'm a tough guy persona Which is just it's insufferable to me It's insufferable like who does that play to does that really play to members of the Democratic Party? Is that gonna excite them to come out and vote for you? I think Joe Biden thinks so because he's a narcissist like Donald Trump and it's insufferable So Bernie's response there was absolutely perfect But one last thing I want to touch on here before we started getting into the policy details is A question about busing came up The interviewer was trying to frame it as if Bernie Sanders made an anti busing statement So Bernie would be technically in the same camp as Joe Biden Bernie Sanders shut that shit down in a beautiful way in 1974 You said that busing policies were well-meaning in theory, but sometimes result in quote racial hostility. What else did I say in that? Tell me no you got it there read Read the whole book. I don't have the whole quote.  That's why I didn't include it. Sure. Yeah, that's definitely why you didn't want to include it Because you know, it was a curse word even though Bernie Sanders said the curse word and you didn't Sensor what he said. There was no bleep So you see this is what the media tries to do. They try to take Bernie Sanders out of context So people will hear what he's saying and Interpret his words in a different way than they are intended to be interpreted I mean the same thing thing happens when it comes to raising taxes to pay for Medicare for all They'll often ask Bernie Do you think that Medicare for all would require you to raise taxes on the middle class?  How despicable, but I mean it's it's not surprising This is the Washington Post and as you're gonna see here Bernie Sanders did not hesitate to take even more shots at them And it was amazing So what we're gonna see now is Bernie Sanders will explain what we can expect if he is the president because we have this idea of The legislative process, you know Somebody will propose a policy and then it'll be debated between Republicans and Democrats and then they'll ultimately be a Watered-down version of said policy, but what Bernie Sanders is going to do here is explain look my Presidency is not gonna be a normal presidency We're not gonna continue to do politics as usual I'm going to make the case that we are not executing my agenda as president We're executing the agenda of the American people and he has a very specific plan To name and shame people who actually don't want to get on board with policies like Medicare for all And I loved everything he said here because he alluded to it in the past But he was very specific here about what that would look like in practice President Obama had to make concessions on the ACA. Would you be willing to make concessions as president on Medicare for all? I think one of the points that I want to make is a Bernie Sanders presidency would be a different type of presidency In other words, I hold the radical vision that maybe just Maybe a president and a Congress should do what the American people want them to do. I Know that's a radical idea In reality Mitch leader McConnell doesn't Doesn't seem to pay a political price for not taking up the House Democrats bill. Let me talk about reality. All right, and again I you know what we are trying to do is something a bit different than other presidents. That's my history politically and What I believe is that right now you have a Congress That is heavily done. We especially the Republican Party. You tell me I maybe the Washington Post might want to do a poll on this And that is to ask the American people whether they think we should give huge tax breaks to billionaires greatly expand military spending and then cut back on Social Security Medicare Medicaid and education Now if you did a poll how many what percentage of the American people would think that's a good idea But that's exactly what Mitch McConnell believes. All right way out of touch with the people of Kentucky with the people of America What we need is presidential leadership that goes to Kentucky by the way a very poor state and says that Stand up and tell your senators that health care is a human right that you will save money by moving toward Medicare program Right now in my campaign for president the thing I'm most proud of is that we have over one million Volunteers the reason I believe we're gonna win the Democratic nomination and defeat Trump is because of our grassroots Movement and as president what I will do is expand that movement and create a process where people all over this country Become engaged in the political process working-class people young people in a way that we have never seen before and put pressure on Republicans that I will do everything I can to make sure by the way that the Republicans do not continue to control the Senate What put pressure on Republicans and Democrats to move this country forward in a way that reflects the needs of the working class of this Country what does that mean? It means raising the minimum wage to a living wage It means rebuilding our crumbling infrastructure and creating many millions of decent paying jobs It means expanding the trade union movement making it easier for workers to join unions It means demanding that the wealthiest people in this country start paying their fair share of taxes So I know we're in Jeff Bezos building But Amazon last year made over ten billion dollars a profit. What are they paying taxes? Not a nickel in federal income taxes. Does anyone think that that is vaguely saying? Okay, first of all, I loved that jab that he took at Jeff Bezos there at the end second of all This right here tells you everything you need to know about the entirety of the Democratic Party primary in 2020 There's one candidate who's truly Fighting for you and actually has a plan to get your agenda implemented legislatively It's Bernie Sanders. He's saying here. I am not fighting from my agenda. My agenda is what the American people want He says what we need is presidential leadership that goes to Kentucky Mitch McConnell's state a very poor state and Says stand up and tell your senators that healthcare is a human right He'd put pressure on Republicans and Democrats to move this country forward in a way that reflects the needs of the working class in this country Understand what he's saying and why this is so unprecedented He's saying I am gearing up to go to war with the special interests with Republicans with members of my own party If I'm president because I know that I will be opposed by all types of forces if I'm elected So what we're going to do is fight tooth and nail and we know that we're going to have to do this in order To get what we want Implemented all campaign in Kentucky if Mitch McConnell is still the Senate majority leader I will go to the districts of Congress members who are in the Democratic Party and tell their constituents Why they're siding with the health insurance industry as opposed to them This is what you have to do you play politics and you fucking crack skulls Bernie Sanders is the only person who's explicitly saying I will not be doing politics as usual And no, this isn't you know the Obama promise of hope and change. We're gonna change the way we do politics He's saying yes, we're gonna change the way we do politics, but here's my plan This is specifically what I will do to make sure that your agenda is implemented. It's amazing to see somebody say this I mean, how could you not vote for them? If you plug your ears and ignore Bernie Sanders Then you have no reason to complain because you have a candidate who's willing to do your bidding unequivocally uncompromisingly Do you expect any other presidential candidate to go to the home state of a different lawmaker and Campaign against them in such a brazen way. I mean who would do that? He knows to be attacked by the mainstream media He knows that this would invite, you know in intraparty warfare perhaps Democrats would attack him the DNC would attack him They would try to primary him in 2024 But he doesn't care because he knows that there's no other way that you get something like Medicare for all you don't have a choice if you genuinely believe that we should have Medicare for all and You know that that's what the American people want You have no choice if you're not willing to do this you're not gonna get Medicare for all So all these other candidates like Elizabeth Warren she could say look I you know, I support abolishing private insurance, but at the end of the day Who do you want battling for you?  This is such a fascinating interview Bernie Sanders truly is one of a kind like I would be surprised if we see another Politician like him who's this strategically savvy in our lifetimes now moving on Bernie Sanders hasn't been accused of being too consistent And that's apparently a negative. He has the same exact message as he did in 2016 But what's interesting is that there are so many swagger jacking Santrists who are copying his message. They're plagiarizing him But yet he's being accused of being a one-trick pony so he was asked how he distinguishes himself in a primary where there's a lot of fake Bernie Sanders who are running to be Bernie Sanders light and This is his response, which I thought was just great And there's a real choice as you outlined today between Vice President Biden's view of the world and your view of the world But you have a crowded lane this time a lot of people echo in your views stuff you talked about in 2016 How do you persuade voters that they should side with you? It's crowded this time around I think I would ask people to look at the record you're on the record No, no, no, no, no, no, no, no, that's no I think it is fair to look at the record I mean anybody can come up with any position today or they can do a poll I said, well, boy, I bet it's about Medicare for all. It's popular among Democrats. You think some Democrats have Well, you can make that determination all that I'm saying is find out, you know You talked about other people saying what I'm saying four years ago was not so easy Because I got condemned by the Washington Post and everybody else about talking about raising the minimum wage to 15 bucks an hour Talk about Medicare for all single-payer system talking about making public colleges and universities tuition free and dealing with student debt Talked about a trillion dollar investment to rebuild our crumbling infrastructure talked about criminal justice reform and comprehensive immigration reform I was there. I did it first enough this time. No, it's not enough But it should tell the average voter that I am prepared to lead in a different type of way that I am prepared to take on the political establishment to take on the corporate Establishment and stand up for the working class of this country one He took another jab at the Washington Post, which I loved and to he made a phenomenal point I mean, you're running to be president because you believe that you have leadership Qualities that are necessary for that position. So he says look I led on these issues. It was politically Not expedient for me to be talking about Medicare for all or you know It was promoted this idea that you shouldn't talk about these policy ideas that are too progressive or too radical But he said I just ran on what I thought was, you know, the right policies I led the charge and now everyone else is following behind me. Nobody talked about Medicare for all Even people who are deemed progressive Elizabeth Warren. She didn't talk about Medicare for all until I talked about Medicare for all Why because I'm a leader. They're following me. I'm the one leading on these issues So do you want diet Bernie Sanders or do you want the real deal? And that's exactly the point he needs to hammer home He was the leader while everyone else was too afraid playing politics to talk about these issues that we all have been wanting For decades. I mean single-payer healthcare is not some new idea. This is what liberals have been wanting Left-wing and progressive people. They've been wanting this for decades. I've always wanted single-payer So the fact that Bernie is just the only politician who capitalized on this policy You know, that shows not only that he's politically savvy, but he's also brave because you know Strategists in DC would say, you know, you just can't take a stance on an issue until it pulls out above 50% once it reaches 51% you can endorse it But you know, if it's below 50% Stay away from that policy Bernie isn't a focus group driven poll-minded politician He speaks authentically from the heart And that's why people like him because when he says I'm going to fight for Medicare for all We can believe him because there's no conflict of interest that suggests He's going to you know, uh, not do what he's saying He's going to do when he gets elected because the people who helped get him in power Are not the industries who would benefit by killing off a plan like Medicare for all So again, I will link you to the full interview. It's absolutely Phenomenal, I would encourage you to watch the entire thing Bernie was really at his best here. He was snappy. He was charming. I loved it Um, we need to share this interview because we need people to see Bernie Sanders, you know, uh in his best uh in his best light, right? He's phenomenal here and he explains very clearly How he's going to be fighting for people if he's elected and people need to see this because they need to see That there's one person in this race. Who's the real deal? It's Bernie Sanders and he makes that crystal clear.  So don't hit the subscribe button, okay And whatever you do folks do not hit the notification bell either Mike treats me so unfairly


So, again as the title says the talk is about the bandwidth problem in digraphs and we will study it from the view point of exact exponential time algorithms and approximations clubbed together. So, let me begin with the definition of the bandwidth problem. So, this is quite a classical problem. So, in this problem you are given an undirected graph G and the goal is to come up with an ordering of the graph where informally speaking the end points of any edge are not very far away in the ordering. So, this is formalized here. So, you want to find a permutation of the vertex set such that let us read the English thing first, a permutation which minimizes the maximum stretch of any edge. So, this is written here. So, look at any edge and pi of u denotes the position of the vertex u and pi of v denotes the position of the vertex v in the ordering and look at the difference between the positions. So, and look at the maximum such difference, this difference is called the stretch of the edge u v. We want a permutation that minimizes this maximum stretch over all edges. So, let us look at an example of this. This is the graph G and this is one ordering of the vertices of the graph G and if you look at any edge of this graph in this ordering, if you look at the two end points of any edge you notice that the difference between the position values of two end points is at most two and in this case it is not difficult to see that one cannot have an ordering where this difference which is called the stretch of edge is one. In this case we say that this ordering has bandwidth 2, this ordering is an ordering of this graph and it has bandwidth 2. So, as I said before bandwidth is a classical problem, it occurs in a lot of real life scenarios and one typical framework in which it occurs over and over again is the following. So, here it is like imagine the red hut like things to be facilities and the blue edges or arcs represent the links between the facilities which denotes the need of the facilities to communicate with each other and they are arranged in a linear fashion in a linear ordering and the distance between two facilities in the linear order is proportional to the cost of communication between two facilities or the delay in communication or the effort required to communicate between two facilities. And again in the bandwidth problem the goal is to arrange the facilities so that the effort required to communicate between any two facilities or the cost of communication between any two facilities is minimized. So, this is a typical framework that the bandwidth problem encapsulates. So, with this article our goal is to add some nuances to this model, we will see what those nuances are and then we will see a problem that encapsulates those nuances of the model and then we will try to solve that ok. So, let us first see what are those nuances. So, there are two nuances that I have added here. One is if you notice now the links are directed earlier the links were undirected. So, what does directed links mean? So, as we said in the earlier case undirected links represented the need to communicate, but the need to communicate might not be mutual. I might want to talk to someone, but it might not be the other way around especially for example, in deliveries model. A might want to deliver something to B, but that might not be the case. It might not be the case in the other way. So, that is one thing and the second thing is a few like I am sure you would have noticed that I made this road or this layout slanted it and this slant represents that like suppose the facilities are to be placed on some slope ok. So, if that is the model it is, but natural to assume that if facility at the bottom of the slope wants to communicate to the facility at the top of the cost it should be harder right and whereas the other way around the facility at the top of the slope wants to communicate with the bottom of the slope it should be relatively easier and we want to and we want to encapsulate these things into a problem ok. So, for example, in this case in this particular example if you notice like if one wants to communicate to three like the cost of communication is two by two I mean like it has to go two steps to communicate to three right. Whereas if I look at another ordering like this is an ordering where I have just reversed the location of the facilities like it was one two three four five six that is six four five four three in this order if you notice that any facility which is below like and look at the facilities on the top of it to which it wants to communicate all those facilities are located at a distance one from it. So, if you notice these larger links they are downward links now. So, any facility that wants to communicate to a top like a facility that is higher up it doesn't have to go to a distance of more than one right. But for the below things for the reverse things we don't care I mean as of now we assume that the downward communication is free because it's easy ok. So, this is what we want to encapsulate and this can easily be encapsulated in this problem which is the digraph bandwidth problem. So, what we have done is we just lifted the bandwidth problem on undirected graphs to directed graphs. So, in this problem we are given a directed graph G and the goal is to find a permutation of the vertex set such that in this case we only want to minimize the stretch of the forward arcs the forward arcs are the ones whose head you know whose tail appears before its head in the ordering. And so, if you notice this problem actually models this because first of all there are directions in the graph and secondly because we are only interested in minimizing the forward stretches we are only interested in minimizing the forward communication and we assume that the backward communication is for free at least in this model ok. So, this is the problem of interest for this top and another remark that I would want to make is like this is not the previous slide is not the sole reason that we are interested in this problem like as a theratation like if there are if there is a classical problem that is well studied in undirected graph it is it like it is a natural curiosity I assume for a lot of theratation. So, see what happens when we lift that problem to directed graphs because directed graphs like behave very differently and problems become very significantly harder there and to justify like and now there could be many ways of generalizing the bandwidth problem to directed graphs and then amongst all the possibilities why did we like why did we choose this possibility where we are only considering forward arcs and working with it. Sorry I mean that is subjective, but in this model we consider that reverse is free like I mean I mean you could consider models where you can also add some weights on the reverse arcs, but in this problem we do not like because this problem itself is like considerably hard. Could be yes I mean we have not we have not studied that, but yes that is the belief it could be more harder I mean. Expensive. Expensive as in. Expensive as in. Yes. Expensive as in. No sure like so the motivation for coming up with this model was again I mean imagine like you are placing some stores on a hill station and there is a slope there and you have to place the facilities on a slope and suppose some deliveries have to be made between the facilities and like and on hill stations are normally on hills the cost of traveling upwards it's significantly much more significantly more than cost of going down so there are links there are links so links will tell us I want from where to where I want to go if there is a link from A to B I want to go from A to B. Now when I have placed these links on the slope suppose I have placed A below B then if I have to go from A to B I have to go from down to up but if I have placed A up above B then I have to go downwards. So now the links are already there we know this communication has to happen so the best cases we make sure that like everyone only does downward communication but that's not always possible because if the graph is not a DAG you'll have forward arcs also so the goal is to make sure that if at all there are forward communications that are going to happen you ensure that like the forward communications are not very costly but as you said of course this problem makes sense like you can add some weights or some cost to the backward arcs also but that's not what we consider here. Okay so yes so I was saying that as a theoretician like so we have pulled this problem up from undirected graphs to directed graphs and then why this generalization to directed graphs there could be many ways of generalizing it but to justify that I just want you to look at this like this is some sample of problems the this side represents the undirected variants like the definitions in the undirected case and this side represents the definitions in the directed case just let's just look at these two of them so for example cuts the way cuts are defined in undirected graphs it's like you want to find a partition of the vertex set such that you want to minimize the number of arcs going across the path but when you generalize it to directed cuts a natural notion is now you want to minimize the arcs going in one direction you fix one direction and you want to minimize that right similarly there is another cut layout problem called the cut fit problem where you again seek for a layout linear layout of the vertex set and the goal is that if you look at any prefix of the ordering for example prefix is like in this case the first three vertices is one prefix if you look at any prefix you want to you want to ensure that there are not a lot of edges whose one endpoint is in that prefix and the other is in a suffix and you want to like go over all such prefixes so this is the cut width in the undirected case and again when you go to directed case instead of saying that we are interested in the arcs going from going between prefix and suffix you fix a direction for example in directed cut foot we say that we are only interested in arcs that start from prefix and end at suffix and we are not worried about the arcs in the other direction right so and similarly there is another another problem there are a bunch of problems and this is this is a typical way in which layout problems are cut problems are pulled from undirected settings to directed settings in that setting we believe that this is a fair enough generalization to directed graphs and why I am even trying to justify all this like if it is so natural and also another thing the problem name if it would have striked to someone why did we use digraph bandwidth and why not directed bandwidth I mean going with the convention that's because the bandwidth problem was earlier studied on directed graphs but this was studied only on DAGs and when I said it was studied on DAGs it doesn't mean that they had defined a notion for graphs and it was studied on DAGs the definition originally existed only for DAGs so this was and and they named that problem as directed bandwidth problem so in literature directed bandwidth is the following problem so given an undirected so you're given a directed acyclic graph G it's a DAG and you want to find a topological ordering of the DAG so there are no backward arcs in the ordering which minimizes all the stretches of all forward arcs in this case all forward arcs are all arcs so the stretches of all arcs so this was studied but this is not what we study so yes so again this paper is about studying diagram bandwidth problem from the viewpoint of moderately exponential algorithms and since it's a layout problem an n factorial algorithm is clear when n represents the number of vertices in the graph so the first step like like like the first question that arises is can we go from n factorial to 2 power order n and this paper is an attempt so of course we haven't resolved this we still don't know if there's a 2 power order and algorithm for this but as you'll see later the results that we get are like all of them have running times of this form but of course they are caveats we'll see so that's the goal and again before describing what we prove or what our results are I would like to give you a picture of the literature from the undirected bandwidth problem just so that we see how our results fit the bigger picture so undirected bandwidth has a rich literature like even from an algorithmic viewpoint and I've just sorted some things here so to begin with this problem is NP hard this is W hard this is APX hard it is just hard and this hardness is carried forward to our diagram bandwidth problem also because it clearly generalizes the undirected bandwidth problem but this is XP by XP we mean that there is an algorithm there is a polynomial time algorithm for a fixed value of bandwidth for example if you want to determine if the graph has directed diagram bandwidth at most five ten a fixed number then there's a polynomial time algorithm but because it's not FPT it's XP this polynomial time is uniform like it grows with the value of b so it's like an n power f of b algorithm and this is the thing and then there is this study around single exponential algorithms for this problem so the first single exponential algorithm appeared in 2000 and that had running time 10 power n and this was followed by like improvements of the base so this is one thing and then the best the currently the best known single exponential algorithm has running time 4.383 power n and then there was an attempt to improve the base of this algorithm and people succeeded but again with a trade off so the succeeded in designing a 2 power n algorithm but that came at a cost of introducing trivets in the running time so here T represents the trivets of the running time and not just introducing trivets at the in the running time but also the trivets like it costs as as an at an exponent of n so that's the this is this is a result and then the best known approximation because it's APXR so the best known polynomial time approximation is log cube log cube n and again because it's APXR we don't expect constant factor approximations in polynomial time there is a study of designing constant factor approximations for this problem in exponential time because again because the problem is APXR already so along that line there is a two-factor approximation that runs in this time and there is an approximation scheme 1 plus epsilon approximation algorithms whose running time is this and if you notice this running time is single exponential but again there is a dependence on T in the running time again T is the trivets of the graph okay so okay so this is the thing so we have a set of results but there are two results that are along the lines of the undirected bandwidth results and which I would like to point so one is we also have a result similar to this as you will see which where it is a 2 power n algorithm for digraph bandwidth and there is an n power T dependence the trivets dependence and then we also have an algorithm we also have a result along this direction so when I say this direction so we also have an approximation scheme for digraph bandwidth so we are we can design 1 plus epsilon approximation algorithms for the problem and in our case we are able to get a running time that's independent of T it doesn't depend on trivets but note that their algorithm like if you forget about T the other things are sub exponential in n it's log n and root n we don't have that we still have n there but it's a single exponential approximation scheme for digraph bandwidth so yes so now I can talk about my results so these are four set of results so again these are algorithms all of them solve the digraph bandwidth problem and the blue colored things represent the running times of different algorithms so for example the first algorithm runs in 3 power n 2 power m time m is the number of edges again in the first glance it might look like a stupid algorithm there's an m sitting at the top of the exponent but note that this algorithm already gives you a 2 power order and algorithms for the class of sparse digraphs and then the second is as I said the algorithm along the lines of Amini's results so we have a 2 power n plus T plus 2 log n kind of an algorithm and then this is an algorithm which is which works for the general case so it's running time like let's just focus on one term let's say this it's running time is 4 power n B power n where B is the optimal bandwidth so in scenarios where B is small for example if B is at most this this is a 2 power order n algorithm and then this is the single exponential time approximation scheme that I talked about so for any epsilon real epsilon greater than 0 one can find a 1 plus epsilon approximation for the problem in this time so if you notice this is like f of 1 by epsilon power n time so in whatever time I have now I'll be focusing on this result I'll give I'll give a sketch of how we get to this result and yeah so note that this is a single exponential time algorithm and on that note I would like to remark that all the results that we like all these results on undirected bandwidth which talked about single exponential running time they all had one template I'll talk about what the template is so they all had one template and the reason one is not directly able to design a single exponential algorithm for the digraph bandwidth problem is because things like there are there are problems that just fail in that template and as of now we don't know if not that template then what should one be following to get single exponential algorithms for this okay so I'll talk about that first and then I'll come to our result okay so from now on we'll be working with the decision version of the problem so I'm also given a graph chain I'm also given a number B and the goal is to determine if the there is a ordering of digraph bandwidth B okay so as I said let's look at what people did to design single exponential algorithms for the undirected case okay so as I said all the algorithms had the following template so they were based on what I call the bucket then order things so it has two phases there is a bucketing phase and there is an ordering phase the ordering phase is different from for different algorithms and that's how they get different running things but the bucketing phase the goal of the bucketing phase is the same so let's talk about what this bucketing phase is so let's say this this figure denotes the solution ordering so this is what the solution looks like okay so in the bucketing phase the goal is the following so we have some buckets and they have some sizes so these sizes again vary with algorithm to algorithm so there is one algorithm that use B by 2 there are different algorithms that use different numbers but let's not worry about that but the bucketing phase desires to achieve the following property so so what is a bucketing phase in the bucketing phase you want to ensure that you have achieved the following if this is the solution ordering that you have in your head that in the bucketing phase you should have ensured that the first B by 2 vertices of this solution ordering goes in the first bucket the next B by 2 vertices of the solution ordering goes in the second bucket and so on so in some sense you have you have some handle of how the solution will look like so once you have this bucketing you know there is a solution where you can rearrange these vertices in some way followed by rearrangement of these vertices in some way and so on and get a final ordering like you don't have to do rearrangements amongst buckets that's the goal of the bucketing phase and now believe me i'll not talk about this order phase because it's different for different algorithms but believe me that once this bucketing phase is done like you get such a bucketing things become easy like you can drive the algorithm from there and so let's talk about how people achieved the bucketing phase in the case of undirected uh undirected bandwidth and this bucket the al dino for the bucketing phase was the same for all the algorithms so in the bucketing phase you just fix you start with a vertex of the graph an arbitrary vertex of the graph let's say v and you guess which bucket it belongs to to to achieve the motives of the bucketing phase so to begin with we will have two power n by b choice like so if if we have buckets of size b by two there are n vertices you will have two n by b buckets so our vertex we will have two n by b choices right but note that once we have we have spent this much guesses to decide the bucket of v other things become easier for example look at look at any neighbor of v okay so if you look at a neighbor of v uh given that v belongs to this bucket the neighbor of v doesn't have a lot of choices so because the bucket sizes are of size uh b by 2 the the neighbor of v cannot be placed for example in this bucket because if you place v in this bucket there will be so many vertices in uh like in between you and v which will contribute to the stretch of the edge right so once v is fixed the neighbor of v can only go either to the same bucket as v or to this or this bucket and this and this so like there are only five choices where the neighbor of v can go to right so once the bucket of v is decided its its neighbors vertices its neighbors buckets only have five choices each right and so we can assume that the graph is connected it doesn't spoil the problem so in that case one can achieve this bucketing phase in this much time like five power n time and that's good enough for us we are we are aiming to design single exponential algorithms right so the this is a simple bucketing uh phase for the undirected problem and uh but when it comes to directed graphs note that this is not true so even when you've decided the bucket of v its neighbor if its neighbor appears before v then it doesn't have a lot of choices but if its neighbor appears after v then it will contribute to a backward arc and in which case there is no control over which bucket it goes to okay so this is where it fails the for the undirected case okay so this was the bucketing phase for the undirected case now again coming to what how are we able to cope up with this and design an at least an approximation algorithm so for that I'll uh yeah I'll I'll just give uh I'll I'll just sketch the proof of designing a two approximation algorithm in two power order n time though I promise one plus epsilon I have a last slate but I don't think I'll have time for that but the idea for that is based on the idea for this okay so now uh how do we go about doing this again it is based on bucketing but it's not based on the bucketing that we were trying to do for the undirected case it was it's based on a different kind of bucketing and let me define what that bucketing is so in this case we do a bucketing where buckets have sizes b and the falling properties hold if there is an edge between uh if u if u v is an edge then either the bucket of u appears after the bucket of v in which case like this will correspond to a backward arc if not then u and v should be in adjacent buckets okay note that the previous bucketing also satisfies this the previous bucketing was the one from which you can derive a solution right the previous bucketing will also satisfy this like if if you have buckets of size b but it's but the other way around is not the case like even if i give you such a bucketing there is no guarantee that there is a solution which can be obtained by taking some permutation here followed by some permutation here and so on right so this bucketing is necessary to get the solution but it's not sufficient but what we show is that this necessary bucketing is enough to get a good approximation okay so this is what I'll call a useful bucketing so again it is it is assigning vertices to buckets of size b such that uh look at any any arc either it's a backward arc in the bucketing or if it's a forward arc then the endpoint should be in consecutive buckets or maybe the same bucket this is this is my definition of a useful bucketing and now first of all how do i find useful bucketing but forget that first but if we have a useful bucketing do we see a two approximation algorithm suppose i give you this bucketing if i have this bucketing i'll i'll give you the following ordering i'll order the vertices in the first bucket arbitrarily followed by the second bucketing and so on you know how long can a stretch of an arc be any forward arc was between two consecutive vertices the bucket sizes are b and b so the stretch of the arc cannot be more than two b right it's as simple as that's enough to give such a useful bucketing and uh now how do we get such a useful bucketing so for this we do the following actually maybe i should have pointed it here during the bucketing phase see the the essence is the falling so the reason this bucketing phase didn't work for directed graphs was because some some vertices will correspond to backward arcs and we didn't know which vertices will correspond to backward arcs right so at at a very meta level like it's it's it's not it's not clear a straightforward but like if we have some information about the edges that are gone going to be backward arcs there is for example if i knew all the edges that are going to be backward arcs then i can then i can execute this bucketing phase easily right so this is what we want to achieve but this is very expensive so but what it turns out that even if we have some information of the backward arcs at various points of times then using this some information we can still achieve a single exponential algorithm but it comes at a cost of approximation so that's the idea and now what do i mean by some information of backward arcs and not all information this is encapsulated here so we begin with it's a divide and conquer algorithm so we have to fill these buckets so we so we first start with the following thing we guess which vertices will go to the first like first half of the buckets and which vertices will go to the second half of the buckets so we define like we guess the left and right it'll take some 2 power n time but note that so this is what i mean in a sense after having guessed this we have we know that all the arcs from here to here are going to be backward like if i know that in the final ordering these vertices appear before these vertices so there are if there are any arcs from right to left they are going to be backward so this guess 2 power n time guess gives us this information right but again i'll not be using this inside crucially but this is the essence of the algorithm but if if it's fine if you forget about it so so we guess this what is in the left and right part and now i want to do a divide and conquer okay let's see what goes wrong if i solve this problem like the problem on these vertices and these buckets independently and the problem on these vertices and these buckets independently so okay so the the problem being like i can solve this problem independently this problem independently but what happens to the across edges that that goes but note that in in this particular case this is for two approximation whatever arcs go across these vertices have to be present in this bucket like this particular bucket that is just before this line and these vertices have to be present in this bucket because the forward arcs are to be in consecutive vertices right so in this case we just decide to put these vertices in these buckets and then recurs now it doesn't matter how i solve the problem here provided i put these vertices in this bucket and it doesn't matter how i solve the problem here right so that's the essence and this leads to a divide and conquer with this kind of a recursion and this gives a two to approximation so for one plus epsilon approximation it's a little tricky so first of all the bucket sizes change and i'll just say quickly it's not like for example when you have these vertices it's not clear which bucket they'll go to but note that they don't have a lot of choices they'll not have a lot of choices so and we can branch so that's the idea and that's it so for open problems as i said for undirected bandwidth there is an x there there is a polynomial time algorithm for fixed b for this problem it's easy to see a polynomial time algorithm for b equal to 1 but for b equal to 2 itself it's not clear whether it's polynomial time or np hard so it'll be good to know it even for b equal to 2 and then of course the generic problem which started this study can be designed a two per order and algorithm for digraph bandwidth in general graphs without approximation