Digesting better.codes

Transcript

page Uh so yeah, I'm going to try to explain the basic idea of this what's called hidden derivatives. Um so I'm going to focus on on the simpler setting of just bounding the list size. MCA it's a more complicated version. Uh So yeah, to fix some uh parameters, let's say our domain size is n. A is our agreement parameter. Uh K is the degree bound. Uh X is our is our set of evaluation points for Reed-Solomon.

And Y is our received word. And now what we're interested in, we're interested in this agree set, which is all polynomials of degree smaller than K, uh that agree f of xi is equal to yi for at least a xis. Okay, so this is uh this is the set we're interested in. And our goal is to be able to give a good bound on this agree set for as small as possible a.

>> [snorts] >> Uh so uh to understand the hidden derivatives idea, you you need to first understand uh what's going on in Sudan and Guruswami-Sudan. So we're going to start by seeing the basic Sudan idea, which allows us to get to a, which is square root 2kn. Uh then we're going to see how multiplicities in Guruswami-Sudan allow us to to get rid of the two. And of course, the idea in Sudan Guruswami-Sudan was that all they also allowed you to efficiently find the close words, it's not just about bounding the the number of them.

Uh and then we'll we'll see the you know, the most obviously the interesting the most interesting part uh by uh mainly by Nascremski uh which is how to how to get below uh Johnson in in this like uh setting of parameters below uh square root of KN. Okay. So, what what's going on in in Sudan?

Uh The idea is to define a bivariate Q. Yeah, I don't know what's going on in in actually in Sudan uh but but back in '97 they were had interpolating polynomials. >> [snorts] >> So, uh the idea is to to construct a a a non-zero Let's say we have some bivariate Q uh and polynomial and univariate F. So, and let's define this notion of of the jet polynomial of F with respect to Q uh which is simply what you get when sort of substituting uh the curve X F of X inside of Q,

right? So, this is this polynomial QF. And the the idea um the idea is to find a non-zero Q uh of low degree uh such that every F in the agreement set uh for every such F QF is identically zero. Right? That's the basic idea of of the Sudan paper. Uh And of course uh right?

This exactly means that if if we look at F is is a unit Sorry, if we look at Q as a univariate in Y, this exactly means F is a root of Q. And so, uh if we if we get such a Q, and we know that the number of close codewords to Y is is at most the Y degree of of Q. >> [cough and clears throat] [snorts] >> So So, how do how do define Q?

So, we're going to find Q with uh that we can call this thing the weighted degree of Q, such that the X degree of Q plus K minus 1 times the Y degree of Q is smaller than this agreement parameter A. That's one thing we'll want from Q. And the second thing we want from Q is that for every index of the received word, Q vanishes. So, for every X I Y I, Q Q is is zero. And uh the the idea is that if you have such a Q, so now take an F uh in the agreement set.

So, we know that for A values uh I, Q of X I F of X I is zero. And at the same time, we know that the degree of of Q F is smaller than A, right? Because if the if this weighted degree of Q, right, what's going to be the degree of Q F, right? We're substituting inside Q this X {comma} F, so so the degree of Q F is exactly going to be this weighted degree of Q.

So, if we have such a Q, then for every F in the agreement agreement set, um is going to satisfy these two properties, so it's going to have more than degree zeros, so it's it's it's going to to uh vanish. And please yeah, ask questions at any point. Okay, so that's that's the idea of how to to define Q.

And now right the sort of we need to to see this this game of of coefficients first constraints. If we want to find a non-zero Q, right this this this constraint Q of X I Y equals zero, it's a linear constraint on Q's coefficients. We want a non-zero solution. We need more coefficients and constraints. So a lot of a lot of this type of work is like counting coefficients first constraints. So the number of constraints is N. We want for every I that Q of X I Y is zero.

The number of coefficients, so again let's I hope I I can't go back. Or can I? Oh, it goes forward once and then starts going back. Okay. I get it now. Right, so how many how many coefficients do we have where this weighted degree right sort of deg X Q plus K deg Y Q is smaller than A, you can you can see that it's it's roughly um it's roughly A squared over 2K over over 2K.

Um right the sort of because because of the the weighted degree in Y, it divides it by by by K. Right, so so we need N to be smaller than A squared over 2K, which which translates to to this. Okay, so that's that's the basic idea in the in the Sudan paper. Right, and again it's not the theme of our talk, but but the idea is that once you have such a Q, you can actually find the closed curves words cuz cuz you can you can factor Q and then the factors Y minus F of X will exactly give you the close codewords F.

Okay. All right. So now let's talk for a minute about multiplicities. Uh what does it mean for a Q to vanish with multiplicity M a univariate? Uh it means that we can we can write Q of F as X minus X to the M times some polynomial G. All right. So this is a this is a zero multiplicity M. And sort of the the question we we want to ask ourselves is what property do we need from Q so that if F of X is equal to Y then this QF will vanish with high multiplicity. Let's say for simplicity

