Proximity Prize (workshop) (Day 3)

Transcript

It's about 50 jumps and I think it would be good for this to like >> JMA. Can you hit the bottom unmuted? >> Yes. Can you hear me? >> Yep. >> Yeah. Sorry. Usually I'm just loud in Italian. Okay. So, for like this part, I think it'd be good to like there are two things that I think would be good to do some progress on. I think they're both relatively like easy to attack. Just a bit of combinatorics and a bit of programming. Okay, let me start with a convenient spark maybe. Well, okay. I'll start with programming because more difficult. So, we have conjectures.

Conjectures like require like some sort of like numeric to them to back their like the formulations. We know like that nobody's broken them yet. So, this gives us some confidence in the conjecture. But I think one thing that I really would like to make some progress on is to try to set up some numerical experiments that can help us get some confidence in like the bounds. For example, this number is the only site and yeah, so Antonio like just here is like already like started setting up a script as a starting point to test like the to test the these parameters. And the two things that we want to test is kind of like

so in this conjecture we're going to have like a batch of like parameters. So we're going to have a code to have a certain domain size, a certain message size, it will be of some field and we kind of like figure out what happens when like n is small, f is small. So when all these parameters are small, so we are like in a computationally tractable regime. What happens? Of course doing this like naively is uh is hard because for example the number of like things that you have to test with this is kind of like the number of the number of code words which there are like you know th to the n many squared Yeah. So we are what we're looking here

is kind of like trying to figure out what are like good ways to find counter examples of this conjecture in the small se regime and ideally we would like to brute force and get like some numbers of like you know figuring out what kind of like asytoic behavior we can then expect. Okay. So this is going to be like the the part of like the let's call it the numeric part of this jam for which we will like go with Antonio and we can show you what we have right now and think of way to improve it some of the problem that we have at the moment.

Okay good. So this is the first part. Second part is about like figuring out what happens when like the syntic behavior kind of like approaches the limits. So okay you can see like indeed this is like a very good community. So if you look at this gap right there will depend on a delta your delta is a distance the distance down because of this value.

This value is kind of like how far delta is from the proximity from the capacity. And the behavior that we expect at least is that ETA should appear like the denominator of the bound. And the reason is that when ETA is equal to zero, we know that this error is actually one. When EA is equal to zero, we know that the conjecture is false. So the behavior we can expect is kind of like a smooth transition. That's like as ETA grows so we get farther from like the capacity we expect the error to decrease.

In the case where for example think that ETA was like one overn so like there's only one position in the code word which which yeah exactly one position in the code word which is which differs then I think that some very nice simple combinatorical arguments about unin should be able to give us some u some lower bound on error. So what I I would like to try to do is try to like formalize this kind of intuition and then figure out what kind of errors we can expect for these kind of things. And this will kind of like tell us if this bound is something that we can even opt

for or if in reality we have to have like some like you know maybe we have to say that is such as some other conditional for this behavior to appear. And I think this particular thing should require only a little bit of communatory a little bit of counting and I think everybody but me here can count. So I think we can try that. >> Okay. Good. So I say like for the purposes of organization we can take like let's put this side will be working on the on the code part and this part side will be working on the combinatorics and I can like uh uh slowly kind of like sketch what the approaches are for both of them. Sounds good. Okay, good. Arrange yourself in whatever way you like.

>> You do both. >> I'm just >> I started like few weeks ago because I was working on like You can open up like this.

Yeah exactly. once Okay.

>> I'm going to be like We can record this session. >> Okay. No no but it >> let me try. But I never speaking about that.

>> Okay. So, okay. Solomon, you know, any variable domain D3 can >> you can you use >> okay so okay and I'm going to yeah and my my rate row is K over N >> and you kind of all >> right so suppose that I tell you like that.

So why is the reason that like at capacity we know things? So remember what is the condition of like mutual agreement? The condition of mutual correlation is that the probability that the delta of f choice gamma f_sub_1 + gamma f_sub_2 is less than any letter because they are and distance f_sub_1 f_sub_2 from This is equivalent to normal agreement.

No, without mutual just in a single pro. >> Okay. So, what's the issue? Well, >> this is already mutual. No, >> no, no, this is not mutual because the the the mutual would be if like this they're going to be close to the interl but they're not guaranteed to be close. The second condition doesn't occur. >> Exactly. Mutually it's easy if you also say that they are on the same side. >> This is just theory. >> So what the claim? Well, >> that's not what makes sense for for every function from Lic.

