Well if you.
Actually think thanks for the invitations
It seems like a really great meeting.
OK so.
So this is going to be
the summary of three fake papers.
But that doesn't mean it's
going to take a long time.
So the first paper was with.
That and
my commit some else it is now in Iceland.
Second paper was with Tony Hanson and
Tony is.
Booked solid in Sweden and Samantha Petit
is here and she's been advised by.
Santa.
I'm Phyllis is fill in because I
gave the last time I gave this talk
it only took twenty minutes.
OK let's go OK So
what's the problem so you.
There's a underline the whole thing
there's a bar to a bipartite graph G..
With two sides Al and left and right L.
and R..
And R.
is bigger than L..
And you don't see you don't see the you
don't see the graph it's given to you
online OK so
what in fact what happens is you
are presented with the vertices of
the left hand side L M When you.
Actually look for it and when you're given
a vertex on the left you're given all
its neighbors so you just see vertex
comes along given all its neighbors.
And.
We assume that everybody has at least
two well actually receive everybody
on the left has L.
neighbors or
where we're at as at least the L.
is always the number of vertices.
Is the number of neighbors
of a sex on the left of L.
for left.
OK And so what's the aim for the i me
as to maintain a some sort of matching.
And the it's a matching on the left
hand side in the sense that each
that he first takes on the left
hand side sees one edge by.
The verges on the right hand
side can see up to our edges.
But our far right hand side.
OK So remember this Allen left and
right OK.
OK so his.
Is a picture of the.
So here's the current state
where we have a matching.
Let's say I think here L.
is three and along comes.
The fourth vertex and unfortunately
it chooses three neighbors and
they're all matched So
Woody So what the vertex does is
it picks one of these at random.
And so you pick this one and
this guy is for now forced out and.
So this one was force that chooses from
its set it choose another one at random.
OK So basically what it's doing is
finding an alternating path on
the actually find in a mentoring path and
is doing it by a random walk OK so
it's just looking for a moment in path and
it's just in a random walk to find it.
So wisely what is going to do it could
use on and of cookies do exactly this.
So this.
So this guy here is supposed
to be a cook OK and.
Picks a random nest this one and kicks out
know which one ethic that this guy
around but this somehow survives and
goes on and pick something else so
that's the one cooking passion.
Story.
Yet all the ages around so
these guys here when it comes along and
picks three random edges
uniformly at random.
Yes I was the what is the problem
in a moment is no problem so
the problem is to sort of control
arm the lengths of the omentum path
What's the expected length of.
Or of the omentum parties died.
And we will consider two cases.
So in the first case we have a large L.
is large.
And but you're only allowed one in a nest.
OK.
And the other case is
Ellie's true exactly to.
But you are allowed day in the nest and
they are specially very different
algorithms by the same out rhythm
the analysis is different and here.
So if you would use if you wanted to
do this in practice you would have D.
small you really would like say D.
not much more than you'd like D.
to be three.
OK.
If there's any sort of interest in
the talk it will be that there's a nice
question is to do some sort of
analysis for the case the three.
Hour.
Day has two articles articles two articles
one is sort of fairly easy it's just.
You just wait for so
we'll talk about that later.
OK so they will be enlarged so
there's some criticism about deviating
you know me better than nothing right OK.
So natural questions are how large should.
So fix D.
How big should M.B.A. or if I fix them
how large should be with this stuff is
completely solved it's not this messy but
you just basically
applying holes there to see when
there's holes theorem kick in.
And.
And how long is it take
to construct this thing.
Is want talking about.
OK so this was it so they know the name
cook who has Xing came from power and
earth and they consider this case and
are two seconds about it later.
Not this yeah.
There are lots of papers on the subject
which are always I haven't read
any of them but this one.
This one the main contribution here is
I think that they show that a sort of
breadth first search breath first search
can be done in sub linear time and
sub linear spies OK so
you don't need to need to do you know
they do the full breadth
first you sort of stop short.
And they also mentioned that the random
walk thing would be of some sort
of interest to figure
out what happens OK So
this is the I've already said this so
I will skip that round already said yes.
So in cookoo hashing
the L A G.'s are the results of.
Pash functions.
And we're going to assume that
they're completely uniform this is
a close you know and should be called
a hash a big Because then you're saying
we assume we've got completely uniform
random hash functions which are not so
easy to produce so another open question
would be how do you do this with.
Hash functions which are.
Not completely random may say
How would you do this with
if you using Linux a linear
congruence would generate.
Something like that OK So
the first attempt I made
with this was when Mark.
Was power males than a Michael MIT's
America and we didn't we aren't we show
that the expected time to insert
was probably logged so before this.
I don't so I suppose only sort of entity
epsilon was none so we surface what we
showed prolly long so how was the argument
he the Army's quotes him Paul.
So M.S.
will be the matching after you inserted S.
elements.
And so now we're going to M.K.
minus one so
the basic idea was the following You
could use you insert the new V..
And if you saw if you
did a bread first raw
what you would find Is there be
a sort of a relatively large set S.
one.
Of an over poly log.
Which can be reached in poly log steps so
this large set of side N.
of poly log.
Such that are that.
So that the probability
you can reach it from V.
in poly log steps is say into a log
steps A is one of a poly log So
this set of size N.
of a poly log and
the expected time to reach it is
poly log that's what I'm saying.
Yes relate to maintain power yeah so
here's this says you can argue by
just say no matter what the moment or
what the perfect matching
is there's a set of size N.
over poly log such it expected time
to reach it is probably logged.
I waited.
For M.
and N.
are Amy's we were seen in the M.
is one perception on times an OK And
we're assuming that M.
is sufficiently large so that with high
probability there is a perfect match or
there's a matching from the left or
the right.
And then you have to argue that.
There not that many as you sort of there's
this say what you're trying to do is
you're trying to reach a set which
has neighbors which are unoccupied
OK And then you argue that So
there's always a so because M.
is one percent silent times an.
There's always a linear sized
set which is unoccupied.
And if you back off from that there's a
sort of a bigger set which is the neighbor
of somebody as I occupied and
you go back further and
further eventually you only have
to go back log log in steps
until you get to a set of
SA is such that all but
something over poly log is within log log.
So So to summarize what it says in
expected time poly log you really
assess a vertex which is
if you only log log or Y.
and if you only log log away and the.
Degree is constant.
OK then you expected time to reach
the end results are only poly log.
And then that's it.
So you this there's this set.
Of a large set which is bigger then
such that everything in this set
is within log log of the end.
When you reach than
expected time Polly log and
you've got a one over poly long
shot now reaching the end and so
the expected time is probably log and
it sort of probably logs high probability
around OK silence means it's Oran OK.
OK So is that OK So
then I was a paper after so
the problem here was I think we had
five day at least eight in that to be
very large they had to be at least
eight and I think these guys.
Show that you could do roughly
the same amount of time.
But you could do for
savings three as well so
that's OK So that was the state
of the art a few years ago and
spent a lot of time trying to get
from Poly log down to constant and
lots of tried lots of ideas
talked to lots of people.
Who turned out to be simpler than
I thought than I thought OK so.
So this is work I did with my grad
student turn a year Hanson which
basically says which made a large enough
you can make the expected time as close
as you like to one so this is.
So how do we do that so we tried using
sort of Markov chains mixing time canals
work but nothing seemed to
work until we had this idea.
To get it where we are yes so
we said this is this is really what
happens for the last for the last one.
So here is the Yeah so some not
only these have been changed to L.
So here L.S.D. and
there's only room for one cook.
Up yet only room for
one bird in the nest inside.
How big is what.
L.S.D. and day is a large constant
Yeah large consonants the point so
it is always a large constant question is
how long does it take to insert a credit.
Or.
Where you go where this analysis doesn't
matter just do it again just keep going
I mean has a side called when
the bird then then what happens is
they will start again.
Don't go back I just assume you just keep.
I mean you can still choose you know I
would have not got kicked out on the R.
though I'm dizzy and I was just added
the beginning I just got kicked out
well I just choose another
random place to go
eventually our farm I work eventually
will find a way to insert run.
One now and then this is Ellie cause D.
left on the left hand
side the articles one.
Redoing the whole thing where.
You're.
Yeah if I was if I was as if it was
a sock or if I came back and I kicked
out the first one I put in just keep going
I just do differ in our Choose another
random number where that remember that so
I might do exactly the same thing for
a long time but
very lightly OK I can skip this so long.
B.K. are those vertices
it on the left right
which have a neighbor that's
not that hasn't been filled.
OK.
R.K. is the rest.
To R.K. month one year or so because
of those can if I gets a big a far if I
if more random walk reaches a vertex
him be undone Rocker's I can see
the outside and I can just put the I
can put the item into that location.
On so that.
Well no actually the algorithm
says R R look to see where the I
mean I could just say will pick something
at random and keep going but it's more
natural to say well I can see this I can
see a place asked the kid in there and.
Only randomize of it if
everything is blocked OK.
Yeah OK so
now our list are come back to this.
Earth and I can live to do this OK so
I'm not an aging Mensing path.
Will look like this something on the left
followed by something that's not in there
because if Y.
one was in B.K.
there and I would be finished.
OK so this one is or I keep going so X.
two is so why one was matched to X.
two and now X.
two chose Y.
those X.
two must not be in here otherwise
you'd be done so no alternates and
no mention part goes left something
not in here than the matching edge and
if it's if if if I'm not in the match
if I don't see if I'm not in here or
keep going so I keep going until
I reach something not in here.
So the sort of powers that
are I'm seeing are of the from
left not in B.K. left not in B.
when actually the other
way round is not in B.K.
up to the top not in B.K. not in B.
can't tell I find something in B.K.
then I'm out.
OK so let's call yes or
there's not a very good choice of words
but let's cause such a path interesting
another set in the sense that any
other part is an interesting OK So
these are the interesting parts the parts
of interest now not all interesting parts
are augmenting that's the point there
are many more interesting parts and
augmenting OK So that's the basic
I was the kid sort of done
thing it's not hard to estimate the number
of interesting powers of a given length
but it is hard to estimate the number
of interesting alternating powers
because somehow this
depends on the matching.
OK And that was a problem which is always
trying to figure out what was the how what
was the distribution of the matching live
you know which is is is constructed by
some process and it's not an adversarial
process but it's quite difficult to
actually understand but if you sort
of forget about the matching and
just think about interesting part somehow
the matchings of this doesn't really
matter what matching you've got so
interesting men.
So it be B.K. with the bad guys right B.K.
can see the outside or
is it the other way around with a look.
Because a because the bad
guys you can't see the side.
So interesting bad guy bad guy bad guy.
Good Guy OK.
And the point is that B.K. is small.
And naive calculation which he would
say that big way is OK says Caleb dom.
And what's the probability
don't see the outside
when it's about one
minus Epsilon to the D..
I mean if it was everything was on
condition that we were minus Epsilon to
the D.
and that's any of the minus EPS less
than any to my stepson on day and
if he is big enough current fastener want
to reps along this is pretty small and
it's not correct this obviously but
you can make something look like that.
The case so B.K. is small so
right means you should get B.K.
bar quite quickly OK so
then you have to argue then you want a
number of interesting parts or with two S.
minus one vertices and then you have
to argue that the expected number are.
Or how do you choose them where they
go the choices are you could achieve
those big hey of the side it's big case
of the S.S. then you go to choose the.
So this is on the left
these are on the right and
then you have to do something about what's
the probability the ages are there.
OK And again you sort of can argue that
this is sort of it's sort of close to been
random and
this is a good approximation OK So
this is the number of paths now
there are possible powers and
this is the roughly the probability
that all the ages of the path exist
OK so a little bit of conditioning is not
easy when you think about it isn't that
there isn't too much conditioning.
And then you can use some
concentration inequalities
three simple applications of Azuma.
And you can show this is highly
concentrated and there and then S.
where you just are the only other
trick mallees So you're right so
you've got the probability that
this is large is pretty small and
then you use the expectation is the sum
of the probabilities have been large and
then you certainly have to
do this up to log log again.
So that we're only looking at really sure
interesting part log log in and then we
can kill it with the previous result
plus the basics so the key there is.
Replacing old Mensing powers by
interesting problems that's the key.
Where we could It is easier with
Well one thing is you know you and
I took out a log log in.
Yeah there is a certain you do you
do need to think about sure parts.
But not log log and
log will again is but you know but
Logan is like a constant so you say.
OK so that's that page OK so
now the one with Samantha Sam Petit.
Are OK So here now we've got Alice two.
And the right hand side are is big.
So it's a completely different
completely different ballgame.
So let's.
Are it's OK So the point is so you see.
Well along comes a vertex the case vertex
and it has two choices P.K. and Q K.
And so that's like an age joining
P Cain Q.K. and one of them has to be
one of them has to be chosen so
that's like orienting it from P.K. to Q K.
or Q kind of Pekin.
So or so let's let's top pick.
OK so so at the beginning when you
have an eight you add it in a sort of
a random order without thinking you
just choose randomly that is D.
and.
There's another thing which we get
by after the ins and what's the list
look at the Insert the insertion algorithm
is quite simple suppose the arm so
what are you going to do if you have to
add the ages then orient them to alter
the you have to order in the edge and
it points to the location
points to the location where
the item is to be placed so
you have to are in the age and
we have to orient the edges so
that no vertex has in
the green more than our
own so here's a case everybody here is
going degree at most or are is two.
So we want to add this guy but
this makes this in degree three so
what happens is we have to reverse one of
these ages so then we reverse this age and
this ages go in degree three so
we reverse that and we've done.
To the algorithm is basically you
have this random die a graph.
OK initially some of the edges some of the
edges which is completely random some of
the edges of been altered and
you add an age you put a give you an R.
and then you what you do is OK if
there's an easy orientation you
do it was an easier in Taishan Suppose R.
is ten and the A's joins two things in one
lead in degree five none other in degree
seven so doesn't really matter which one
you do you just orange it randomly but
if both of if both are in degree
ten then you're in trouble so
what you have to do is you have to sort of
find a path reversing orientations until
you find a vertex which has indeed agree
less than ten and then you can do it.
OK.
OK so.
OK so his in our study so
I is the set of vertices within
degree at least are minus one in D..
Today's other ones are likely
to get saturated very quickly
OK so we're trying lots of complicated
arguments trying to figure this out and
then somewhere Samantha
noticed the following
orders happening again the point I first
of all is these going to be very small.
It's going to be exponentially small.
In our run
OK so this.
Samantha notices that this set contains
all the saturated vertices there so
this is the segment you get as
follows You start with the guys as
the ones with very large in degree.
And then you add you start to follow it
you take a vertex if you've got
two neighbors in a as you add it.
And then you keep doing that and you keep
did it until every vertex is going to
most one neighbor in this and
then the point is that this set S.
contains all the saturated vertices and
that's pretty simple because you have
to have you need to flip the gate
because you weren't in an eye you have
to have two neighbors to get in there.
And the point is that because A is small.
S.
is small.
There's some sort of standard random
graphs way of doing things and
it turns out that if S.
is small a is small basically small sets.
Have a very low density.
And if you keep adding the disease
a degree to and get big
that means you have some or you you've got
to dense at some stage and very nice trip.
And basically that's the end of
the game once you notice this
once you notice that this set S.
is small contains all the saturated
vertices What does that mean
what it means that all that the graph
induced by the small vertices
is basically little trees and
little uni cyclic compounds.
It's just subcritical And that's just
a sort of first moment calculation
and then you can basically it's done
right because you only got to do is
do random walk for little trees.
And that doesn't take very long and
these are most of the trees are constant
size arrives.
Yeah definitely there knowing this and
calculation.
OK So that said What's the weather I think
I've been through the question is that
the real questions are.
Reduced the independents from large
day to three only say some so
it's obviously for small obscene lawn
you're not going to get away with three.
So one thing you might want to do is
say replace the grows one over epsilon
two The grows like log one of reps
alone or give me something for three.
Not when are when thirty thing were.
So when Ellie's to R.
and R.
is one you need.
To N.
You need to air the M.
has to be two in.
Mind because this is just
sort of subcritical A-T.
in the random graph process.
And the other thing is if you could
make it in you could do deletions So
it's toward tempting to think that if
you do random deletions It's like they
never were there.
And so sometimes that mark that
might be so are fairly easy and then
handle the case where the hash functions
are only or not already K Y Z depended on.
What might be more interesting and
never saw the other the one of them and
OK thank you very much.
Thank you.
I know if you do prefer search
it takes up too much space.
Than That was the original paper.