My one of my favorite problems which is the graph they are major problem so let me. OK So in this talk imagine we have an underactive graph unweighted and will particular be interested in the case when the graph is very sparse it has ended for the season and poly log and I just as well that all Tilda means and will be interested in some natural graph parameters one of them is of the eccentricities of the vertices was the eccentricity of a vertex Well just imagine the shortest path tree root of the V. and this is basically the depth of the tree how far can you go from from that's the eccentricity of the vertex the diameter is the maximum out of all the eccentricities or equivalently the maximum over all pairs of vertices of distance between them that's what they're going to regret and as you might imagine just from the definition is very easy to compute all these parameters using an algorithm for all players shall just pass it just compute all the distances and you know take the maximum for each vertex and so on OK So. For sparse graphs this gives a roughly and square part algorithm using B.F.S. from every note. OK. Perhaps surprisingly this is the best known algorithm for these problems even just for computing a single integer the diameter of the graph and squared seems different. OK You know we like to ask these questions so we say well maybe I don't want to compute it exactly let me just approximate this quantity I want to approximate the diameter I want to approximate and get approximate estimates for the eccentricities how well can I do so this is what this talk is about. Art so. The first thing you think all of is well you know an underactive graphs when we talk about. Distances you can always use the triangle inequality so here are very simple linear time approximation algorithms for both of them and all the eccentricities What do you do you pick an arbitrary vertex in the graph run B.F.S. from it OK for today I'm a very you just call this vertex V. for them or I'm going to return to estimate which would be just the eccentricity of the how far can you get from three and for the eccentricity for every vertex X. will return the estimate of the eccentricity of v plus the distance between v and the X. divided by OK so. That's not too bad this is a folklore approach is very good and just here's the triangle inequality in action immediately get this estimate of the eccentricity of the vertex you picked is always a two approximation to the diameter because well you know if the diameter is the distance between X. and X. prime then this is a most dx V. Plus deviates problem which is of course reappears both and both ways here and you get the two approximation and similarly you can do a little bit more of a messy announces a few more click ations of the triangle inequality and you can show that this particular estimate is a three approximation to the eccentricity for every vertex and there you go a linear time you can get the two approximation for they are murder three approximation for the eccentricities Well I can't I do better what about I want close ups on approximation a linear time what about something else so. These two or three have stood around for a long time like the folklore algorithm. OK so I told you these simple algorithms but actually there's other algorithms for these problems as well so if I were present them in these graphs So what do I have here on the Y. axis I have the run time. Exponent it's essential there's an end to the Eat algorithm remember her spars graphs are aware measuring the run time in terms of L. and L. in the X. axis I have approximation ratio. For this is for the eccentricity zone for the day I met up here we have the exact algorithm that computes all the distances right that's and then squared algorithm the achieves a one approximation over here is this linear time algorithm that does B.F.S. from a single node it achieves a three approximation for the eccentricities and two for the diameter. Now there's these other algorithms out there to for example I had a paper will erode it in twenty thirteen and we got a five third's approximation running into the one point five time for the eccentricities and roughly the same algorithm gives. Three Has approximation for them. And then there is a generalization of our ideas achieved all these points here the kind of lead to three that lead to to do it and the exponential decay of the approximation ratio so if you want the exact statement there up there is a two minus one over to the K. approximation for they are modern and to the one plus one over K. plus one prime something like this for every integer K. at least whatever one. So you have these points but are they optimal Why can't I have. You know linear time I want to supplement proximate for example well it turns out there and are prepared to any thirteen and in the fall of paper with a few other co-authors we showed that under a hypothesis called the strong exponential time hypothesis which I'll talk about in a little bit you can show that if you want to do together better than one point five approximation for the damager then you need to spend on square time we. Is essentially like completing it completing all the distances anyway and here if you want to do better than five thirds then all the something then square tiles well so pictorially What does this mean means if you go a little a little bit below here the runtime jumps up somewhere you might as well compute it exactly and and similarly there if you have go a little bit below here you over over some go up there. The some experimental time process I'll talk about it a little bit more later but you can think about it as the problem of the pups is that c and there sat down and variables in a linear number of causes requires roughly roughly to time actually it's a very big strengthening of P. not equal and P. It really really starts but people still believe it so OK but this is this really you this but this doesn't answer the question for example can I heard of a linear time five thirds approximation algorithm for its interest of these and linear time. While one point five approximation for them and maybe I can't and we tried it for a long time to get this now let me measure Why do I care about the AM or we always have to ask this question and of course there's all these applications but people care about it in practice they computed but for me it's interesting because it's kind of a nice playing ground for these techniques that have been developing for finding complexity so it's a very very simple to state problem and it's still very interesting it's interesting to get stuff about and as you see in the second. OK So here's what we do we show in this new paper. Well first we show the actually for the eccentricity is there is a near linear time to close up to learn Proxomitron algorithm. So in a sense this or. Region is not interesting. That's so this is the first thing So actually these green points here they're completely subsumed by this new nearly new Taiwan to perceptual approximation Allen. OK Also will prove this theory which would be very easy to read but in picked already it looks like this. There under the strong exponential I have boxes there's the stair functions so. If you need to go below a certain approximation Reacher need to get a certain amount of time so like this and notably it shows that if you want to run in nearly near time to approximations the best you'll be able to do if you believe the strongest nation of pot. OK so. I do specific graphs so you know you what's going on here are basically what you do. You do get these specific graphs to come from a reduction in the sense from Sat so. So what you get is that for every integer kid distinguishing between eccentricities took a minus one or four K. minus three This will give you some approximation ration did you need to beat namely four K. minus three divided by took a minus one you need this much time. And so for every came because kids have to be integers it's a discrete thing. OK. So what nearly I'm nearly noon your mirrors yes there's like too little too long so any logs square then divided by epsilon let's say something like that so you can get very close to two. Be lice. Get rid of the steps along it's probably possible. OK. So this is this is for the eccentricities what about for the diameter so we had this orange long there. And the picture is not as nice. What we can show is that if you want to go. Below into the one point five time then. You can't do better than the one point six approximation it inserts so this what it means. It says the this point is optimal under the strongest one inch of time for pulses into in two ways the first way which we knew before if you improve if you only improve in the approximation you have to spend then square time no we are saying if you want to improve on the run time your proxy mation ratio has to go up to one point six. So this is some. We have this point but we don't have this nice staircase thing for diameter. And so the question remains so that means that algorithm is optimal but the question remains is like is there actually an algorithm over here can we get a linear time one point six proximate good where is there like some staircase that's hiding here then go somewhere. OK And the results clear any questions yes. So. There is. Actually the way our state is five and eight but usually you can add some more tricks and you can make it five to eight T. for every integer so you can make it for larger and larger things it's a good question. I'll write. It. So this is where we're going and no I won't be able. Show you all this so show you some of the techniques of going to this. To the way we got to proving these things is by first defining a new problem it's a natural problem so this problem is that matter WHAT IS THIS you're given an underactive graph and you're given two subsets of the vertices S. and T. they could overlap but they don't have to cover the whole vertex set so they could be alike in overlapping and they could be some some for this is left over and what I want to know is the maximum distance between a vertex vertex in S. and a vertex in T. first S.T. than. Yes So if S. and T. were acquired to be a partitioning of the Riddick said then it would be a by chromatic version of the ever but this is a little bit different because we allow them to overlap and to not cover everything all right so you may ask you change the definition maybe this problem is hard my maybe it's much harder than they are later but when it comes to exact computation nested am under diameter computation equivalent you can prove this though there are roughly the same problem for spectra exact computation if one can be solved in the end to the C. time so can the OP. OK. And where Spector approximation will be unable to take any approximation algorithm that exists for diameter and converted to one for us today I'm better but the proximate racial changed. For example. The you know that simple linear time approximation algorithm for diameter where you take an arbitrary vertex and run B.F.S. from it you can do the same thing here except your own B.F.S. from an arbitrary S. in this and an arbitrary T.. But so what you do is well let's let's suppose the maximum distance between a node in less than a node in T. is between a star T.V. star and then if you run B.F.S. from an arbitrary S. in this an arbitrary T.N.T. and you are return the maximum distance between S. and the node in T. and T. in the node unless in particular you are considering this distance this distance and that distance all these three and they cannot all be less than that they are murder less over three because by the trying going to call didn't kind of you get a shorter path and so this can't be true so at least one of them one of these distances the distance from the maximum distance from S. and the node in T. and the maximum distance from T N A node in NS and the distance between us and T. one of these has to be at least a third of the rest of the Emmott or so this gives you a simple three approximation in linear time. And if you take any one of these other approximation algorithms for they are not your problem you can similarly adjust the one to some other you know when every during B.F.S. is from a loss from a vertex you can do be a pheasant from S. and T. and you massage it a little bit and you get a new approximation algorithm for this problem so these problems are kind of related we have no formal reduction in the approximate chansons between them but they're related so we study this problem OK. What we showed is the following First here's the algorithm some of the algorithms that we have we have today on what are the exact algorithms and squared and get everything exactly this is a. Two approximation and then to the one point five time this is an adaptation of our algorithm for diameter from twenty thirteen and this is the three approximation algorithm that I just showed you that runs in linear time. And what we showed is this theorem which pictorial looks like this it shows that these three points are up to more outward so in particular if you go below or two approximation you have to spend squared time if you go if you want to be faster than N. to the one point five ton you have to spend to get a worse than two approximation and so on and if you want to run in nearly in your time we cannot do better than a three proxy. OK So Christy they are not or we can get this nice picture explaining a lot of stuff under just our experimental time hypotheses and so then we asked OK this this problem is related to their modern eccentricities can we get from this harness reduction can we get something for the other problems and we did so what we did was we took the constructions there we got I will show you the construction on one of the constructions and we had some gadgets and with these gadgets we were able to all. So show it for downward eccentricities but this is really the main main result. OK. Any questions at this point. Is. Yes I'm getting there OK OK So get it. So in the remaining time I'm going to tell you just what is trying to strong exponential time to Ponce's I'll define this problem called K.O.V. which is very related to this problem and then I'll give you. A stadium other lower bound construction in a particular case and then no conclude with some open questions. OK so. Let's talk about case at OK we all know this problem we have a brilliant formula where every clause has a literals and we want to find an assignment to the variables that satisfies all the calls so. We know it's and P. hard wired What are the best algorithms for this problem the trivial algorithm is basically I try all possible silence and plug them in this runs and took the D. N. times the number of calls of start. The best known now we're going to run into the N. minus some constant times and divided by K. work is the with clauses times put in on the end and. Notably this goes to to D.M.'s K. gross. OK so this may be available this strong exponential time hypothesis of him probably as a pituitary insane and they said look for every fix K. maybe you can get a faster into the D.N.A. algorithm but no matter what epsilon you give me plumb brigadier a zero there is some clause with K. for which you cannot beat to the one minus Absalom Panza So as the with of the clauses grails you have to basically spend to the D N R This is what the strongest potential time passes serves. And it's a big strengthening of people not equal N.P. in clean Arctic when people we say sat requires super power nominal time here I'm not saying it requires super prolonged term I'm not even saying it requires exponential time I'm actually saying it actually requires two to Deanne the brute force time they might be a weird assumption why not believe it but people have tried for a long time to disprove it and maybe this is some evidence that it's true or maybe it's false but who cares we're maybe you this is a way for disproving it but reducing it to problems important on the far right. OK so this hypothesis has become one of the main harness hypothesis and fine grained complexity and we've reduced the two thousand many many problems in Parliament tarmon you know exponential time and so on to many problems. And it implies tight that the known algorithms are tight for these problems if you believe this. All right so here's another problem which is also central to going complexity is the care orthogonal vectors problem here you are it's a problem about vectors you are given K. sets of L. victors each the vectors are. Over zero one one so there are binary vectors the dimension D. you can think of is probably look like and. What you want is to find key vectors one from each set so that their generalized inner product to zero what does that mean it means that there is no coordinate such that every of the cave vectors you picked I want so for every coordinate there is a list one of them is zero. So that means certainly sometimes right this is the inner product it's. So Brian Williams in two thousand and four his paper kind of implies that if you can solve the kid you're talking over to spread them faster than into the Kate will normally faster for any constant K. that you pick whichever one you pick then you can refute the strong exponential pattern hypothesis. So now this gives you these problems that under strong teacher hard for a new fix polynomial time that you want with a with an integer X. ponit like so if you if you want a problem that requires and to the tenth time there's ten will be OK One hundred and then to the one hundred time one hundred of the OK so now we have these problems and. We have this new hypothesis trying to fix integer we can say kill everyone and vectors in the dimensions requires and to the K. poly did part isn't essential. In fact this cripple says is much more believable than a strong th strong th could fail for all we know and this might still be true so now we can just focus on this one and forget about trying to age. Yes it's very easy to reduce from K. to came in this one but the other way. I could get good. Yes. So if you believe. So the most believable parts is to require that quip to get slightly less believable as you increase K.. So anyway it's an interesting problem. And what we're going to do is we're going to consider different kale reads who present reductions from them to the diameter problem and give different approximation of the runtime tradeoffs for. It so OK so now what I'm going to do is the first thing I'm going to tell you how you can get. A very simple reduction from the two of the problem to they are modernized today are much OK with this with this is known for a while so here's where it is a this is the two are talking of actors problem you have two sets of vectors of length D. both of them of size and then you want to know have these two one from each set the sorted there orthogonal in the usual sense so we're going to take this instance we're going to produce a graph out of it and the first graph I'm going to produce is an instance of S. T. diameter and then I'm going to add a gadget and make it an instance of the AM OK so. So this is from twenty thirteen OK So what do we do we take every vector from S. one and create a note for it and this will be the same as every vector from my steward create a not for a does the set T. and are literally K. These nodes corresponding to the coordinates and there's denotes here D.S. like so no we add in their age between a vector here and a cord and that if the vector is one in that coordinate and similarly here a vector here and accordingly if if it's one and a coordinate Now what happens is that. From victory in hearing of action here there's a prophet linked to whenever they share coordinates in which they're both one they're not our problem and otherwise the distance must be at least four. Because it's a bipartite graphs so and they're trying to lay there in the same partitions so if it's not too must be at least four so. OK so this gives a. Two versus for. Instance of S.T. the M. So this is this is T. if there's a DE If every pair of a lessening of pair of nodes one innocent pointy is a distance do then there is no orthogonal pair and otherwise if there's a pair that's a distance at least four of them there is this one OK so. So now this is us today I'm going to the simplest possible reduction you can think of also the number of nodes in this construction is and was D. two and Tuesday and number of edges and times D.. And D. as Paul look at like so this means if if you think two over corners and square turn then this should also require distinguishing between as to damage or two and four should also require an square back because the is time by and by and square them into to the end to the to minus little all of one. Hour. Do you do use just the dimension of the vector as some poly look at McCann is Pole look like logs quit. A little bit more dialogue and basically this. It comes from this person for occasional M four for satisfiability basic you if you think there will you reduce up to kill you you create these vectors and dimension corresponds to the number of calls us and the vectors correspond to partial assignments of all and over two variables so if this is a number of calls this is linear bias person fixation this is looking like roughly speaking but anyway so you can think of deal as logarithmic and therefore this graph is very small and you get this nice tradeoff that if you want to do a get a better than two approximation for us today I'm a value you need at Square time OK here's a gadget for diameter and I forget about S.T. diameter what you would to do is you add two nodes X. the can makes everything in that. All the coordinates gadgets coordinates here and why that connects everything here and what this gadget gives you is that every pair that is not in S. crosstie is a distance two or less and then an other was the distance between A Not unless a node in TS is. A can you know if it's two is still two otherwise it's at least three. So now it's about regular diameter This is between I need to put any pair of nodes in the graph and it's about distinguishing whether they are matters two or three if it's three then there is an orthogonal pair and otherwise there isn't. OK. Felicity this is what we knew before so this this gave these orange lights this gave the orange line for the press today only or from them. But what we want is these red lines and I will show you just this part here. And you can probably tell what will happen after that but when you see that part maybe you can generalize it for laid for bigger K. It's a bit messy but is doable OK questions up to this point. Yes. You can make them bonded or yeah. Maybe maybe. You mean the X. and Y. that's those are the only two notes of high degree. I think you can make them bond. Think about. Just remove X. and Y. and put make the the notes in the chord in that gadget corded know the all the nodes in the middle make them a click No the degrees logon because the D. is logon roughly. And you still get this distance three or. You could just make it a click the minute middle part can make a click and you still work just. Yeah. But anyway it's a good question. OK So here's the idea I have this gadget this graph that I showed you before it was based distinguishing between the case where there every poor every node in here never know if your has a past of link to this report and otherwise the case that there is a notary here in the know to hear the Who's best path looks like this this is two vs four and we use to all three which gave a lower bout of and squared and we created a graph of on roughly and nodes and and ledgers number D. is small. What we're going to do for. Larger carry Let's say we start with three of a now our lower bound is a cubed because we said Kill requires into the K. by assuming stronger th and now will create this longer layered graph they has end square nodes and squared ages instead of ten. And this is OK because we're trying to fight against Thank you not at Square and now we're going to be distinguishing the case where for every pair of nodes running in one here does a path. Like three the red pump welder is a parent whose best path looks like the yellow one and all the yellow one has like seven so between three and seven and in general what will happen is if you take care of the. For which the run the run time we're trying to be to center the K. will create this very long graph on Caylee errors where we distinguish in the case that every pair of notes on the left and on the right has a red path of length K. and the case when there's two nodes whose best path is a yellow one. And the yellow one has length three K. so as K. grows to be distinguishing between came three K. now we don't really get that we get three K. minus two similar to the case over there but this is roughly the idea the idea is to to create these graphs where there's a huge gap between the maximum distance K. or three K. minus two. OK. Any So I'll show you just the one from three of the two distinguishing between diameter three and seven in a graph with roughly and square nodes and edges. So. In through V. We have three sets of actors and vectors each dimension D. there zero one and I want to find detect whether there's three of them whose generalizing the product is you're right there's no chord in which they're all one so what I'm going to do is only a create this layer graph and. Insert in the same S. before I had a note for every vector but now I'm going to have a note for every pair of actors one illness one and one S.G.. Symmetrically. Here I have a note for every pair of vectors one in that's two N one S three in the middle I have coordinate nodes like before except now they're pairs of cord and that's together with a node in this one and a pair of cord and that's an unordered list three. OK now I have to tell you what the edges are OK don't worry it will look a little strange but you will see where it comes from in the mix light OK So what are the edges if you take a pair of vectors here one in the US one is two I will connect it to one of these nodes in X. If the load in the vector and a S. One is the same OK And moreover a one that factor in last one is one in both of the coordinates where is the vector in S. two is one in the for only the first one. OK Selectric Look here I'm going to connect these if they share the same vector has three here and a three is one in both coordinates and a two is one only in the second. In the literal I have these bipartite clique's these by protect leaks will correspond to sharing the same pair of cord and that's OK So for every node in here and every node in here I will put in marriage if and only if they have the same pair of coordinates and you can check the number of edges is no more than an square the square. Because you know every edges hidden here they share the same and one and therefore it can have one square here times the number of course in it pairs of corners here is a square Discworld and in the middle here they share the same pair of coronets but they they can have two different vectors so it's as quickly squared again. It's larger it's a very sparse graph but why in the world should do work so I have to tell you so this is the set S. and this is the set T. I don't care about the pairs of the here. OK So let me tell you why it works. All right so now I will show you that if the original instance of true or B. had no three of the solution so for every pair every pair of vectors was not orthogonal then. The yesterday under here is three. I.E. though for every pair of notes one in here one here does a path of like. OK So let me show you why that is so so low three of the solution means that for every triple the A one B two B. three there is some coordinate system there are one right so there are not a problem this is what no three of the solution means so no let's take an arbitrary noting here it's a pair A one A two an unordered here a prime to a three there. Are basically four vectors. So we take these and then we say well because this is true there are some coordinates there stood a one eight two and the three are all one call that quarter and see one there are some quadrants it too so should a one A two prime and they three are on that C two. OK. Good therefore this path exists a one a two two A one C. wants it to somewhere here because you know a one is one and both you only see two and they two is one as you on. This one exist so the surgeon does because this is the same pair of coordinates and then once one exists well because a three is one and both coordinates and two problems once you do so this is where the finishing of the graph comes from OK so this means that this power of length three. Exists. Now I have to show you that there's a gap whenever there is a tree of the solution. OK And then I'll be done. OK. So imagine now that there is a triple of actors a one a two or three that are a tug and also there's no cord in that thing which they're all. OK I will consider a one they two and they to a three over here and I'll show it to you that their distance is at least seven. OK. Now because this graph is layered on by a proton their distance is either three five seven or some other number all the number bigger than seven. OK So first of all it cannot be three just bit by the definition of these edges because if it's three then you go to some C one C two and is the same C one C two here so all three of the vectors will be a one in both coordinates the to go through so the distance is definitely not three. Now could it be five. If its five does three options one option as the distance the path goes like this another option is the path goes like this and the last option is the ball goes like this now I claim this option is not going to happen because this is a. Man. In the. Corner and. This is in the. Now. Right. Here. On. The. Ground on and then you have. To go from here we're. Not. Going to take you. Back here. On the. Ground when we all played. There. On the grid on you. Want to. TEAR. Down. The. Hall. And it was like we're going. To. Get. A lead to it. And there were. Only. A few women who knew. That it. Was the media. Coverage for a. Local world that it. Was not foreign companies. Could. Really get it. Back to where. It. Will you will be able to test it then it is good for. You in the past it. Will leave. You in the right. It could. Be a very good deal to him. It would be. Nice to. Get. Their. Hands over that it was their last. Going to argue that. It was nothing. To fear coming in on. Them. In the Middle East. Forum if. You have the money and really thought of it he talked a little bit about her. If you want me to be more. Patient. And therefore. We're. Going to. Be. In code. For a little bit here. And are standing about these problems modularly you know destroying experimental time and kill the hypotheses and we still have these open problems so the first one is can we actually get one point six approximation algorithm for they are modern linear time or is there an improvement of the slower bond that we have basically our gadgets are not sufficient to give a very good reduction there and in my just be the diameter I do think they amator has a festered and has a linear time or a grid on that gives a better than two approximation we just have to find it just because for eccentric cities we were able to get a better algorithm for them to simple one depicts an arbitrary vertex so there should be a one that's better for diameter I just don't know about approximation ratio is. Killing a higher conditional lower bounds so I don't know we were able to do it if you instead of underactive grass you look at Director graphs or if you look at Wade instead of on the way to grass you can get better higher approximation lower bounds for example. You can get a five third's. Laura bond for the fourth approximation ratio for linear time algorithms when you consider underactive weighted or directed on way to graphs for diameter so that's better than the one point six I showed you before. But anyway so there's more work to be done there. Was a true trade off I don't know thanks. For average case for diameter. That's. So so kill V.M. particular for the natural distributions you can think of is easy on average like for example if I. Pick every chord in it with some pro probability P. to make it one and one minus become independently random and I pick some and vectors and you can solve it in so less than enter the gate down so it might still be my still requiring to the killer two I don't know but yeah so because of this problems like diameter We don't know if you can show any hardness on average. They might just be easy all players are just passes. In way to graphs as fast consoler faster for various distributions so yeah but there are other problems that have potential. Thanks.