The distance of f from the original code is less >> than one >> minus so I'm saying like >> so in particular why is it relevant for >> well this that means that basically this condition is backwards because this all for anything so anything that I have in the line will also be close to the the threat but this is not possible rights to >> it I think so because we can do a counting

argument >> it is >> so it just says I would have put the the thing outside the probability because it doesn't >> so so so given that we know that the distance is larger than only few randomnesses that's the small >> epsilon >> can fold us down combine us every point is close >> well that's for this oneus row is the covering radius of >> so that's happen >> yeah exactly like I think I'm not exactly sure but I think this condition I can find two code words that have you

know they agree with the Solomon code in a individually but the interle one does not agree >> first agrees in the first half and the correlate agreement is sort of >> yeah you have to play around more than halfus right >> well take the row one half >> and the second half Sorry.

>> No, this is just saying that the covering radius of this code is one. >> Yeah. Which is >> for me is like the degree one. Yes. I think the first part of this condition for for agreement.

>> Yeah, exactly. So like saying like when we put our delta to be like you know exactly one minus O. So this is when zero. This is back this is like a vacuum statement. We don't really tell it anything. And uh in particular if there exist like two code words which have not corre they're not in correlated agreement with each other then the error must be one. Okay. So it's very >> not right the distance is n minus k plus one but there's this weird thing where non code words are actually closer to code words than code words are right

other words when distance between a word so you know for all w there exists c such that distance between w is less than minus k right but this is this is different for definitely true because okay sorry >> yes so then this is this is what we want >> so the claim of this is just that I'm going to take f I'm going to a subset of of f of size 1 - I'm going interpolate

and this gives me a code word which agrees on exactly that that condition. >> So this is true. Okay. So this is the initial part of it. So one and so what did at least tell us is that when delta is equal to to 1us we cannot really hope to tell anything >> later. Let's figure out whether this happens. >> Exactly. This is this is this is step one. >> It might just it might still be true if this doesn't exist.

>> Yeah. But what I could do, I can choose F1 and F2 and like interpolate them at the same location and then I get the two code which agree with each other in the same location. So this is actually both. >> So there is zero. >> If this can't happen then the conjecture is actually true. It's vacuously true, right? >> Sure. But yeah, exactly. But they're best kind of like >> everything is like needs to be like a linear leadus like like if

it's also going to get a break, right? like it should be like minus that's what I want to figure out like when we have like for me like the simplest case is when is uh one n so now basically we'll have code words you know this argument does not directly work and now we are like in a case where like you actually >> sorry so what's here is delta >> difference between delta >> oh I see from >> yeah so 1 - row minus delta. I think if I'm not getting there wrong.

>> Okay. Is this this saying isn't this saying picking a random code word? What's the chance of agrees on a polomial of length k on k plus one points? Right. >> Exactly. This is exactly the the argument that I think we can make here. >> I think you just bin right almost like almost probability. >> Wait. This is the part to explain this. >> So, so isn't like like so so the reason n minus k breaks right is is that we say so so this this state say what's the probability this agrees with some coordin of of size k on like k points and the point is that here is do interpolation and so here is say okay well we don't want to be on k points we know k plus one points and my statement is well we can just take all subsets of k points do

interpolation of them >> and the question is like do we get a collision and and am I saying this by by like binomial arguments? There are like so many subsets of cable. >> Are you allowing >> are you allowing f1 and f_sub_2 to just be like arbitrary junk? >> Yeah. I'm saying take a random word. Just take >> you're not even caring about this. >> Yeah. >> Yeah. >> Okay. >> You like there are some of them which are like they do not agree with each other in a correlated manner which I think you can also do with accounting argument. That's the second part to prove. >> Sure. So you find first you find that there are f_sub_1 and f_sub_2 which do not agree with each other in a correlated manner >> and this is probably just counting argument. I think there's something similar of this in the ACY paper that

you can do and then once you're there you can like start looking at like random things for each one of them you use against the correlation and you see what happens. >> Yeah. Yeah. Because you I'm saying just count the number of subsets of size K. >> Okay. And each one corresponds to a code word. >> And if any of those two subsets correspond to the same code word, then we win. >> Why? >> Because them corresponding to the same code word means we can find a subset of size at least k + one with with nothing agrees with the code. >> Yeah. >> And since that is compatible with the result actually.

>> Exactly. So this is exactly what I think happens in >> but how many subsets of What? >> Yeah. Yeah. But it's quite polomial. Yeah. >> I mean this argument is just the the usual angle argument sounds like a common argument but usually just applies when you know you have the list size

