Proximity Prize (workshop) (Day 1)

Transcript

price session. I think this is one of the most interesting ones to me personally. I mean uh we are putting out a million dollars. So uh we should be careful about what we uh what we give out that money for. So uh the goal of this session would be that we sort of discuss and maybe reach agreement or at least some sort of pre-agreement on what the the rules should be for this proximity price. And uh sort of as the as a an inspiration I I put some questions here.

There are for sure more questions that we need to answer but these are at least questions that came to my mind and that we should try to answer. So first question is what is awarded? So uh you all know about these conjectures and I think Jako will give more uh introduction to the conjectures uh soon but like uh there could of course be a proof for the conjecture there could also be a counter example for the conjecture. Do we award both positive and negative ones or for example for the negative ones do we only award those that have a direct impact to the proof systems that we care about? What are the conjectures exactly? That's why Jakamo is writing this this document with with Dan. And uh then it turns out that some

of these conjectures have constants baked into them. And the question is what kind of constants do we care about? So uh I think in practice people just set these constants to one and now the question is what if someone proves that the conjecture holds but with some larger constants. Uh all of these kinds of of questions. Do we give small small bounties for special cases? Uh or do we try to reserve this 1 million just to give it uh to the big results? Um are all contributions awarded with the same amount? Probably not. So uh if not, how do we decide how much to give to which contribution? Do we for example give

more to positive results than to negative results and so on. uh and then once we have figured that out question is how do we evaluate if something is really a contribution and if it's correct and so you could of course require that the result first needs to be in a peer-reviewed conference but I think many of us don't really believe that this is a that this means that it's correct but uh what you could for example ask is what role plays formal verification here do we only pay out the bounty if uh if there's a formally verified proof or do we split the money between people who do pen and paper proof and then someone formalizes it again at which ratio do we

split it and uh yeah then how do we present this and what is really the target audience is it mathematicians coding theorists that have not looked at these things before or is it the people that have already looked at it I think our goal should be to at least reach some people who have never looked into uh into proofs but they are maybe excellent coding theorists and uh yeah so I guess what we should also understand is why we are making all of these decisions how does this really impact the security of the systems that we care about because that's ultimately our interest and uh for example the concrete sound and uh if you have any questions that we

should add here then let me know and Um probably I cannot see if it's here but uh I think one important things to be specified if it's not in the list is really the use of AI or machine learning things or I don't know in that list because my opinion is going to be a bit controversial somehow we've seen some recent case and you know it's like some doing things with producing anything with machine learning nowadays like super fast but trying to assess the is correct or incorrect can take an order of magnitude more time than producing it. So you just listen >> but you can discourage them. You can say

like if the papers are generated we might take longer to review it or say something like we will do a different thing which are >> but if someone want to say it was trash the same thing as >> true for a technologically advanced uh community as we claim to be rejecting something like technology like this sounds lame I would say standard is really the same regardless if it's AI or humans will reject human trash and AI trash and like what we care about is quality so yeah I don't know that we need to explicitly state >> no AI we just should state the quality >> and you could probably add a simple

thing that says like you could submit at most one attempted proof a year or some sort. So like someone can't send like a million AI papers at us. So get the said one and then come up with the new identity and maybe we can come like with a similar things that the Euro this year I mean I don't know if you have seen the Euro uh submission rule this year there were at least like there were session that you state >> how you I mean >> you self assess how use AI >> adopt the same policy as the >> exact reasonable they operate in different environments so in they want to select some number of of good papers and they are key of rejecting good papers because kind of these papers can

be resubmitted at the later confidence. We are at a little little different situation. We want to accept everything that has a chance to be right and we potentially have long enough time to to look at this. I'm not time constrained as >> but self self assess self assess how much you say I don't see is a big limitation I use AI only for editing or use AI to I mean you can you can cheat you can say the things is not true but at least like putting a self assessment or how much use AI I would put it >> you would never choose what to review and not to review based on that self assessment >> no no no but at least like being written explicit where you use AI for like only for for editing only for the table.

>> Maybe we're trying to solve a problem that hasn't appeared yet. >> Well, technically appeared already. >> Yeah, but is there a problem? >> Well, it took me like two days to figure it out, but no, but I spent some time. >> So, I think the the thing that we want to get rid of is like these these spam submissions. Limiting the amount is a good idea. I think in the end, we don't really care whether the result used AI like if it's correct we we are happy right so >> maybe one question about this would be like for example are we allowing anonymous submissions but as a community I think we like that but if we want to

do like some spam limiting then this ends up giving problems so there's a >> you can do anonymous submissions as long as they're tied to a pseudonym that was previously active like if someone has a GitHub repository where if they've been doing stuff for the past few years then pseudonym is fine >> yeah so like you saying I not create a fresh git that will not exist. >> I think like anonymous admission I'm all for it but I think they will fail. I don't know if this is the case that Ethereum K will require KYC. >> Yeah. So they will fail it >> above 10K.

>> Yeah. I don't really expect another submission which satisfy >> I mean the I mean the last guy I mean it's kind of I mean who is this? this like she wakes up. >> Well, since this is a a cryptocurrency, can't we have a prediction market? It needs to hit hit some threshold. >> I mean, it's it's not here. >> Yeah, but we saw this with the was it the super conductors or something markets were going all over the place. >> It's it's a spam prevention mechanism. >> Oh, you mean like you only consider submissions like above 50% on?

