Ethproofs Call #6b: Proximity gaps

Transcript

Intro

[music] [singing] Okay, welcome everyone. We're going to get started in a few seconds. >> Thanks, Will, uh, for this light entertainment while we wait for people to come in. Okay, great. Let's get started. Uh, welcome everyone to EF proof call uh 6B.

This is the first time that we're repeating a topic, specifically proximity gaps because we have uh just so much content to discuss. Uh, and if you'd like to join the uh, Telegram group, uh, here's the QR code or you could just join in with the URL eve proofs community. There's, uh, some good discussion there. Um, zooming out, uh, I'd like to say a mission accomplished on one of the biggest missions of 2025, which was, uh, real-time proving, trying to prove every single block with low latency on a reasonable cluster, um, drawing in particular, less than 10 kilowatts. We had three different teams at EF proof day uh, that showcased this

and we have more teams over the next few weeks and months that will also achieve it. So, fantastic. Congratulations uh to to everyone involved. In 2026, what I expect will happen is that there's going to be a shift uh away from performance. We still want to keep performance of course uh but we want to do u things above and beyond just just just raw performance. So looking at for example the foundations of security trying to avoid these proximity gaps conjectures trying to make sure that our our proof sizes are are reasonably small and making sure that uh we can deal with prover killers and and livveness and uptime and and all of these uh good

things. So this has been the the schedule of 2025. We're wrapping up with call uh 6B and um as you can see, you know, there's already more of a focus as we approach the end of the year towards 2025 and in 2026, the three calls that we tentatively have scheduled uh are on security as well. And the next call will be on guest diversity. So, not only do we want a diversity of ZKVMs, but we also want a a diversity of guest programs that get compiled to these ZKVMs. And uh we already have uh today integrated four different uh guest programs uh which is uh which is really amazing including some some more recent

ones like u EVM1 and LEVM from from Ephrex ZK sync OS in addition of course to our EVM. So um here's a little update to the uh ZKVM tracker. Uh in yellow we have the some of the the new updates. So we have two new columns the 10 kilowatt uh proving which three different teams have achieved. So congrats air bender uh SP1 hyper cube and zisk and we also have a new column around the usage of of proximity gaps and whether that's proven proximity gaps or conjectured and we're already seeing a a kind of industry shift towards provable proximity gaps

with uh espe hyper cube and zisk leading the way but others like openvm um kind of signaling that uh they will be moving to uh provable proximity gaps and we also have two new integrations on e- proofs uh from powder and lambda class. Um now here just a super small update I guess is uh uh risk zero um is no longer integrated with e proofs because firmar uh as one of the provers uh proving them uh is uh has stopped proving but I'm expecting them to go back in this uh top category very soon in 2026. I'm working

on a v3 uh which is uh much uh faster and uh we also have uh two new uh zkms for which the name has dropped. Um so we have the lambda vm from lambda class and we have the zk dtvm from antchain. I think that stands for deterministic uh virtual uh machine. And then finally I've added kind of a new category at the bottom here which is ZKVMs for which you know from my perspective uh development has paused at least temporarily. Um so these are ZKVMs that might not be uh actively maintained but of course they could jump back up if uh

if they come back to life. Okay. Okay, so talking about security foundations, um you know, we want to move to proven gaps and uh just yesterday uh we had uh George uh post a new uh or maybe it was today actually yesterday foundation uh blog post on on on that and George will be uh talking about that shortly. And final slide uh this this is uh today's agenda. So, we're going to have a few updates uh starting with with Jordi who will talk about how they kind of very very quickly move to 128 bit of provable uh security which is great and then we're going to have miscellaneous

updates from various ZK uh VM. So for example, exciting news, Lineia is going to be building a type one uh ZKVM uh trying to to to join the race toward mainet grade ZKVMs. And uh we also have other excitements exciting announcements coming up and uh we will have eight uh presentations. So extremely packed schedule today. We might go slightly over the the the two hours. Um but really the the highlight here is all of the papers, six different papers uh that have uh come out very recently in addition to all the papers that we talked about last time. And one of the big themes here is that the the

proximity gaps conjecture is taking punch after punch after punch. Um and um you know every time it it receives a punch, the researchers will tweak the conjecture and form a new conjecture. And now we've had three rounds of this where the conjectures have been proven false. Um but we're going to end with um some hope um uh a result from Vancat which actually shows that the proximity gaps conjecture is true in you know some some other settings uh like the randomized setting and um we're giving Vancory 20 minutes uh to to show his result partly because uh of of what it is fundamentally but also partly because um

Gurus Swami is basically from the celebrated guru Bruce Ramy Sudan decoder. Okay. So uh without further ado, I'd like to invite uh Jordi to the stage to talk about 128 bits of purple security for ZISK. >> Hello. Well, I'm I'm I'm very proud to announce that we are currently releasing version 050. I think that we are running the last continuous integration right now. So if everything goes well it should be in a few uh hours uh available and this version mainly what it does is I mean it's already 128 bits provable security the interesting

Jordi Baylina of ZisK: 128-bit provable

part is that the proof sites uh still be below 300k currently it's about 400 400 uh 240k without uh compression but actually compression does not do anything so this is the like the the the final proof move and uh all these keeping very much the the keeping exactly the same timings and uh the same performance that we had. This is possible mainly for many things. Uh there was a uh so that mainly there is an an important optimization in the ketchup circuit. It's a fully new arithmetization and some cool ideas that we divided by uh just one order of magnitude the cost of the ketchup

armitization. But there was also a lot of re-engineering in the in the circuit in in the in the aggregation circuit. Mainly there were some optimizations there like reducing the like reducing the the in the the top of the trees just um only proving it uh once uh we added grinding uh in there and we added some some uh little bit more polomials there. So we keep the the the order. So there was a lot of engineering there.

[clears throat] Okay. And uh yeah and in this version also there is some modeps modep fixes optimizations uh to keep that fusaka and all this more or less keep working and of course we are still open source and quantum resistant. So this is our very much the the the update for this version. >> Uh congrats. Uh quick question. Is this using goldilocks with a degree two or three extension? God loves over degree three. We didn't change that. >> Okay, perfect. Uh and super cool that you've managed to keep the proof size under 300 kilobytes at 240. That's uh super super cool.

>> For this we we in the in the final step actually we just uh do a binary tree. So this is much uh shorter and with that we keep uh all more or less the same size. >> Okay, interesting. Uh I don't know about the details of that but I'll ask you offline. I'm quite curious. Um next up we have Alex uh from the linear team. >> Alex thanks for having me. Uh so yeah on our side the team recently shipped Fusaka or the mainet of Linear. So that was a very important upgrade for us because uh it we in the span of June to December we cover London to Fusaka. uh that was really important for us uh to

Alexandre Belling of Linea: type 1 zkEVM

test uh whether it was actually uh achievable to uh keep up to date with uh Ethereum uh while doing the arithmetization by hand and we think it's a success uh and the uh other things that are coming up is uh the completion of the migration to collab so it has taken a considerable amount of time because it meant rewriting a lot of of the Uh but once complete we so we already have some benchmark and it is going to be a super massive performance boost. Uh we are using quartic extension now but we are going to reach it very fast to sex tick in order to be fully at 128

bits of security. Um uh and so uh one very interesting things in how we are approaching type one compatibility because uh like doing it like being type two by hand is kind of proved to be possible but being type one is more complicated because we have to be good at doing RLP encoding and catch encoding and those are super hard to do by hand. So uh what we developed is a language named ZKSM which is partially fleshed out but already put in production for some uh of the use cases. We use it already to uh prove black too.

Uh so it is at that level. So it support control flow. It support uh recursion. It support uh uh wide degree because it's collabor time six uh and then there is all the losses in the protocol. uh and so the uh so the language compiles into airs uh and uh from that we uh we implement Patricia Merkel trees and uh and RLP encoding. So one feature we will need will be uh the support for memory addressing which is not current

implemented but will be very soon and is being actively implemented uh and and those are the main things that are missing to be type one anyway. So uh we think we are very close. >> Congrats and great to see that you're so flexible uh while being super lowle and performant. One quick question from all rich. Um, why degree 6 extension for 128 bits of security presumably as opposed to maybe degree 5? Uh, yes. So the reason we do it is so degree is possible if we use grinding but we don't use grinding. uh and um like some of the loss we have come from

the proximity gap but also from the enormous size of the traces like if we simplify a little bit the sunless loss in a protocol that use F or any codebased thing there's a loss that is associated to uh the list decoding error because we tend to use F as a polinomial commitment but formally that's not true and there's also less loss associated with that uh a few doz a few dozens of byes bits and uh there is a usual short loss which is kind of proportional to the trade size. So 30 30 to 40 bits. Uh so the accumulated means that you need at least six five is not going to give uh enough security out of the box.

>> Got it. Uh Ben in the chat is pointing to the new result by all rich. Um maybe degree five is possible. Uh but yeah, thank you so much, Alex. Next up, we have uh Diego uh from Lambda Class. >> Thanks a lot, Justin. Um we are pleased to announce that we started building uh the Lambda VM and the idea of behind this is the the same as we had in Ethrex uh and and what we did related to execution client. So the idea is to make this VM like really simple, minimalistic, track a lot the number of dependencies, keep them at a minimum. Uh the idea is that we are not only going

Diego Kingston of LambdaClass: LambdaVM

to develop the VM but also the proof system. Everything is going to be directly incorporated into it. Uh we wanted to to make it postquantum secure from from day one and achieve the 128 bits of security. We are um going to build a risk 564 uh virtual machine. Um and we are working closely with uh our partners um to make this um very comprehensive spec uh have everything like clearly written down and make it really easy then to to audit and and formally verify. Um so it's part of the the same philosophy. We

we think that uh this this can add a lot of value. We of course like a lot many of the VMs that uh they've made they and they've made like uh great contributions but we want to make something uh simpler and also to add diversity to to the VM space. So that's the the news. We are like trying to move as fast as possible so as to have like a minimal version and I hope we can we can show some things uh really really soon.

>> Okay, great. Looking forward to the uh codebase being open sourced. Uh and great to see more ZKVMs looking to uh have a super simple codebase. It's reminiscent of Jolt and and Lean VM which is which is great. Um, thank you Diego. Uh, next up we have a new another new ZKVM ZKP1 sorry ZP1 from Vishall. >> Uh, Vishall, are you here?

>> Yeah. Yeah. >> I cannot share. >> Oh, strange. Um, okay. Let's move on to the next speaker and we'll we'll sort you out. Um, next up we have u Ming from Cino who will talk about real time proving. >> Yeah. Hello. Thanks Justin. So I'm looking to I'm looking for how to share screen.

Ming Wu of Ceno: Ceno RTP

>> H that's it. We can see your screen. >> Okay. Cool. Okay. So uh yeah I'm mean from seno team. So today I will share some uh progress update for the the the quad quad Q4 for the milestone. So right now the project overall is in the late alpha and early beta stage. So and in in the the Q4 we are majorly achieved like the first one is the pre-ompile acceleration. So previously we don't have much pre-ompile. So we integrate few pre-ompile for acceleration and we also have the multi-shot support right now to prove the the minute block. Yeah.

And the November we are try we are integrate the GPU end to end and right now the best there is in the risky GKR and the recursion is in the stark which is powered by the open VM. Yeah. And uh here we show two simple diagram is a simple breakdown for the data we have so far. So uh right now we we divide the execution in uh we divide the proven flow into three stage the emulator and the risk of fi and the the risk by GKR and the recursion part. So in the November we are optimized it and uh so far we uh on the December part we are have some result now and right now we are still trying to optimize because uh we optimize more on the shard number we

