thanks Ron so today we will look at three of these concepts polynomial coding theory and all steel inserts and this is joint work with shahar love it so the organization of the talk is as follows just to say so I told a friend he is getting a connector for me i’ll just i’ll be back he is already have to tell him that he is coming all the way from Princeton yeah so so zero randomness of polynomials algebraic geometry coding theory and finally a summary of the results okay so what is pseudo randomness of polynomials so consider uniform random variable x over FB now now we know that expectation of e of x is 0 since x is uniformly random where a of X is e to the 2 pie IX by P okay so then you want something similar to hold for pseudo-random de greedy paws known as you want expectation I use a wide / or something just a small ok yeah ok yeah that’s fine yeah I do so for so this is going to be the setting throughout so I’m going to keep this part on the board so we are always going to look at n variate functions from F to the N to F and we look at the greedy polynomials and important in this talk is d is fixed and so now we want to say that what does it mean for a degree polynomial to be pseudo random well it means that every so here f is FP it means that every every field value is taken with the same probability right and for that you need something like right you want something like this to hold the output is like very random yeah okay so the degree is fixed throughout the talk and but then so what happens if if this is not random you know so what happens if this is actually large it means it is not random so it has to be structured right so what can you say quantitatively about the structure this is the complex the unit circle so so it’s I g of 0 e of one your finest won so e is a shorthand for e to the 2 pi I xyp right is like some a scalar phase

shift so for all a so a is just a is and FB star yeah so you want this to be small for all a right only then f of X would be like completely random function yeah you don’t want it to be large so I mean it’s a very so it’s because if i look at probability f of x equals C it can be captured as summation a a of a f of X so that’s how it works that this is what f of X equals C breaks down is right because now if I ensure all of these are small then only the trivial term equal 0 survives so it’s like 1 by P plus right so that is why usually this is an equivalent way of stating so what happens if it is large like can you conclude some structure about f you know and this is a central problem in algebraic geometry and higher order for analysis ok so again degree polynomial d is fixed so let us say it is like the bias is really large so the reason I say it’s really large because this is the this is like the variance pound right i mean there are like p random variables and you would expect this kind of ask standard deviation so so in such a case you can say that f is actually a composition of only one low degree polynomial and in fact we know what it looks like and this is the veil and Deline bound so so they say that so if then right so so but but this is like really this is like a really large requirement on the bias it says that if your function is not of this form then the expectation is very small which means that if the expectation is large f is probably you know f is then a function of just one low degree polynomial H of X so we want to know okay so I cheated here so I should have written a d over square root P but just to put this in perspective I had to drop the d because i’m going to keep d fix throughout and p is going to vary okay so so my next question would be what if i replace the half by something larger it is a 10 then can you say something in so can you say something like well then f of X is not a function of one H of X but maybe see H of X is see lower degree polynomial and this lower than D yeah because you cannot allow the greedy because then it’s you can just write f of X is f of X and yeah and you cannot say it has to be degree one because trivially it’s a function of n variables so it is really very large so you are fine even if it’s just less than D and that seems to be enough for all the machinery so something like this was proved by green tea and Kauffman love it so they showed that so they did show something like this where if F is not a function of so i am writing the counter positive on the board and positive here just whichever you would like more but then the see here has very bad dependence on d k and p right so so k is this and d is the degree and p is the field size but the nice thing is it