bound. >> Absolutely. Yeah. And in a lot of settings bound will not tell you anything. in some others it will both different >> so there will be some bad dependency but what I want to figure out here is exactly what this is dependency what is the relation and what's best we will know >> yes so is it like when I have two different randomness and they have the same approximate I'm not even talking about the agreement set then I can then I can invert by linearity and and construct a correlated proxy.

>> Yeah. >> Exactly. So this is the this is what I think is interesting and then if you manage to get like an argument which is agnostic on like you can kind of like start thinking how how this behavior >> kind of do >> but what like what epsilon I don't really get like you need to be very >> bas You're saying that every >> What about the intersection size of the agreement sets of different gamma foldings?

>> Okay. So, I'm going to talk about I'm going to come. >> Okay. Good. The interpolation of So now things do classical

the seven you want to figure out from which >> I mean it sounds to me like the classic covering radius we know is we know that anything of degree like one too big to right is not it attains the covering so for this to work you need to argue that like there are few point in other words like

degree K is not smallite So when you say you mean like so every point is close to right >> sorry isn't when I say I mean they >> you want the distance between any word >> is most and my statement is that for the vast v if you pick a random code I can tell you the ones that are distance exactly as I can tell you what >> they're 3k pol.

>> Oh, perfect. Yeah. So then I say if you pick a random polin random not >> random word probably one >> it's probably not the evaluation of that is a random word will be just by just by consideration. Are you sure? I mean those those are definitely those. Why can't it be >> anything? This is actually a conjecture. I think it's actually so certainly a if you pick a random code >> probably even

this is like this is my life. that we know that's a common like delta shouldn't be one much less than >> outside we know that we have this unifor with these just compare with proxy.

Okay, there's only one which I know I have my F12 question what is the F1 and F2 that we use? Well, we kind of like need them to like be F1 and F2 which do not agree with each other in a correlated way.

>> So we can I mean the maybe even easier thing that we choose them so they don't agree with any code and we just try to attack agreement to other correlated agreements because anyway an attack on agreement will translate to anything else >> right. Yeah. In this you're you'reing >> yeah agreement is that we can property attack from the in general like

kind of like and I want to kind of like figure out to it I make a strong assumption like there how do I disprove it how do I well what I can do I can choose like in some way the other notation I on the other board right then I will have S1 and S2 >> and I kind of like >> this will be like the line spanning them like connecting. So this is like S1 >> and for simplicity I want to think of agreement now. So what's the agreement?

the probability I'll turn the for like the thing the probability that like >> well the one delta and the delta this is actually so this is the kind of thing that I want test.

So currently the way that we have correct me if I'm a moment Antonio is that okay I choose these two functions input then I choose them so that this thing so I want to choose them that this thing is false so that they notically play with with and then what I'll do I like for each gap for gamma I just look at all the lines for the line I look at what visa is there from the code and the way by so my complexity naively kind of like my

for each pair I feel like No, but I'm taking an F1 F2. >> I don't. >> Yeah. Yeah. I'm going to fit in for now. when I figure out for a single function what is so for each one of these when I want to look at the ball around the ball and am I this action

And like I want to look at the other nearby >> like the old downing bolts that are nearby today like landing like competitive which is pretty bad because I think this thing it's pretty it's pretty bad. It's pretty

bad. Now the question is whether we can be more clever about this. So in some settings we can be so for example if I set actually my delta to be in the Johnson bound what I can do is I can rotate it with one obvious thing I can do and it is already nice because I can figure out whether it's quadratic or like so this is like a starting instead of you just want to improve the existing >> yeah I want to figure out whether the n

the existing bound is n or n probably like this thing you know I don't know if you small number you don't just >> sure but Okay. So, your error more than one exact one we care about.

Uh and maybe we have we have anything or we like power. Sorry about I was having >> I was having like a

>> like be very Royal Brian.

Okay. Okay. can go six and 14. >> Yeah. 14 is >> Yeah. Okay. like >> that's

an object. and what I don't need to all words all like or all words I can just like throw out a few ones and see what happens for most of them it will be small but there might be you know a word they're probably the worst case it's good it would be good to to find a way to set up that code words as So this is one of the approaches and >> that one is like okay

>> I would like to try to also use solver and I have no idea how they work. >> I mean just believe But I think if you want to set that this will be able to write you have you know variables and then you want to set I guess a bunch of variables which correspond to different cases.

I guess the annoying part of the fields. And then you have a bunch of variables which are like What is the degree of that? That is

larger than >> because subtracting off will not decrease your degree. >> Yeah. >> Sure. >> That is that is okay. So this has more than K. We don't whether there's more than zero, right? You could have >> you could always have zero. I'm pretty sure I think there's a pretty >> Exactly. Exactly. >> It could be that you have zero. >> Can it attain the full amount of zero? >> Wait, but if it has more than one zero, does it have >> K? No, no, it has to have >> you want it to fully k.