are reduced from the 30 to 15. So uh l the the emulator part is occupy more proportion right now and also the recursion part is also occupy more proportion if we up optimize the GKR part uh like more and more. So later we will try to al also working on the some the more general optimization for all the part. This is by the way this data is proving the the block with which is around like 20 million gas in a single 4090 GPU. Yeah. And the right diagram is like right now we also have another challenge is like uh in in all the shot we are or our GPU prover is not very like uh the performance is not very consistent across all shot. You can see

some shot we can reach the very high like cycle but some are below like uh some above below average. So for now and beyond we are working on like firstly we try to reduce the shot to be less than 10. This is our first goal and with that we can probably reach make all shot reach the four mega mega megahertz and later we will try to make all shot to reach the 10 megahertz. Yeah and uh once we achieve that then we are moving on to the cluster realtime proving and uh right now we already on the east if proof staging so we also on board to risk uh it proof life sooner and that's it if you are interesting in the GKR security or like some uh

integration with the GKR some check or like or interest in the the co flow we feel free to feedback and discuss that's it Perfect. Thank you so much. Uh we have a question from Kev. Uh what CPU was used here in the benchmarks >> CPU right? Is it? >> Yeah. Which CPU was used? >> Oh, CPU I remember is like EPYC which is like 20 uh 64 core for now but I I forget the real number is based on AMD.

Yeah. But the CPU in here the majorly work of CPU is the the pro the witness generation and the emulator part and for the all the other part like the uh risk 5 GR layer or the recursion part we are we are turn we are switch on the GPU mode. >> Nice. Uh Kian has shared in the chat that it's an epic uh 9554 64 core. Uh great. Looking forward to uh see you on Eve Proof's uh uh production and uh I know your your back end is quite different from the others. So it' be great to see the the performance deltas there. Uh thank you so much Ming.

Uh >> Val, do you want to try sharing your screen again? >> Yeah. Oh, still not. >> Still not. Okay. Uh maybe it's like a setting on your computer and you need to kind of restart Zoom. I'm not not sure. Uh next up we have um Gal uh who is joining as a new proximity prize judge. So I wanted to give him another opportunity to introduce himself.

Gal Arnon: Proximity Prize Judge

>> Uh yeah. Uh thanks Justin. Uh hi everyone. Uh yeah, Justin thought I should uh introduce myself. It's a good idea. Um yeah, so I have uh just joined the prize committee. So unfortunately I have the uh difficulty of trying to parse everything uh while things are still changing every day. Um so just a bit about myself. I uh about 6 months ago I guess I finished my PhD at Vitzman Institute with Monol and Alonv.

uh now I'm a posttock at Bone University in uh Italy. Uh most of my work has been on IOPS more the theory side but in this field uh theory and practice are very close to each other. So that somehow turned into practical things like stir and were uh more recently I've looked at security of uh famir and uh things like the minimal size of uh um group based snarks. Um so that's me. Thanks Justin.

>> Perfect. Uh welcome uh to the panel of judges and uh we've updated the website proximityprize.org. or I'm hopeful that very soon uh maybe early 2026 we'll have the actual uh formal uh rules of of the prize and we can start uh delivering uh some some of the prizes. Uh cool. Vishelle, do you want to try one last time? >> I am still not >> okay. Um I mean do you want to just give an intro without slides I guess?

Vishal Singh of Zippel: ZP1

>> Yeah. Yeah. So uh so uh it's a zipple at ZP1 and opensource uh uh risk 5 work in progress ZKVM. So we are using uh RB32 IM uh with circle on meren 31. It's totally open source. uh uh it's been uh 10 days we open source and uh it's still licensed and it's currently in uh research and pre-alpha phase. So what's the motivation of doing this? Uh it's challenging and uh I see it's it can have a huge impact. So uh what's Zipple Lab and who we are? uh we are an small

independent uh research and development team not backed by uh anyone currently uh and what next what's the road map so uh in Q1 what we will try to do is uh release white paper and work on recursion and GPU acceleration then try to uh prove EVM minute blocks in less than 12 seconds and then in Q3 uh Early Q3 we will try to work on security formal verification and in early Q4 uh we will try to u uh real time proving on uh it prove thank you

>> amazing um and if I understand correctly um this is at least historically been mostly a oneperson effort and especially impressive because you're still at university just uh finishing your your your final exams. So, looking forward to uh to the future of of ZP1. Cool. So, that finishes off the um section on quick updates. Now, we're going to have slightly longer presentations ranging from from 6 minutes to 20 minutes. First off, we have Will and Farah uh with a six minute update on ephus.

Will & Fara of EF | Ethproofs: Ethproofs updates

>> Thanks, Justin. Um, yeah. So, if you didn't have a chance to join uh each day in Argentina, it was a blast. Thanks to everyone that participated. There's a YouTube playlist that's available now. So, all the talks are online if you want to go check them out. Um, I used my talk to speak about the like overall like magnitude of this entire effort that we're all a part of and likened it to a public private partnership where on one side you've got the dynamism of these private industry part uh participants the ZKVMs and the provers like setting breaking new ground and setting new benchmarks uh day in and day out and really just blowing our

minds. Then on the other side, on the public side, you have all of the EF teams and researchers that are really kind of setting all of these uh non-negotiables in this direction and really trying to make sure that all of those industry actions are sort of done in concert and alignment with broader Ethereum protocol objectives. And so in between is where e-roof sit. So as a literal interface, you know, the website itself and then as this kind of community mimemetic rapper trying to help drive alignment uh along, you know, all of these objectives that the researchers are are uh positioning. And so as Justin mentioned earlier, like

2025 was decidedly the year of performance. And uh with a lot of the blog posts that you're seeing posted recently and conversations with researchers, it's clear that 2026 the center of gravity is moving more towards security, diversity, and resilience. All with performance in the backdrop as table stakes never going away. Um so this week we also launched a blog and there's a couple blog posts up if you want to go check them out. Uh the first one is all on these 2025 highlights. a lot of links to great content. Um, and then the second part is all about 2026 roadmap objectives as we see it now.

Obviously, this is constantly being updated. Um, and so one thing that we know is for certain is that eofroofs itself as a platform. We really want to try to like scale up and improve um the back end and um the the operational functionality of the interface. And so like really working to make sure that we reflect the operational profiles now that we've seen nine months of of activity on the site and all in service of uh providing clear consistent neutral performance benchmarks. Um, so there's a second blog post that's also on the website that's all around, you know, in sort of the spirit of that that's about

uh prover personas and GPU price indices. And I'll throw it to Farah to talk about that one. >> Yeah. So when ETH proofs launched, the only game in town was for provers to submit proofs for every 100 blocks using a single GPU prover. uh then beginning with ZK cloud in March and more recently in the push up to ETH proofs day we saw the emergence of multi-GPU provers submitting proofs for every block. So in 2026 we will begin to roll these out as what we are calling prover personas on ETH proofs. So when creating a new cluster teams will need to choose which goal they are targeting.

Additionally back when we launched we started with a snapshot of cloud hosted GPU configurations for several vendors. This approach helped us bootstrap our efforts, but it needs to be modernized to be less brittle, more scalable, and reflect the reality that most provers are converging on a limited set of hardware. So, in response, we are introducing a simple GPU cost index, an average of globally available pricing for a single readily available 5090, which can then be multiplied by the number of GPUs the prover is using. We feel this approach provides lots of advantages and reflects our mission. The mission of ETH proofs is to measure tons of proofs over a long period of time to help surface directional trends, not to

be a detailed cost model that is easy to game and nearly impossible to verify. Some of these advantages include bucketed data, meaning provers submitting proofs for every block won't distort the data for those submitting every 100 blocks. It also opens up new design spaces. We can easily provide a simple admin dashboard for team onboarding and cluster maintenance. and we can derive a reliability or livveness score that punishes teams for missing proofs. From there, we can take the most performant provers and add them to a real-time proving cohort. And once we have that foundation, we can begin to monitor teams even closer. Anytime more than one fails to prove a proof in under 10 seconds, we can designate that block as

a prover stunner. And anytime more than one cues a block but fails to submit the proof, we can designate that block as a prover paralyzer. So monitoring all this behavior can help us generate a resilient score and surface issues because if 2025 was the race to prove Ethereum in real time, 2026 is the race to mainet grade ZKBMS >> and the race continues. So we're excited to announce the next ethuse day which is going to be uh just prior to ETH uh CC and CAN on Saturday, March 28th. And then we're calling that day beast mode.

And then the following day is going to be uh a chance to learn more about the postquantum cryptography and postquantum consensus fast finality efforts that are also underway and we're calling that day fort mode uh which is on Sunday. So we hope to see you there. We'll drop links to both lumas here in a second and feel free to sign up. Thanks. >> Okay. Amazing. Uh, right on time. Any questions from the audience? So, one question from Resa is, "Is the 6000 the RTX Pro 6000?" Yes, that's what it is. Um, it has big uh uh more VR RAM.

Um, and yeah, I thank you so much uh Will for all the coordination and and Farah for being, you know, this this interface. I think this is a great mental model. Um and uh you know going forward you know we want to be uh you know have have a finger on the pulse both on the community side of things but also uh internally to to the EF and um you know we have at least four different teams within the EF essentially dedicated to to ZKVMs. Um and uh the the closer we can work together the the the the better. Um, great. So, I don't see any questions, so we can move on to George who will talk

George Kadianakis of EF | Cryptography: soundcalc

about SoundCl, uh, as well as his latest blog post. >> Um, hello everyone. Let's do the classics. Can you see my screen? >> Yep. >> Got it. >> Okay. Fantastic. Okay. So yeah, let's go a bit into uh this blog post and this push towards security and foundations that Justin and Will have been talking about. Um but before we do that, let let's do a little bit more of like world building and you know like if you've been following these calls uh you know that like you know projects relying on conjectures proximity gap conjectures on huristics uh lately they've been working

on pretty shaky ground and you know uh days pass and conjectuous crumble and bits of security fall with it. So us as like the EF cryptography team uh I think we feel quite uncomfortable relying on such conjectures that one day they they they hold and the other day they don't. So from now on uh we want to focus on provable security only and not only that but I think there is something to be said about bits of security as well where many projects you know they for performance reasons and for other reasons they they are going with like

100 bit security um which is reasonable in some ways but also you sort of then you need to go and count bits and see how much how many hashes Bitcoin does and do like you know do some margins and and you know this is not the way we want to think when we're talking about L1 mainet grade security so we want what we're trying to do is sort of set the goals to provable security and 128 bits which I think is a like a reasonable goal that the rest of the industry uh does so right so That's sort of setting the stage and over the past months uh

we've been uh creating like from talking to teams and uh trying to understand how they calculate soundness and how they calculate security. Uh we found that each team does it differently. And one thing we did is create uh sound calcul which is basically a universal soundness calculator for hashbased proof systems. And what you do is you have your ZKVM, you go to soundk, you integrate your proof system, you integrate your PCS, you integrate the parameters of your circuits, you know the trace length, um if you're doing fry, what rate, what folding factor, all this stuff. And then

[clears throat] uh sound calcul essentially spits out um an overview which is quite detailed because we're dealing with many circuits and recursion and stuff but in the end of the day it's basically uh the final proof size like the final proof the wrapper proof how big it is and also the final bits of security throughout all the circuits. Um so you know here you see you know it's 53 bits of security in the Johnson bound regime and the circuit with that security like the offending circuit the weakest link is the risk five circuit for example um anyhow uh so with this tooling uh having this tooling and these

foundations um let's go a bit into the blog post. So what we're trying to do in this blog post is set up some milestone for 2026 uh that basically we want in the end of the year to take us to uh the ideal security level. So let's go to the milestones one by one. So um by the end of February uh we expect projects to have integrated to sound. What does this mean? It means that like you know if you're using some sort of like a univariate to multilinear adapter, we would like you to integrate