is an independent of n right but the dependence is ackerman so so even logarithmically growing field sizes are not enough it is going to break down it is going to make it look trivial right because trivially F is a function of n linear right it is an N variate function so C has to be much much less than n to make any non-trivial contribution but since the ackerman on P rack and the dependence on p in ackerman so it is like really weak so you want something more efficient and this kind of a theorem is very very important in higher order for analysis okay so so next we are trying to we are trying to make it more efficient in P and so surprisingly we are able to remove any dependence on p and so this is the main theorem of our work and i would like you to compare this to the k equals half setting and C equals one so so recall that when K was half it was the one over square root P barrier and then we saw that f of X was exactly a function of one low degree polynomial so here it is saying that ok I am going to go so if K is larger then this is what you have like no dependence on field size no dependence on n it has to depend on D and K but but this constant is not that great that is why I had to hide it I had to write C of something it’s Ackerman yeah okay so proof outline I’m going to show how you can almost get to a decomposition but not quite and so this part is very very straightforward so you have to basically play with the derivative structure so so if any part is not here i’m going to use support ok so you have this you start with a low degree polynomial that is biased like 1 by P to the K all right so you define the derivative in Direction Y so it is f of X plus y minus f of X okay so so for fixed X i am going to look at the expected value of this random derivative in Direction y all right so yeah so I just expanded out dy of FX as f of X plus y minus f of X right now if you see X is fixed here so I can pull it out of the expectation and what I am left with is just the expected value of F right because X is fixed and why is random if it’s a visible by x1 minus 1 then all righty it will be 0 with probability 1 over P just because of x1 yes yeah so then then it is a it is a yes but it is a function of few it is a function of just too just less than D yeah so then this would be a function of X minus 1 X minus 2 and this other thing so three so it is very loaded ok so for fixed X we have this thing is equal to something fixed times the bias of the function let us call it mu so we have this is equal to mu times e to the minus FX right where mu is the bias of the function and we know that mu is large just to keep it in mind so if I just rearrange stuff I get e to the minus FX equals this so it is kind of a recipe of computing f of X you using lower degree polynomials so we are not quite there yet but it gives you an idea like this is how we are going to cook up f of X is value by looking at these lower degree polynomials but again this is too much they are like too many derivatives right so first step is to approximate this and you will just do some kind of chebyshev inequality so we are going to approximate this by capital n random derivatives and just taking the average right so so my new recipe of ya and mu is large so we can allow some kind of larger error in our estimate like inverse pauline p and also there is

resolution in between like two consecutive a of I be of any FB so so finally we have f of X is this 10 it means that to a of so II of A&E of BR like at least one over PA part oh so so you’re asking like yeah like two of these complex numbers are at least one over PA part so so you need some kind of resolution right to figure out what I’m closest to because the way I am going to guess f of X is it is the largest it is the a that minimizes this value right I’m going to compute this expression and I’m going to see well which a of my closest to and that is going to be my f of X right so this is giving you a way of computing f of X for a fixed X using capital and many lower degree polynomials but there are problems one is that capital n is Polly in p to make the chebyshev argument work but which is too large you need something independent of p so to fix it we are going to choose a random fixed dimension subspace and choose all the wires from that subspace okay so if you’re if the number of II’s you need is like let us say p to the s so now i’m going to pick a random s dimension subspace and basically take everything in a exactly right so then you then what did we gain we are still taking poli p points right but we gained just in the structure so we are going to use that later so he’s right so you’re he’s saying that well even if you take everything in H still p to the s right but now those wires are more structured and the way helps us is so you can show that only constantly many dy is determine the rest of the dy is so so technically you are taking all these but you can show that there is a special interpolating set which is constant in size such that a if I know the value of F for all Y in s everything else gets fixed so there is a lot of redundant foremost yes yes yeah so that’s another problem right so but even with all this what we have achieved is for a fixed X this statement holds with high probability over the Y is right and therefore for some setting of Y is we have this probability over X right so we have almost solved the decomposition but only like like high probability over X we still don’t have exact computation right so this is the first step of the proof and so the next step is to basically get this to exactly equal to one and so I’m not going to present the proof here but it requires some higher order for analysis which are introduced later but for some other purpose but it follows the proof structure of green tell the from here getting it down to equal to one and basically you are going to ultimately have f of X equals this for all X right but these are the starting polynomials you work with this derivative polynomials you are going to make more refinements as you go on and make it this near-miss result into an always correct result okay what is capital n you mean it’s going to be Ackerman in d and k k is the