>> Why? Why can you easily get K? >> This is the same because distance, right? Like you can always get K. Like this is the statement of distance minus K. >> Oh, sure. So, so getting ker is equivalent to covering radius, right? So, the question is um so >> can we can we just count the number of of of C's or like choose the random C and comput the probability? I think this is a hard problem. I think we should and see if we can prove it assuming >> I think these two problems might not be equivalent to be honest. It might might well be equivalent in some sense. Oh, the Jakamo thing and yeah >> like I think I think you wanted to construct something with

one zero. >> Yeah. >> K plus one zero >> because if you have one should know where it vanishes. >> Is this a fair statement? We start with something of degree >> then this vanishes also when this one >> Yeah. Yeah. But we can only um I think is that we can only add on the column with degree less than 10. >> Right. So you have f and you want to subtract f is arbitrary and c has to be >> so I need to add here something less than yeah yeah but this idea I completely agree it's >> this one >> sorry p could have a fairly high degree >> so

>> yeah because if this has that might have degree like 10 >> yeah I was I was thinking maybe since this degree one and this makes up for the degree. >> Yeah, but >> I would need something with a multiplicity for this, >> right? >> If I if I if I build something with a double zero, >> yeah, >> uh then at that point this one vanishes. >> And if I evaluate another zero, >> okay, so >> yeah, the question is Okay.

>> Okay. Maybe we should So let's >> Yeah. Let's just assume this holds. Yeah. This claim, >> right? Yeah. Um reverse direction. >> Okay. So now claim You want to come?

>> Okay. Do >> we need to say do we want to say so I want to I want to say that the combination will also Okay. So,

>> yeah. So, so everyone Yeah, you need to kill the high degree part of of like f1 or >> and like that just >> would that be just one gamma >> at most. So then applying the plane we're basically done, right? So like >> what does that mean? We have prove it with one. >> Yes. So so that means that not X1 will be so bad that it will be like size of one.

>> Yeah. >> Or all of them but it won't be less. >> Yeah. >> Yeah. Exactly. >> We're pretty sure the one on is not going to help us here. You know, to go a long way a long way. >> Yeah. Even with n even kus one we still can possibly >> so my my very conjecture is you need to get to like n >> I think anything that's like linear and

n I think you're going to be able to do this sort of essentally The idea is that we know what the covering radius of the code is conjecturally like to know which words attain the covering exactly which ones are okay. >> So one those things are actually very far from every distance. >> One direction you can prove and the other I think is actually a conjecture. >> What does what does anything show? >> Um That means okay I can now pick you two that so neither of them is of small >> neither is a

so I have two that are not a >> and then you say so that's sort of giving you an error term >> so it's a very large so this actually doesn't make sense for the vast majority it will be this one that's what >> you want to say with high probability this is a counter right >> the counter example means they are both not degree K but the combination is degree that has to be like the hypothes is is like

>> oh >> this is what we put a It's like not >> so you say this is a of degree >> just just not equal to K >> not yeah maybe right right no you say you say this is of degree not equal to and because of this claim we now know that it has less than distance which is like n which is like 1 - >> less than the cover does not equal the provided why we don't both of that's the only case that just like doesn't work.

>> Oh yeah. Okay. Well, no, we're good. We're good. Exactly. So So start with it to be not. >> Okay. Then the only the only thing we have to worry about is that the combination becomes of degree K. Exactly. >> And that just won't happen for most. >> Okay. Assuming >> what this claim is >> the claim is that the only words that that attain the covering radius >> are the degree k polic okay other thing will not >> be less everything will be less than the covering radius >> okay so wait so what's the claim what the beacity >> no you are saying if if if we go this is

going up to capacity like equals zero right >> this is = 1. >> So when a= 1 n let me just translate what the statement even is. So the question is if we have it if we have a line we need to look at so close to the code >> but they are close to the code if this holds they are close to the code. Why is that? Why is that? They could be bigger than K. They're not close to the Oh, I mean like they're not very close in the code right? >> But they have >> they have a distance that is less than, right? Technically, we we need F we need the correlated distance of F1 and F_sub_2 to equal covering radius for this to or or be greater than or equal to cover greater than covering.