this component into sound calcul. If you're using a lookup for uh input output consistency or like for memory checking or if you're using multicet hashing, we want you to also integrate those components into soundk and then also integrate your circuits into soundk. Um you're not alone on this like uh we are very actively working on Sankal. So please reach out and we will help you integrate your stuff. Uh but we do want your assistance like we cannot do it on our own. So that's the first um milestone. Then uh by the end of May which is before the glamsterdam hard fork we want projects to have ended up

with 100 bits provable security and less than 600 kilobyte proofs. Um which I think we we like we think is an achievable goal and then by the end of the year we want projects to have 128 bit probable security. So like the the industry standard and proofs less than 300 kilobytes. Um these numbers are not random like you know the proofs the proofs need to be small enough because they will be eventually transmitted through the networking uh P2P backbone of Ethereum and also uh these numbers are not random in the sense that we talked to the teams

and we got um positive reactions and teams being optimistic that these milestones can be hit. Um right and because you have the slide in front of you and you can see like these items there is also uh one item related to recursion that I would like to go into. Uh basically like again from talking to all these teams um one one thing that that has been um sort of quite different between all these teams like they're all using hashbased PCs.

They're all doing pretty much reasonable stuff, but they everyone is relying on recursion to sort of take the big EVM trace and chunk it up and do continuations and do all the nice stuff that allows uh such a big trace to end up with a very small proof. Um but because each team is doing this recursion differently like like like they're using different techniques they're they're they're like they're sort of do using different fanouts they're using some some projects are using circuits other projects are using risk five machine to do their

recurration like we see lots of differences on their recurration. So one thing that we want as part of the milestones is to put to put a bit more sanity into this process. So like we basically want to end up with recursion specs. We want projects to document how uh these uh these components connect with each other, the techniques, the lookup arguments, uh the glue basically like we want the glue to be documented so that we understand um things what we're dealing with and we we ideally we would want to integrate the glue as well into sound calc. So um these are the recursion related milestones and and

eventually we do want also to prove soundness like an informal soundness proof that this whole recursive thing um produces the security that we want. Uh like treating the proofs as black boxes. Why does this recursive thing produces uh the security that we want? Um anyway uh we will go more into these formal details uh as time moves on. Um so these are the milestones from the blog post and I just want to take like a a brief second to talk to why we think this is these are the right milestones for this point in time. Um basically

we think that you know we spent last year obsessing about performance and rightly so because we want to derisk the entire pro project in terms of performance which is like the main component but at the same time we think that this is the right time to pin down the security part because if we keep on uh if we keep the security uh as a free variable basically ically like we we we want we will never oify the foundations like the proof system the PCS's so we hope that by the end of this year the the foundations of the ZKVM have oified or at least stabilized

in some way and this will allow us to um do more proper audits. It will allow us to do more proper implementation level specs. it will allow the formal verification uh initiative to uh do more deep work. Uh so yeah, we think this is the right time to basically set up this foundation. Um and wrapping up uh I know that the blog post is quite high level and my talk here has been high level. So um we are writing down more specific details particularly about how we think

recursion specs should look like and we plan to uh publish a more formal technical document on the milestones uh early next year like in January. Um and also we're working on uh revamping ETH proofs to make it more security focused so that we basically uh highlight teams that improve their security the way we would like them to. Um so yeah uh that's it basically. Now you know what the blog post is about and let me know if you have questions. Thank you.

>> Thank you George. Uh feel free to unmute or raise your hands or ask questions in the chat. question from Resza. How to adjust for extra bits of security when comparing ZKVM proof generation times if it matters. Let's say we're proving 60 million gas blocks. I'm not sure exactly. Uh C Reza, can you say a few more uh details on what you mean? Maybe Justin, I don't know if you got there.

>> I mean, my best interpretation here is that if you have longer traces, that affects uh security a little bit. Um and so as you increase the gas limit, maybe there's a degradation of security. My hot take here would be that these are very minimal and I don't know Ben is saying his interpretation is that if different provers have different security levels how do you compare proving times? Um I guess what we're trying to do is to normalize the security levels so that they do become more comparable. I guess the other

Alistair Stewart: On Reed-Solomon Proximity Gaps Conjectures

observation is that at first approximation when you increase uh security you don't really degrade uh prover time you increase the proof size which will affect prover time indirectly because of recursion but at first approximation it's it's a a fairly minimal uh degradation in proving time cool I think that's mostly what we have uh in terms of questions thank you again uh George so now we're going to start the hardcore mathematics part of the uh of the the call uh starting with with Alistister who had an initial paper um a few weeks ago proving that the conjecture uh was was incorrect. Um and

then right after that we have uh Jacob who will talk about a paper that builds on this initial result and makes it even stronger uh and made the attack more potent. Alistister, the floor is yours. >> Hi. Let me see if sharing works. >> Oh, >> uh, see that? But I can't maximize it now. No, it's inside. >> It's pretty big. Yeah.

>> Okay. So, yes. So, we we have this paper on Sullivan's proximity gap conjectures, Elizabeth and I. Um, we had two results. uh one of which over overlapped with the paper for four days before that that the Ben and Angus presented and one of which overlaps with uh the paper two days later that also got presented. Um ah okay. Um so yeah the basic idea was um this conjecture in the deep fry paper about list decoding up to capacity was already known to be incorrect from about the 1950s.

so Peter alas looked at this and there's basically a threshold um below which some codes are list decodable. I'll give you the number for this later. And above which every code has exponential size list. Of course when I say some codes are list this decodable we still have no idea about beat Solomon. Uh and there's still a huge gap. Um yeah and and the point of this paper was to see if this also applied to proximity gaps. And the answer to that is pretty much yes. So just like uh Ben and Angus' paper, we uh looked at the um the chance that a random word was close to the code and

from that you can get a uh a proximity gap for correlated agreement failure. Um this is the formula that that we got for the bounds on this probability of being close to the code. Um and yeah here's the formula for this query entropy that appeared in the list decoding bound statement. What does that mean? Um basically uh very soon after this list decoding capacity bound um we end up with uh proximity gaps completely failing. Um for anything far from the code we can find something which you can just take at random. Um and almost every point on the line apart from uh the end

point you started from is actually close to the code. And to go that you only have to go uh as far as this form would suggest this this term in the square root is the square root of almost the whole gap in between proximity and this list decoding bound. So it's um this lower bound is very much closer to the list decoding thing than capacity. >> Ben is asking what is wrong with n minus f minus one. Um, okay. Maybe I'm being um paranoid here. Right. So, there's there's one thing where um everything that's not in the code. Um, right. So, so so so if something's not in the code, it's n minus f minus one.

>> So, covering radius is n minus f unless I I think you have the same convention as us. F is message length, not not degree or something, right? So, covering you can find a deep f is a number of Yeah. >> Yes. Right. So you can find a [clears throat] deep pole of distance n minus f and then uh the line will be will be less. So >> I I think you're off by one. >> Um maybe we're off by two like one by one. >> Your k your k must be less than capacity.

>> Yes. >> So your so covering radius is n minus f for you. Your k can be must be less than that. But That makes sense. Okay. Yeah. Um that's one out. >> Uh the end thing is that we think the list decoding capacity theorem it's probably typed for correlated agreement as well. Um and this holds I think in a uh a bigger regime regime more useful regime in practice than Ben and Angus' thing. Um so that's where we got with with that.

Um again how big is this? It's, you know, about one over uh log q uh is the gap from capacity. Uh and we can do a more complicated formula here that goes off the edge the uh binary entry. Um and the technique um we used uh agreement sets. We we actually well we're talking about disagreement sets, but it's equivalent. Um and we're being inexact in that we don't require to guess exactly what the uh you know we we can agree on some things where we uh don't let we weren't assuming we agreed. Uh if you do this then everything ends up uh much nicer.

All the numbers end up being simpler. Everything ends up being uniformly distributed. Um and everything works right. So, so concretely it's like we have two sets of size f and you interpolate polinomials outside of them. if uh the two things intersect by uh you know the intersection is smaller than the uh uh minimum distance then um clearly if these things are low degree and get a code word then it must be the same code word for these two things and otherwise um the events that these things uh are are code words are independent and almost everything you know all our

events are pairwise independent and the variance ends up being small and then everything ends up working pretty nicely. Uh the variance of a number of uh of sets where this works end up being uh small and everything end up nicely. Um and then we made some conjectures which uh you know our original conjecture from 3 weeks ago uh was proved wrong by uh Ventian Sanso. Now the updated uh conjecture from the e-rint we published today was uh survived until yesterday. >> [laughter] >> So yeah um so so our suggestion was we take the existing conjecture you know with with with this eater that was a

distance to capacity and instead make it the the the distance to the list encoding capacity bound with with with this entropy term. Now the question is a bit uh is cury entropy. So originally we was testing cur entry for the field size um and then we thought okay let's be conservative and move it to the characteristic which gets the wrong um thing for binary fields for sure. Um and then that doesn't work either and now maybe the minimum of the characteristic and uh the domain size n is is going to is going to work here. uh this is a conjecture that I don't know of any um things wrong with it. Um but uh we

can almost certainly do better for small characteristics. Um so for binary fields I we really don't have a clue. so that's the conjectures. We had some other results. We got the list decoding empies correlated agreement result that was also an overlapping result uh with uh copy habok and many other author's paper. Um but that result has like this this failure probability correlated agreement of about one over one over k uh where k is the um like the degree well degree plus one and um that's not ideal. I mean it's

still a useful result that you might have to repeat the test a few times. If you batch enough stuff it still works. Um and then we um looked at this regime um where the domain is in the subset in the sub field. That's why we were suggesting the characteristic instead of the the size of the field for extension fields. And basically what happens is that correlated agreement uh fails when list encoding fails just like in um benzianso. uh and this is not uh the one over k this is the complete value we're getting before where every point on the line but the one endpoint that's um far from the code is close um and again yeah this is why we were

suggesting HP because uh we get uh when you uh go past the list coding capacity for the small field basically uh you can use these small field words and which are close to small field code words and lots of them um to build the correlated agreement failure. So that's our results. [snorts] Um so so one thing I wanted to highlight that I don't think anyone really has done any work for. We're doing lots of work on these conjectures, but it's not obvious just because the conjecture fails that the snarks are actually insecure.

um rather what happens is um so you know I can easily find something that's uh far from the code which if I proved it was close to the code will allow me to uh just start proving basically anything you know we have this quotient which uh I can easily commit to a a word that that um looks like this rational function but um it's far from a polomial but if I combine it with with something at random then I end up with something which is um close to a prob polinomial with with high probability. The only problem is I've got no idea how to find it. Like you know what is this polinomial that's close to? If I find the polinomial it's close to I can probably prove it with fry. Uh I can go

through with the entire fry fry proof for this thing being low degree. Uh but I've got no idea how to find it and we don't have any algorithms that will be on the Johnson band right um even if we knew this was uh you know there was something close we have no algorithms to do it. Um a list encoding might be completely unfeasible beyond this length list decoding capacity bound that that was you know the the classical result that the list size becomes exponential but we just need one element. The only trouble is is that uh this problem bounded distance decoding for ret we actually they're actually hardless results for it. Uh but none of them really apply for this this random word case. Uh you know there's a couple of people showing it's

empty hard. um and one paper that has this more general reduction from discrete loss for extension fields. None of them work. And this last one is not postpont uh and really decoding random words seems a really hard problem because everything looks random and you've got no way to no way no idea which way to go. Yeah, that's all I wanted to say in the 10 minutes. I have lots of slides on techniques if people ask questions. >> Thank you, Alistister. So is it fair to say that you've kind of ended your presentation giving us a little bit of hope that actually these conjectures might come back from the dead uh in terms of uh proofs of of of of uh of it being hard to find uh to find attacks?