multiplicity two. >> [snorts] >> All right. So the claim is so suppose F of X is Y uh and now look at the Q shifted by this little X little Y. And the claim is that if this shifted Q has zero coefficients for one X and and Y then QF will have a zero of multiplicity two at X. All right. And of course in general the uh you know, if you want multiplicity M so you'll need the all the monomials of of of of degree smaller than uh M to be to to have zero coefficients.

And uh I think this claim is is makes sense is is believe but yeah, basically to to prove it you you sort of just substitute uh you say you shift Q by by little X you substitute uh and and you just write it out and uh uh and and you see that it it corresponds to to sort of Q prime. Well, I I I think I don't want to get into the exact details here, but I think this is believable this this claim.

So, the the idea of Guruswami-Sudan is that uh the this game of of coefficients going with versus constraints is is going to be in our favor >> [clears throat] >> uh for for higher multiplicities. So, now say we uh beca- because we're going to use multiplicity two, uh we're going to now I'm going to allow you to to use a Q where the weighted degree has has gone up by by a factor of two.

Um and now I'm going to ask instead of just to vanish at X I Y I, I'm going to I'm going to ask for this property we saw in the claim that the the shifted polynomial, the shifted Q, has zero coefficients at one uh X and Y. And then we we see that if we have an F agreeing with Y in the agreement set, so now for A values we have that X minus X I squared divides Q F.

And we have that the the degree of Q F is smaller than than 2 A uh because the weighted degree is 2 A. So, again we can we can conclude that the Q of F is is identically zero. And and the thing to check is that this this sort of ratio between constraints and coefficients has like worked in our favor.

So, now, how many constraints do we have? Well, instead of one constraint for evaluation, we have three cuz we want the coefficients of 1, X, and Y to be zero. And what's happened to our number of coefficients? Well, our total degree has increased from A to to 2A. >> [clears throat] >> And and you can see that this this makes the total number of coefficients uh go up actually by a factor of four.

If we had A squared over 2K, uh now we have 2A squared over K. Um So, we need 3N smaller than 2A squared over K. Uh or equivalently, A larger than square root of 3 2KN. So, we went down from square root 2KN to square root 3 2 over 2KN KN.

Uh Yeah, and Guruswami-Sudan showed that if you take large enough constant M, you can you can get as close to to the Johnson bound to square root KN as as you want. >> Okay. So, so now we we get to the to the

new thing. Um So, so the idea in in hidden hidden derivatives is let's work now with uh with a trivariate Q. And and redefine the jet polynomial to be Q of X F F prime. Um And now again, we want to get this property that if F is in in the agreement set

uh Q QF is identically zero. So, at first this seems hard. Uh right? So, we want cuz how are we going to define uh we want to define Q so that say when F X I is Y I, Q of F vanishes at X I. Right? But the but we have the received word has no information about F prime of X I. So, how are we going to define Q?

So, this is sort of where the name hidden derivatives comes from. I I have no information about the derivative value. But still I want to define Q so that when uh um F of X I is Y I, uh even I I I I vanish. QF vanishes. Any Any questions so far?

Okay. So, So, how to define Q such that uh when f of xi is yi, Q of f vanishes at at xi? Um So, basically the idea is since we have we have no information about f prime of xi, the only thing we can do is we we require that Q, when restricted to xi yi, is just the zero polynomial in Z. Right? That's the only Since we don't have no idea what f prime of xi is going to be, that's that seems like that's the only thing we can do.

Right? Um so, So, to write this and and the in sort of the intuition, which is not which is not totally right but is not completely wrong and sort of in in how much it's not wrong, that's that's sort of where how much you go beyond Johnson. Uh we we can think of in this trivariate setting of an uh of a constraint that is like identically zero in Z as like just one constraint in the in the XY setting. So, sort of like say if we the degree in Z is going to be S, this is not accurate, but sort of we've

the number of coefficients has gone up by a factor of S. So, like an identically zero in Z constraint is sort of similar to a a single constraint in the in the bivariate Um So, let's take let's sort of take that as an axiom. Uh so far it's still like we haven't gained anything cuz all right, before we had one Let's say we call this identically zero constraint with one constrain. We haven't gained anything, right? Cuz before we had a a in pseudo on a constraint Q of X I Y I, so it's one constraint and now here also even if we call this one constraint, it's we had one we we still have one.

Uh sort of So, sort of the punchline is that when you go to uh multiplicities because of the way uh via the chain rule derivatives interact with each other we're going to have non-trivial savings in constraints. So, let's let's see that now. So, say now we want we want also we want to get uh that when f of X I is Y I, we want to get a vanishing of multiplicity two of of QF.

So, it's it's not hard to see that vanishing of multiplicity two it's exactly equivalent to both Q of F X I is zero and Q prime F uh and the derivative also being zero. So, let's say we've already constrained Q of F to be zero at X I and we want to get also this the derivative to be zero. How How are we going to So, what does the derivative look like? So, let's use the the chain rule to get the to get the derivative an expression for the derivative.

So, right, the chain rule tells us that right, each time we need to we need to uh de- derive differentiate Q by each variable X Y Z and then multiply by the the derivative of the inner expression. So, right, so we have uh Q we have Q over derivative by X of Q uh plus the derivative of Y by Q times F prime because we had F in the in the second variable plus the derivative of Q by Z uh times the second derivative of F right because we had in in Z the the first derivative of Okay, so this is uh