>> Yeah, for sure. Yeah, I mean it's a good test of prediction markets about resilience. How much >> seems quite imperfect information like I assume like most of the people in the prediction market won't really understand >> well how how much would it cost to get your submission >> because it might not be that expensive. >> I have a good question. Um is there any work on potentially easier problems like proving a reduction to a known problem or I think it was mentioned earlier today that there were cert that were particularly interesting. The reason I'm asking is because usually I think with these kinds of prizes maybe the the problem is really hard and u

even if there's just like a certain implementation specific or very narrow scope from a theoretical perspective that wouldn't interest theorists might be a gamecher for us. So maybe it might be productive to just have like here's like three or four tiers of what we think are relevant and if you can show these two or three special cases we're going to give you some money. >> Yeah, this is possible like this theorem from my understanding like they don't really reduce much they're kind of like standalone like the problem in coding theory like I don't know for example of like equivalent formulation of this decoding for Solomon codes which implies what we care about >> there could be a show

>> yeah yeah there could be like we have a lot of options for these kind of things like Uh there's also like you know classes of attacks. In fact later when we talk about the problems there are like some toy version of attacks of the problem that one can try to analyze synchroniz techniques and then you can start getting limitations. There's like a lot of like thing that one can do in there >> just to put on the agenda. I I saw that there was talk about disqualifying certain characteristics or something like that. Um I I don't I don't support this but maybe add this to the list of topics that

>> I don't know if this counts as parameters or >> can you repeat whether >> I think thought that flag that maybe in characteristic two it would be easier to disprove We have so we have some limitations in that like in characteristic two we actually know the sum of the for think in list size yeah in list size you get like some uh uh you cannot you must get like a factor of n in the numerator of the error while in the rank field case you don't get this this thing so the large characteristic and the small characteristic case have some different

things but I think this is mostly like maybe we should like divide. So there's the part which are about bike shedding. So this is like a rule of the price or kind of like agnostic of what the problem is really and then the thing which are like about the price which is kind of like the scope of what we want to audit. So this is like parameters the field characteristic understanding the count for example exist in the literature the numerical parts. So I think it's like two two distinct things. So one part to solve first is just the bike shedding like when are we going to give the money if we have to and the other one is like parameters and figuring it out. Yeah. So there is some difference in the small field case and the large field case that we need to account for

a little step aside uh when a couple of well a year ago or a couple of years ago we're trying to organize something for for Poseidon probably not that big but for example I approached many prominent symmetric photographers and asked well why are you man with so big like number of sitations why I'm not trying to go to a workshop and try to break aside and try to write a paper to motivate a student or something. Many of them explicitly told me that uh there are like two big reasons they are not participating. First reason is that like this thing is too short so that they cannot for example hire PhD student to work on this because it will end before they even hire it. The second thing is

that this uh kind of this uh idea this initiative may be known in one particular area but not very well known in general community scientific community so that it's difficult to for example ask for a grant or mention it in a grant that doesn't give you immediate benefit and so on so what I'm hinting at is that uh first of all did we consider already like pre-approaching different people and ask them what would motivate them uh to work in this area because in many times it's not only the money and maybe they already have the money or maybe they cannot use the money but they maybe make can use of something else. I

don't know we can help them hiring the student write a grant I don't know whatever I'm not very close to academia right now and I don't know what exactly they need right now but maybe we can try to think a bit outside the box and maybe suggest something else uh aside from the money to like prominent people who can take part of this. >> Yeah, this is something that in part we want to do. So one of the reason the formulation I was thinking of was to make it very mathematical because at the end this is like a very natural polomials and something that should appeal to the wider mathematical community. We've independently been like already talking with some of like calling theories people like for example Mary Ward of Stanford we talked with we talked with a few people which have

experience in the field. So the conjecture so there are two problems that we are kind of interested on on one is this list coding and one is the proximity gaps and list coding in particular is a very well known and wide coding theory interesting like uh conjecture. So we think that by making it like both the problem very accessible sharing it widely for example uh we one of the plan plan was to uh advertise it in the journal of the ACM to like the American mathematic IMS that's the one ACM is the other one we we want to try to get like a wider community plus the prize usually gets some good

attention but we'll also try to like talk with more people outside of the usual uh Uh like maybe something that we could organize is like a press tour like going to different university trying to like go to different like mathematics department to try to like actually advertise the problem more widely. So this is something that could be interesting to do. >> This is not really a great cryptography problem in this like I feel that it's like more different community than the people. >> Absolutely. This is a problem about polomial. There's no cryptography.

There's no security parameters you know >> can this I mean why why do we even allow sudonmous or anonymous functions? You know it's not like Bitcoin which solves a societal problem societal problem I would say even say here nonimmas is fine that's my person >> yeah so who who suggested anonymous can whoever did that can you repeat what the motivation for that would be >> I mentioned it just because I think like you know this first AI submission with an anonymous one and in the community

you know there's some I don't even see the word prominent let's say and I I would really forbid this because like whenever you it's not like one uh round uh protocol right to get the price you have to interact with the person like back and forth you have to present this results around some people may not be even comfortable to >> I mean maybe reviewers should should should not see the name right we should like if I don't know if if someone submits something in Jak says okay I I will review this but I will also give it as a sort of external review to I don't know really right and then maybe