bias like 1 by P to the K well the tower bound is are like very weak lower bound so it’s much much worse than a tower bound so even if d is like three it becomes like W exponential now for d3 is exponential d for it so i think when you hit d equals 5 you get a tower in k a tower of length K yeah and it’s already very bad yeah right right yeah yeah you’re right for lower d we are still good but yeah we are in that range okay so this is going to be the central theorem and now we are going to look at we can look at some applications in algebraic geometry and coding theory and so I’m going to keep the central theorem here and then I will move to the applications so if if this is if it is biased by more than 1 by P to the K then f is a function of a constantly many low degree polynomial where C is dependent on D and K okay all right so let us look at an oyster answer so the Hilbert not sure sure so so you have these k polynomials of degree D and then you have another polynomial H of X and H of X is given to be the promise is HOH vanishes on the common zeros of F is then you know there exists integer are so that we exist integer R and D capital D such that you have these multiply polynomials g1 through G K such that this holds write summation f IG i equals H to the are ok so the usual yeah so like knock a point on the in the usual setting you want a stronger assumption you want that H of X vanishes on the common 0fi X in the closure of FB ok that is actual but the so we would work without that and we will see in the next page what the rules are so the idea is to get bounced on our and capital d ok well as I say tell you about the result i will say which ones required the stronger hypothesis of closure 0 and which one is required just the finite field analog so I’m going to assume the number of polymers is fixed okay so the first result is by Herman and she proved like capital d is w exponentially in n and r is some constant depending on d and there you really want your working in the closure and so then brown oval and color in a breakthrough world were able to get it down to single exponential and they proved that capital d is just e to the K and r is some function of D again in the closure world so green inter worked with a finite field analog saying we do not need it to vanish on the closure as long as H vanishes only on the common zeros of F is in the in the field itself then you can actually get something very strange you can get R equals 1 but you lose here you get d to be something which is equipment and D&P but you get r equals 1 so the moment you get R equals one immediately get an ideal membership algorithm like like given F even a fun through FK tell me if H is an ideal of their face so you can get at algorithm

that runs in time and to the this right because all these these two would give you radical membership algorithms but sometimes it’s just well ok so the counter example that you are trying to say is something like well what if I say that y this is X square and my H is X ok so then so that the promise is that whenever this vanishes this manager that is true but can you write this as can you find multipliers GUI such that H of X is equal to f1 g1 so so the the way to get around this is they have P here so they are going to use the fact that x12 the P is x1 so I’m going to choose my multiplier to be X to the P minus 2 okay what you mean what this function C is so these are like a very efficient these are like D to the K or K is fixed so these are like pauly d but this this is like like in the previous result it’s it’s worse than a tower of length D and K so so you can have 2 to the 2 teaser and this would have maybe so even this is a lower bound so it’s worse than this so it’s it’s more like a it’s an asymptotic result in the true essence like it’s and here p also enters the picture so this also helps p the main point is that they are able to get r equals 1 which immediately solves the ideal membership problem and right and so we are able to basically get the pee out in a linear way and this is tight because of the example you have to get p but this is the shape you expect and you have p times c of d and you still have R equals one so you can still solve the radical the ideal membership in time n to the capital d it says functions on FB yeah right as evaluation so mod mod R X I to the P minus x i’s for ya point so and there are like other applications like this in like counting points in rational varieties and holes in the number of points in varieties and so on but I’m not going to go over them right now so I’m going to jump to another application so coding theory ok so just introductory slide on codes so codes you have a what is the code you have an ambient space you take a subset in it that is a code but and the way it’s different from any other subsidies you have two parameters that you care about so the rate and minimum distance so rate tells you how many of these code words you have so what is the size of your subset and minimum distance tells you that well how far apart are each one of them you want you want them to be as far as possible from each other and at the same day you want lot of them so kind of like contradicting ok and what is lista code ability well it asks for the number of code words in in a ball of radius R and you want to show that it is bounded like what is the maximum radius you can get to and still ensure that the number of these black dots is bounded right that’s the list decoding problem so getting in to more specifics so the raid molar code alright so here you the space is the space of all n variate functions over F P to the N the from FB dozen to FP and so your code words are basically lower degree polynomial so you can think of each point as a evaluation