Um so is it fair? >> So there might there might be a computational hardness result here, >> right? >> Hardness assumption that makes everything work, right? This is the the thing you'd hope if you can prove this this hardness and you can get a reduction. Of course, getting that to work, getting that to be postquantum, which was part of what we uh wanted from these lights in the first place um adds to the difficulty. But yeah, there is a hope that that all the that that these things are secure. Um but we have to make a new assumption other than just uh you know the random oracle model uh that we're doing for these Merkel trees.

>> Got it. But maybe these assumptions could also be proven at some point. Well, it's cryptographic assumption. No, they can't be proven. >> Okay, got it. >> Jako, you have your hand up. >> Uh, yes. I had a question like uh when you're talking about the conjecture talking the new conjecture is in a part you replace the the the query entropy with the the entropy of the characteristic of the field and I was wondering because the attack that we that we did in particular I'm not able to bring down exactly to the characteristic of the field. For example, if I have a read Solomon code defined over a binary field, I need to still choose my evaluation point to be over like some larger sub field. So I

will not go down to you know size two but like maybe to the 16. Say if my size is to the 15 for example. >> Yeah absolutely. Uh we don't know what the right answer is for really small fields. So so for things like this 32-bit field the characteristic is tight. It's going to be tight. But if you have this sub field which is you know smaller than the logarithm of the extension field size um then there just aren't enough um you know if we um list decode uh something which you know has the domain is the same same size as the field um there just aren't enough code words uh for the list size to be huge.

No, what I'm asking is [clears throat] slightly different like so your attack the the new one for this field. So suppose for example I choose a read Solomon code over 31 bit field but I choose my valuation domain points to be over the extension. So they're like over like you know extensic extension. So my code is still like uh over like I still have like an extension but uh my evaluation domain is now over the tension and I'm not over the base field like >> yeah yeah then you might be fine. So so in particular um but you end up having to do something interesting to get points in the base field. So if you look

at like say what circle FFT does um then yes I'd imagine that's looking at the the extension field um list decoding capacity bound and not the sub field but not only do they evaluate on the extension field but they're also like effectively some kind of folded read solment code where you have uh the conjugate um and the point itself uh in your um evaluation domain but you give them as the same point. Um if you look at it as a code over the original field then you're giving the real and imaginary part but you don't imagine like your Hamming distance should not be less if the real part is wrong and the imaginary part is the same it should be smaller and as a result the effective alphabet size is the extension field

size and not the base field size. Um, >> wait, are you saying you can dodge your attack if you choose your domain to not live in the base field? Then >> that's that's right. And and the reason is is because effectively your health website is is bigger. I mean, bear in mind that folded read Solomon codes are secure to capacity, right? We we know. >> Uh now >> um and I'm sure there's going to be a talk on that. >> Yeah. So we can like Yeah. We like if you basically the only case in which my attack and I'm guessing Aliser's one as well applies is when you know as a as a you know if you encode like base elements if you only do base base multiplication our attacks applies if

instead you have do base extension or extension base then as far as I know both our attack would not uh would not apply in that case >> like intuitively >> Jako Do you want to uh take it from here? >> Uh sure. I can share my screen. Uh there we are. Uh okay. Can you see this? Oh, sorry. The zoom thing always goes in the wrong places. >> Yeah, we can see it. >> Okay, good. Then I'll go ahead with this. I think it's a very nice segue. Um so, okay. So, this I'm going to talk about small field ashbased nar conjecture. So this is a work with

Giacomo Fenzi: Small-field hash-based SNARGs are less-sound than conjectured

Antonio Sanso and it's going to contain a few things like the attack itself there is more of an observation and actual attack. It's just combining two results previously known in the literature but I want to talk a bit about some of the other works that we've done the things that will it will connect to some write up which will eventually come out regarding the proximity prize. So I think this could be like also a quick tidbit from what me Dan and Gal have been working on. So let me start talking about this and I want to introduce first a toy problem. You know toy problem is a very loaded term in this. There's been the very famous ETH stark toy problem like long time ago. And now you might be asking okay Luke Jako why are we introducing a toy

problem. So I don't think I'm a particularly uh you know smart individual like I cannot hold many things in my head. So being able to like figuring out having like a very minimal example which allows me to get intuition on the security of like uh of a protocol I think is a very worthwhile thing and it allows us to think so this toy problem from is basically taken from the security noise of war is a very simple uh protocol and if I can prove this I'm confident I can prove like larger protocols and analyzing the soundness upper bound and lower bound this protocol will in further inform our understanding of what we really know

about these problems and it's a very simple protocol and it fits on one slide. So, so basically you're going to be trying to think about constraint codes. So these are codes. So you have f_sub_1 and f_sub_2 which are in the honest case they're code words and some and they must satisfy some sort of linear constraint of them. So this dot product with V Z V and U1 are inputs were given by the the person who's running the protocol. So what's the protocol? Well the proven verifier the verifier just asks for a random combination. The verifi the prover sends the random linear combination and then the verifier spot

checks that the encoding of the linear combination uh agrees with the random combination of the two input code words. Very simple and nice. uh indeed you do the queries and you can do a soundness analysis of this protocol and you can show that the soundness error and in fact a stronger version of ramaround knowledge soundness error of this protocol can hold given the and is bound by three quantities. One of them is the mutual created agreement error of the code. This is the what proximity gaps been traditionally about. one term which depends on the list side of the code and one term is one minus L thet which is essentially is the proximity

error and so these are the three errors and what you should say is that these are errors by a parameter delta which is basically how many errors we can tolerate and these errors they have contracting behaviors when delta grows to one for example the MCA error as delta goes to one will go to the list size error it will actually go to something even larger than one once delta goes to one because it will cover the entire space and instead the one will go to zero as as um as delta goes to one. So finding the a security analysis which gives you what you want

the the efficiency parameter you want is about really finding the right like um uh the right balance between minimizing t which of course like the the larger delta is the the smaller t can be and maintaining the other two errors under control. So this is the toy protocol and is what we're going to be starting with. So we can prove soundness like in for as long as I give you an expression of MCA and the and the list size I can actually compute the soundness. For example, if I set key to be 128 and I use a rich Solomon code of a typical size using provable conjecture provable

um bounds I can show this as approximately 64 bits of security. So this is one part. Now uh just for this presentation I'm going to just talk about the list size part. So I'm not going to talk anything proximity gaps and this part because I also believe that list size you know is a more fundamental notion as part of the work in CS25 and in BCHKS25 has shown that the list size and like a fundamental hurdle that we have to overcome in order to actually be able to give stronger security guarantees of this protocol.

So what is this notion of list size? Well, I'm giving you a word and this word is could be a code word most likely will not be and I want to look at the aming ball around it and see what things are close to it. So within these uh unique decoding radius there will be at most one but in general there might be many more and the intuition why you should care is that when you have like when in an analysis you have to deal with um a list size you usually have to do a union bound and this union bound is problematic for a soundness error and this appears in a lot of places like for example in the constraint folder within the toy protocol in auto domain

samples it's very inherent in anything you do flashbased and in fact you can even vary some of the protocols that we know about to get security which does not depend on proximity gaps but only on the on list the coding conjectures. Further we think that this is proving this is at least as hard as proving that the improving distance preservation is at least as hard as proving the list size is bounded when we're talking in the Johnson to capacity regime. Even more fundamentally like maybe you could say like Luke Jako you have this protocol we have an analy which relies on MCA and list the coding but it might be just a feature of the analy that you're doing. So part of the reason why

we want to have a toy problem to analyze is that we want to show that there are some lower bounds on the soundness that this protocol guarantee which depend on quantities of the code that we know how to analyze. And this is how you show that exactly that the problem that you care about is inherently related to the security of the toy problem. And what we show is that this toy protocol has a soundness error of this form. This might be like a very annoying expression. But you can look at the first term to be roughly the list size of the code divided by the size of the field which is the same term we showed in the in the in the knowledge soundness analysis.

The attack for this is exceedingly simple. What you do is you start by choosing some f with uh which achieves the maximum list size radius. And by definition this must be must exist. Then you start uh we start the claim by choosing a v and a u which satisfy two properties. So first of all you want to start with an invalid claim. So in particular you want that for every uh code word close to f the claim that you start with is invalid.

And second you want that this V is chosen so that actually the H the you don't have many collisions when you apply this linear transformation to words in the list and turns out that you can do like a very easy averaging argument to show that the there must exist a V which achieves exactly the expression in the bound. Then the attack is just that when V chooses the randomness for the combination, you find some word which is close to the um to the input code word which satisfies the constraint that you care about and turns out that this succeed with probability s over f.

So what does this show? That basically any lower bound on the on list size directly translate to an attack on the Troy problem. And our goal is now to find like the best result or we find the best lower bound that we find on list size and the distance delta star at which we maximize this assessor. Some caveats. So this is a very theoretical attack. You don't actually this is not concretely instantiatable. We don't know how to actually run it in practice. you rely on some of these problem that Alistister was mentioning that are thought to be hard and also it's a very a very generic attack any code that we use will actually fall short of attack I am using no structure v Solomon code at

all any code uh well any linear code will will also satisfy this attack so this has been bit of it and this part here of the computational efficient seems to be common in a lot of other works which exploit proximity gaps. Okay, now we have a framework and our last part result of the paper is just an instantiation. We combine two results. So first is this classical averaging argument by Peter Alias that shows that the list size of the code must have this um must be a list of the size which depends on the size of an arming ball.

This bound already leads to an attack and an attack with success probabilities can of maximize when this error is like one minus row minus log of f. And we notice that we actually can do better in fact by like um this is just a slide I swear. Um in a lot of cases in practice you actually have the fact that the code that you use is an extension code. So is a code that is obtained by taking a code over a base field and then embedding it into an extension field. And in this case we show that that you can actually get a success probability which is maximized when the delta depends on the size of the base of the base field rather than the extension

field. Concretely this chooses for like common parameters around a 9% degradation the security margin and we have tables for like a bunch of settings that we analyzed. So this is what we did. But I think the main contribution is like having a nice toy problem that you can analyze. You can give upper bound and lower bound. It enables you to like make informed decision on what your protocol is about. Thank you. >> Thank you Jako. Uh I guess one question that I have is do you think this toy problem could be used as the basis for the proximity price? And I guess we could rename it to the prize problem >> and then we can look at you know the the

best known attack and the provable security and then kind of paper bit if you will of uncertainty that is cleared off. >> So I think so there are positives I think me and Gal working very hard to find a nice formulation that for the for the price which you know captures a lot of the livveness and soundness properties that we care about. I think this can be part of it. I think we I believe that this is something that could be a good starting point for a lot of the the price discussion.

I also am a bit worried you know because there might be results that come out which don't have a direct impact on the toy on on the price problems let's say but are nonetheless breakthroughs which in my opinion like for example somebody showed at some point that Solomon are at least decodable up to capacity for fields which are maybe are slightly larger than the koala bears that we care about and then somebody later improves that bound slightly by you know by actually applying to the price problem then I think there is like some there will be a situation in which we cannot base the price solely on this type problem.

I think there's it could be like I think it's definitely something that people should try to improve and see whether they can tighten the margin and it will definitely tell when which progress we're doing. But it might be that a more nuance and a more qualitative rather than quantitative like um decision might have to be made. So this is a I don't want to commit myself. I think it's part of the solution but not all of the solution. Justin, I think the toy problem is a great motivation for the problems in the in the prize, for the uh challenges in the prize. So, it's kind of serves more of as a explanation for the community for why the prize is so important.

Got it. Makes sense. And I guess now that I have both of you, uh Dan and Jako, um when do you feel uh you think we'll have uh prize rules ready? Uh, okay. Maybe I'm uh I'm a little worried to commit, but we're hoping we're hoping for sometime in January. >> Okay. Wow. That's sooner than I expected. Amazing. >> Oh, then February. Then February if you're expecting Yeah. [laughter] [gasps] >> Uh, any other questions? Feel free to just unmute or raise your hand.