really should not see the name >> maybe it's okay to see the name as long as there are like really many people working on on each submission and uh you have like a diverse view just redundancy you ensure that there's no censorship like we do this in signature. >> So I think I I prefer I I wouldn't say allowing anonymous but not forbidding anonymous um basically because um I think we should give all submissions equal chance. Now that's not to say that we're obligated to read any submission even if it's not anonymous. So if some public person submits us something bad,

I don't think there should be an obligation to read that either. But if we start forbidding anonymous, then it makes it feel like we we're promising to re to give you time if you aren't anonymous, which um I I don't think we really want to do that either. So I don't see why we should um even distinguish between these two cases. Uh I don't think the clay uh prize has any stipulation uh one way or the other. Um and by the way, I mean for the Millennium Prize, I don't think there's any committee who's promised to

carry out the review, right? How does it work for them? Isn't it just that the community has to accept it? In other words, Clay is not undertaking the review process themselves. They're kind of letting the community do it. Maybe we should try to do something like that. >> Then their case is probably much takes much more time if you don't if you don't care. >> Why can't we also take that much time? >> Well, because we did it kind of yesterday. I said, well, not yesterday, tomorrow really. So, we need we need this for to make sure that our the KVM things run securely and this definitely not

>> but I think there's a sense of like okay we have a submission that's really good and we feel confident about it and so we're happy with it with our CKBMS but we're also happy to wait an extra amount of time to see if anything comes up before we actually pay out a million dollars like paying out a million dollars to something that ends up having seems much worse than paying out a million dollars later how's with with the new VM uh because I know just from the big project it's not a show stop but to move from conjecture parameter settings to pro r provable ones so it's doubles the proof size essentially uh so what's your thoughts in regards of

the time the the quite strict time frame you have given from a slot >> for I guess the proof is easier and because you have if you have more challenges you have to comput would be slower and be easier but might be worth to think about because then you always fall back solution you know just considering it's going to be disproved not saying it's >> yeah but you I don't think you want to think like oh we want this to be true within the next year or so we kind feel incentivized to give out the price

sooner rather than later that seems like a bad idea. >> Something that I I noticed I think um for other big open problems that they do for example I think the P versus MP problem is that they have certain subasses of proofs that are known to be broken from the very beginning. I know that they're doing a lot with SAT solvers or something that there if it you know might be productive and I think this goes back to the conversation around spam submissions uh but not so much malicious but rather some people are all going to stumble onto the same thing and they're all going to submit that kind of thing. So it might be worthwhile having some kind of technical document where we say we know for a fact

that A B C and D as potential avenues are going to fail and here's a proof or this is what we think and please don't submit those because it will be an automatic rejection. >> Absolutely. It is something that we can do the kind of one of the issues that we you know for the P versus MP there's like amount of people that tried to do it. They also have a bunch of like very rigorous complexity right >> there is they have a precise sense that the proof cannot be simple >> yeah like advisation all these like techniques in our case uh like I don't think that I know many strategy which I can tell you like oh this will

definitely not work because this breaks some other barriers that we have like we we don't have this sense of barriers in the composite sense that we can like you know not that we have reduction. You know, it would be worthwhile for somebody to like think about and which exactly which strategy can work. You know, >> I mean, we could publicize submissions and then >> maybe negative results can be incentivized as well. >> Yeah. >> in like different. >> Yeah. We have found results. We can publicize submissions and like some kind of review of the submission that says this tried this technique and it didn't work.

>> Yeah. Do we want to put some upper bound on the complexity of such such a proof >> like kind of we require that a proof can be read and understood by a single human being within well >> are you trying to avoid the ABC case or >> oh yeah >> I mean they could just give a snark that the proof is correct >> provid something avoid some proof that it's supposed to be like Russian checkable or something like you know like if you go over all these 20,000 sub cases then >> but I think this is implicit in the fact

that like if you say you know we obviously won't pay out for proof that we're not confident in then clearly if anyone can understand the proof it gets disqualified that way and that's also one of the motivations for having a formally verified proof as the ultimate maybe just giving part of the money into a hand. >> I don't know if we really want to force people to formally verify the I mean it could be someone else, right? >> Yeah. But but I mean like I feel like the proof could be arbitrarily complex provided the community understands it. I don't necessarily see the issue not fully verified, >> right? you would still I mean at least that's how I would you would still get

get money >> but you would maybe would reserve some amount of money for the for someone that takes this proof and then for >> and like the process of making it amenable to for application would improve the readability proof by quite a lot. >> Yeah. If we're in a good where we get like actually a proof we can also make the choice of like we look at the proof and we say the building blocks are already in our clip for example then we just prove it directly the We did like campaign then we can maybe put a bounty out of it for like the full verification at this point we can make the choice that we want like I guess what I said is that if we have a proof that the community is accepted I think they should get the full bounty and then if

we decide as a community that we also want to formally verify that might be something we do in in addition to this but like like sort of the the millennium prize problems you get the $4 million like I don't think any of those have been formally verified the >> requirement is coming >> it hasn't been proved yet they're working on it. >> Yeah. But like yeah, definitely for not be a requirement for like winning the prize. I do believe that if somebody wins the prize, then we should follow it very hard. But uh yeah, it's a separate thing.