of the function so you can think of it as a vector of length p to the n and the distance between two functions is defined as the normalized Hamming distance between them so so distance between these two is simply probability that p 1 of X naught equals P 2 of X right and you can show by Schwartz Whipple lemma that that the minimum distance is 1 minus D over p so I am assuming d is less than P now and just for the proof outline and presentation so the so any two polynomials are at least 1 minus D over P apart and this is type so this number is going to be important the minimum distance so we will see that later okay now that we saw what reed-muller code is now what is lista coding or admire code so there is something called a lista coding radius and what it means is it is the largest r 0 such that if i look at any ball of slightly smaller radius then the number of code words is independent of n so so what is the maximum r 0 you can have such that if I shrink the ball a little bit the number of code words loses any dependence on n so let us see what the list according radius would be so let’s look at a ball of radius 1 minus D over P and see how many code words we have inside that I mean less than equal to 1 minus d / p so here you will have exponentially many code words and it is very easy to see what the polynomials look like so take any linear function of your choice and you look at LX minus 1 dotted or LX minus d right and what is the distance of this polynomial from the 0 function it’s it is 1 minus t / p right and there are P to the N many choices of the linear form so there are P to the N many code words that are sitting on the edge but that doesn’t rule out the fact that the list decoding radius can be this because recall that the list according radius is the largest are 0 such that if I shrink it then the number of code words becomes independent of n so so what if I ask the number of code words at radius 1 minus D over p minus epsilon can you show that it’s independent of n right so in fact people have shown that for a large number of settings of d NP so they have shown that which means that list decoding radius equals the minimum distance so they’re show that at the edge you have exponential in n code words but the moment you come down little bit it’s independent of n so we have listed when radius is the minimum distance for for the linear case this was proved by go Drake Levin and go to Groban fill sudan and for the binary setting gopalan sliven Zuckerman proved it in 2008 and later gopalan extended to the quadratic case for all fields so this paper is heavily dependent on the field bing binary like the techniques but gopalan used some fourier analysis and he was able to prove it for the quadratic setting for all field and in an earlier work with low and we were able to resolve this for all fixed dnp so far as long as these are fixed you have lista coding radius equals the minimum distance and over large fields there are a lot of results but they all seem to so they all seem to point to the conclusion that list decoding radius is at least this number right here 1 minus square root d over P so this is like called the Johnson bound and all these results say that well if you’re if the ball is of radius 1 minus square root d / p then i can output all the code words in it efficiently and so on and people did not know what happens beyond this and we are we know that 1 minus D over P is the maximum you can get to because there are all these code words lying on the edge so that is this gap from 1 minus square root d / p 2 1 minus d / p so so in this result we actually show that we can go all the way to 1 minus d / p again for fixed degrees so we show that even for large fields you can list decode up till 1 minus t / p which is the maximum you can do and it’s algorithmic as well so so I’m going