If not, we're kind of tight on time, so that's great. we can move to the next speaker. Thank you so much Jako. We can move to Olrich uh who will be uh presenting a constructive result uh which is great to have as well. >> So hi thanks for the invitation first of all. Can you hear me loud and clear? >> Yep. All good. >> Okay. Share does work. >> Everything works. >> Okay. So going to talk uh on a note how to generalize the gurus sudanistic code analysis from Ben Sassan and others from a 2020 paper

Ulrich Haböck: A note on Mutual Correlated Agreement

to prove mutual correlated agreement. So this is a note that I I pushed online a couple of weeks ago. I shared it in the course of the last year with a with several people. Um I expect also some some of them are here in the call. So okay let's uh 10 just 10 minutes I want to keep it simple uh let's start correlated agreement uh or what is a correlated agreement theorem so given two words over a domain d with values in a finite field f uh so so what is the theorem or what we want to have is if with notable probability with small probability a random linear

combination. So the probability with respect to Z is close to the code then also U1 you the interle code word U0 U1 is close to the interle code in other words there they're together close to the code there exists a joint agreement set which is sufficiently large over which both U0 and U1 correspond to code wars. [snorts] Okay. Uh I will work and it's it's quite useful uh not just for mutual correlated agreement also for correlated agreement to work with a proxy and the proxy here behind a correlated agreement

equivalently strong is uh is the following colinearity claim or property. So if with notable probability the random linear combination is close to the code then a fraction of them of the approximate polomials are colinear lie on a line in the code. Okay. So that's >> we have a question from the chat from Mikle for which choices of Z >> uh I just say for for notable notable probability so if sufficiently many so let's say if you if for sufficiently

many Z's from the field the random linear combination is closed then a certain fraction I'm not I'm not going here to specify uh it's it's it's it's a big O fraction here. So of one fraction anyways I don't think so so so then a certain fraction of approximates lie on the line this is the theorem so once you have proven this this is this is like the bare metal notion behind correlated agreement so all the correlating agreement theorems I know also the mutual correlated agreement theories go essentially that road so they show they show that a fraction of the approximate code words of the approximate polomials are colinear and from that you are as

good as finished. So this what I call the proxy property. So I will focus more in this talk on on colinearity approximate instead of bottle not correlated agreement on I hope I'm not sure if this answers the questions. I hope it does. Okay. And now much correlated agreement. uh this is a notion that goes back to the war paper and also sailberger who who who who used the notion I think strong correlated agreement in her work uh so so given given you zero and again two words so what's the difference here is a type of uh that's the yeah so you

say except for few there might be some few bad apples but except these if you throw them all the proximate all all the proximates for whenever they exist. So when I talk about except for fuzzy so let's consider the good C's where have proximate but linear combination approximate uh except for fuzzies the approximates of the linear combination stem from proximates of the interl code award. So that that's the statement here. So nothing. So first of all one one direction. So so one one is one observation is obvious. If you have correlated agreements so if you if you take something that's close to that

word uh in in in the interle sense then of course the random linear combination is also agrees on the same set. So it's also close. So one one direction is is easy the other one is just you claim more. So, so every approximate except for view but appos every approximate stem from approximates of the interle word and in terms of more and more geometric picture here is just except for fus you can partition take take all the approximates you have for for all the C's where the where there are close enough polomials take all and they can be partitioned into colinear ones so they're in one set big

picture so in Other words, there exists a collection of lines such that uh except for this few bad uh approximates uh all the others lie on one line, one of these few lines. So this is roughly the picture one could have in mind here. This is why I prefer often to say it's a global or list correlated agreement theorem. Okay. [snorts] So results just an overview uh for general linear codes it's not here maybe I'm missing something here uh I hope I'm mentioning everybody uh so uh yeah results here correlated agreement versus ma

correlated agreement which ma correlated agreement is a much modern notion came up much later so uh yeah in a unique decoding regime up to min distance of the code over three uh this was essentially go paper together with Ross Roth and Seamour. Uh this was then strength. Ah I mentioned also to forget one one of the early work of of of swastikati and uh and then these were generalized to double Johnson bound one minus fourth root of essentially raw of the code let's call it that way and 1.5 Johnson uh in the deep fry paper.

So, so this is like the classical correlated agreement. Can you see my mouse cursor by the way? I'm not sure. >> Yeah, we can. >> Okay. So, that's that's the classical correlated agreement and much and for general linear codes and mutual correlated agreement uh was proven double Johnson bound was it was in one of the early version of of Syberger's work. I think it's the Katan paper [snorts] and uh and even before that almost around the same time uh the Chinese team uh I forgot the name uh which which which had their more global proof of correlated agreement up to 1.5

Johnson. So both of them can be somehow viewed as as as a generalization of this track of work. Okay. And and then for Rol Solomon codes, you can do a bit better use algebraic decoder analysis and uh and yeah the classical BCIPS paper, proximity G paper uh proves it uh for both up to [snorts] uh mean distance over two and the Johnson bound uh that correlated agreement theorem holds. This this was recently just been improved by by by by by the new prox paper swastikan and I and uh afterwards uh yeah in terms of ma correlated agreement the paper that

explicitly defines it that name also proves it for for that for mean distance over two in the UDR and actually I hope I still have few minutes left uh this talk is here about how uh how to prove it for read Solomon goes between mean distance over two up to Johnson. How many minutes left? >> Less than two. >> Okay. So then I skip over our set intersection to game. Okay. So ret.

Okay. Uh so they use uh error correcting decoders algebraic error correcting decoders in the UD it's a bell in in the LDR in the list decoding regime it's a gamudon decoder and the the main idea what to do is you consider because you want to understand uh how the random linear combinations can they be glued together for all these different scenes you in some sense. So they consider the word here where the Z is not yet taken. It's a it's a symbolic variable. So they consider this word as a word in the field of rational

functions over Z in the variable C and and and uh the goal is to infer something about the decoder in that large function field here of rational functions given that we know for certain for certain specific Z's for certain specific Z's the coder succeeds on that specialization of the word. So that's that's the main idea and for the Google Swami Sudan it looks like this.

You I mean if you never saw Sudan decoder you probably won't understand it. Uh so so so you start off setting up and interpolating B varied polomials. I hide here the Z because it's over the large field. Uh uh I'm not sure if it's still displayable. So the Z's are here but but just a bit more uh more hidden. [snorts] So so you start you you you you set up this interpolating variable polomial for that given word over the large field and then and you may always think of it factorized into into irreducibles. So these are the irreducibles. There's some content here which doesn't depend on y. uh and the

thing is now let's look at it for certain good C's we know that the decoder succeeds which means for this good C's uh where we have approximate polomial PC we know that one that that that this PC must belong to one of these irreducibles must be the solution of one of them in Y and uh so and the goal is so so again for each good C approximate belongs to one of the irreducibles and the goal is to show that that that one of the irreducible has a smooth solution a smooth dependencies on on the

Z. So not so it glues together the different Z approximates we see Z and now almost last slide. So what's sufficient and that's really where all the all the all the tough works of the PCIS paper goes into what's sufficient is if the irreducible factor of the Goswamic Sudan P if it if it hosts more than this number of approximates I already took the new bound from from the new paper uh then I really can say that just jumping back here that we that that that then we can

glue glue approximates together and that's good enough for correlated agreement essentially you show yeah okay that's good enough and the funny thing is once you know this and this is how the proof is written in the BCIPS paper once you know this uh the only thing that leaves is the pigeon hole principle so because the sufficient consist consistency talks about one I if one covers sufficiently many approximates then it's it's already uh it it defines the line it defines the cor a correlated agreement approximate uh and for uh and and now given that we have more

of these of these irreducible factor the only thing if you have irreducible factors by the way L is the number of factors here or let's say the Y degree of the go swamisudan interpolant then uh then uh yeah just use the pigeon hole principle blow up that number by number n then you know if you have more than these then at least one of them must have a the initial uh must exceed the initial threshold that's that's what a proof does and already >> three minutes over sorry to interrupt >> um >> we're we're very >> this is really the last slide here there's nothing to say there's just one change just look at pitch and all principle the different way and that's

it. >> Okay, got it. Thank you so much uh or Rick. Uh and I just want to give a heads up actually um a shout out sorry to the uh attendees. We have roughly 100 attendees who have made it one hour and a half through. So congrats to everyone who stayed so far. Um thank you again Rich. Next up, we have uh Mal uh who will be uh making another uh 10-minute presentation. Real the floors uh yours. >> Uh my screen. Give me a second.

>> I think uh has to stop sharing for >> Yeah, I'm I'm trying to find out how that works. >> I think Did I Didn't I stop sharing? >> There you go. I did it for you. Thanks. >> So I believe this is another constructive uh paper which is nice. >> Uh thanks Justin. So uh I'm going to talk about uh a joint work with uh ah sorry yeah I'm going to talk about a joint work with uh praad harsha and sham

Mrinal Kumar: Deterministic list decoding of Reed-Solomon codes

chattery at tifr uh uh and this is going to be a deterministic list decoding algorithm for read solvent codes uh okay so uh this is a very different audience than the typical uh audience that I've given and technical talks in uh so please stop me ask questions at this I I just want to convey the statement and uh that's all so uh so the setting uh is the following uh we are over a finite field f uh we are going to look at read solomon codes uh the dimension of the code will be k + one so we are going to look at degree k polomials univariates and the set of evaluation points that we are going to work with is uh some subset of size n of uh of the field f uh so this is a set Yes.

uh the rate of the code is k + 1 / n. The minimum distance is 1 - k /n. And combinatorally the distance of the code already uh tells us that uh uh this code can be uniquely decoded from error half * n minus k /n and uh can be list decoded uh from error n minus t nk uh by the johnson bound. in terms of algorithmic uh statements uh we have had unique decoders efficient unique decoders for this code uh since the 1960s. Uh so these decoders are deterministic algorithms and they run in time polomial in n and log of the field size uh and require that the agreement

is greater than n plus k /2. Uh there are various versions of this uh starting from the 60s in the list recording regime. Uh so here the we are trying to decode from agreement uh square root NK so match the Johnson bound and here we have uh algorithms of Sudan and Gurusami Sudan from the '90s. Uh and uh their running times uh depend on whether we are looking at the deterministic version of these algorithms or the randomized version. Marina we might be looking at the wrong slide. We're back to the first slide. At least that's what we can see. Uh uh. Uh all right. Uh

let me just try again. Uh >> can you see um my screen? >> Uh it's taking a while to load. Um maybe if you try turning off your camera. I'm not sure if it's an internet issue. >> Uh yes, I can do that. Uh, does that help? >> Okay. Yes, better.

>> All right. Uh, sorry. Uh, so, uh, can I just continue? Uh, is that okay? >> Yeah, go ahead. Yes. >> All right. So, uh, yeah. So, I was talking about list decoding algorithms. So in terms of efficient algorithms uh we know this we know how to do this from algorithms of Sudan and Gurusami Sudan. uh these algorithms require the agreement to be greater than square root nk which is uh the Johnson bound which matches the Johnson bound for the code and uh uh the running time of the algorithms is uh so these algorithms run in time polomial in n and log of the field size uh if we are happy with randomized uh algorithms and if we want them to be deterministic then they run in time polinomial in n

and uh the field size uh the main question uh that we look at in our work uh is to understand if we can list code read solomon codes up to the Johnson bound so match uh the performance of the gurus sudan algorithm uh but we would like to do it deterministically and we would like to still run in time uh polomial in n and log of the field size uh I stumbled across this question a few years ago and I wondered uh why this hasn't been studied uh in in the coding theory literature before And there are good reasons uh why that has been the case. So in typical coding theory settings uh the field size uh for read