this is a derivation by by the chain rule. And now again, we have we have no information about F prime of X I or F prime prime of X I. So the only thing we can do is just um when you think about it require this this uh this polynomial in in right so we just replace the the the derivative second derivative by variables the only thing we can do is just require this polynomial to be identically zero. This one?

Why why? >> Isn't Y I F of X I? Sorry, like like like I thought the the the way we did this channel is isn't Y I F of X I? >> Yeah, Y I is F of X I. >> So wasn't our first Wait, don't don't we have our first constraint says that that thing should be zero? >> Uh so our first constraint says that let's see. It says that Q of X I Y I Z is is identically zero. Yes.

>> Okay, so so like we could slash out the first. So like in in that sum the first thing doesn't >> Um but So let's see. So if >> Oh, okay. >> I'm not exactly So you have Q uh restricted to X I Y I Z. So I don't know if that means that this uh this polynomial is is zero. >> I I could be wrong, but I think you're thinking that like Q _ F uh at X Y I Z is zero, but this is like a different jet.

>> Sorry, I think I think you're right. Yeah, sorry sorry. Okay. Yeah, sorry sorry. This is the derivative of Q with respect to X. >> This is the derivative of Q with respect to X, yeah. >> Okay, but yeah, but actually uh this is similar to what we're going to see next, so there is there is part of this expression that we can or deduce is is zero. So, so maybe someone has a guess of what what that part is. Exactly, the third term. Nice. So, we

uh we did uh already constrain Q uh restricted to X I Y I to be zero as a polynomial in Z. So, that polynomial in Z its derivative, just as a univariate in Z, does is the same as as this thing. So, and and this is sort of the the the the punchline that we know we can we get for free that this this thing is zero.

So uh morally we have just one constraint. We just need need this thing, which is some polynomial in Z, to be uh to be zero. All right, so we again, we had we had this this expression, we want it to be identically zero, and it's sort of equivalent to and all all all that's left is requiring this to be identically zero. So, so roughly we have in total two constraints compared to three that we had before in Guruswami-Sudan.

Right? In Guruswami-Sudan, we needed to constrain the coefficient of one X and Y to be zero. And here, uh we have we have we needed to constrain this to be identically zero, this this Q restricted to X I Y I. And just this uh extra polynomial in sort of because we get we get sort of we get this part for free because of the it's a derivative of something we already constrained.

Okay, so any any uh more questions? >> [clears throat] >> Uh okay. So, so now uh I can show if there if there's a request, I can show you I didn't have an I didn't show these these parameter games of constrained coefficients. I I can show it in the paper for the for the hidden derivatives case. It's just more messy, so I I don't have it here for simplicity.

Um but let's say let's say we we we did that. We managed with smaller than Johnson agreement to get that for all F's in the agreement set uh QF is zero. We're not done yet. Right? Because in Guruswami-Sudan or Sudan, when when we have when we have this, we already knew, "Okay, all the F's in the in the list are are just roots of some univariate, so the number of them is at most the degree. But now, what do we know? We just know that Q Let's think of Q as like a bivariate just in Y and Z over, you know, polynomials over X. We know that Q F F

prime is zero for some low degree Q. Does that Does that give us a bound a good bound on the number of of such F's? Um And And the answer So, the answer is Can Can Can someone think of Actually, let me show Let me show you an example. Uh right, you would think maybe a a priori there's like there's a good way to like just Okay, if Q has low degree, there can't be many F's such as this. But look at this Look at this example.

Uh so, say we just take Q X Y Z equals 1 minus Z. And now take any F of the form uh X plus C for any constant C. So Right? So, we get the the derivative of all of these F's is one. So we get it zero. Um So this is where sort of the the second part of Uh yeah, there can be a lot of solutions.

So So, we need more fancy ways of bounding the number of F's with Q of F being uh identically zero. Um And I didn't In these slides for simplicity, I didn't get into to how that's done, but if I I I'm happy to to do so. Uh but uh yeah, so this is the algebraic geometric part in in in these papers. And And this is the part that fails in in characteristic two.

Um So uh As as a historical note, uh it's worth It's interesting to note that before these hidden derivatives, we we had we did have in the literature unhidden derivatives. Um And And what I what I mean by that is what people have called uh multiplicity codes. >> [clears throat] >> Where you uh instead of Reed-Solomon, you have a code where yeah, you think of your message as a polynomial, but now the

the ith symbol of the code word contains not just f of xi, but also the derivatives of f at uh at xi. Uh Yeah so So that's uh I'm happy to go more into details of about uh stuff, but basically that's that's what I had. So yeah, thank you.

>> [applause] >> Thank you so much, Ariel. We're a little bit pressed on time, but maybe have time for one question. >> [clears throat] >> Uh what going beyond the proof, what was your process to go from what was posted on this uh Uh, from this PRs into understanding what was the process of interpretation of the results?

>> Uh, asking asking chat GPT to to explain the the main ideas in the in the submission. >> Cool. Thanks again, Ariel.