>> Yeah. Yeah. That's what I mean. I think that that should be like something we do after we've awarded the prize. Once someone has the thing and we've given them money, then we go, okay, you know, let's put some money aside and see if we can hire someone to go and formally verify this >> on every on every price we impose a VAT mean verification 20%. >> Yeah. A question that one can make, you know, if somebody sends us a lean verified proof but no pen and paper proof, do we accept that? >> Oh yeah. Yeah. Which would be amazing like >> I mean it's easy to check. Yeah, >> just for a comparison, have the current results on correlated agreement been proven formally yet? And how much work?

>> Uh, they've been stated, not proven yet. >> Okay, um, how much work did they represent stating it? And then >> so stating them took a bit of work because a lot of coding theory was missing from massive, but now that's been done. So Katie here did a lot of that. Um so now we're able to state them and then for proving them it's probably like a matter of weeks or months. It's not so insane effort. Okay. It's definitely doable. >> I guess like you know the delta over three lema for example should not be too hard while you end up going with the crazy one then there might be more challenges.

Yeah, that's kind of the question people getting into. >> Yeah. So jumps and bound for example is right that wasn't some crazy >> you mean UDR >> not like >> what's the state about the UDR up to radius? I thought I thought that was much easier. >> Yeah, I think they've proven what the Johnson bound is. Do you know that you prove like what about the Johnson B?

Have you proven it? >> So >> yeah, we basically have that uh sol decodable up to the Johnson bone. That's half. >> Sure. Sure. So by decodable you mean the gurus who done decodable. >> So constructively decodable. >> Uh yes >> because this decodability just means that the number of the list >> constructively but like >> definition >> existentially decodable >> like we >> efficiently decodable.

>> No no no not efficiently. It states on it that there exists >> but that's that's just >> like the the you know the the intersection of the ball radish. >> So you verified Johnson's theorem. >> Yes. >> Okay. Is there any >> Thank you. Is there any interest potentially in um actually running like I don't know if you guys do this

>> just uh I was actually going to say like um like workshops at very specific places where you can just I mean hype this up as a real question. you mentioned that it sort of transcends fields in a very big way and sort of cryptography doesn't really seem to be the most relevant one. So potentially to get smart people to look at this it might make sense to have some sort of continual um kind of either budget or workshops to deploy into it because it just feels like then you can only get submissions from people that know about it might solve a lot of these social problems.

>> Absolutely. like uh having like large like trying to like advertise it to like a wider community like it's something that I think is we should do like it don't affect like this problem like to be solved in next year or next two years and so on. So you know if we manage to you know once the problem becomes large enough that people care about it it's nice so we can start like thinking about workshop thinking about budget but yeah I think all of these start with like a very good formulation of the problem very good like submission guideline and very good initial advertising of what we do here and I think uh yeah yeah I think we can do a good job there about this big uh computer science

conference like I know I yes or like ECC this sort of things do they have like ramp sessions or something where just yeah I'm announc like we can uh like you know we can we can advertise it there as much as possible and then we see how things go there. >> So back to formal verification just a quick uh opinion from my side. I I would guess it makes sense even from the practical target to first verify the much much more success proof in the unique

decoding machine. >> Yes, that's what we're doing. >> Sorry, >> we're working on that. >> Ah, okay. You're doing it anyway. >> Yeah, this is all this is we're doing that. >> Okay. Okay, good. We're just waiting to have on instructions and ability to take everything in place. >> It would be interesting as well. >> It would be interesting as well if the process goes for quite some time to run as sort of like C fail uh stuff of like we get these best approaches that were very interesting they didn't achieve but this can inspire >> further ideas or something and this can also be a sort of like promotion.

Yeah. >> Yeah. I think that's something that we should do like I love Cale. It's one of my favorite conferences and sessions and I think something we should do like one thing that we could do you know we could set up like a website where we end like all the submission get sent and time stamp. So we know that when people take priority and then you know we for those who submission which are like uh broken we do a postmortm we write it there and so we have like we have like reflection of method which do not work plus submissions of like phase approaches.

This is like all thing that we should do and I think uh this should will very much benefit the the overall approach. Another part that I wanted to mention which is quite important is that I think this kind of conjecture they need to be like very much verified numerically. So this Antonia started like working on this and this is also something that even the le the people which are a bit less theoretical but we would code which is not me can help out with and like you know these conjectures as far as we know they will hold like for small for very small fields as much for large ones. So h we would like to run a lot of numerical experiments possibly

continuously to try to figure out whether like you know the conjecture that we're making make any sense at all in these small cases and this is something that I think you know Antonio started like I had a parallel CPU implementation we start with I think there's a lot of tricks that one can try to play and this is something that you know if people are interested in this could be a good thing to also jump on during this session I think because it needs like relatively little like background to start with There's a whole journal of experiment. >> I didn't know about that. >> Yeah, we could we could do it. And then >> special edition.

>> Yeah. And submit it. Yeah. >> Yeah. >> It would be cool to, you know, they have these distributed searches of like, you know, large large MEN primes or something. It would be kind of fun to it would be a lot of work, but to set that up to search for um search random app lines and search for close points or something like that, right? >> Absolutely. Absolutely. Like I think this is nice. We like in general like I think we start with the simplest possible experiment and then later on we can like >> so that's one of the things I think we need to know that