solvent codes the field size is typically polomial in n or even n in which case poly poly in n and log f is just uh poly in n and the size of f. Uh so uh uh yeah so there's nothing to be done. Uh the other setting where uh uh where something similar holds is if we are working over finite fields of small characteristic over such fields. Uh we know how to list code deterministically in time polinomial in n and log of the field size. so so this question of uh having a for eight solvent codes uh is

interesting only when the field size is much much larger than n or the characteristic is much much larger than n uh so so uh so so from a coding theoretic perspective especially with respect to applications I think it's of limited interest but uh from a computational algebra perspective uh I is still a very basic technical question uh to understand. Uh the source of randomness the use of randomness in the in these uh list decoding algorithms of Sudan and Gurami Sudan uh are to uh to efficiently factor biariate uh uh polomials over the underlying feed. And these biariate factoring algorithms in turn rely on univariate polinomial factorization over

over the underlying field. And for univariate factorization we uh we uh yeah I mean we we know how to efficiently factor univariate polinomials in with randomness in time polomial in the field size in the in log of the field size and the degree of the polomial. But we don't know deterministic algorithms for this problem even for very very special uh and simple cases like factoring polinomials of the form x square minus a. All right. So our result is uh a polomial in n and log of the field size time deterministic algorithm that list decodes read solomon codes up to the johnson bound uh over all finite fields

f. So this matches the performance of the gurusami sudin uh algorithm but uh is deterministic. and uh our main uh sort of technical observation in this uh is built around the fact that the polinomial factorization instances that show up in these algorithms are uh uh can be solved efficiently. They are special uh and uh they are special in two ways. The first way they are special is that we are trying to factor polomials for which uh we have access to a lot of their zeros. Uh and uh the other uh the other additional structure is that we are looking for very special factors of uh Q in these uh list coding algorithms.

As far as I understand uh this does not seem to provide any general insights towards the complexity of univariate polinomial factorization over finite fields. uh I would be happy to be wrong about that but uh uh to the best of my understanding right now uh that's the case uh so what we have really are two different algorithms uh based on uh what kind of agreement we are looking for uh so if the if you're trying to decode with agreements greater than square root of roo<unk>2kn uh this is what sudin's original paper uh uh worked with here we have a slightly simpler and cleaner algorithm that's based on uh Newton iteration and if you want to decode all

the way up to the Johnson bound which was uh the setting in gami sudin uh then uh we have a slightly more technical algorithm that's based on uh uh this idea of hensel lifting uh that's very widely used in uh the polinomial factorization literature uh uh let me just flash the main technical theorem and uh I'll stop I believe I have a minute Uh so the main technical theorem uh is the following. Uh so suppose we have a biariate polinomial q of xy and a point alpha beta and for this discussion let's assume that q is monic in y. So now let's classify the irreducible factors of uh q into three sets a b and c. uh the set A

consists of irreducible factors uh P of XY such that uh when we substitute X by alpha uh so we get P of alpha Y this is a power of Y minus beta uh the set B consists of uh irreducible factors P of Q such that P of alpha Y is not divisible by Y minus beta and the set C consist of everything else and let Q sub A Q sub B Q sub C be the product of polinomials in the sets A B respectively. Uh then uh our main technical theorem uh gives a deterministic algorithm that takes Q as input and alpha beta as input and it outputs QA QB QC in time which is polinomial in degree and log of the

field size and deterministically and uh so this is sort of the main technical engine uh combined together with some more ideas this is what uh gives the final uh deterministic output uh I'll stop here uh any questions Thank you, Munell. Uh, I guess I'm trying to connect things with uh proximity gaps. So, I guess proximity gaps is related to list decoding and you've made an advancement in in in list decoding up to the Johnson bound. >> I guess a couple questions like one, does your work provide insights potentially beyond the Johnson bound?

Um, and two, are you also interested in working directly on on proximity gaps? Is there a problem that you're looking into? >> Yes. To the second question. Uh, as far as I understand, no to the first question at the moment. Uh, so uh, beyond the Johnson bound, I I'm not sure that this provides any insight at the moment. >> Okay. But are you optimistic that some insights could be found and is that something that you're also looking into? >> Yes, I I think so. I I actually didn't expect that we'll be able to prove this without uh being able to say something about deterministic factoriization, but this turned out to be an easier problem uh than what uh at least I had imagined

earlier. Uh so so maybe there's uh there are things to understand. Yes. >> Okay. Perfect. Uh thank thank you so much again Maral and I see we have Mitri who's ready uh who will be showing a very recent result from just just a few days ago. So the floor is yours Mitri. Um so hi everyone uh I I do mathematics so my my talk is going to be mathematical with without much mentioning the applications or the meaning of this but hopefully I can convey sort of the basic idea of what we found. Uh we found this maybe two days

Dmitry Krachun: Proximity Gaps unpublished research

ago. So this is very recent. Um so let let me describe the setup again. So we we have the proximity gap conjecture which is stated and restated again and again in different forms and we're trying to sort of understand to which extent it holds. So the in essence the proximity gap says that for general codes but we will specifically focus on Solomon codes that you have this code which is a subset of some uh linear space over FQ and the claim is that if you have a line then to check that the

whole line is close to the code for this it is enough to check that sufficiently many points of this line are close to the code. So the general philosophy is that you have rich solomon codes with some parameters and taking some line L once you know that some fraction of its points is delta n close to the code then you know that the whole line is close to the root. Okay. Uh so getting closer to the parameters the original conjecture was that you can actually take the fraction of the points to be polomial on n in n divided by q. So q is the total number of points on a line and the claim

is that it suffices to check that polomally many n points uh are delta n close to the good. Okay. So n here is the size of the domain on which you evaluate your uh polomials of degree at most key. Okay. So what what is delta? So depending on the sort of distance to the code the whole [snorts] picture has different flavor. So you have this unique decodable parameter 1 minus row / two below which everything is understood pretty well and we know that it's actually enough to have linear in n number of points. So epsilon which is linear and n divided by q is already

sufficient. Okay, then you have the the next parameter gap which is up to Johnson's bound which is delta small and 1 / square root of row and there we it is known that the conjecture is true. So it is enough to have the uh epsilon which is polomial n / q and the sort of conjecture is that this is also true up to the capacity regime show. So all the way up to 1 - row. So beyond 1 - row nothing is happening because all points are 1 - row * n close to the code. Okay.

So we we want to bridge the gap and understand either the failure of this conjecture or to prove rigorously this conjecture is in this fusion. Okay. So the basically the the result uh we found is that there are constructions where this conjecture fails when you get close to the capacity. Specifically if you take delta which is ether close to the capacity regime and EA is much smaller than one then the epsilon that you must take should be at least exponential in one one over EA / Q. So in particular if you take ea which is say 1 / log 2 n then you already get something super exponential in n. So the

conjecture that is polomial and n doesn't hold okay so you you kind of need to incorporate the exponential dependence on one over ether. Um okay so maybe at the end I will mention what I think should be true or how to state the conjecture but for now let's briefly look at the at the construction it's very easy and very explicit so we work with a prime field so a field with prime number of elements and then we evaluate the code at the nth root of unity where n is a power of two this is as I understand what is actually done in practice and n is power of two dividing by p minus What we do is we split this subgroup of

the multiplicative group into s cosets where s is again a power of two which divides n. So the size of each coet is going to be m n / s n is equal s * m. Okay. So now our parameter roy is going to be r minus 2 / s. So this is the degree of a polomial we allow divided by the size of the domain and the line that we are going to consider. So the the space fp to the n can be thought of as functions from the domain to fp right and we look at the line which is passing through the point given by a function x

to the rm. So this is above the allowed degree. So the allowed degree is r -2 * m and we are taking a polomial which is of larger degree. So it's not in the code. Okay. And the direction of the line is again given by a next monomial which is x to the r minus 1 * m. Again this is not in the code. Okay. And lambda varies over fp. And the idea is which is was also present in the previous papers that you can take some subset of your domain evaluate the smallest polomial which vanishes on this subset of the domain and then you will get a polomial which has these two terms

the two large terms and all other terms are going to be of degree at most k which will allow you to see that you know this specific point for some specific lambda is going to coincide with some polomial of degree k at most k on some large part of the domain. So the computation is actually easy. You you just take r different cosets you evaluate the polomial which vanishes on the union of this r cosets and it's not hard to see that you have cancellation when you multiply over a given coset and you have this gaps. So the polomial is actually a polomial of x to the m. It has uh leading coefficient one. The next

coefficient is some sum of roots of unity and [clears throat] the rest is going to be in your uh in the code because it's going to have degree at most r - 2 * m which is exactly the parameter row. Okay. So then the the only question that you you need to to be concerned with is to check that when you when you sum 1 plus etc plus r then you actually get many different uh many different values in your field. So this is one one thing to to carefully check in different regimes it has different flavor but if you take a field large enough so roughly speaking you

know that r is like constant time s and so you choose r taples out of s possible roots of unity and essentially you should think that if your field is exponentially large in s then you're going to get almost all of these sums are going to be different. So you're going to have exponentially in as many sums. Okay. So basically the parameters that that you get is your ea is 2 / s. So this you can see you know the the parameter row is r - 2 / s whereas uh you have r / s the for the domain

right for uh sorry for the distance because you have r r cosets where you coincide okay so the distance between 1 minus row and delta is in fact small it is 2 / s but the epsilon must be actually 2 to the s over p roughly it should be exponential in s. Okay. So you can take some specific parameters to to break the conjecture with polinomial. If you take like ether which is 1 / log square n then you can take a any field which is which has size which is at least exponential in ea in 1 / ea sorry and then epsilon is going to be super

polomial on n / p. uh you you can also try to to take a smaller field and aim at proving that not you know all the sums of one plus are distinct but that you actually cover almost all of the field. So probably smaller field you can come up with examples where epsilon is very very close to one but we haven't done this yet. Okay. So I guess that one way to look at this is that in the original conjecture you I think the safe way to phrase the conjecture is that you just fix delta ahead of time and then your bound which is polomial and n / q. So this bound should be

this constant which depend on EA and presumably the actual dependence should be exponential one over EA but this is like a more precise statement but what what I want to stress is that it's still quite unclear what happens between the Johnson bound and capacity regime. What we know is when you get close to the capacity then everything fails spectacularly but maybe below that there is still some hope for this to be true. Okay, I finish here. Perfect. Thank you so much. Um and yeah, I was going to ask how you think you can fix the conjecture. Um and you already shared that. I guess I'm it's great to

see that, you know, mathematicians that are seemingly dis completely disconnected from the blockchain world learned about this. I'm curious how did you learn about uh this conjecture and the desire to solve >> Oh, I I think I think I saw like on Facebook someone like brought >> I mean I I I do have some friends who are like more into like uh blockchain world and stuff. Yeah. Uh I I doubt that this conjecture is sort of known in the math community. I think not really. >> Just to verify, is it only for prime fields or does it work for uh does this apply also to extension fields?

>> I think it should also apply to extension field. I mean the only thing is that you need q minus one to be divisible by n. And the only thing construction uses is that you have a cyclic group in the multiplicative group of the field. >> In the article that made an attack about field f to the m they thought it's very exciting to do this with prime fields. So >> all right yes I think our original thinking was that it has been done kind of for like a fields of characteristic two and so we tried to do in the opposite side for part fields but it works for like extension fields as well >> and is the paper public somewhere? No, we we we initially wrote it like two days ago, so we haven't actually like written up it.

>> Dan, it's in the Telegram group that you're in. >> Oh, perfect. Okay, thanks. >> By the way, if anyone's actively working on these proximity gaps, uh we have a Telegram group of about 40 people. You're more than welcome uh to to to join if you're actively researching. >> great. Thank you so much, Dmitri. And >> so, can I make a a quick comment? Uh So your proposed your proposed fix uh it seems like you wanted to fix uh in advance how close the proximity parameter can reach one minus row and then let this constant O of one depend on uh on on that choice. Right? So I I think this is essentially what we did. I