to give a proof outline for this a shortly okay so we saw what happens at 1 minus D over p or the minimum distance of D comma P but what happens if i increase the size of the ball so so so what if I want to know how many code words are in a larger radius ball like so fix some a less than D and you look at a ball of radius 1 minus e / p minus epsilon right then how many code words do you have so you can actually show that you will have at least these many code words sitting in a ball of this radius and again a counter again a proof for this would be to look at polynomials that look like this so so take your first variable x1 you construct this form x 1 minus 1 dot x 1 minus E and then keep another variable spare and then you construct any you set any degree D minus e polynomials in the remaining variables and if you stare at it enough you will see that like the distance of this polynomial from the 0 function is slightly less than 1 minus a over B so you have all these polynomials sitting in this radius and how many of them other well how many degree D minus e polynomials do you have you have these many so this is the lower bound you have you want to prove something like this as an upper bound so so in fact an upper one of this shape was known for the binary case in a work by Kaufman low weight and farhat and in the fixed field general fixed field case in an earlier work of hours and in this result we are able to extend this to able to extend this to general fields right and so in this work in the earlier work we actually had two to the Ackerman in P comedy comma s so in this work we are able to pull down the p2 it’s right shape so now it’s P to the whatever remains and as we saw the shape of n is the right shape and shape of peas right so an open problem would be to fix the shape of s and D over f2 yeah but but over f2 these this work already gets like an exponential indiebound and Amir spilka at all their result makes it exponentially in e always because e is less than D so and they really wanted that for their Brazil they wanted something that only depends on e and not on D because what if I am interested on in furry at equals one or two so I do not want any D dependent but all that is like they are all extremely good bounce compared to what we have right now here at least for the general field case so for f to all the results are like the bounds are very good like poly and exponential things I mean you see all the time but in the general p even for the fixed we have this problem of bad constants okay and just as an aside as direct corollary is that we now have a better idea of the weight distribution of reed-muller codes basically the number of code words at wait 1 minus a over p minus epsilon is exactly this so you see kind of nice jumps in the number of polynomial so so you start with e equals 0 so that’s like allowing everything everything so then you have D minus 0 so you have all the polynomials and as you keep increasing e the number of farmers keeps dropping until you lose dependence on n and that is when you reach 1 minus D over be so any substitute equals D you get like you don’t get any more in so it tells you where the number of all of them is keep jumping so we look at a proof outline for this okay and we are going to set D less than P for now just for the outline so this is the goal you want to show that the number of code words in a ball of radius

1 minus a or p minus epsilon is this number p to the n to the d minus e so the proof at the high level the two-step proof so given a center g now construct a ball of 1 minus a over p radius so the first step is a week regularity lemma so so you basically replace the center g by a low-complexity center g prime which is more structured so so you get a set of low complexity proxies g prime 4g and low complexity means it is made of few low degree polynomials and essentially it looks like this it is a composition of constantly many low degree polynomials so instead of working with the center g you work with the center g prime that looks like this structure thing and and the second step is to say that i’m going to go over these steps again in more detail but just high level and the second step is to say that nef any code word that is close to g will be close to g prime as well because G prime acts like a proxy for G and anything that is close to G prime is much more easier to analyze and you can show that any such f is really structured so there cannot be too many such f’s that are close to g in the first place know that you cannot ensure just by a counting argument or way too many you so g prime is not an approximation to g g prime just looks like g to the class of low degree polynomial okay let’s see if the next slice make it clear otherwise i’ll use the board okay so step one expanding step one so you have these code words which are lower degree polynomials and you have a center G which is an invariant function and the proxy is defined as follows so so there exists DC sea of these code words which will act as a proxy for G and what that means is so whenever a polynomial P is close to G close meaning this whatever ready is very interested in then that polynomial is also close to a G prime which looks like this so but note that this is a bit misleading g and g prime need not be close to each other all this is saying is whenever a p is close to g there will be a G prime where P is close to G Prime and the advantage is that this p1 through pc are universal they do not change with they don’t change with a capital P the only thing that changes with capital P is this composition function but this is fine for us because it is a see variate function so we can we are not unhappy about that okay so that’s the first week regularity lemma so it basically reduces the list decoding problem around a general Center to a lista coding problem around a more structured Center and so I think I’ll take this down and the motivation to reducing it to structured centers is as follows so so what if the center was zero function then you know that nef so let us say equals D so we are looking at you are looking at any polynomials which is close to greater than D over P so let us say we are trying to solve at radius 1 minus D over P which means that how many polynomial f do we have which are more than d / p fraction close to g if g is the fixed if g is the zero polynomial then f of x is the 0 function just by short simple right so it means that F does not depend on x1 through xn now if I if I change this to if I change this to G of X 1 through X C which is just a sieve ariad function then if I have this hypothesis then you can show that F does not depend on X c plus 1 to xn again by

