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.