think this might be broken by Jakamo and uh Antonio's result. Uh in other words, what they showed is that you can break this by uh essentially letting the extension degree get large. So you kind of fix you fix your word that has a large list size, something like that. And then you let Q grow, you you keep the characteristic the same and let the extension degree grow. And this list size sort of won't change. uh and that seems to break that seems to break that conjecture. Uh so I'm I'm not sure that that approach

works thanks to Jako. I had the feeling that their parameters tend to one that like both row tends to one and also delta tend to one but I'm not sure I I should check again but >> we can we can discuss yeah uh yeah I I I'm hoping to get a gathering of of people to to to discuss the the the the the fixed conjecture and what it should be. So definitely you you you can uh join that. Yeah, and I think we'll try and organize this gathering through this Telegram group that I mentioned that if you want to join that uh do let do DM me on Telegram. I'm Justin Drake all lowercase uh all one word. Thank you again Mitri.

Venkat Guruswami: Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes

We're running uh late on time and I want to introduce our next speaker um Venat Guruswami from the Guruswami Sudan paper. Thank you so much for your patience Venat. We're running about 20 minutes late, but uh I I've given a heads up uh to folks and uh I expect many people to to stay an extra 20 minutes. The floor is yours. >> All right. Can people see my slides? >> Okay, great. Uh thanks again for the patience. I know the call has already gone for a while. Uh I only joined midway. Yeah, I'll be talking about positive results which show proximity gaps hold albeit for some variants of read Solomon codes namely something called folded read Solomon codes and also when the evaluation points are

chosen at random and this is joint work with Rohan Goyle who is a PhD student at MIT. Okay. So very quickly some background mostly to set notation. Code alphabet will be sigma length n delta will be relative hamming distance for us and the distance is the usual thing the minimum relative hamming distance between pairs of distinct code words and the rate is uh the usual stuff. Okay. So all this is standard and uh we will be talking about linear and additive codes. So maybe the first thing to slightly point out is that uh we all know what linear codes are which are just a linear subspace over the underlying field and additive code code is also a linear subspace but the alphabet is it it's

it's like a vector code so each symbol is a vector over the base field okay so it could be a FQ linear code but each symbol is FQ to the 10 let's say okay and this comes up in these folded uh breed Solomon codes okay so that's the maybe one small change so uh Um but of course our results on random read Solomon apply to usual read Solomon. So we also have things for linear codes but additive codes come in. So what are proximity gaps? Obviously this audience doesn't need this definition but just to set up some notation and I will only focus on lines. Our results in the paper are worked out for curves um uh and so on. This basically uh says that um if you have a line where there are sufficiently many points close to the

code then in fact uh all points on the line are close to the code. Okay. And pictorially so you have this line here where a few points are close then all are close and this delta is the proximity parameter epsilon is the error. Hopefully these are standard notations. Now uh a code has delta epsilon correlated agreement if basically under the same premise not only is the entire um all the points on the line close to the code but in fact they are close to a line of code words. So namely there are there's exactly what this red line thinks. So you take a C not and C1 and take the line through them and that entire line is actually close to this.

Okay. So this is a more geometric picture. So you kind of know that the proximity arises for this geometric reason. Again, standard definition. Please stop me if something I'm saying is not clear. Uh but so far same thing, right? So it's just a slightly this is a stronger notion because this of course implies this because every one of these points on this red line is a code word being a line of code. Great. Um read Solomon and friends. We all know what Reed Solomon codes are. So you have an evaluation points. Take degree k minus one polinomials evaluated at n points. The alphas are the evaluation points. Usual stuff. Now a standard read solomon code has arbitrary evaluation points or maybe you pick it

from some nice subgroup. So you can do some uh good algebraic fft and things like that. For a random read solomon code you simply take a field a little bit larger maybe but then you just sample n random points from it. Okay. So you pick the evaluation points uniformly at random and there is also folded read Solomon codes which are like read Solomon codes except you essentially bundle every consecutive for example if you order these things as alpha alpha gamma and so on for some primitive element literally take every s symbols and bundle them together as one mega symbol one vectors okay so the iat symbol looks like this the exact definitions are not important uh because I won't get to the details here uh but this is what a folder read

solomon code is it's essentially very close to a uh read solomon code and why do we do this for list decoding reasons we'll come to in a second okay so what is known about proximity gaps for read solomon codes itself so uh by these beautiful results uh of benasan and others from 2010 this year we know that they have proximity gaps for proximity up to the johnson radius and the error parameter is going to be small as long as now with the new result q is linear in n and and these are based on list decoding algorithms for Solomon codes as we saw now one predicament is that for general read Solomon codes we don't have better list decoding results and and therefore um you know it's been hard to push beyond this Johnson radius and in

fact a couple of these recent results GRE Stewart and and the the same paper show that if you want to make the error really tiny then there is a reverse connection you have to do list decoding for approximity gaps. uh okay maybe for slightly higher errors you can get away without list decoding but somehow the feeling is you need to list decode and we don't know how to list decode read Solomon codes and what is list decoding um so a code is supposed is set to be delta LS decodable if no matter what point you take in a ball of radius delta around it you won't have more than L code wordss compared to usual decoding where you want to correct uniquely you will say that if I have a code of

distance delta in any ball of radius delta by two I of course have a only unique code word but as you stretch the ball bigger you can get more code words and that's listic coding and another way to say it slightly goofy way to say it but you'll see why in a few slides is that if you take any L+1 code words close to some center some two must be equal you can't have L+1 distinct code words okay and uh so that's just the contraositive of this and it's easy to see that if you have a code of radar you cannot list decode beyond 1 minus R your list size must grow exponentially then so it's not possible and I should say that your goal here is to keep L kind of small otherwise the problem is not interesting but the surprising thing is

that this is a very simple limit but you can actually approach that limit so the list decoding capacity is actually 1 - r you can actually correct all the way up to 1 - r which is twice what you can do with unique decoding even with the best codes so in some sense from an error correction standpoint list decoding is beneficial because it allows you to correct 2x errors. Now, as I said before, list decoding beyond Johnson is not known for read Solomon. What about other codes? And um about 20 years ago, we showed that this folded variant of read Solomon codes indeed allow you to achieve list decoding capacity. So, a small twist allows you to go all the way to the list decoding capacity. And there have been lot of follow-ups to this and improvements on the list size parameter

which is an important thing as was mentioned in a previous talk. and culminating in this beautiful result of Chen and Zang from last year which say says that these codes and in a more general class of subspace design codes um are actually list decodable up to capacity with an optimal list size this one over epsilon I said the list size should be small and they said it's as small as it could be for these nice codes okay which is a very very nice uh result and a similar result was also earlier shown um in a pair of works um and we just published this jointly in a journal this year um that this also holds for random read Solomon codes and random linear codes. So at least we do know codes which are list decodable up to capacity with the best list size.

It's just that they are not read solomon. Very good. Okay. All this is about list decoding and this is about proximity gaps. And I guess our main result is that can translate these capacity achieving list decoding results all of the known ones so far um to proximity gaps. So essentially basically all the codes we know decodable capac capacity have proximity gaps up to this 1 minus r bound with an error parameter like this which another way you state is that the field size can be linear in n and this holds for proximity gaps and correlated agreement and also for mutual correlated agreement. Okay. Um and and this class of codes includes as I said

older read solomon codes. The amount you fold needs to depend on how close you get to this 1 minus r bound. So that's the the tradeoff here. And it also for what are called multiplicity code. It's very simple. Instead of when you take a polomial instead of only giving its values you give it the values of the polomial and its derivatives at every point. This is perhaps more natural than folder read solomon even. So those also have this property. So your evaluation points can be nicely structured. Um but uh but you just have to include the derivatives value uh valuation as well.

And this also >> question from the chat here. >> Okay, I'm not monitoring. Yeah, >> almost all codes here. >> Yeah, maybe I should really say uh everything I know to be list decodable. I just maybe I was just hedging uh a little bit. But all the positive results we know um I think at this point um are translated. But but I think it's important to point out we don't do it by in a blackbox way. That's why I put this all we basically take these results and in each case we manage to get proximity gaps but there could be some other result known which is not covered. Oh actually you know what actually I take it back. Um um there are these variants of algebraic geometric codes which are also distable to up to capacity and uh those uh we don't know how to get

proximity gap. So that's what almost qualifies. Okay. Okay. So another way to say it is that these this list here is almost many of the codes which are list decodable up to capacity. So we can also do some random expander based codes. I won't focus on it here. And for this audience perhaps most interesting is the random read solomment codes. So if your field is large enough and the length is large enough this holds just for plain old read solomon but the evaluation points I can't tell you what they are. If you sample them randomly you are in luck. Okay. [snorts] Uh that's the result. So hopefully I I want to at least get the result statement clear. So essentially we get proximity gaps up to the optimal bound for these classes of codes. Hopefully

the result is clear. If not, good time to ask before I move on to some techniques. >> Yeah, pretty clear. >> Pretty clear. Great. All right. So techniques um I I guess a crucial notion here uh uh which actually already was mentioned in Olri's talk also is uh this concept of line decoding um and this very much smells like correlated or mutual correlated agreement but we somehow ferret it out and we use that to do all our results which made our life um nicer. Um so what is informally a code is sorry a bunch of parameters here a code is delta line decodable if the following picture happens. If you take

any a code words which are all close to some line then among themselves you have many a smaller number b will be smaller than a which are themselves colinear okay so that's uh somehow the the idea so if I take this uh this red line here and there are many uh code words these uh which are close to it then in fact uh there are many uh on on a line actually the red are the sorry the so the red line is the code wordss line um and so if any a code words close to a line at least b of them themselves will lie on a line and there are extensions to curve decoding and so on I'll define this formally in a second and the nice way to

think about it is that list decoding says there aren't too many close by code words to a single point line decoding says there aren't too many non-olinear code words close to a line so it's some sort of a degree 1 version of list decoding. Okay. And and and this is also why I stated the previous thing like that. So here we are saying that if there are any if there are many code words close to a line enough of them are colinear much like for list decoding if there are many code words close to a point some two must be identical. Okay which is like a degree to zero constraint. So this is the formal definition. A code C is delta A listicable if for any A points on a line which are close to some code words.

Those code words themselves at least B of them lie on a line. Okay. So you take any A points any code words close to A points on the line among them there are B of them which themselves are on some line through C and C. Okay. And this is somehow in various forms implicit in I think many works and uh it's also the crucial notion driving our work. Okay. So with this actually our proximity gaps breaks down into very nice modular connections. So the first thing and I have a slide on this if I have time I'll show it. It's very simple. If I have if I get enough points on a line, if I have delta a n line

decodability where n is the length of the code, then I immediately get correlated agreement. Okay. So essentially to prove correlated agreement with a exceptions, uh I just need to find n points on a line amongst any a which are close to a line. Okay, this is good. Getting n points colinear may be difficult and then we give a simple combinatorial reduction to say that actually it suffices to get three points on a line which is the first non-trivial thing right some degeneracy and that we can amplify to getting any number of points in the line by giving up a little bit in the exception parameter okay so this a becomes a squared and the final thing is that and this is

important for us to get really good error parameters if we combine line decodability with normal list decodability then we actually get correlated agreement and the difference between these two is that now the the error parameter is much better right and uh and the nice thing is this is each of these is very simple combinatorial uh uh reductions in fact I think the union of all these proofs maybe two pages in our paper but with all this all that we have to do is to get three points on a line and then by these lemmas you're Okay. So that's the the goal. Okay. So now I'll talk a little bit about subspace. Uh um oh there is I'm not monitoring your chat but if there are