simple short simple kind of argument you can say that F is actually independent of anything outside G which means that the number of F which are close to G is small right it’s just no no that is the that is a that is why it’s powerful I mean if G is low degree then then you have something stronger right then f is the constant function because F minus G is also low degree I am saying gee is an arbitrary function but G is only see variate the only reason this can ever overshoot the legal limit is if F does not have any dependence on the remaining variables F is also a see variate function which automatically puts the number of such f @ e to the d I mean p to the c plus D choose d right the number of C vareity greedy polynomials is this is one way of bounding the list according sighs when the center is structured now now we we almost have that we we have that it’s we are counting the number of code words around number of these polynomials around this structured center but we do not have x1 half right it it is a number of compositions on c plus k variables that is a lot p to the p to the k plus C right and the way you get it on that is you somehow do an argument saying that these are all they behave like individual variables so so if the left hand side is a degree D polynomial you cannot have an arbitrary degree decomposition you can also you will prove that even the composition itself is a degree D polynomial so you do not have so many of them you have the right number you have you have P to the and this is like very very small compared to this because you have n in the left one you can show that even T has to be like a low degree composition so that is how you get away from the double exponential bound so how much time do I have do i summarize then I won’t go through the so I’m going to tell you the proof outline one more time and i’ll skip the higher order for analysis okay so then let me tell you about two problems with this approach so the first problem is that we we can no longer work with degree D polynomials we to get this kind of an this kind of a conclusion you have to get to a sub code of red molar codes and the sub code is actually we are going to only pick so we will change our definition of code we’d only keep those degree D polynomials which are also of low rank which means that keep only those degree D polynomials that look like for some see so we are going to work with that sub code and and the second change is that we we can no longer get one proxy for every G there will be a bunch of proxies like g 1 prime G 2 prime G K Prime and all you can say is P is close to one of them and then basically you bound the list sizes around around each of the green once and add it up so these are two main points of departure to make it more precise going to keep a lot of slides ok okay so complete proof outline for that is as follows so first you reduce list decoding problem for the general reed-muller code to a special kind of code of reed-muller code namely only the low rank degree so we only keep those degree D polynomial which have this representation so where is fixed we’ll fix the universal c and then say any low degree polynomial that can be written like this for a constant C we’d only keep those and that is a new code C

Prime and so we showed we also show that this does not this does not mess up our analysis because we show that most of the bad code words lie in this c prime so the fact that we threw away a lot of these code words does not affect us because there are any there will be many fear there won’t be too many of them around the ball so we can work with this structured code which is actually responsible for all the code words if you see all the counter examples were very very structured so like x1 minus 1 x 1 minus 2 and we are going to keep those things here and we will say that the others do not matter and now given any function g and n variate function so there is a list of these structured proxies g1 through GC so that whenever f is any f in c prime is close to g it is also close to one of the GIS and finally we show that list size around the structured GIS is easy to bound by generalizing this short simple kind of argument and then you combine everything combine everything together and that’s how you have there so yeah that’s an outline for the proof okay so take home message would be like like the notions of structure and Shiro randomness have a lot of applications and just to recap it says that whenever a function of n variables is biased it implies that it is not really an N variate function but it is a it is almost a see variate function for a constant C but I’m lying a bit I mean it is not see variables but see lower degree polynomials so you can do this kind of dimension reduction as long as you are happy to work with lower degree polynomial instead of linear like Lanier’s would be too good to be true but if you relax this in the dimension reduction then you get from n to constant and and this kind of dichotomy theorem I mean they have been used a lot in this work which we saw how to apply them in algebraic geometry in coding theory and there are many other areas where they have already been applied and so open problems the first one is basically improved the bounds on d because right now there ackerman and something polynomials are even exponential would be great not in this algebraic setting I mean there are in the graph theoretic like triangle and I mean there are people already shown the tower bounds but here we do not yet have one but this regularization technique you have to avoid that I mean otherwise you will keep incurring an accra mean loss right and the next so computer science open problem would be to extend this result to Reed Solomon code reads Solomon codes are essentially one variable soda greedy but over one variable instead of n variables and can you are can you decode up till that one minus D over P radius right now we know how to decode up to Johnson radius from guru Swami sudan’s work but can you beat that can you go all the way to 1 minus d / p so right now we we showed this only 48 Mulder codes and that would be a very nice open problem so yeah that’s it any questions or any