>> No, for the pair >> the correlate correlated radius can be worse. >> That's the whole thing I was asking about. >> Right. Right. Right. But but this is just saying I mean if they could even have like a smaller >> but then you know but in order to disprove >> okay so we want to show towards f1 and f2 >> yeah we want we can choose towards but they they should have correlated distance that is greater than yes exactly so greater than or equal to n minus k and then we want to show that many points on the line >> right but why doesn't this show that >> I guess this doesn't show I guess you saying like >> well this doesn't The argument is that like so the fact that like f1 and f_sub_2 have >> here's the game okay you give me a pair

whose correlated distance is bigger than or equal to n minus k >> what I want to show you is that many points on the line have distance less than n >> I agree but that is not what this is saying >> it is though it is because the only thing I need so so >> so I win if I show you many points on the line whose distance is less But by the claim it's equivalent to show you that many points have a quality not equal to K. If they satisfy this then they already have distance less than N. >> No not correlated >> not correlated >> correlated correlated distance.

>> It's on you guys. You guys are the ones who told me that that the correlated distance can be high. I believe you like in the case where equal to zero. I don't think it's true actually. >> Okay. This is also >> is it? That's what we were arguing about earlier. >> This is just like what's the largest? >> Oh, just interpolated the same place for both. So yeah, exactly. So then you so then correlated distance can't be bigger than >> so I guess also applies.

Exactly. So >> wait but waitition is true for that have bigger than covering okay you have an equal covering radius I actually don't know with an example >> you mean equal to >> you could have both degree k >> the question is can you have an equal degree >> then they must have okay then they must >> yeah no I can do it easily just have one degree Okay.

>> Okay. Great. And then does that you're claiming that that equals >> it has to related >> because we know that the distance of one of them is nus. >> Oh, and it can't be bigger. So it must be at least that. Okay. And then we're done, right? We're done. So start with a pair that pair. >> Okay. the the correlated distance is equal covers and but for the vast majority of of gamas the degree will be more than k not equal k but more than k and therefore the distance will be less than n minus k not equal n but less than k >> so we're done >> so you think the vast majority of the direction the degree will be larger

larger than K >> larger than K. But the degree of the claim >> the claim is that if the degree is bigger than K then the distance is less than >> less than okay. >> So this this thing >> is not of degree K. So it's >> this is less But this this actually needs only one of the direction of this this claim. But I think it's the one that we it's a distance degree bigger than K distance.

>> So that's the >> other bigger distance. >> Yeah. Yeah, but I think that you have a weird white. But one should so the intuition is start

with something of degree bigger than K and then range over all possible code words. So for each code I want to find one so that if I subtract out code then I have many then I get something that has more than the question does there exist a code word that does that >> I see and therefore you have to do a counting argument. Well, I I think this is actually not but is thought. It's complicated like it's a research like >> you reduce it to a different project >> for like when the parameters like like really >> really what check

but this might we should check the status of this because somebody double check >> yes do you know where >> I can I can do is like the false depends on >> number of games for which we know >> well Let's get one n I think you can

like I would be shocked if you could have one. I feel like you need to take like you need to go. >> He's saying that your distance from capacity needs to be uh like omega basically >> but typically like what the English most in practical thinking that I said that would be divided by 20 >> that's fine because rate is assuming that rate is constant.

>> Yeah. So rate is like Yeah, exactly. So, but but K grows with >> N. So, >> okay. So, like the one like the setting where you have it should be omega. So like - one thing that I want I think is quite interesting is that one now what that we can do is that now that we have like gap in the proof >> now like one

people working on check this. >> Exactly. So now like what I would like to do is like we should keep a document where we write down this kind of things and write it down like move it to the numeric. So they want to create a ripple. >> Yes. >> Can also be an over >> I don't guess it's called deep. That's the magic

Google deep. So deep is a word that achieves. So the question is what are the deep >> okay the time that we have >> okay I'll set up the two things like you I guess the question is like I know like another like

another argument where it gives me like some kind of bad depending kind of like a kid of the field in so this kind of like setting you really like it'd be good to have like a collection of like possible attacks and things that we know that we think about the convers Right. >> Yeah. What can you prove?

>> I think I think people have prove I think you said someone you can prove a lot that actually work. >> Oh yeah. >> Yeah. Exactly. >> Yeah. I mean I know that this is the me and Ben have a bunch of examples of code of like achievement because our example in the achievement event >> the other thing that I was like the like this is their other close and it's

kind of different because >> yeah capacity or the range like very trans. So which is maybe another one we can consider like when the when the rate is like enormous huge turns out it's also how this condition will attack also. Yeah. Yeah.

>> Results like you know one over. >> Yeah. Okay. I'll write a very interesting playing ground as well. >> Sure. Sure. >> Yeah. Yeah. Yeah. I agree.