OK.
OK since we're inviting me and
that's a lot of welcome to stop OK today
I'm going to talk about protesting
OK as many of you may know poverty
testing is to be determining
if I'll be challenged so why certain
property of our from a sense of poverty.
Or among family I have a space of object.
And a property will be
a subset of the objects
and the will also defy the distance
to sell to find this problem
to satisfy the property I'm ours objects
in that space so basically you're really.
How much information do you need
to change to make the object of
a sense of a problem.
And so we see are always them is and
probably testing always them for
the property.
If it's always them except always probably
at least two thirds if the object exactly
comes from the other property and
Regev two is probably
at least two thirds if the opportunity
is at least absent or far from.
The property.
And therefore the case in be true.
We do not care about
the house our reason behaves.
How it will reach us but
it doesn't matter.
OK And the in a lot of cases we
can't distinguish these two cases
without exam me Aus information
about the product about that object
so in the scenario of probably testing
we do not he's previously given the full
information about the little object so
east has now risen we know nothing
about that object but it can't do.
Choose.
To the object.
And then the problem becomes
how much information
the algorithm need to instruct from
that object to solve the problem.
Because this is definition
of the problem testing.
And the main message I would like you
to do you bring this talk is that
the action or
information is a key to bypass
the whole complex to simple lower bound is
a classic example in my sample of models.
And the idea of making use of
extra information is actually how
powers to solve the problem
even with a classic example.
OK let me start with an easy problem.
Testing the.
Situation close nice ways this is less for
now Mr X.
pronounces So in this problem
well given two distributions.
And the other is the why is no and
then we want to decide if the two
distributions I exactly I don't call.
All there are one distances
at least I have zero for
some given absolute parameter
which is a small constant.
And the will assume that
the distribution is a discredited.
Dummy of size.
OK.
In the classic example in model OK.
There is a at least one distribution is
around the stores are always a need to
char independent random
samples from distribution.
And then distinguish the two cases
there are true versions of this problem
one is that since one one is
the first case one is usually easy.
So as always I'm to money
to to make curries and
the one distribution is the norm so it's
always a need to tolerate them samples
from one of these rouge and
the for this case but two for
now Fisher in the row before the proof of
that squad in some posts are necessary and
enough and also the second scenario
is the both intrusions are not.
And the for this case but
two for not being for
this means and the why it gives
until two thirds are propounds and
the poverty into later shows adds
this into two thirds actually tight
and then your wrist in
the drawing to work always on uk.
Will propose a different somewhat
model called a probably really model.
In this model.
Every time the algorithm can draw
random samples from down or.
Another same time it's also caves
are probably value for the sample.
Way So clearly this is a stronger
something model is the classical model
because I have the additional information
probably value for the samples.
Targets in the next start.
And the way shows.
In this probably really.
For the case of the one distribution
is no and one distribution is own
a car the number of samples and
use enough to distinguish the two cases.
And the fourth case of
the post distribution are no
squadrons our hosts are necessary and
also sufficient.
So compare.
This to most clearly where this is
stronger example to model the number of
some holes required is much smaller
than surprising someone OK to ask.
A question so
why is this model is interesting so
first if he's actually pretty.
Realistic you many scenarios for example
why you have they would have sorted
it in the database or your data starts for
a certain job graphics property
is that allows you to estimate
the probably value for
the samples with a very low cost and
the for
this narrows to it has a close news of
the distribution can be done much more
efficient by estimates are probably
off for somebody else so.
That's a very good question so
here we can show that I would love you to
really need to be exact change can be.
Small factor and I for one pass on minus
Marty but if I was sure that's OK.
But.
Absolutely here should be much more than
this or otherwise I cannot do it and.
Secondly so this simple model is part
of the reason to work are protesting
of quite isomorphism there's
a beautiful connection to this work.
So in the rest of this talk I'm going
to show you this nice connection OK.
So I mean imagine I need
to give too much program to
it's a very classic problem
in your home versus And
the problem is to deter me to only
able to cross are identical or not.
I'm a forty if I ask the following
question given two graphs
if there is a projection between the
verses of the first graph to the verses of
the second graph such as two verses
in the same graph in the first graph
adjacent if and only if after
the projection they are adjacent right.
And.
Is so pretty well studied a problem for
your camera size and
the wrong time in the standard
the exact origin of the problem
was moderate expansion time and
in the past
a few years there are some progress
on the special cases I mean John and
I did a lot of work on that and the
recently lost but by greatly improved the.
Time and
in this talk him going to consider
probably a version of this
problem OK here I assume
that I have to dance graphs where
is the same number of verses and
I want to distinguish the following
two cases I want to see
our ism that accept will probably
if the true graphs are as Mavic
and the Reject will probably if I mean.
At least are absolute terms in square
edges to make the true ourselves more
vague OK so I need to I assumed
here to have that dance so that.
The problem is not non-trivial.
And here.
These And absent are small constant I see.
OK so.
I do not want truly examines the full
information of both were
asked to solve the problem so
instead of given the two graphic spaces
algorithm I would use as Curry's.
Choose or two graphs the.
Following is to ask if
a certain vertex and
fifths of vertex adjacent
are not in the first one
and then the question is how
many question her is a enough
to distinguish these two cases
is a problem clear I agree.
And this problem was the first
study by Fischer and
most of the year and
they gave our programmed.
Always I'm that makes into a five Force
as chorus to distinguish the two cases.
And they also gave a lower bound
linear to the number of vertices and
clearly there is a part normal gap
between the Laura Brown upper bout So
which one is the rights.
And as our main result we
came a new hour ISM so
it makes use of shooters quote of
allowing us to solve the problem so
this new are bound almost a measure
lower bound to some subnormal
So basically the in your thumb
policies are the right answer.
In the following of this talk I will.
Go first introduce the idea
of fission mycelium for
the problem and show was a barrier for
the further improvement.
And the streets how
the problem is revealing
sample comes into the picture and
the House passed and
then is paradise true for
the better for it for this improvement.
And the family hours I will give you Marty
House about what what we really need.
OK.
In fishers and them ourselves
must first work the goal is to
identify morphism better action
between two graphs if they can
find it then they claim the answers to
our otherwise they are not us moving.
So to do this.
Is the first to run the Mr catalogue
to choose their self versus C.
G.
and C.
H.
in both graphs.
Such that a.
The size of C.G. times the size of the H.
is at least a leaner choose
the number of verses OK.
And the way this condition one has shows
that are if the two are so small for.
Them for arbitrary isomorphism but
Jepson arbitrary one.
We could probably add here there
would be a log of side subsets with.
Such that after applying them by
junctions of VS are waiting stage for
arbitrary isomorphism the better option
this hole is always a good probability.
By person paradox.
And the based on this observation each.
I mean search for such large size.
Verses in the posts in the book
insurgency age respectively so.
Let's see if we cause a lot of
science upset in the States you R.C.H.
to be the Corsairs So it's the first
human race over all the possible loss has
cost us insurgency two respectively and
the for each session you know ration it's
a first son labor for each of our tax
according to the can ask her here with me
to the core to the courses for each works.
No it's not.
Evil because upon I'm actually OK.
That's not just a yes or
no I cannot give us a commission.
If for example this word X.
is adjacent to the first.
Car set so
it's a label is why zero zero and
this word halves is our energies into
the last of our tax zero zero one.
OK I mean in this way we define
the labels for every word halves.
And the will also view this label
as a distribution the distribution
proportional to the number of
occurrence of the picture.
And then it in price
the distribution causes testing
to it has that if the true label
distributions are identical or
absent and far you want this OK
in Fisher's I must just work
the employees are worrisome for
the case and so one distribution is no and
the one distribution no.
And recorded so for this case.
We need to.
Work this into an all distribution OK.
So to apprise is always a.
It is the largest verses in graph G.
and the.
C.
to the.
Two is to say G..
And also in one of each if
you need to forty known
they will distribution one of each.
So you need to carry
the collectivity between C.
H.
and the hours of work this.
And the way is is as if he is enough
to perform the distribution companies
testing for every cop cars that can hit
the label distribution so
basically was a fix is the fix of course
that I can define a label
according to the captivity truth.
And I also view these labels as
the distribution the distribution.
Value of a property value proportional
choose a number of occurrence of the label
so this is a distribution and it has
a cronies of these true distributions OK.
All.
So Sue Me stands for.
Why.
Why are you doing because it
doesn't work as some does work.
Every.
Single one.
Yes Does it worry.
You not me that this is.
Like a one forced use is one.
Way.
You know and I seen the information here
is that it was a long is if you can use
random graph with a log in other
words have this thing the labels and
it's pretty easy to somehow separate
to distinguish two verses and
I have to assume that's one of here
because otherwise I need to change
the model because if it is a spouse
graph I mean most of the carries just so
the someone model as a model not
that that doesn't make excess.
Or.
Good and to automate the total
as her is for here so
we start a city to be in a war through
force and search to be one force.
And then this condition hold and
the total number of will be and
two of the five forces in both wars.
And the way this into the final fours as
Haris it is enough to test the cronies of
the two distributions for every possible
ourselves by union bond and the you for
some cost as a discrete distribution
coldness testing past so we further check.
If the true same distribution
actually gives us.
A better option by mapping verses
with same labels together.
But by pipe produce.
Action which preserves the labels.
Where the hell or
why there is to verify if.
By junction preserve label is
closed to isomorphism projection.
You need to do the cover Well let me
show you and then to do this step.
First OK conceptually construct
isomorphism objection construct
a projection preserve labels just a
construct conceptually and there is a left
versus in first of graph and the structure
another one of the words is in second.
OK.
And so it's a for
further occurrence actually is for
this new samples to the concepts and
then the labels for these words this.
Is not.
And the four here because of all
the labels already know it's always OK.
And the one shows that with that concept
projection and the way this quarter and
some holes in both graphs was
good probably there will be.
World Series in the sample of a graph G.
such that after the projection the verses
are within the samples of the average.
OK Again this is by person paradox and
we're only in focus on these
poly logarithmic versus.
I
don't need to do that.
Yeah.
Actually I.
Don't need to do that I mean because it's
probably the arguments
I just need to verify.
I just need to verify something in
probably the way I see the idea.
Here but there's also been the buy
it because I can compare another
log factor to cover this.
Now.
Thanks.
Yeah I'll just take this fictional one and
do it before every.
Year and I don't know.
But for here I need to look at the labels
because I want to improvise
the algorithm for one the one.
With the current between stage and
all the other words yes I know I
know the labels for our records and
the four here into the know the labels for
this or that in words OK.
And here OK we know that so
we're going to probably hear for
every course search there exists.
A third party a party normally or
lower is make money versus have their
image also in the sample the worth of age.
And then with just a verify as it was or
I mean the connectivity is preserved for
this reason me verses basically
means that if I have to work.
Through verses such as.
Some poses for them verses such
as a after is a projection
the verses are ways in
the sample of a graph age and
the base of each other you cannot
have the here is same to the here.
And to you for this whole is always good
property that I claimed to access Morphy
otherwise and that you for
I cannot find any sense of passes this.
Claims are true are far from as more like
OK this is a hello why
the officer must be.
There anymore.
OK good.
As our first that him so
we are trying to imply a difference
probably distribution cronies
testing our reason for
the distribution crossness testing because
the usual cause the starting is a.
For the simple complexity.
And naturally we would love to apprise
a situation crossing the starting for
the case that the postage wishes are more.
Because that for this case and to
the truth or is them both unnecessary and
the enough to it has a distribution
closes and to do this you
are satisfied this condition we can set
a city under siege to be squared off and.
And then I sample another's into two
thirds some posts in both graphs and.
Respectively and the way this I ask
her if he has enough that has
the closeness of the two distribution for
all the possible courses OK and the total.
Required for
this step is into the statistics.
This already improves into the five
fours previous an hour about.
Where this looks great but if he also
looks it's the best we can hope for
because the other two sets for
this condition we need scrotum we're
scoring some holes for stage and stage at
least one of them should be swapped out.
And the other two applies this person
always them we need to into the truth
there are some holes in both wars so I
think it's a one of the graph need to have
into the seventy's it looks like and
this is better we hope for right.
But.
I mean all that in the we are not able to
prove the same more so what happened here.
So the idea really saved us is
the probably reading sound.
OK Because that is a probably
revealing sample every time want.
Some hole we also had a probably
probably value for example and
the four that case for
the postage Bush are known
then Scruton posts are you nuff
that has a colon is off today.
So that means that if we were able
to simulate it are probably really
a sample perfectly there were
only the problem samples and
her is required can reduce
truly knew it was numbers OK.
But the question is how do we
really simulate this simple model
because every time we get a sample
we need to know the probably value.
Maybe not exactly but
after some small part.
Of surprise factor but
I mean this imitation is actually now that
you can actually we cannot really do that.
Reasoning is.
The probably value for
a single word house as a label for
a single word has come
various Why choose different.
Parts for example for
this course urge to vs X.
or Y.
adjacent to have same
adjacency to this concept so
they have same label but
if I choose a difference of course.
They may have different labels and this
means there is a if I am gave our word
access so I want to ask them a surprise
the value of that label is hard because
even two verses have very
close adjacency to our other
words these if still have some reasonable
chance that this is have differently.
That means that it has mation
opposite a single problem for
three overtax it is not easy.
But that addition we misuse of
information to bypass a barrier
the additional information that really
useful is a distance between pairs of
words here I defined there actually
is in the between two world series as
the normalized Hamming distance between
the question in those insurgents Matrix
for example true since you
are on the way here so.
They are same on the first part of
the eight second the carbonate and
the fifth carnage.
And the different.
For other candidates so their.
Distance is four seventh's and
they use classical.
Probably argument we can show zero to
with Earl over Delta square as Horace I
asked him eight The Actually distance
are true additive they are zero.
For every pair of verses
which go to problem.
And to do this I just need to sample out
how it works this and then how to use
from this data vertices two hours in
other words these and then you get what
I show you and there you can you obtain
this in quality would go to probably.
And it holds for every properties and
the why is this information is
useful How is are some information about
the probably value the intuition is to.
Fight if I have a course which
runs randomly selected and
with another prime to our and
this as distance as mission.
Tells me allows me to roughly
estimate how many verses.
Have label have label
with distance at most
are OK It cannot use that it
gave me the probably value or for the core
set but if the course of his random it's.
Some probably value information even
though it is still another use that.
Yup The idea is that I
pick up a random subset
OK The idea is that is following so
assume that I have a random course else.
I shouldn't have a random process and.
CROSS It's a matter to
another in another graph
then if it is random them
basically as the verse is
with the same label will be close
enough with respect to as Jason C.
of the graph.
And the US so that basically means
that if I just randomly mapping versus
with the same label it has or
is already close enough to isomorphism.
And I only need shoot to some
random is some pairs and
the birth five Is there a projection
to the other graph preserve.
Adjacency and that's enough for
me to verify it as movies.
There's only a question.
Or.
Yeah yeah.
He said But I think we all do to the other
two shows they are as morphic actually we
only focus on the what we should promise
that should be isomorphic but so you all
are true rejection after far from as
a warrior I mean some union bound to true.
I mean I needed to apply a union
bound to true show the answer for
every case if he's OK but
this union banner just need additional
Lowry's in the factory for some.
OK here we have some rough
estimation of the probably value but
the problem also comes from
this traffic estimation because
if he's not enough to simulate two
simulators are probably really simple
so we need some other ideas so I mean this
idea is inspired by the probably really
example but we cannot if you have a prime
problem of any sample forty three
version code needs testing to solve the
problem so we need to do something else.
OK these are easy OK OK OK.
Now let me let me tell you a little
bit about what we're ready
to do this when I need to first define
the matrix the first one is estimated
the distance I mentioned before.
If that's mission of
the numbers I mean distance.
Between.
The two verses insurgences matrix.
And as I said so
over to has her samples which I asked him.
The this distance for
every pair of verses to doubt her.
Second distance I call it smart in this
he's build upon this as a method distance.
I mean the inclusion of this
distance is the answer I want to.
Come here how to work this can
map a cancer with genes the.
Distance metric that he's
a that is something in the following so
I give you two distance metric.
And I give you two verses I want
to understand how well this is
how well this one word has come out which
was the other well preserved the view
of the well preserved distance
preserves a distance for
our other verses but specifically.
This distance is defined as following
I first a three by junction
between verses of the after you
two verses of age such that X.
X. X. is a match to Y.
and I So why is the input and the for
such a bijection I look at
the every pair of verses
and take the maximum hours Piers for
the difference between.
Asked me to actually since between
the two verses you are in the way and so
has made a huge distance
after the projection and
there's a mapping distance is basically
defined for the minimum amount of.
Possible projection.
For this maximum.
And though to have some intuition.
For this case.
What if X.
is the map in the sense of you know X.
true Y.
is small because I come out
of this one to this one
this one to this one man is one
who is one of these one who is one
then the pair wisely My
business is pretty small.
But if I look back as
a medic this is you know X.
and the Y.
prime If he's pretty large because
in this graph all of the.
Also all the other words
have same distance same same
as method actually is and two X.
but the for this graph the other words
have different as made into my prime.
OK so then there are quite He's a large.
And the we can show that if G.
and H.
She's as morphic then
if there is an arbitrary as morphism
by objection map here extra why.
Then there may be is there is at most
a truth out here that how is this measure.
As the Middle East or
is this is the purpose of the map
in distance we want some properties or to
the map in the sense for two verses that
are potentially mapped to each other have
some more ideas have a small investors.
Just this one from has made it a distance.
OK.
And the third this is
a little distance and
it's easy to understand it's just numbers
I mean these terms because the labor force
obtained from Zocor sent to the courts.
OK.
And then instead of you making use of the
distribution coding is testing we want to
make use of the added distance testing and
it is defined as the following I
want I gave however some points and
the labels for the points I want to
accept if there is a projection such as.
The label is preserved
by the budget action.
Like this and the real challenge.
For any by junction as a research council
fraction of the word c is such that
the sizes of the label
distance is large for
the vertices and their image is OK.
Actually this problem has thing
at a distance was studied before.
Example a model here a classic
family models as you can take.
You can take an arbitrary point and
occurrence of Abel and
the one to decide if you want
to distinguish these trees.
And this problem of priests previously
started by our union knowing and it will
be felt they gave us a lower bound which
is a minimum of one over absolute zero.
Choose a truthy.
Or three.
And the two thirds here is the number
of part and it is a dimension
OK but
in our case we need that dimension D.
to be larger than sound so basically
this lower bound is basically and
two thirds and this is a good enough
because we hope for square with our.
So that means we for this problem we still
need to make use additional information to
bypass this now and
the problem we actually
studied is threated different because we
want to make use of the property from the.
Isomorphism.
Here I slightly restrict the case so
I want to accept I want to only
what I want to accept only if
there is a projection between
the two us preserve as a label and
also verses and
their images have a small map investors.
That basically means I only want
to accept the first case or
two of the as more of it.
And the first case I want to
reject it is a must be four but
still this problem is not easy intuitively
by Jackson is a very close property.
But so I thought what I can do is
learning to make a low Curry's So
it is not clear how to use low hurries to
impress on property some global property
and what we actually did is
to further solve this problem
by two sub problems the first why I
call it a self esteem matching words is.
I mean if used to test
if most of the verses
in the other graph has a matching word.
I'm going to define
a matching birdhouse major.
And the second one is true for
you because testing this in the metric.
And the the.
The goal is to test if the label distance
basically approximate I have to make this.
Which shows that if there is some
case some even instance pass this to.
To some problem that it actually
implies small business and
just the from the statements of
this true problems it's it's
much easier because I mean if verb have
to use a match you would have asked for
the other words I mean it's a very local
property it's only really two words this
you know is related to other things and
here we have most of verses of housemates
even though they were disinhibition
close to us as the has made it actually
since it is also can be commies or
the by sample sample pairs overseas OK So
basically to solve the first one or use.
The number of matching
verses from samples and
check if we are close to the expectation
and the first second while I
just the random is IMO some vertex pairs
and checking for this condition hold for
the samples OK this is a the hello
picture of our result.
And there is the following
I don't have much time but.
Let me give you some very brief
idea about this reduction and
I'm happy to talk about it
half the algorithm of life.
So the hello idea is to
construct fractional matching.
Between two graphs so
that's why the condition of the match
in size is large close to N.
and the work has pairs of ways non-zero
matching Mylo only if there are.
More if I have to have a front row
machine where is this true properties
that use the classical
result of series Same for
paragraph Maximo fractional matching have
a side same to the maximum if you go.
There it implies that I have
an interval matching offices across
such that the words there are a match
with a small about distance
star and that implies mildest So
my goal is to construct such a fractional
matching and has to these two properties.
So let me first show you how to construct.
I first of the fire internal flow
between vertices pairs in the same door.
I want this flow has
the following properties first
they're all going flow for
every word have unit.
And second most of the flows are only
among the verses with a small distance.
And assert it is as Mavic.
Environed meaning that you
have two pairs overseas.
And that's private prime So there's
a after we comes from the same graph X.
privat Prime comes from somewhere but
so X.
and X.
prime numbers are really come from the
same graph but if they have the conditions
that are there mapping distance between X.
and X.
Prize and most to doubt her
marrying this is a variant of a prime
is at most two thousand then there.
Their internal flow from
actually is closed shoes and so.
In their own flow from X.
privat we provide
the information here is that
a if I have isomorphism
by objection from X.
mapping X.
two X.
prior and which will be prime so
I wanted the internal wrong flow from X.
to V.
You seem to be in the flow from X.
probably pretty OK.
I'm not going to show you.
The definition of this Internet for
it I need some idea but it is a little
bit complex our definition but
I promise you that your function is just.
And by based on this I define across
in flow between the two words OK.
So to define this one for
every word has X.
in order to define
the crossing flow from X.
true for to see why.
I need to first to find
a correlation of vertex X.
here of X.
is basically a vertex in the other
graph which have a small which have.
In the sense of the multitude of her and
also have smaller able to just and
assume I can find this one
I can find such overtaxed.
And if zero is not unique.
And then once I determines overtax X.
pry the crossing flow from Marks true
why is the internal flow from X.
privat why prior to.
Yes.
And them.
And again if I cannot find
any correlation forwards are just a sense
of the crossing flow to be zero OK.
And OK now we have a function which should
build up a relation between verses in
university but again it is not a matching
because of what has what I can receive or
are we sure about how.
So we need to be.
If you do this.
The idea to do this is true
redistribution of crossing flow.
Meaning the answer for
the crossing flow extra why I
redistribution the flow to other verses.
With the restriction that the British
were to flow from have the summer for
the rich will from as to why.
The possible verses say is
our panel by the crossing and
the cover saying here is another construct
designed to for every work hacks
the redistributor the flow from two to see
the word has the why redistributed flow
to see is after banning
the received internal flow from Z.
and the way this truth to constraints.
OK Basically if this if I me for some
word has to use a rift if there's some
crossing flow more than I need to receive
the internal flow I just suppress and
then smashing Valeo between two words
this is the richest will flow from X.
to Z.
We are all the possible versus Y.
OK And then you can show that
if this is a rational match
I mean the first condition is easy it is a
diff it is it comes from crossing flow and
the second the condition it
comes from this condition
this is in the definition of the internal
flow because you are in total flow
I revert how to stand out how
you need to model flow and
we are the redistribution is the only
receives I'm also seeing a unit about.
OK And now we have a fraction matching.
And we still need to consider the true
conditions for a smile business.
The first condition is
a machine with two and
the second is the word has the verb the
verse the word is person only have noun
the off nonzero matching value
it was our liberties in this
we need with us this is two conditions
based on our definition of marriage.
Or into the first the one
we are serves as a if.
As a fraction matching is have a side
close to him that it actually impressed
that for most of us is why it is received
the crossing flow is close to the rest of
the internal flow this is by definition
of a fraction of the crossing from.
And so we can first of this addition
just by hosting this condition for
most of us and
to do that is what defines the matching
words warehouse which I mentioned.
For the big picture.
We do you have the earth is a matching
warehouse of why use the other graph if X.
is a correlation of Y..
And also verses are wrong X..
Have a correlation around the Y.
with this which is constrained.
I mean you can see this condition
is basically how the four was right
concepts and the way shows that.
If we actually use them as
you work herself why them.
And also for
the most the verses are wrong X.
and also correlations for the first
house have a small pairwise small
distance than is received
the crossing flow for Y.
is cold sure it's actually so
close to it so received internal flow
and this implies that to you for
most of the verses in graph G.
here has a three to one correlation and
also correlation have small.
Distance and therefore the most overtly
seen one of each it has at least one
matching birdhouse that is
enough to have this argument.
So it has to these two conditions
using it as a matching vertices for
both graphs meaning there's a want
to accept if all the world says have
at least one matching what I see is
the other wife and all these measure words
are close to each other as Mater
agitators and the way to judge the for
other is a constant fraction of
the verses does not suffice OK And
this has been using now through verifies
this condition for our constructors.
And the for the second the condition
where once is the verdict is Paris
have a non-zero measure of L O only if
there are bodies there seems more and
clearly our construction does not.
Satisfy this condition for
now because it is because of the internal
flow is defined upon every pair
overseas and it's impossible to some
there is some for some pair of words is
larger as distance with non-zero value but
our internal flow make sure that such
Piers I mean all the pairs always largest
since the flow of total
power flow is not orange.
So we need to reverse our fractional
matching were first the remotest crossed
crossflow and redistributive flow for the
case that the crest punning pair of verses
each have large as many
here as distance Y.
uses the property for the internal flow
we can show this to stab does not hurt.
Too much just a small factor and there
were also removed the crossing flows and
the reduced water flows for the case that.
The cross ponding pairs overseas have a.
Label these terms much larger.
Distance as possible and
I can also directly Argos add
to this does not hurt as a.
Fraction of mashing but I can use.
Probably testing to verify it is two steps
that is the testing distance military.
But should I want to accept you for
every pair of verses the level
distance is a close to the.
Distance and
the real challenge if some reasonable
fraction does not satisfy the property.
And the why I put this
together I can shows.
I can tell that it is to us in this.
Way this is our.
Big picture for the testing.
OK I'm not too going to give more
to help but let me wrap up so
in this how I present
a new result testing.
You know probably testing.
Using and true this quote however logon.
There's a very good question it comes it
actually comes from this one verse this
is coming from this part I'm having
to talk about it are complex.
And the main message I would like to
deliver results are the actual information
is useful to bypass the law banning
is a classic example of model and
also how past Shui improves our ism
your classic example of models.
There are quite some open
questions the first question is
Is there truth to this course
of a lot of factors necessary.
We can generate his knowledge but
don't know how to do that for
some technical reason.
And second can we improve is wrong and
exploring time so currently
proves the feature must be a have long
term polynomial and our resulting C.
The is very intrusive out of law again
because we need three numerator caught
at our side to swallow all of them so
the question is can we improve it for
example to close upon Ami or
even better the second one is that.
For the same problem first parse case but
for the first pass case
you need to have different models there
are quite some work for example for
the hyper finite apparently group of four
the arbitrary degree forests but for
general problem it is still.
The last question it's actually what I am
very interesting So there are some work
on graph isomorphism as more and
more ways and probably testing and there
are also some other work around function
isomorphism problem so here are you only
find a form work for all these are small
things and has problems on the.
OK that's it thanks very much.
OK You look.
Yeah.
I mean.
It was.
Something.
This one is that this one is the exact and
this Y.
is are bonded by this because
if the reason is as if two was
isomorphic I and if I choose a right
of course there is the isomorphism
projection will give me this condition so
I only want to accept this one.
So.
I mean they are.
The cars that are right yeah.
You know what do you know we only
use this to replace our original
distribution closeness.
So we require you to submit
all these I think we
all need to distinguish the cases of the
two distributions are I don't you whole.
Have one of these days at least I have
seen so use this one to replace is
a different thing for
the second step to verify the projection.
Yeah we do not really need this
condition where we need to relax
is a conditional bit but.
But but
is more complex talking out of line and
I answer the question a little bit so
this is the reason for I need to
to those fall out inflammatory or
if it is because I need to choose
the right prime of her to make sure that.
To make sure that.
The number of the number of expected
a correlation is a predictable.
So basically I mean that So that means
there is an unusual cruiser prime there
are I want for most the verses.
The number of correlations
with seeing this Hyperball or
if he's somehow stable is he that
means the most the most the verses I
mean there is no match for words this are
most around as a severe so that I need to
choose a proper set of this condition to
choose that condition I need to carefully.
I mean basically I need to do
some geometry properties here.
And there is a trade of four As for
the how many how many R.'s I can choose
and what the size of the inside because
and they don't need I need you what I need
revenue to do is that I give up work as I
have a pretty sure how many words how many
coalition you see have a need to further
tests if this number is close to my
expectation so this is the truth this
is comes from the truth of the size
of the the this is the verses
inside of the ball and
the how many possible that
a predator I can choose.
Very OK since I don't.