>> and the other part like figuring out like the state of the literature for like counter examples that exist for the coding figure out which implications we can impose. So once we have like a kind of like very nice footing on the theical part, I think we can be confident in the problem statements and then from there like you can get everything out like you know >> maybe one question we talk about problem statements that I want to revisit is this range of constants like >> for which range of constants does it make sense for which range of constants do we want to pay out money? My personal opinion and I I think I shared this with

Dan is that >> you know constants get better with time. >> So for a lot of these results like the capacity result in particular the barrier is a lack of techniques. So we really don't have any techniques to go from above Johnson to to capacity in the settings that we care about. So the breakthrough would be like getting from getting the technique and then if the technique give you both end to the eight it is most likely because the technique will end up like because the technique has not been optimized yet and then people will optimize it. So my personal opinion on this is that we should uh try to give like very clean very asytoic style result where we don't care too

much about the constants see what happens and then if we end up like you know If we end up getting at the point where like we find a proof which by the way will be already amazing with bad constants you know this will probably be many years in the future then if we really want to optimize the constant we do another bounty >> and constants >> yeah very dumb question of the constants like when they get very big does the gap still exist or like when the constants get very big there's no gap >> well so for example like you know some of these con like the form evaluation domain side over side of the field Yeah, >> if if this evaluation size to the 100 side of the field >> then you know for most care is like meaningless.

>> Yeah. >> So yeah this concept we're talking about is there mostly >> maybe worth it to show them on screen or show the formulation. >> Yeah >> I can I can >> do you have a link on the hack itself. >> There you go. >> He's trying to Yeah. So this is the kind of like error that you kind of like end up getting. So this is what is known and proven. So we scroll further down.

>> Yeah. And these are like some of the conjectures that that one can think about. >> Yeah. These are some of the example. >> We got a question after this. I I I was just going to suggest that if to to fight spam instead of putting hard requirements maybe we can have things that uh that help us to rank all the submissions and maybe I don't know if you get some review some professor we we consider you we give you a little bit more priority or if you don't don't do it under if you if you put your name we give you a little bit more priority and that way you don't block anybody but uh you if you have too many you have way to know where to

start. >> Maybe that's something that also we could do. >> Yeah. >> Based on >> Yeah. Yeah. Yeah. Like I think what we should do is that submissions >> they should be timestamped anyways. >> Sorry. >> It's like when you review for conference, you look at the paper. >> It's true. I think there should be like some time stamp when people submit the paper just in case there was conf >> not for reviewing. No >> because also some will just take more time.

>> Absolutely. I think in general like a submission should not like commit the reviewer to like any timeline for what they use like we get to >> unless the only way you would do that is if it takes too much time. >> Yeah. I think this question is going to be way more convoluted than we imagine. Even like the only submission I mean it's not submission that the paper j was mentioned before is clearly machine learning generated but I read I read it contains some some deep stuff as well I mean you know it's not really clear what is good what is not some things in that paper actually pretty good I think agree on that you know to me in my be pretty

convoluted to reduce I mean that's what I expect and I will not expect >> yeah I just don't think I think this is just the way it's always been what I think is fundamentally chang >> um so I I guess one question we have to think about is like how tied are we to the specific statements of the conjecture so I know I like for example for these conjectures usually you assume something like so the proximity gaps are saying like you know if if a random fold is close then the the things that were folded are equally close and I know there's also been work recently on stuff like if the random fold is close then there's stuff is not quite equally close but almost like there's probably lots of places you could add deltas and epsilons into these sort of conjectures do we want to be like very willing to hey you

know if you have something which is basically because I think most of these del are good enough for our purposes so like like we could say if you prove a conjecture that like is good enough for our purposes it's fine even if it's like a bit weaker than what this is or we could be quite strict >> yeah so it's a good question like uh the will be like you know there will also be this kind of which are like another part to do there's preservation things so one thing that we could do and I was onto it. Like you can write very simple version of like the protocol that we turn out which you can analyze under different version of the conjecture and it will give you different like bounds and depending on like so this should one tell us exactly these are the conjecture

that we care about and two it also will tell us what um yeah so we can get some we get some so for example one proposal that we could do and I was thinking about is that for counter examples, right? So, we can have for counter examples, we can have that we only award money if the counter example ends up like uh lowering the the conjecture security of some like uh toy protocol that we design. So we do a toy version of war for example say oh under these conjectures this gives you 128 bit of security and then if I give you a counter example which lowers it from 128 to 125 then I

pay out >> but but do you >> some parts maybe not all of it >> so so who is who is convincing the reviewer that it really lowers the samples because if you say that part the people submitting it have to do that then you rule out coding theorists Sure. Like you can like what we can do is like if you give me a a counter example of say you write a paper which gives me some lower bound on the only thing over there the question of the attack. Okay I assume let's assume for now that attack is in the situation that was talking about before. There's a there is information theoretically things work but it's not a

constructive attack. So we don't really know how to how to deal with that. So one thing you could do is then like you know if if as a trivial consequence of the lower bound you get like a like a a lower number of bit security then this is something that the committee can take care of of like you know in some cases I can figure out how it goes down while if instead like is very non-trivial then you know for exceptional price is exceptional contribution you you will like to take care of you We can help with that. But uh yeah, something like that.