any questions just feel free to unmute and ask. Also >> we do have people that are surprised that the the result holds on for for random read element codes. >> Oh okay good. >> Was it a surprise to you? >> Uh yeah I guess in some sense. Yes. Yeah. I mean we've yeah it was it was also you'll see in a uh in a bit it was also a bit serendipitous that certain results came out which uh translated uh results from subspace designs to uh random read Solomon just a few weeks before and as we were working on this so it was good timing for us so if I take the union with that result then sure it's surprising but >> okay I'll talk about subspace design

codes because that's what we were actually uh working on um in trying to extend some list decoding things. So these additive codes as I said each symbol is a vector. So each coordinate itself is high dimensional and we get more structure out of it and this definition is a bit technical but um you don't need to understand it but the point is an additive code is a subspace design. If the following holds, if I take any lowdimensional uh space of uh code words, you know, things like lines or low dimensional subspace, then what happens is that if I in that subspace, I look at those code words which are zero on the ayat coordinate, that's going to drop the dimension of the subspace perhaps. And the subspace design says that that happens very nicely on the average. when I take a subspace and I

set each coordinate to zero um the average dimension drops by a factor of almost the rate which is the best it can drop okay it may not be clear why this is the the correct notion I don't have you know this talk you know it's not long enough to convey that but this is the key uh common notion property of folded read solomon codes so swastiki kopati and I showed u that folded read solomon and multiplicity codes are subspace designs and these recent line of works have brought to the four that this subspace design property is really the core of lot of list decoding results and this nice paper of bracken shake at all showed that these folded random linear codes are also subspace design.

So um these arise in many places and how are subspace designs used just a bit of a schematic for list decoding uh with Carol Wang we showed for folder read solomon codes and also holds for subspace design codes is that if I take the proximal code words to a point they must belong to a low dimensional subspace and then there has been a very nice line of work uh listed here uh which showed that in a low dimensional subspace you cannot have too many code words so essentially showed list decoding bounds for lowdimensional subspaces and now for line decoding we literally translate both these steps. So first we show that the code words which are close to a given line as opposed to a point also lie in a low dimensional

space and this pretty much follows from the definition of subspace designs and then following the second step we only then have to prove line decodability for lowdimensional subspaces because we know that all code words of interest to us are pinned down to a low dimensional subspace. Okay. And that's how we prove things for subspace designs. But of course, you know, people are surprised about the random read Solomon result. How do we do that? Okay. So for that there's been a beautiful line of work on what are called local properties. I won't define them formally. But essentially these are properties about small sets of code words like for example a small list lying in a small bot. And there has been a beautiful line of work trying to understand when local properties hold

for random codes of various forms. And uh a remarkable result here by Levi Moshe Shagrayav which appeared in Fox this year uh just earlier this week I guess showed that all LCL properties of random linear codes also hold for random read Solomon codes. So if you want to tame RAM random read Solomon you just have to tame random linear which sounds much easier because there is more randomness. And then this work of brackenshal and this was the serendipitous thing which I was mentioning said that if I prove a local property for a subspace design code like a fixed code like or or all subspace design codes like folded solomon codes then they also hold for random linear codes and then there's one

more result on expander codes which I'll skip but just even putting the first two things together we have this nice uh compiler essentially saying that if we can focus on local properties and we improved for subspace design codes then we have it for random read Solomon and that's essentially how we made the connection to random read Solomon but of course this requires casting this line decodability as a local property which unfortunately does not seem easy or even true as is but we make a variant of line decodability which uh essentially line decoding is some sort of degeneracy right it says three points are on line and we essentially replace that by

something we call VD decoding uh which then fits into the local um um properties framework and uh and then and we and these are up to some small loss in parameters equivalent. So then we show V decoding for subspace design codes as I indicated earlier and then by these beautiful body of results we have them for random read solment as well. Okay. So some work goes into casting line decoding as an LCL property. But that's really what we do. Okay. So I'm almost out of time. So this is um our result again. We get proximity gap all the way to capacity for folded read Solomon and random read Solomon.

I've just stated the result again. I had a couple of slides on um techniques but I'm going to skip them. uh but I will just say that the way we prove line decoding leverages some very nice recent progress on list decoding algorithms and how you prune uh a subspace which contains the list to actually find the list. Okay, and this is the the entire thing and I should say that each of the steps we have is very simple and just pretty short and I mentioned that line decoding implies correlated agreement that was implicit in previous works and if you want the full proof is in this slide. Okay. So, um really and there's there's not too much going on and perhaps one novel part in our thing is

that we take line decoding plus list decoding to get improve the error in uh correlated agreement and this is also not very hard um and this goes by allowing some proximity loss in an intermediate step and then leveraging the listic coding to uh to improve parameters and it's also pretty short. Okay, so these three are the ingredients. Okay, so that's I think I'll close uh more or less on time. So folded and random read Solomon codes are optimal proximity gaps over linear size fields and this is enabled by this clean abstraction of line decoding extending list decoding algorithms which have been found to line decoding by suitable subspace pruning and using

these nice results to translate from subspace designs to random read Solomon codes by carefully casting line decoding within the framework of these local properties. Okay. So, I think I'll stop there. >> Thank you, Vancat. What a great way to end. Uh, any questions from the audience? >> Yeah, I have a question if I may. >> Go ahead. >> Yes, of course. >> It's a bit of a technical question, but in the definition of the folded read Solomon code, >> you have this like geometric progressions on which we >> Yes. Yes. Yeah.

>> The gamma in the progression >> Mhm. It needs to be a generator still because >> it doesn't have to be a generator. It has to have large order. Let me see >> because I I I saw that like in the reference that you use it is written that gam is generator but now you drop the this condition and so because somehow you I mean you you you can't let the domain to be a subgroup of the of the multiplicative group, right? or >> so actually yeah you're absolutely right the original work with uh Atri Rudra where we proved these achieved capacity that used a different proof and there it was important that gamma was um was a

generator because it required that certain polinomial was irreducible >> okay >> but there was this later linear algebraic approach to decode um and that only required that gamma has large order I believe the order just needs to be more than k >> okay so you you need large order of large gamma has to have large order Okay, fair enough. >> So maybe a question for me like uh we saw like we have random um code achieving list the coding up to capacity >> with a probability and uh also having mutual corregment up to capacity with a probability. Mhm.

>> Is there anything known about the correlation like of these two probabilities? Like if I sample like uh if I sample a random code, is it possible I get one property not the other or am I >> I that's a great question. Yeah, I think both of these follow the same framework. So the probability bounds you get will depend on like how local the parameter is and so on. I suspect that um the property here is a bit more complicated. Um so at least the tail bounds we get may be weaker for uh proximity gaps. And it's important to note that we are not saying that list decoding implies proximity gaps. So you can certainly get

both combinations. You can actually uh I don't know if you can get proximity gaps. You can probably even get proximity gaps and not list decoding. Get list decoding and not proximity gaps. And of course with high probability you'll have both because so >> and what's your intuition like you don't get a black box result here you have to use the the actual properties of the of the code the subspace designs like do you believe there's uh something more that we can be said about the black port relation of these two notions or >> just at some points when we were working on it we even thought with some exponential loss in this epsilon right like you know we might even get some blackbox notion but those turned out to be misguided. Um so I'm not sure I don't

think it's ruled out but uh but at least currently um essentially you're decoding many code words and you have to correlate them in some way and that seems hard if you only assume a blackbox list decoding statement, right? >> maybe stronger thing like release recoverability could help or do you think it's uh >> uh yeah in actually in yeah in a way list recoverability played a crucial role in this genesis because essentially a line is uh in each point you're list recovering a set but it has a low dimension thing. So so list recovery did inspire some of these things. Um, so you're right. I mean, in some sense,

this line decoding was an abstraction of the kind of list recovery guarantee you would need to then get proximity gaps. So, but yeah, so it's blackbox around line decoding, but you could say you could argue whether line decoding is essentially the same as MCA or not. So, >> I think thank you. But again, did you did you say that you have an explicit example of a code that's list decodable but does not, but proximity gaps are false? >> Oh, no, no, no, I'm just I was just answering Jookcom's question that you know these are both probability results. So it's the sample you know the success events could be you know each could happen and not the other. So >> but do we do we do do you know of an example that's list decodable but proximity gaps are false?

>> Uh no no I don't. Yeah. So yeah I was just saying it's possible that uh that that >> Dan I thought there was a >> that's not ruled out. No neither event dominates. Yeah is what I was saying. Dan, I think there's the, you know, not for the random code, but there is that um example in the deep fry paper, the the 1.5 Johnson we we looked at some time ago, I think. >> Ben, when you when you zoom out, um the the Snock industry has basically gone all in or essentially all in on uh on read read Solomon codes. I'm wondering if if you as a coding theory expert that knows the whole zoo of of of codes could

basically help design new snarks as opposed to us trying to improve our understanding of of red solment codes. So I guess I'm wondering like do you think there's an opportunity to use folded resolment codes or random resolment codes to to design new snarks and is that something you're interested in? Yeah, I I definitely yeah I yeah one thing is yeah I don't know the full practical parameter space that well um but one thing in in a way folder read solomment quotes just compresses thing I mean I I I assume you would want to keep the same proof size and query complexity and those are very paramount right so so a priority I don't see why I mean I think

use it attempting to use folder read solomon into some of these things seems at least worth a try, but I I I don't know enough of the design space to have a sense if you know that is something yeah a no-go or maybe worth at least spending some time on. Maybe I can comment a little bit on that because I've been thinking about this. The the kind of annoying thing that happen when you use folder with Solomon code in some of the protocols I was looking at is that going from like Johnson bound to capacity is around a wet saving queries which you can also achieve by just increasing the rate by a factor of by a factor of um two. Mhm.

>> And so when you run the numbers and you look at the proof size resulting from like the folded read Solomon code and um and um usually it turns out that just using a bigger rate is somewhat better for like your uh for like your um your your argument system. >> I see. But I guess then you can only check proximity to close. I mean your proximity radius obviously will drop right as the rate increases. And that's okay. Yeah, exactly. saying it's probably still all right because at the end what I care about really is the number of queries and if I do 128 or um or you know with rate one quarter 128 with rate 1/2 the important thing you

can always trade off prover time with um with um um yeah you can always verify time with query complexity and some and with resolon codes the the is good enough that actually is not that is not that But it might also be that I miscalculated something. So this I'm also going to double check again. >> Res is asking what about the encoding cost for folded read Solomon codes. >> Oh yeah. Uh I guess it's same as encoding cost of read Solomon, right?

Because you just encode it and uh bundle the points. And unlike random read Solomon, you can pick your evaluation points to have any nice FFT conducive structure as you would like. So, so encoding complexity is the same. Yeah. And Venat, in light of the the recent attacks on um on the conjectures and and and the evolution of the conjectures, like do you feel kind of bullish or bearish on um kind of new insights that at least partially replicate the results on random resolment codes to non-random resolment codes.

>> Yeah, I think that's a great direction. I think uh I mean clearly we know these things exist in abundance. So finding an explicit evaluation point where you can beat uh Johnson is you know a very fascinating question and uh and I think this has come up in various things as well. Maybe looking for special fields like prime fields and special evaluation points maybe there is uh there is something the trouble is that we don't have a good pseudo random criteria for what these evaluation points should be. So if we gave some crazy criteria saying that if these alpha satisfy this then you will have this property then presumably you can you know throw a lot of number theory at it or other things to try to find these in some prime fields and we don't have that understanding yet. So so perhaps

inspecting these random read Solomon proofs to sort of see really what they're using may be a good direction. >> Okay. Well, I don't see any more questions and we've been at it for two and a half hours. Thank you so much to all the speakers. Thank you, Vancat. And thank you to all the attendees who made it this far. Have a great day. Yeah. >> Bye, everyone. Thanks. Bye.