>> Do you think that we can uh to make this conjecture a little more specific to make sure that it smoothly continues the upper function? >> Well, the issue that we don't really know is a tight like >> Yes, but we can at least kind of for different constants we can select uh uh like outer constant factors. So that this function would be like a direct continuation of of the upper formula just with different uh how we call it derivative.

>> Yeah. >> Yeah. Well maybe if we kind of we know that like we have already proven it like this and then depending on C1 and C2 uh for the next segment it should go like either this or either though here and what is in this range is a proof and what is like here is a counter example to me like I would like really my opinion that we should not specify the constant at all like you just really make a very statement like there are some constants if there are one billion okay they're same but still a constant and then this constant will get better

because the universe is the right place 1 million is never the We kill here like we can kill this part like we used because we needed at some point but if you look at the the equal >> but I'm not sure if you can really kill L all the time from the case of >> no I mean if you I think if you do like batch five for instance. The question is how do you batch? Do you batch?

>> L is not the list size. >> L is the length of the batch. >> So if you just if you prove it for L equals like one then or two or whatever >> you need two you need two >> but but two does not like so a line do not give you powers. >> You get you get I mean >> there's not a >> I mean what you get is I think you did it in in one of yours work. If you have the linear combination, you can do multilinear combinations in a blackbox manner. >> That should work also up to >> I think it should also work in MDR.

>> But I my feeling is sorry my feeling is with arbitrary powers. >> That's basically what I'm saying just we just care about the case of lines >> I would say. So >> so at least for for things like war for example you only are you are fine with lines because you're doing multiar batching you can prove that is fine like even outside of unit coding there's a paper that's going to come out in hopefully a week or so about this I don't know I've heard about it but basically uh for like multilinear things lines is all you need to prove there is a minimum

if you want to like get arbitrary polial combination of the randomnesses then you also need powers and as far as I know there's no reduction between powers and the lines directly but uh yeah like in general like you don't lose much by doing the mult cleaner folding compared to the power folding you use a bit more randomness but it's logarithmic so who cares and uh it's still usually good enough but yeah so in the actual document I'm at the moment working with the literature. I check I look at the case where we only combining two functions.

>> It makes the things much >> I think the simpler the more attraction. >> Yeah. Yeah. Maybe for the beginning we can have just L equals 2 and then after a couple of years when you have >> no we only pay out if you can also prove. Now we have the guy who proves. >> I wanted to suggest something for the tax. So now just proving also disproving the conjecture. I wanted to attract also like people from the analysis community and not only like mathematician and theoreticians.

>> Yeah. >> So I think you talked about a few practical things right showing the security bits goes from from some toy where example reduces still that seems like how do you convince me? I wanted to propose may be more practical. Okay, let's even think about list coding. Okay, like slightly sler than this if I claim that the list encoding bound is is fix some you know sizes some field everything. Okay, conjecture says that this is the list coding bound. Okay, it should not have more than two to the 40 code words. Yeah, okay. I I claim no I want to disprove it. So now I can give

you a word, right? And then you can kind of hash the the code word. You expect that if you hash with, you know, and you see something that start with more than 40 zeros, then there's not going to be anything in the list that hashes to something that has more than 40 zero. Kind of like versus lower bound. So you can actually just have a code, >> right? Where somebody gives you any word that he wants, okay? And then like this defines the list decoding around. Okay. So he has to give you something that hashes to enough zeros and is close is delta close to the

word that he gave. This is something that you can just have a code that checks if he's correct. >> Right? He doesn't have to give you a formal proof. He might do this using some sats alberg or something. I don't care how he did it. Right? I don't need him to formally prove that what he's doing is correct. Okay. I just need it to work with high probability and this you can efficiently check. Yeah. >> And if he does that, >> he disproved the conjecture and I'm like fine giving him some of the price. >> I mean that's that's great. But >> there could be people disproving the conjecture in different ways, right?

>> You could proic method you find. I'm saying this allows to attract people that don't want to write a former proof that they disprove the conjecture. >> Okay? But they know how to practically disprove it. Okay? So that's like a different avenue of getting you know use AI use that solver. Okay. Find me a code word that you know hatches to enough zeros and is close enough conjecture for this setting. >> Don't do you get wind just by trying a lot of different Yeah. So you're going to like to get the prize you're going to run this experiment many times and see that he kind of succeeds with hyperbility or

something like that. is the goal that it's more easy to check this like send >> they send even the code or something like this >> and yeah that's easier to prove >> the grinding formal proof >> but why don't they just send the whole list in other words now you're relying on the hash function being secured and like other words you could get lucky and a nearby word that hatches many zeros, but that doesn't mean there are two words in the list. It could be smaller.

>> Well, yeah. Yeah. But this is something make sure it happens. So you require zero and you can make but I'm saying like like don't be lucky. send me a code, okay, that gives a a word and then like every time we let's say we sample many hashes, okay, and each time they have to like do this. So we can amplify the sounds of this protocol. >> This is something they can huristically try to solve without trying to write formal proofs. Oh, why is everything >> but they could also Yeah. Okay. I mean a simpler version of this is they just try

to find all the all all the post words and forget about hashing just list all the post >> yeah but 2 40 250 2 the 60 right >> I I thought it's a it's supposed not to be approved so we don't care if the if the candidate even has a full list so just by the grinding principle with high probability the list size can is bounded is that the idea behind your proposal. >> Explain again. I I thought you know so you demand if I got it right you you demand that the candidate just pro gives you a close code word which has hashes uh to a given prefix which is small prefix

and and just by the possibility that he the person manages to solve that problem we can say with high probability list size is bounded either The list size should be bounded and that's why there should not exist any code word that hashes to zeros in that list. Yeah. >> Ah now I get the way of okay okay >> okay >> potentially >> so this is but still it's not approved but it's something >> it's an argument. Yeah >> invalidation. Yeah.

>> Who picks the the challenge point? >> They submit a word. >> They submit a word um and another close word to or or the closed word hashes. >> They need to be nearby. No, I mean the the hash that hashes to zero needs to take as input also some challenge that comes from the very first you could >> otherwise you could just choose a code word and something that is closed and then you take that >> or maybe you hash them both

>> I mean it's just >> it's just an interactive problem right asking for smart proof for this >> how many how many iterations you will need to enough to enough to convince the community. >> You have to make sure that the error is like, you know, very small. So it's not somebody winning money just by some chance. >> Imagine that it's like sort of rare to find points with a larger ball than the bound. But so like if you the judge get to pick

the word but they need to find something close to no word. They pick the word they they pick the other element of the ball that has that hashes to many zeros or maybe you should hash the word and the other word and then both should have >> but isn't I thought your point was now now I get to grind on like both picking the word and so >> think of it as an interactive okay they send a word okay at this point in time they're committed to the list decoding around this okay the contor is true then there's only 100 code words around.

Okay. If there's only 100 and then we say okay bring us now back some code word that hashes to 40 zeros then >> there's not going to be such >> a to hashing both words. So take two words hash them both and get a bunch of zeros out. No, I don't think so because then you can just take a code word and something that is close by and hash it and if it doesn't work take the next code word and something that is close by and hash it right >> so you need to do it in this round way but I I think we are getting sidetracked here write it down but I I agree like I think that >> like you know look if somebody can

that's actually better than a proof code that's actually going to happen right I can like one fry would definitely be the kill. >> I want to say people can come up with whatever tax they want as long as they >> exactly. So say it again what uh does this prove or what what if someone cannot find this what does it >> no no this is like an additional way so there are many ways for the to disprove the conjecture so one way to disprove it so you give like a >> this disproves but if you cannot if if I provide such a code such a code it disproves a conjecture if no one can provide such thing does it say anything >> no just we're not good I mean this is just this is just a succinct succinct

argument of knowledge of a counter example >> is it that >> yeah it's a way of not sending the whole list. >> Yeah. >> But if no one can find it doesn't tell us anything about the list size. >> Yeah because >> well maybe it makes us more more >> positive. The problem the problem is in comp right we we can find we can find a easy weakness of no membership which which is interactive proof while finding you know to show the conjecture I have to show that every word has like a small list while for like the counter example I just need to find one word which has a

large list and this is a easy way to show that this one word has a large list. >> Okay. And we suppose that if if there is a counter example it can be just one particular word not like >> yeah like in general I think that uh if you give me one if you tell me that there exist a word with a large list then I can just as a pro I run my protocol using that word as my like uh my the thing I commit to with the oracle and then I try to play games with it.

There is no way to amplify such a word such a ball like to kind of copy it across >> the conjecture is that all balls are small. So if you can find one that one that has a large intersection then that's already a dis. >> No I think it's saying like supposing I tell you there is one large pole >> then can you leverage that to say there are more than one large pole? >> Yeah because codes are like identical right? You just add on code words. You just add code words and you get the whole thing. >> If you can find one thing with a large ball, then you can find lots of large balls because you just add code words.

>> Yeah. >> Yeah, that's what I actually >> Yeah. Yeah. >> What if random words have small small balls and but there's a specific word that has an article. >> So they can't just be one. Once there's one, there's a lot of them. >> Yeah. But if you pick it randomly. Sure. If you pick the word randomly, >> but the pro the provers picks the word. Like the person who's providing the counter example picks the word. >> But if we are using these results in a broader context like Start. >> Yeah. So it's possible you could come up with a car example but like our stock isn't broken. >> Yeah. Exactly. >> Yeah.

>> I I think this is Yeah. Yeah. >> Very dumb question. What about the list size projector? Right. Also >> mutual correlated agreement. >> Are they both under the mill enterprise or is it just the mutual correlated? >> Yes. So currently the plan so when you're working with like things in list decoding like a worst or or you need some list size bound somewhere so the curly the millennium draft if you can go to the do like what I've been writing down is having both the millennium so both is the two variants of the listing conjectures and then there's the at the bottom of the document there's the

mutual creative agreement conjecture And so the price for both simultaneously or just one of them does it get split? >> No, no. We I think that what we should do is split the price on like this part because as far as we know they are related because they both have our code but we we don't have any formal guarantee that one implies the other. So it I think it makes sense to like uh you know each closing either one of them would be a breakthrough. How do we weigh how much of the price grants to each cone?

>> No, I I think that's a good question to discuss here. I think we should weigh them by importance for our our project, our ecosystem. >> Maybe I thought that was >> Jako. Can you can you like list down the conjectures and we see how many we have and then we can sort of >> Yes. >> see are we want to weigh them or >> like the conjecture? Yes. >> So in reality we only have like in the moment I have three conjectures in this paper which are related. So I don't know if this is what we want to finally go for but basically uh okay let's first go to list coding which is at the top.

So uh for list decoding uh so this is the problem again of like I have a word and I want to figure out how many code words are in a ball at a distance delta from it and there are like two settings that we're kind of interested in. >> There's the one of 3.5 and 3.6 >> what's the difference? Well, uh 3.5 uh is for the large alphabet regime while 3.6 is for the small alphabet. So we know that in the I think there's a there's a counter example in our old paper by Vastig and Elli like from 2005 I think which tell you that like if you're working over

fields where the characteristic is two you're actually able to get like you know that the numerator of like the list side will depend on the code word length in some way. >> So there is this factor of n. >> Can you zoom in please? >> Uh old people. So >> notation list of the code at a distance >> and we know that for the large alphabet for the small alphabet case this is the best that we can hope for which is basically that the list size depends like in some way ste probably imagine it as bigger than

one on the on the evaluation domain size. So evolution domain size for most of the things that we care about is between 220 30. So basically yeah here you have like 30 bits of security that you lose give or take. If you going instead go above. So for some context there's been like a lot of progress recently like list understanding the list decoding size of randomly puncture solomon code. What is this? Well, usually with Solomon code, I have an FFT friendly domain. So I have a root of unity and then I evaluate things over that. You can also think of like there is Solomon code where like I pick

at random like a subset of the code of the of the field and then this is my code. So in that case in this proistic setting we're able to get some to go a little bit up. Yeah, we get this thing here. This is proven. This is proven that for like randomly puncture rich solomon code as long as the field is large enough in this case like linear plus a little bit in the plus a lot it's a result we know that the list size of the code is like uh this conjecture you want to any evaluation doain

>> so I would care about FF friendly evaluation domain So any evaluation >> for all evaluation domains would be enough. >> Yeah, all evolution domain would be enough. But uh if they can like >> no but to prove they >> they prove for all then that implies of course >> no but I'm asking if they prove for one they say here's evolution it's not a randomly pointed one it's a specific one >> and they prove that >> yeah I think like the right word is like structural domain we're interested structural domain like >> so so the random ones are just non constructive they don't even tell you which doains >> yeah so you're saying >> it's not it's constructive random.

>> But then it's easy to do what you said. You just pick one of the ones that come out of >> No, but then it's going to be like for every you have >> I want to show something. >> Yeah, absolutely. Absolutely. This is one of the things we need to figure out like In my opinion, we should like so there there's a few options that we have. Uh so at the moment here I said like the same result holds for like some move evaluation domain where L is a some arbitrary root of unity of like the

field. This is the setting that we typically care about sometime we care about causes of that. Uh I'm not 100% sure what's the right way to do it is because you we one thing we could do we could like say look we care about koala bear over like you know koala bear and we pick one root unit of kala bear maybe seven I don't know what the the roots of units are and then we just say like prove it for that you know for a mathematician this is not exactly what they want to see like >> yeah the more specific you make it >> exactly >> less attractive Yeah, >> but I don't know maybe

>> I think so like look as long There's a subgroup right >> as Yeah, we can say like for for an

arbitrary like sub specifically more than one. >> Absolutely. >> I think it's not the same, right? Because like for constants, you're >> Yeah. But I think there's this significant difference that is for constants you say things will get better and constants improve over time. I feel like if you have a proof for one

specific field and specific evaluation domain, then this tells you nothing about a different >> No, I think what I mean is that like what we're interested in is a general proof that works, >> right? >> Yeah. Maybe not. >> Yeah. What I'm like kind of worried about really about the collabor is that a lot of the probabilistic techniques that we have a are relatively large fields like maybe a very sometimes a very large fields like you know these are theoretical results there are constants which are not great

so if you look at the one I before like something like two to the 20 /a you know this is large much larger than what we have so there is a chance that when we end up like working with this kind of thing we end up uh getting results for like fields which are like too uh too large. So and this will not transfer like for example if I give you like a proof for fields greater than two to the B 100 you know. >> Do you mean characteristic because of course we always can use extension fields.

>> Yeah. Yeah. I mean a characteristic. >> I mean characteristic. Yeah. Okay. So uh I think we are at time. So uh thanks all for the session. I think we will have a proximity jam session I think tomorrow >> or >> after tomorrow. >> Day after tomorrow. Okay. So we can continue these discussions there. I think this session the proximity session was planned to be pretty like open. So uh yeah you you see the questions I put some notes there. This is from the hem that you should have and we can continue the discussion then. Thank you.

I think >> I think I think we have some takeways right the clay people don't have like some very strict set of rules like if it's going to work it's going to work and figure out if this thing works. So I think this this part is kind of a takeaway right >> so I think we need to try and specify like very precise exact >> we should have like yeah so I I think take away I I think

this was a clear takeaway how to advertise it. I think we made some progress there. I think we are now we know there are much more details about how to specify what the conjectures are. I wasn't expecting that we figure out these details today but I think we made progress and uh also the spam protection. I think there was >> let's do that tomorrow. >> Okay. Thanks a lot. How was the sleep?

I think every I won't have any Let's see how

we get this guy. Just last time I had like actually We're going to be fine.