Ethproofs Call #6: Proximity Gaps

Transcript

Justin Drake: Intro

KVM. >> Okay, we're going to get started in two minutes. We have 74 people, 75 people on the call. Uh, welcome Jakamo, Alp, Alim, Zandro, >> Ango, Antoine, lots of new names. That's fantastic. >> Welcome everyone. Make your verify sick copy paste repame you recursive dog please pause so deep Santa Claus lost back sweating chain hall drama verify slower than your grandmama prom

looking shaky man tweet but you can't even verify proof laughs [music] while another zkm >> every VC got a VM they all the same V code fame change [singing] Alexa testing spin figure boot up stall your mainet fake Okay, welcome everyone. We're going to

get started in about 15 seconds. You can't even verify proof lab. I drop entropy like E40 slang. You prove or crash. That's bang bang bang. Claim your plunk [music] but you just confused. Circuit sloppy benchmarks bruised back looking janky like [music] scraper paint. Nah, it faint in the shell. crying frying tweeting out swing deceased proof labm.

>> Okay. Uh welcome everyone. We have over 100 people on the call. We're expecting more uh folks to uh come in. So uh this is EF proofs uh call number six. If you're new to EF proofs, it's an initiative to try and accelerate the advent of proofs uh snarks on Ethereum L1. Today's call is dedicated to proximity gaps which goes to the the foundations uh the mathematical foundations of u modern hashbased knocks and uh we have a telegram group e if proofs community uh with a with a QR code if you'd like to join this this group and that's a way to um register for future calls.

So, uh, so far we've had, uh, six six calls, uh, on all sorts of of of great topics. And just to give you a sense for what's coming next, we're going to have a call on guest programs, former verification, and alternatives, uh, to risk 5. So today, uh, we're going to be discussing proximity gaps, specifically these three papers. Um, they came, uh, over the last few days. Um it's been a a great uh treat to have so many uh strong papers come coming out uh all one next to the to the other and uh we're also going to be discussing the

the proximity prize uh and I believe uh both Dan and Jako are on on this call uh today and above and beyond the papers that we're going to be discussing u there's just a flurry of papers uh related to proximity gaps um that have uh landed in the last few days. So over the course of six days, I believe we've had six papers. So that's one paper per day uh which is pretty amazing. And um I'm hoping that maybe we can organize uh if proofs call 6B uh where we can discuss some of these uh other other papers on on the topic.

I just want to give uh a few uh quick updates and then we can move on to the the content. So one uh update is that we've had a uh workshop uh last month uh in in in Cambridge dedicated to postquantum cryptography. It's been a a massive success. There's a lot of content that you can find on the internet, something like 25 hours of content uh on postquantum cryptography. Uh and the the efforts, the engineering efforts that we're uh in investing to to get this stuff on on mainet. Um and it was such a success that we are going to organize it again uh next year. Uh so we've already pre-booked the the venue.

Um, another quick update is that this uh ZKVM tracker is getting greener and greener every single week. Um, so the top ZKVMs are those that have either integrated with e- proofs or are expected to integrate with e- proofs later this year. Um, and the the things that are highlighted in in yellow are are new developments. So uh, airbender is being proofed by matalabs and ferma. OpenVM has also been integrated to EF proofs with Axiom as the prover. We have uh Zilkworm uh which is using SP1 Turbo.

Uh SP turbo GPU acceleration is now source available if you want to have a a look at what they're doing. Um and uh we also have SP hyper cube verifier that is now uh dual licensed Apache MIT. We have a new ZKVM that I just learned about uh yesterday called Toka uh Mac. Um and we have uh a couple ZKVMs that are still in development by a a couple uh projects that uh disclosed this recently. And we also have two redacted ZKVMs uh in stealth uh both of which are um building latisbased uh ZKVM. So super exciting uh

development here with a new flavor of of ZKVMS. Okay. And the second update I wanted to share is that in a couple weeks on November 22nd, if you happen to be in Argentina for death connect, we have EF proofs day. So you can find more information on eroof.day or uh luma_day. Um we have um uh a very exciting demo that we'll be doing uh on E proofs day specifically uh we'll be running a validator node uh verifying ZKVM proofs and we'll be turning off the execution layer client um and running only on a on a consensus

layer client and we'll have multiple provers proving every single mainet L1 block uh in in in real time using a very modest number of of GPUs in the grand scheme of things. And uh another piece of of great news is that Farah um has joined the FM Foundation and uh she is now leading a a new team within the FM foundation called the the ER team. So uh congrats and welcome to to Farah. So this is today's agenda. Um we're going to have a few ecosystem updates before the the hardcore presentations.

Um and then we'll have uh 1.5 hours of of presentation. So in total we'll try and wrap everything up within within 2 minutes. So we have a lot of content. Without further ado, I'd like to invite uh Justin Faylor to talk about uh Jolt streaming. Uh are you here Justin? If not, we will move to Alan from uh Prism. Sorry. Uh Pico Prism.

Alan Li: Pico Prism

>> Hi. >> Uh can you see uh my screen? >> Yes. Okay. All right. Cool. >> Yeah. Uh so I'll start. Uh so hi everyone. This is Alan from Brevis. Uh so I'm I'm pretty honored to share with you the journey to uh Ethereum real time proving uh here a little bit of our journey here. [clears throat] Uh so back in the day of uh at the beginning of this year we just released our first generation of Pico which is a modern and performance ZKVM and after that we have been like moving all these kind of CPU computations onto GPU. So there's a bunch of thing that we have been doing right here. uh so moving the heavy lifting parts uh since we have been building on the on the ponty 3

there's like PCS commit open quotient computation etc all these computation are pretty heavy and we move them all to the GPU so that for each of the phase we have we have GPU proving while still the emulation the trace generation is on CPU but at uh but at this time the the single GPU is already pretty performant already pretty performant and has no idle time. And then next step would be to move that to the to the multiGPU version. So this is our second generation. It's the first GPU boosted version and we link it to the to the to the E groups at that time.

[clears throat] And then going from single GPU to multiGPUs. What we did is to just try to find a better coordination between multiple GPUs and CPUs. And later we have figured out that trace generation is actually one of the bottlenecks there. So we move that all of them to the GPU to first further boosting the the efficiency. Um and then at the end of the day the workload is almost is almost achieved at a perfect balance. By perfect balance I mean this this is a machine of like eight GPUs uh with 124 CPUs and then either adding more CPUs or adding more GPUs will not further boost the whole performance. So

that's what we call that achieving the perfect balance here. So they do have a pretty good balance of the workloads between CPU and GPU and they communicated pretty nicely. So that we were able to achieve pretty good results there. So [clears throat] there comes the pico prism which is our third generation which is essentially unleashing the power of computing clusters. So currently we are still working on the single machine but now we since we are aiming for uh real-time proving with accessible consumer grade hardware uh we went with the uh with the subblock solution which is essentially dividing the one Ethereum block into several several sublocks and pring them by event conquer and then uh at that

time like we have eight machines in total each of them have like eight GPUs And we last seven of them to prove seven subblocks and one of them to do the aggregation. Uh so that we have a pretty good divide and conquer scenario and then uh all things uh they are most of the heavy lifting part is already moved to GPU. So it's still a pretty good balance. Uh so that's the results that we are showing here. um brewing the etherum blocks on September 1st. In total, there will be 7,200 blocks there and then on average it is nu 6.9 seconds uh on average uh to prove all the blocks and then uh 99% six Ethereum blocks are under proved under 12 seconds and about

97% of them uh under 10 seconds. So it's uh is the standard of the of the of the real-time proving. So several observations and what's next uh very quick real quick. So doing this kind of sublocking are invariously paralyzable. So that is to say the pico prism will be able to prove arbitrarily large blocks with minor overhead. Uh so performance will stay almost unchanged. So we will still expect the real-time proving as long as we have enough machine for doing the doing the proving for larger blocks and then the emulation uh becomes a new bottleneck. So we are still we are already on the way to do the optimization and we believe that currently what where we are is that we use a single machine which is eight time

uh 85 5090 machine to produce Ethereum block proofs with average time of 14 to 50 seconds which is already pretty close to the to the real-time proving and then we expect that after the optimization of the emulation like maybe like in two to three months we will be able to achieve the real uh real real time proving with 16 uh 1590 clusters uh that is uh uh yeah well like almost all the blocks will be proven under 10 seconds. So uh so that's the performance uh uh for foreseeable future in the in the foreseeable future and then finally we are constructing our pro network. So please stay tuned. That's all. Thank you.

>> Amazing. Thank you Alan. Uh I don't see any questions in the chat or any raised hands. So I'll just ask one very quick question. Uh what is your current emulation speed and uh what are you trying to to target? >> Uh so the current emulation speed is about 10 million cycles and then we expect to uh to do at least five volts uh uh increase. So that that will be uh that will be like 50 uh at least uh so yeah so that's our our target. Yeah.

>> Per second. So 50 megahertz. Is that right? >> Yeah. >> Okay, got it. Cool. Um, yeah, I know that some teams have gone much much higher results, so it makes sense that this is the bottleneck, but otherwise these numbers are are amazing. >> Uh, next up, we have Michael uh from Airbender. If not, we'll move on to Reza from Wholesome. Uh hello, can you hear me?

Reza Hasanzadeh: Wholesum updates

>> Yes. Hi Raza. >> Uh let me share my screen. Hi. Okay. So the idea is to prove Ethereum blocks in a P2P setting. A single client node is responsible for fetching block data and preparing the stage for proving. Uh there is also a set of proven nodes whose task is to generate proofs. We use lip P2P for network formation and node communication. RSP sub block and its block division logic is used as the ZKVM.

Currently we average at 1 MHz on a single RTX490 which is obviously not really enough for realtime proving. Here proving follows a two-step sequential process. First we have to prove n sublock guests and then push the generated proofs into the aggregation guest and obtain the final block proof. We plan to only serve the Ethereum network. And this means that while waiting for the aggregation gifts to finish up, n minus one prover nodes are idle. To counter this inefficiency, we

are working on a plan that starts proving subblock guests for another ZKVM. With this we believe that we can effectively obtain 1 half proofs per block. Okay, this is it. Thank you for your attention ladies and gentlemen. >> Amazing. Uh thank you Raza and great to hear uh that we have uh such a project uh I guess from from Iran I believe. Uh so covering many places in the world. Um and we have a question in the chat from or asking how can we have embarrassing embarrassingly parallel proving uh and

the answer has to do with with subblocks uh which is this idea of taking a big block you you chunk it into smaller blocks at transaction boundaries uh and in Fusaka which is the next uh hard fork coming in December 3rd we're going to have a 16 million um gas limit per transaction. Okay. Uh Resa if you'd like to uh stop sharing your screen. >> Uh we can move to Vanish uh who will share updates about Ferma. >> I think I need the request approved to Okay. Uh I think now I can do it.

Vanishree Rao: Fermah updates

Cool. Um hey everybody my name is Van Shri founder of FMA um I wanted to give a quick update on FMA generating air bender proofs for ETH proofs and our goal here is three-fold um one is um in line with what uh the goal of ETH proofs itself is which is bringing diversity of proof systems uh to e proofs um and the second one is to showcase a specific strength of forma and in this case um fast integration of any proof system and um um to contribute to Zikas Singh which is for mass one of uh key uh projects um that we have partnered with um with respect to uh bringing

diversity of proof systems and uh to showcase um our ability to integrate any proof system quickly. Um we started with ris zero uh which is a fairly complex proof system in the sense that it uh has its own uh proer network uh with its own um um storage layer for example. Um there there is a whole uh stack uh and we quickly integrated uh risk zero without using their stack at all. Um this is how we started uh integrating with um this this is how we started uh generating proofs for ETH proofs. And secondly we just recently as I said uh started generating air vendor proofs um

and this is a generous quote from um our friends at um uh CK Sync. They um yeah um basically our ability is to um our our tooling helps us integrate any given proof system with any um uh complex workflow of uh different kinds of um workflow steps very easily. And uh thirdly, our goal of course was so this this I want to also highlight the amazing work done by ZKYNC.

Airbender has phenomenal uh proving times. Um and along the way of because of our continued uh partnership with ZKYNC, our goal also was to help them reach their goal. Um and we contributed in in the best way we can and uh we pretty much uh behaved as uh one of their uh team members and um uh contributed things like um uh fixes that were uh uh that went upstream um etc. Um this is my update. Thank you so much.

>> Okay, thank you so much uh Vanushri. Uh again, feel free to ask questions in the chat, raise your hand, or even just unmute and uh ask your question. Uh if if not, we're going to move in the interest of time uh Jeremy about running Linux on a ZKVM. Nice. Literally running Linux. I think you you might want to unmute.

Jeremy Bruestle: RISC Zero running Linux

>> Thank you. >> Apologies [laughter] about that. Uh yeah. So um anyway uh what I wanted to show is basically we have a demo here of running uh Linux on the on the ZKVM. Um so what you're seeing here is actually a real Linux kernel booting. Um the basically what we've done is we've modified the ZKVM adding the support for risk 5S mode. um which effectively allows there to be a separation between a user mode and a supervisor mode and a full MMU that contains virtualized memory. Um so by extending the sort of proportion of risk 5 that we uh are able

to prove we actually are able to boot Linux and actually log in here. Um what this does is it opens up uh sorry um it opens up the possibility of running multiple processes uh as you can see here um you know it it provides basically full support for a very large number of different uh types of software uh you know like I think in terms of producing proofs for ETH proofs um you know I think state transition functions don't need an entire operating system usually although this will open up the ability to run more managed languages very easily. Um, but but what we're moving toward is for a lot of other use cases

this idea that the ZKVM isn't just executing a single executable, but actually this idea that the ZKVM can be thought of as like a similar to a normal VM where you actually uh like a Docker container, right? You actually give the ZKVM an entire container to operate on. Um we're also like working on for example a block device that's a Merkelized block device. Um and so on. Uh and just just as a heads up right now what you're seeing is we have fully completed all of the witness generation. Uh the prover is largely complete. There's a couple of additional constraints to get done. So this isn't like fully fully complete yet. Um but it's uh we're making excellent progress and it will be uh we will have this in our next version of the circuit that we

release. we will have full support for S mode and we will have full support for, you know, a working Linux system. So, um I think that's pretty much it. It's mostly just a cool tech demo largely. Uh but but we're very excited about uh about this. And in terms of performance, you know, what you're seeing, I we should be able to prove live at the speeds that this current uh uh emulation is going at. We are making additional improvements to our uh execution layer uh to go faster. The adding of it things like the virtual memory did slow down execution. But this is actually like effectively how fast it'll prove live. Also the the delay on the typing is a little bit induced by um

currently it's using polling for accessing the the uh the key inputs. But what's interesting initially is that also this entire system is fully uh deterministic. Uh so there so when you run it allows you to run Linux things in a completely deterministic way. The only non-determinism is the user input in this case and that could also be controlled by sending in scripted things or you know so on. Anyway it >> wow Jeremy mind-blowing. Congratulations. Um this is super cool. Uh we have one question. Can it run run Doom?

>> Doubtless it can. Uh in fact what what's interesting is is that um because the entire operating system is there effectively not everything you know more or less works the the as long as the operating system supports it. Now of course getting the frame buffer output u might be slightly annoying uh but yeah. >> Wow. >> Go ahead. can right I was just going to ask Jeremy this is this is amazing but what links distribution is this working on because I know like for risk 5 there's only a few distributions >> so interestingly for RV32 there are somewhat limited distributions and this is actually like um uh it's like a busy box uh version of things

>> uh now the for for when we go to RV 64G there's actually a full debian distribution for RV 64G that basically is almost as complete as the ARM distribution if you at supported uh software packages. Um and so once we have 64-bit as well as S mode, um you should be able to run a complete full totally modern Linux distro, all the compiler tool chains, the whole nine yards. We've already built run GCC inside this thing. Um and it works. >> Amazing.

>> Jeremy, thank you so much for this fantastic demo. Next up, we have Leo uh who will share some uh real time proving updates. >> How do I stop share? Sorry, I'm just uh >> my thing is not >> noise. I think Leo has started sharing. >> I I can I see my screen? >> Can you see the site? Not yet. Okay.

>> Okay. Try again. >> Okay. I'll try again. >> Nope. Still no. Um. Okay. Let's move to Emil. Uh, and then we'll come back to you, Leo. >> Okay. Can you see my screen? >> Yes. >> Okay. Thank you. I'm going to share quick updates about LINVM performance. Solid VM typically is a VM whose goal is to um is an an attempt to replace BLS.

Emile: leanVM benchmarks

So at the consensus layer of Ethereum to make it postquantum and so we need to be able to aggregate XMSS signatures and to have recursion. To do so, we need a lot of posetons. And recently, um, we passed the bar of a million posed per second on M4 Max using GKF. And we are still approximately at 15x overhead versus plain text poson. In term of XMSS, we are approaching the target of a,000 XMss proven per second.

um on the Mac and still at 300 XS per second on an old Linux laptop and still this 12x overhead versus proving row posance without the VM overhead. Um in terms of recursion there is there is not the full end to end system implemented. only have one opening implemented and there is that's mainly the bottleneck. We need a third of a second to prove one opening which is still much slower than what we target to have the full end to end recussion uh for like a t of a second.

So conclusion, the VM runs currently approximately 1 to 2 MHz on laptop CPU can probably do 2x or more in terms of purely software optimization. We are not too far away from thousand XMSS per second uh using purely software optimizations for recursion. will probably need more ideas and recently there is this nice um write up by Gorg Viza about making work making twist and shout work in the hashbased setting thanks to logup star based approach and potentially new pre-ompiles like modular recompiles inspired by OpenVM or something like this. Thank you.

>> Thank you Emil. I love seeing the charts just getting better and better every week. uh at such a fast pace. Um and I find it mind-blowing that the overhead of proving correctness of poseon is only 16x. So that's the the overhead of uh of a full proof system. Uh and Vitalic, you know, several months ago asked, you know, should we organize a competition to try and and and have like uh you know, proof systems that only have an overhead of 10x. And I was like, you know, you're you're crazy, Vitalic. This is not not possible. But actually he he was uh his intuition was correct that we can we can do a lot with tiny tiny overhead.

Um congrats Emil all the progress. Next up we have George uh who will talk about the soundness calculator. >> Uh hello everyone. Uh this is George from the AF cryptography team and for the past uh six months we've been looking a lot into uh soundness of ZKVM projects and you know there is many ZKVM projects and each of them is using uh its own weird soundness calculator and it's quite quite hard to compare apples to apples like it's needed for this L1 ZKVM project. So naturally what we did is make another soundness calculator that is supposed to be universal. So uh it's on GitHub it's under my profile but

George Kadianakis: soundness calculator

we will soon move it to the Ethereum organization uh through the help of various projects. We currently support Risk Zero Maiden AISK they are all thrive based proof systems. Um you can go to the results page and uh you know for example uh you can see for zisk uh some of the parameters being used and then you can see you know like uh the regimes and how many bits of security it has. So you know like you have the unique decoding regime, the junction boundary, the broken capacity boundary regime and the stark uh heristic and you can see how many bits of security you get and how we want to use this tool is sort of kind of make it use it to think

how trickle upwards like how we can get from this huristic up to where provable security is uh for each project. So, uh, I just wanted to put this on your radar. Uh, we are going to be working on it this year. Um, we still don't support the new results that we're going to be hearing about today. Uh, we don't support the 1.5 Johnson bound regime, which is kind of interesting. We don't support other PCs other than Fry. So, there is work to be done and please get in touch if you find it interesting. But yeah, just wanted to put it on your radar. Uh, thanks a lot.

Thanks George. And yeah, this is a great initiative that should provide legibility for the whole industry, which is uh fantastic. Uh Leo, shall we try again with your presentation? >> Yeah, sure. Yeah, let's try again. How about now? >> No. Um >> no, >> maybe weird. >> Maybe we can get Will to share the presentation. Uh, I think Justin Taylor might be in the chat. Justin, do you want to talk about uh Jolt streaming?

Justin Thaler: Jolt streaming

>> Yes, sounds good. Can you see my slides? >> Okay, great. Um, so apologies for missing my slot before. Uh, so yeah, what is Jolt streaming? Uh, let me sorry, exit full screen here because this isn't Oh, there we go. Can you you see the second slide? >> Yeah, we can. Yeah. >> Okay. So as uh probably everybody knows the way uh the prevailing way of controlling prover memory today in ZKVMs is to break a big execution trace into chunks prove each chunk kind of se almost separately and then recursively aggregate the proofs. Uh you do have to kind of link the state of memory at the end of each chunk to the state of memory at the start of the next chunk. So that is a complication. Uh so I yeah I want

to start with motivation like what why do I want to change how we do you know this technique for controlling prover memory uh the the reasons are both simplicity and performance you know I think there's a a view that this way of doing things is fine everyone does it this way uh I I think that we can do better um on the simplicity side this recursive approach uh you know invoking recursive you know proof systems everywhere is just a massive surface area for bugs so let me just leave it at that It'd be nice if we just didn't have that surface area. Then on the on the performance side, there actually is a performance hit to this. Uh some some projects today are spending the majority of the prover time on the recursive proving, which means if you could get

rid of the recursion, it actually even if your non-recursive prover got 3x slower, it would still be a net win to not have the recursion. uh other projects to link memory between chunks, they turn to elliptic curve based hash functions and that gives up both speed and postquantum security. Um so and and you know so let me leave it at that. So so we can hope to do better right like every everyone does things this way but it doesn't mean it's the best way to do things. So that's the motivation for streaming. Uh today Jolt is not streaming. That means the prover space grows linearly with the uh number of cycles being proved. Uh now it's still like you know a pretty good spacebound per cycle 850 bytes or so per cycle at

at this moment in time. Uh this means we need about a terabyte of space roughly to prove an Ethereum block which is you know just maybe acceptable for you know the machines with the with the largest amounts of RAM. Um you know uh so but we we want to do better than this right. Um, so, uh, the the goal is to make the prover space, uh, you know, at most 2 gigabytes or something, uh, regardless of cycle count. Uh, so where are we? So, I hope to be a little further along and give you like a real update today. Unfortunately, we're we're not all that far along. So, uh, Jolt invokes the Sun Check protocol about 20 times. And if any single one of these 20 invocations need linear space, then, you know, in total, we need linear space, right? So,

we have to go through each one of these 20 checks and kind of make it streaming. And so we've done two of the 20 and we've also made uh committing and evaluation proof streaming. So that's where we are. Uh but getting the first two of the 20 out of the way is sort of the hardest part. So now to do the remaining 18 I think we'll be done in about a month and then uh you know hopefully we'll come back with awesome results. But that that's all I have for today. Thank you. >> Okay. Exciting. Thank you so much uh Justin. And I believe that is the main bottleneck to getting Jolt integrated with eofroofs. So hopefully we can look forward to a Christmas present. Uh >> next up uh let's try again with Leo.

Leo Fan: Cysic RTP updates

>> Perfect. >> Yeah. I guess like we'll uh just share my uh my night which is easier. Uh yeah. So um my name is Leo from uh CIC. So today I'm here to report some like progress on uh or some updates on Venance. So men is a hybrid uh proof system combining GPUs and FPJs and then we build based on the uh hyper cube proof system for succinct. Yeah. So since last month like we integrate like all these like 50 plus like chips for this question and we bring to to GPU. So as you can see the table uh yeah so like uh compared with a hyper cube uh performance we we somehow like achieve

around like 500 times speed up. If you count this like PCIe perform uh P PCI transform transformation, we still achieve about like 30 plus uh uh speed up. And in in addition to that we also like um doing some fuse and unified most of the booming kernels into like just a single CUDA C++ uh kernel which bring another like 15 to 30% um booming speed. Uh yeah so the takeaway is like right now uh venance is about like two times faster like end to end compared with like hyper cube and we hopefully like by

estimation we can achieve realtime proving on uh using just uh 70 149 GPU cards and our goal is to push the limit to 30 to 140 GPU costs. Yeah. So that's all. Thank you. Thank you, Leo. And yeah, this is a super cool approach to have a a dual FPGA and GPU. Um, and yeah, the numbers that you showed me, you know, just a couple weeks ago were were really really impressive. Um, these speed ups are are pretty insane. So, uh, congrats.

Um, is Michael on the call to talk about Airbender or anyone from from Matal? I I don't see Michael here. Uh to be honest, I'm not sure what he wanted to prevent here. Uh do you have a topic from him? So I may try to cover it early. >> Yeah, the idea was just to give a flavor of the next generation of of air bender. Uh well I mean so for the next generation his uh his message to me uh this early morning so late evening for him was that he finally finished the largest uh GPU uh piece of code which is needed for the next version. So the one

which is on inh proof is the old one back from Aprilish something like this. Um so it was done just for fun by Martin. So he he did it all by himself to try it. We never actually planned to do it on the old version but he did it all by himself and uh so for the demo day Justin as I explained we will try to get the the new one in. Uh it's tested like CPU on fully ser it's fine converging all the way with a recursion. Uh but we needed this piece of GPU code from uh from Michael himself to finish and we will try to fit into

the next two weeks to get everything. Uh the slowest part is still a simulator but for this one we don't have capacity to to improve right now. So we should have a maybe not the base latency in absolute numbers but throughput. >> Okay. Super exciting. So I guess what you call the old prover is still like the fastest on leaf proofs uh by a factor of 2x. So looking forward to uh the performance of uh of the new version.

>> Um >> Michael was like most likely was just working all the night to get this message today in our Slack. So most likely he's still sleeping. I mean, just in general, I want to say thank you to all of the the ZKVM teams that are really really grinding extremely hard um in this very competitive environment. Um, and the the performance is insane and you know, they're all working towards this big demo for for Dev Connect. So, thank you so much to to all the devs uh working so hard.

Cool. Uh we're done with the ecosystem updates now for the mathematics. Uh so I'd like to invite uh Z to talk about the the first paper on uh distance preserving generators. >> Thank you. Um let me just uh try to share my screen. >> Okay. Can you can you see it? No, this doesn't amazing. Um >> here. Okay, great. So, so we can see the

Ziyi Guan: distance preserving generators

screen. >> Yes, we can see it. Perfect. >> Okay, great. Okay, so hello everyone. I'm Z. So uh I'm going to give a very very brief overview on our um recent paper we submitted to errint earlier yesterday. It's going to be online soonish I think and the topic is uh about uh polomial generators and in particular their distance preservation property um especially their um mutual culture agreement. This is joint work with Sarah Ali and Ignasio. So let me let me start with uh defining the problem. So what is distance preservation? It's usually defined uh

with respect to a linear coach with minimum distance delta. And then usually we're given just a batch of vectors UIs and uh the goal is to check each one of them whether they're close to the linear code or not. And uh however in applications it's usually like not very costefficient to kind of check them one by one. It's going to cause a lot of randomness complexity uh verify running time uh so on and so forth. So then uh one kind of um systematic method that people developed to to do this type of checks especially when the vectors are given in groups is to check their linear combination instead. In particular, one

abstraction for this kind of um linear combination approach is to consider a generator which is a function that takes a seat and maps it to L coefficient and then we use this coefficients the output of this function to do the linear combination uh of all the words we want to check um and arrive at this ux and then we check how close ux the combined word is with the linear code. And in particular, what we want is that if the combined word ux is not super far from the coach, then we know that uh um all the words that we start with are also not super far from the code.

And one way to formalize this is to use uh mutual correlative agreement. And intuitively, what does it mean? Again, we have a generator that takes a seat. And for simplicity, let's assume that we uh the output is two coefficient alpha 1 and alpha 2. And I have two vector that I want to check to start with the chrome one and the dark blue one. And I just use the generator output to compute the linear combination of these two words to arrive this at this light blue one. And I check how far it is from the linear code. And now as the picture show like at four positions um kind of uh specified by the arrows they agree with the code then mutual

correlated agreement enforces that if that's the case if those four positions are the ones that uh the combined code word agrees with the code then it has to be that this four location positions are fine in the original code words the original words that we start from and this can be formalized by this property called mutual cial agreement. And in this paper um one of the central question that we uh study is uh we want to figure out what type of generators have mutual correlative agreement either for general linear codes or for specific linear code and in particular let's consider the universe of all generators

and prior works has uh have studied a lot of different generators like uh um the alphine space space one alpha line one univer powers even like all multilinear uh monomials and just by inspecting the definition of MCA and also um structures obtained by previous papers it's not so hard to see that having a generator to be zero evading is necessary which means that you take the generator the probability that the generator maps a nonlinear vector to a linear vector is very very small. This is a necessary condition.

But is this sufficient? The answer we give in this paper is that a subclass of it what we call polomial generators. Meaning that the output of the generators are composed by linearly independent polomials PJ here. All those polomial generators um have mutual correlative agreement for linear codes. And in particular it covers all generators uh which people uh previously studied their distance preservation property before but which means that polinomial generator is a sufficient condition. But we also realized that it's actually not necessary because we also additionally studied this uh

generator which is not a polinom generator for the first time but we still establish its uh mutual corial agreement for arbitrary linear codes and then we of course specialized our result for resolment codes as well and we obtained more fine grain bunch and in particular what we show is that all polinomial generators again everything included in this picture have MC MCA for resolment code up to the Johnson bunch in particular it match with the best font the best font as of like 5 um 07 a.m. this time this morning uh uh for correlated agreement for this two specific generators for resolmenting codes and uh e-print is going to come

soon and thank you so much >> just on time thank you so much uh Z so um we have a question what is phi x to the power j >> um fi this one >> yeah yes >> um so this is kind of a uh such a abuse of notation. I didn't introduce such but basically um you can view it as somehow like the univar powers generator but we just need to need to do some field isomeorphism to make the the domain works but if you're interesting I can I can share this offline but I don't think it's too meaningful to get into the details right now.

>> Cool. Uh Ben is asking what range of proximity parameters are your results operative for in the case of general linear codes. >> Pardon? Um which uh okay let me see if I can see the question actually. >> It's in the chat but Ben you're welcome to unmute as well. >> Which range are result? Um okay for the specific bond I actually do have a slide for that and uh in particular for example um in the alpha space case this is the bound we get and in particular it does match with u the previous best bound for mutual cor agreement obtained for this generator

and uh in particular for general code and general polinomial generators this is the bound we get which is uh uh there's a reason I don't uh want to talk about this uh within five minutes the bond is complicated but in general for all the generators that um I [clears throat] have in this picture um everything uh every bond we achieved in this paper match the um all the bonds in prior works um except for this uh new paper by uh showed up on ec this morning >> perfect thank you so much Z so I guess we have two classes of papers we have those that are that have positive results s those that have negative

Angus Gruen & Ben Diamond: up-to-capacity conjecture invalidation

results. This is one of the the positive results. Uh and next we have I guess a negative result uh from Angus and Ben and you know their paper uh kind of did the rounds on on Twitter uh for the last few days and I think is a a great wakeup call all while still giving us hope that uh we can we can still squeeze a lot of juice uh with the remaining uh conjectures. Uh Angus, the floor is yours if you'd like to share your >> Okay, great. Is that worked? >> Yes. Uh wait, not yet. Yes, now we can see it.

>> Okay, great. Um I guess as a first thing before I get into it, like a massive thanks to to Justin and Will for organizing, I guess, the conference in Cambridge from which I think this work came out of it and also all the work regarding the proximity prize. It's been sort of amazing how many papers have come out in the last week and slightly terrifying. Um but so so the idea of Ben and me was to basically one of the hard things about studying proximity gaps is you have all these codes and there's like lines between codes and you've got these polinomial relations and and this is really hard. So we thought what if we just take a step back and only think about randomness just pick random words and ask how likely is it for a random word to be close to the code and the

sort of surprising result that we show is that actually the answer is it's a bit closer than you expect. So okay so to give a brief picture and I think this is picture is still valid but it may have been uh upended in the last week so I apologize if this is slightly wrong but roughly speaking what do we know about proximity gaps there sort of three regimes that we knew a lot about the first is in UDR which is the green and in LDR which is the blue where we have these nice proximity gap results that have just gotten a bit nicer uh as of this morning. Um and the other thing we knew about was in capacity. So this is this black regime and here proximity gaps is just impossible because I mean it's it's vacuous. Every every single

word you pick is close to a code word. There's there's sort of no meaning to the statement. And essentially what the proximity gaps conjecture was was if you look at the sort of the white r the white area in the middle, how much of this white area can we push out? How much how can we how far close to the black area can we get uh with with these proximity gaps results? And what me and my Ben result shows is that while we might be able to push it out somewhat, there is a small sliver away from this black region where proximity gaps simply aren't going to happen. And they're not going to happen basically because what we find is that in this red region uh which is the size is roughly proportional to the the one on the log base of your your prime in this red

region just random words are way too close to the code. And so proximity graphs breaks for these sort of very simple or random reasons. So I think probably the key thing to understand how our result works is the following theorem that we prove which says if we have some statement on about the probability that a random word is close to the code this gives us a lower bound on the on the proximity gap error and so I think a great question is like why is this true and this is true from sort of a pretty simple counting argument. The idea is you take some word which is far from the code and now you partition your space into the line into the set of all lines passing through this word. And so basically a simple thing about partitions is that uh

because this is a partition the proportion of sort of close points on one of these lines at least one of these lines this proportion has to match will be bigger than the proportion in the entire space. And the proportion in the entire space is exactly captured by this probability function. And so what this says is that the uh there needs to be a line with a large proportion uh of of closed points on it which is exactly a line that sort of breaks your proximity gap. Now a very open question here. So currently we've managed to restate sort of trying to bound this error function in terms of trying to bound this other probability thing. And so there is a question well is it actually is this easier? How how easy is it to sort of estimate what this probability that a

random word is close to the code is? And for that let's first turn to the sort of simplest case. So if we take our codes to have K equals 1. So this is where all of our uh it's read Solomon code but actually all the code words are constants. So everything is just the repetition code. And additionally we're going to take H equals one. So here h is the shortfall. So what does this mean? So if you take any code right there's always going to be every like a character appears once. So the maximum distance away from the code is going to be n minus one or more generally n minus k and h is trying to capture how much extra is it going extra close outside of that initial uh bound are we so sort of how how far sort of closer than the

maximum distance are we and so in this case when you take h and k to be one then this probability becomes what's the prob like what is the chance that a random word u is of distance n minus two and this is exactly the same to saying what is probability that the two entries of the random word are equal. And if you sort of think about this for a second, this is the birthday paradox. You take sort of, you know, 30 people in a room and your uh word here is simply the vector of their birthdays and you say, well, what's the probability that two birthdays are equal? And so in this case, there are sort of two things to note. Firstly, we can actually compute this probability exactly. But also, one of the takeaways from the birthday paradox is that actually sort of the numbers higher than

you expect, right? you need about 23 people in the room in order to get a 50% chance of two birthdays being equal. So this sort of gives you an indication that actually it maybe isn't so surprising that that in these codes you end up a little bit closer to the code than you might naively expect. So obviously this is a very simple example and I'm mostly going to be look talking about sort of huristic picture here. I'm not going to go into so much the hard math that's going to be Ben in the second half of the talk. So one question is well how do we use this to make some estimates in uh in the more general case and for that I'm going to use two assumptions and roughly speaking I think one of our the results from the rest of our paper show that these

assumptions are roughly reasonable. So we're going to let x denote this random variable which is equal to the number of locations in which sort of our fixed code word and a random variable agree. And so we have two claims now. The first is that if we take two different code words V and V prime, these random variables behave like independent random variables. So one thing that I think mathematicians will many people will immediately see is that this is clearly false in general, right? Some of these these code words are sort of uh you know they can be equal at points. But it turns out this isn't a bad approximation. And the second claim is that that these uh independent random variables look roughly like they're pon distributed. And this one's more

reasonable. This is sort of a general like large person approximation to the binomial distribution. But the key point from this is that what it allows us to do is it allows us to write the left hand side the the probability that we're close to the code in terms of this fancy P where this is just the probability that we're close to a particular code word. And the statement is that the probably you're close to a particular code word is much easier to compute. So the first question is well is this approximation any good? And so what you can see here is for the birthday paradox we can compute all these things exactly and you can see so here what I've plotted on the uh the x-axis this is sort of the n so the number of people and the y- axis is the probability of having two people with

the same birthday and you can see that these these all line up very well. So this is like a pretty good approximation in this case and so hopefully you can sort of believe that this is a good approximation more generally. Now what I then what we can then look at is well what happens when we sort of fiddle around with our K and H values and so here I've chosen a much bigger P. So in the birthday paradox case P is 365. Here I'm choosing it to be about 60,000. You know in our um in our proof systems it's like 2 to the 128 but the same pictures will sort of apply. And over here what I'm graphing is basically each of these lines corresponds to like a different value of h. So the red line here says what's the probability we're sort of one closer than we expect. The

blue line is two closer than we have to be. The green line is three closer. And what we can see is that sort of when k equals 1, we need to get n to be about a th00and before we end up to be sort of one closer than expected. But all of a sudden when k sort of rises to two, this the distance away we need to be goes from a th00and to much less. It goes to about 100. And we can play this game as we keep increasing K because in practice K here is telling us the size of our code and we usually work with quite large codes. And so you can see that as you keep increasing sort of here I've slightly changed the picture scheme. So because as we get to larger values we're going to find that we're not only like one or

two closer than we expect, we're like 50 or 100 closer. And but you can see that as K's increases basically the the value of N you need to pick such that you all of a sudden start becoming much closer than you expect uh rises quite quickly. As you can sort of keep going through and you see if you once you pick K to be say 200 you find that if you have n to be around a thousand you're about 80 closer than you expect. So you actually do get a fair way in from this capacity bound. The other thing you might note if you sort of look at these is that these lines are getting very steep. They start off sort of slanted but eventually these basically become these sort of thresholding values. And so one of the questions we want to ask answer was well

can we estimate where these thresholds are because these thresholds are basically where we think proximity gaps is completely doomed. And so basically through our work we get this rougher estimate of the thresholding value where here eater and row are relativized. So here eater is h / n and row is k / n. But this gives you a reasonable estimate. If you plug in a row, this says, well, if if you have less than sort of e to shortfall, you're almost guaranteed to be close to the code and proximity gaps is doomed. If you have more than a shortfall, then our attack won't really work, which is I guess is good news in some ways. Uh, and so you can then take this and ask, well, how does this change actual in production snarks? And we get this sort of simple table. Uh and basically what this table

is saying is that if you want to use this the conjecture of proximity gaps up to capacity you should sort of adjust this a little bit by our results and you should increase the number of queries by in the row or half case by three in in the row quarter case by sort of one and you can play around with this with sort of different different numbers to work out exactly where. So this isn't a big hit, but it also is a hit. And I think it's also worth thinking about this and trying to work out does it make sense to exist exist all the way over here or should you maybe be a bit closer list coding and I think this is one recommendation we'd have if you know if you can we'd definitely recommend trying to operate in proven securities regimes particularly now that the proofs are

getting so much stronger. Okay, I'm going to pause for now and switch over to Ben who's going to cover uh some of the maths the math side of things. Uh how do I >> uh Okay, so I just tried to share. Is that uh going through? >> Yep. Yep. >> Yep. Okay. So um thanks Angus and I want to reiterate the gratitude u we both have for uh this workshop and and also the proximity prize. I think has been amazing to see all these works that have been coming out. So really cool stuff.

Um so let's get into it. Uh so as Angus said uh we we have we have an overriding uh problem we want to talk about which is that the probability that a random word will be close to the code and in in particular closer than it kind of has to be. Okay. So the capacity uh you can think of as as the covering radius. It's sort of the farthest that a word can be. So a word will not be farther than that. But will it be will it be as far as it can be or closer? And essentially what we want to show is it'll be much closer than than it has to be than the farthest it could be. So here's a here's a probability we care about. Um symbolically u is the random word and z

is a radius. And um as Angus said already if this probability is high then the proximity gap error also is. So it's enough to just talk about this visually just very crudely. Right? So fq to the n is a kind of box let's say and wi within it we have these points which are code words around each one we inflate a ball of radius z and we're going to take a random word and the question is is u the random word in any of these balls or not. So this u is is far from the code and this one say is close to the code. Um the question is if we pick you randomly which of these two cases is liable to happen.

So as you could see from the last picture this probability we care about up to dividing by q to the n is a is just a union. We care about the mass the probability mass of this union of balls. Uh so by the standard inclusion exclusion principle we we want to bound the union from below. To do that, it's enough to look at the first two terms in this inclusion exclusion sum. The first is just a raw sum of all the ball volumes excluding overlaps and the next is a kind of pair-wise intersection term. If we look at these two terms, this gives us a lower bound on the union.

Okay, so as a kind of cartoon picture here, if we care about this gray union on the left, we can add up the individual balls and then subtract off these pair-wise intersection terms. Okay, so to do this, we're going to tackle these one at a time. Okay, so we want to lower bound the sum term and upper bound the intersection term. That's essentially the program of what we're going to do. So first things first, bounding the sum from below. Uh the sum is actually pretty simple. We just take the number of code words. If we can learn the volume of one ball, we just multiply that by how many code words there are. So we turn to the ball

volume. This is an extremely classical subject. Um this is kind of the standard approximation for the ball volume. It's two-sided. You could, for example, M Williams and Sloan classic 1974 textbook. Um now actually this is really not good enough for us for the following reason right so this is a lower and upper bound if you divide these you so the multiplicative gap between the upper and lower bounds actually looks like this root 8 n term it actually goes to infinity as n grows uh so these are drifting apart from each other we actually need really sharp control we need an asmtoic estimate so in short we have this theorem Um, this

expression looks a bit nasty. Actually, it turns out to be quite usable, arguably more so than this one because it it has no entropy function. But more importantly, it's asintoic, right? So, um, the ratio between the ground truth here on the left and this expression actually goes to one if if um, ZQ and N are chosen in such a way that these expressions become small. We call these controller expressions. If you choose ZQ andN so that these go to zero then this ratio goes to one. So that's really important for us. Um and even concretely you can see this thing in action. So um it's actually not hard to find parameters where this thing is already

outperforming the classical entropy estimate. Um here's Q= 365 continuing the kind of birthday analogy and and N also 365. And you can see that when Z is closer to N for these high radi Z um we're we're already outperforming the entropy lower bound in the sense that we're closer to the ground truth than than the lower bound is still below the ground truth but close. Okay. So turning to intersections um we we want to bound this from above and and to do this we we do a couple combinatorial things. So, so it's pretty straightforward that if if we're interested in all pairs V and V prime, there's a kind of translational

symmetry. We can actually just look at the zero ball and then nonzero code words V and ask how those intersect and then multiply by Q to the K. And and moreover, the intersection between zero and V actually only depends on the weight of V, how many nonzero components V has. So it's enough to partition this sum um in into weights and then study a few combinatorial things. So this is what we do. First for each weight w which must be at least d going up to n how many code words uh are there of weight exactly w. This is not too hard to do. Actually this is the only place in the whole paper where we use the mds assumption. This is kind of funny. Um

but um now for each w moreover um what what what is the size of the intersection between the ball around zero and the ball around v where v is of weight w this is not crazy hard it's a bit tricky it's a bit cominatorily intensive um but we can do this as well really the hardest part is to bound uh this weighted sum and this requires a couple tricks you'll see here again more of these controller expressions. So what we state is that this sum and and our estimate for it the ratio goes to one if these controllers become small. How do we do this? Um cominatorics of course uh

here's here's a picture from the paper. Essentially what matters is the weight of v which we call w and this other quantity s basically s is a technical value. It says um where U disagrees with zero, how many of those disagreements happen at a place where V also agrees with zero? Something like that. Um what we show is that actually there's a double sum and and one of of the sumands ends up dominating the entire double sum at least for Z close to N or or or when the controllers get small. Okay, so that's a speedun of of our of our lemas.

Here's our main theorem. What we're going to do is we're going to let n drive to infinity. We're going to specialize and then as a function of n, we're going to tell you what q should be and also what z the radius should be and what k the the message length should be. The claim is that as n goes to infinity, first of all, these specializations make our controller functions get small. So our estimates become sharp in the limit. Um and moreover the intersection term divided by the sum term actually goes to zero. So this means we we've thus rigorously shown that you can ignore intersections. Um that needs to be done precisely but we do. So the last thing

standing is is just the the the the first order approximation the sum term and um what we show is that that thing actually decays slowly actually more slowly than n the c over q which is enough to prove the theorem. So here's a bit of a visual explanation. It looks a bit crazy here. You can barely see it because it's covered by the orange is the is the actual lower bound with intersections. The orange is the first order term that ignores intersections. Now, these are essentially identical. You need to prove that you can ignore intersections, but we do. You can see that they make effectively no difference. Now, we're going to lower bound orange in a sequence of steps. Um, eventually we get to this guy, the

green. Actually, we go first uh to to uh to purple, which eventually becomes bigger than black here at at a kind of predictable crossover around 10,000 for us, but it can all be changed. Um so and then finally bigger than green and and this way down here is is n to the c star over q which is actually 1 over n. We we just choose q to be um n to the c star + one. Uh so we're we're blowing this um out of the water here. This purple. You can see that certifiably orange is decaying more slowly than purple is. So that um disproves the conjecture.

Okay. Looking ahead, we did propose a revised conjecture. Um, basically what we want is our rates, our relative rates and what we call the shortfall. So the shortfall again like Angus said is how much smaller than the covering radius is the ball radius. So we want both of those to stay away from zero as n goes to infinity. Basically, here's our conjecture and um our constant C this looks like the the Ben Hessan um at all conjecture, but um C and K depend on row and ADA. Now, I I I thought that this might fall as of this morning um I thought it might be a

short-lived conjecture. Actually, my best understanding as of now is that this conjecture is still still alive um even despite the great new work that that came out. So, um, that that's it for me. So, I guess we can turn to questions now. >> Fantastic. Thank you so much. Uh, Ben and Angus, feel free to, uh, raise your hand or unmute. I guess one question I have is, um, as far as I can understand, there's like two other papers that have these negative results. Um, are they basically the same idea or are they different ideas that could be combined to have an even stronger negative result?

>> So, I know only the one other paper by uh was it Elizabeth and uh what's the name? >> Alistister. >> Alistister. Yeah. So, I think uh that paper is actually answering the same question to ask of what's the probability that a random word is close to the code, but they use uh sort of quite different methods. Um but I mean sort of nicely we end up with sort of similar uh takeaways of you need to bound your distance away from zero. Um I think they might have slightly different constants but I think morally uh they're roughly the same. I I don't know what do you mean the other paper is one that came out this morning. Uh >> I haven't Yeah, >> I can try this. I I think we've all had at at most I don't know a couple hours

to to process this paper. Um, I think well I I guess Swastik I see here is is on the call so maybe he can he can tell us but I I I I I I think there is a result there that does disprove the original uh capacity conjecture um using of course I I I think the techniques are very different. I also think it's characteristic specific uh whereas and and maybe domain specific whereas ours is not. Ours is more of a generic comatorial argument. Um I believe uh and I I I think so I believe that our current conjecture is not disproven by by the new results. Um but maybe I I should let let swastik tell us the real

truth here. Maybe if he wants I guess I guess he's so that's all I'll say for now. I guess we we don't fully know, but I think um yeah, lot lot of things going on. >> Okay, I just want to give a few seconds for people to ask any other questions. >> Oh, I do see a question. Um I think it says are these conjectures just related to proof sizes, number of queries or are there other impacts? So yeah, I I think the main impact is proof size um mediated by by number of queries.

Remco has a question. Uh the conjectures are for general codes or general read solvent codes but in practice we are only interested in specific ones with co-ets of roots of unity as evaluation domain. This weakens the conjecture. Could that change things? So it's not >> Yeah, go ahead. >> Okay, sure. I Yeah, I think so. So So our results uh basically completely don't care about any sort of what you pick for the domain or or honestly any of the parameters. It's sort of purely randomness. There's like almost no algebra in it. Um that means that there was a big paper that came out I guess yesterday uh by Guraswami about random read Solomon codes and so it does seem like the random case might be different to the specific case but I don't think

we currently know like so I think the answer is plausibly but we don't know enough oh infinitude of primes. Okay, so this is a an a bit of an odd and interesting um aspect of our proof technique. So what we're doing is we're specializing Q, K, and Z as N goes to infinity in certain ways. Actually, I can go back or I'm not sharing anymore. So um >> Ben, would you mind repeating the question? I don't see it in the chat.

Maybe it was a >> you mentioned the infinitude of primes inside a certain interval. Can you explain how this fact is relevant to the proof of your main result and how does it relate to the conjectures you discussed? Okay, so how can I say this in in simple terms? Basically, we we let n drive to infinity. We define q as a power of n. All the numbers shake out combinatorily. But there's a kind of odd technical problem which is that q might not be a prime power. So in order to disprove the conjecture, we we need these to actually be read Solomon codes that we're creating as N gets large. Um if Q is not a prime power, this doesn't really make

sense. So it turns so so we could start rounding. Let's say let Q be the the smallest prime power that's bigger than such and such. Um our our bounds are very delicate. So we don't want to push numbers around by rounding them or taking floors or ceilings. So instead it turns out to be simpler to just say well maybe n is already prime maybe q is already a prime power. Um and the question is will that happen for infinitely many n along the family that we defined. Uh it turns out that in order to guarantee that you need there to be a prime in in some certain interval. So the question is as we go up to infinity as we pick a bunch of

intervals that are are growing but growing a bit slowly the width is growing like x to the 2/3 or something can we guarantee that there will be primes in those intervals and the answer is yes this actually goes back to some kind of classical analytic number theory from from the from the 1900s. So this is a bit of a technical obstacle that turns out to be not an obstacle. Um, could we bypass the number theory? Maybe. Um, I I think that turned out to just cause more problems than than it than it solved.

Uh, but but I I don't view that as essential to our proof. Kind of just an interesting side quest. If I'm not sure if that answers it. I'm happy to discuss more offline if if anybody wants to talk. >> There was one other question. What does it mean to petition the sum by weight of V? I I think what what we mean by that is just sort of every so we're summing over um all code words and what we're saying is sort of two things. Firstly, if so the weight of a code word is the number of non-zero elements and our claim is that like the contribution to the sum depends only on the num n number of non-zero elements, not sort of the actual structure of the code word

outside of that number. And so what we say is that like instead of trying to like do these things for every code word, we just sort of pick a canonical representative with some number of non-zero elements and then count the number of code words with that number of with with sort of that structure. So sort of it's a way of um simplifying the work for us I guess >> right and then right so the non-zero elements are the part the parts of the partition right? >> Yeah. Yeah. >> Right. And just just another question about the the conjecture itself. The conjecture to be honest like like combinatorally seems to sort of like be believable because even if you just think about the like the trivial bound and binomial trails um the you I think you do sort of come to that sort of k

over q I can't of course calculate it immediately but uh it seems to be cominatorial believable. >> Uh yeah. So you you mean our new conjecture >> the 5.1 yeah >> um >> don't yeah >> I think sorry you want to go >> so are you you're talking about how the binomial coefficient I don't know like n behaves like >> I don't think that's the right way to go here right because for us C is is that would make sense if C was like >> the distance or the proximity parameter or something but but that's actually not what's going on like for us >> okay >> um the proximity parameter is actually growing linearly uh in n the that binomial coefficient will not be bounded

by a polomial in n right that's actually going to probably be exponential in other words if I take n choose gamma n where gamma is some fixed real constant that will not be polomial in n so I see what you're saying but I I don't think I I think that might be not the interpretation you want >> uh Ariel asked uh you want possibility The result is for any MDS code, not just read Solomon. And the answer is yes. Okay, thank you so much uh Angus and Ben. Fantastic uh result and presentation. Uh next up uh we have uh Swastik who will be talking about uh his new paper that landed this morning and uh various people regard Swastik as

Swastik Kopparty: improved provable gaps

basically the world expert in proximity gaps. So Swastik the the floor is yours. We can't hear you. You might be muted. Can you hear me? >> Hello. Yes. >> Okay. Great. Okay. So, I'm going to talk about uh our paper from just this morning on proximity gas solment codes. This is a joint work with Ellie Benasan Carmuk and Shivangi. And uh so we have a bunch of positive and negative results.

And uh so I'll tell you a bit about some of them and I'll tell you some of the I mean I'll tell you one of the ideas that goes into the proof of it and you please ask me questions as as we go. Okay, good. So the setup for proximity gaps I just want you to get used to my letters. So C is a linear code uh and I'll say C has proximity gaps up to radius gamma with proximity loss epsilon star with a exceptions. Okay, these are my letters gamma, epsilon star and a. If uh the following happens whenever you have functions oh can I point to point I can't I can point yes no I can't okay so so I'll just uh uh whenever you have uh uh two functions f and g uh such that

there are many combinations f plus zg which are close to the code there are more than a of them then f and g are jointly gamma prime plus epsilon star close to the core. Is that okay? So, I have a gamma prime sitting there which is Oh, you can't even see what I'm pointing at. I really would like to point at something. So, that's a good point. Yeah. No, we got it. Okay, good. So, yes. So, for any two functions f and g if many linear combinations are gamma prime close then fg together are gamma prime plus epsilon star close. And the gamma prime is anything going up to gamma. So, gamma is the radius up to which I'm giving approximity. So this these are the definitions of this is

what proximity gaps means and uh and what we want is uh and we want to get proximity gaps for resolment codes. I will just very briefly summarize why we why we care about this. I guess to this audience maybe we don't I don't need to say this but okay I'm just general computational claims reduce to proximity claims to read solvent codes. A claim of the form this function is close to read solvent. uh a single proximity claim to read solvent codes can reduce to several proximity claims to smaller read solment codes. This is an FFT like decomposition. And finally, several proximity claims can be combined into one by the proximity gap statement. So this is uh how uh how proximity gaps fits into the whole picture of

everything. And the the things that do this are for example the fry stir and word protocols which sounds like everybody here knows. Okay. Right. So, so some more notation. We're talking about read Solomon codes over FQ with evaluation domain D and degree K. So, polinomials of degree K evaluated over D. And the K is going to be 1 minus delta* N where delta is the distance. And I'm going to say everything in terms of these letters. Uh, good. And what we want out of a good proximity gap result is gamma as large as possible. A as small as possible and epsilon star being little o of one would be is nice. Zero is even better. And these are things

that can be used in analyses of things like et and you cannot take gamma as large as delta. This at that point you need a huge. This is a trivial result. So so maybe one could hope that for every gamma less than delta you can have a small. And how small? Maybe a being polyen, maybe a being uh one could have conjectured a lot of things and uh and in fact it was conjectured and it was famously disproved five minutes ago. Uh so uh yes so so so what you have to be careful about what you want to conjecture but uh it's not uh yeah I mean lots of sometimes a lot of things like this do work out in this case we found out that it doesn't uh but uh so so the big question is how to make gamma

as large as possible while keeping a small and epsilon star almost zero and sometimes epsilon star being exactly zero is important this shows up in the stir and war protocols but uh epsilon star being little one also a respectable question which we should all think about. Okay. And so I'm going to say what the latest known results about proximity gaps in the positive side are prior to our work. Uh there are three kinds of results. One of them is up to the up to half the minimum distance. This is gamma going up to less than delta over two.

Then we have proximity gaps with n exceptions. So a being n and epsilon star being zero. So there's zero proximity loss and there are only n exceptions. So the soundness error which is this a over q parameter is now n / q in uh if you use this and maybe you would set q much bigger than n and you get a nice approximity after that which you can use. uh there's the other uh there's another version this is goes up to the Johnson radius the Johnson radius is the best list decoding radius that we know for reading codes in general and uh and there we get a bound of when gamma is less than slightly less than the Johnson radius we get order n square uh a being order n square so you would have to set your field size so that n square

over q is as small as the soundest error you want and epsilon star being zero and there's also this annoying e to the seven which depends on the gap and okay This is what it is. And there's a third incomparable result which achieves a different kind of proximity gap which is which works up to this 1.5 Johnson bound. And it says that going up to 1.5 Johnson bound minus EA you can have a being really small. This is a constant. This is only gamma over EA square. And so this has its own merits in despite the existence of those other two. And these were this is the status of the best known proximity gaps results very read all my codes prior to what I'm about to say. Uh great questions about the setup for my letters.

Okay. Uh good. So, so I'll tell you what our main results are. Uh our main result is uh better proximity gaps for both up to delta over two and up to the Johnson radius. Roughly improving the previous results by a factor n. Uh so when oops uh when gamma is less than d2 so up to half the minimum distance we can get proximity gaps with a being uh this is a constant if epsilon star is a constant so you set epsilon star to be 0.01 01 and this a is a constant bounded by whatever this is. So there's no n involvement in this but it depends. I

mean I guess in application sometimes n is epsilon n is not so huge that uh you don't want to pay the n penalty. So I mean it this is the quantitative behavior of this. So this improves the the unique distance decoding result from the paper bcs which was uh from n down to this con. Uh and our second result is improves the BCKS result uh uh up to the Johnson radius by changing the n² over e to the 7 down to n / e to the 5 and uh I mean so I guess the n uh yeah uh right and this achieves it with zero proximity loss. So the previous result

also achieved a zero proximity loss and this is the statement and the constants in this big O are all very reasonable. Okay. And so this is the statements of the main result. Uh questions about the statement. Okay. Great. Uh w I'm going faster than I thought. Uh great. So this is the table of everything that was known before. I also want so so yeah this is this is the unique decoding statement I just said this is the list decoding statement that I just said up to the Johnson radius.

There was a paper also just a couple of days ago or a day ago maybe by Goyel and Guruswami proving this amazing result that for random read Solomon codes uh one can have listic coding and one can have proximity gaps up to radius delta minus EA with a being linear in n uh with proximity loss zero. This is this is for random codes and it also has this extra condition that q has to be at least 2^ 1 ea square. I guess this was somehow this is an important thing that makes it consistent with all the impossibility results from last time.

This I learned. Okay, great. So, so these are so I mean if some read solvent codes are amazingly do have amazing proximity gaps but these are random read solvent codes and my understanding is that if they're like the listic coding results we don't have an explicit criterion for when you sample the random evaluation set whether it is it works for you but uh but most solment codes where you choose the evaluation domain at random uh do have really good proximity gaps just like they have good list coding from other work from before. Okay, so these are the positive results. So I'm going to now give some flavor of what the idea is that helped improve. So if you know something about the BC KS uh uh oh I see

a question but okay let me just say I finished my sentence. So if you know something about the BCIS result uh so there was uh yeah this then so it had some uh it had some simple parts and it had some complicated parts and we're going to improve one of the simple parts. So I don't know if that's good or bad. Uh okay. Uh great. So I'm going to uh start with the outline of how BCIS proves this and I will talk about how we change uh what changes there to give us the quantitative improvement. Okay. So what is our set what what's the problem? We we know that f + z * g is close to the code c for many z's. Okay. We want to deduce that f and g are jointly close to

two true two polinomials. capital F and capital G that's what we want to do okay so how are we going to use the information that F plus Z * G is close to C for many Z so the idea is to replace the multiple little Z's with one capital Z the formal variable Z and we look at the the the field of rational functions in this formal variable Z and you look at f plus capital Z * G this is a this is a function from the domain D to the field K at every point it gives you if you [clears throat] look at it it gives you a linear function in Z and we're going to view this as a received

word for a read Solomon code which read Solomon code it's the read Solomon code uh K over the field K this is a huge field you would never use this read solment code but it is a field we can think about we can use this we can think about this read solment code there is a D and uh the same domain D which is a subset of the field FQ but it's also a subset of K because K is even bigger than FQ and K the same degree and this F plus ZG is we view it as a receive word and the main idea is to decode it to a nearby code word of this read that's what uh so uh I have to talk about how we decode it but uh that's what uh the proof will try to do once we

have decoded it uh we will then see that oh actually the C any code word CFX in this read solved word of this form f plus z g uh is actually of the form capital f of x plus z * capital g of x. So it's actually a true polinomial in x plus z plus plus z * capital g of x and these f and g turn out to be the elements of the original red solment code that are close to f and g. This is the high level outline of uh how we are identifying the f the capital f and the capital g that end the true code words f and g which are close to little

f and little g and uh yes uh the crux is how to decode it. How do you decode it? Well, we will run a known decoding algorithm on this received word. This run is only in the proof. It's not an algorithm that anybody's done. Just the proof is going to imagine running a decoding algorithm on f plus z * g. As it's running it, it's going to try to do some things. We won't know whether to make some steps succeed. We will keep going back substituting capital z back to little z using this knowledge that f plus little z * g is close to c. This will help some this will help our decoder run and we

will show that this decoder does succeed in its run and end up with a with a nearby code. uh so in some sense algorithms give you a crit an algorithm for decoding gives you a criterion for whether a string is close to the code or not I mean it is also an efficiently implementable criterion uh but for the proof it's not relevant that's efficiently implemented it's just the fact that it is a criteria and it's one we can reason about so we so that's that's what happens here okay and so so when we prove our result for gamma less than delta over two it used the ber felt decoder when it proved for gamma less than johnson radius. It used the Gwami Sudan decoder for its own codes. Both of these are really beautiful algorithms.

If you haven't seen them, I highly recommend they both have I guess one page uh proofs and analysis and uh okay so now I'm going to say what changes and improves. Uh so so both these proofs uh are interp they use interpolation as their first step. The first step is to find a a polomial q of xy that vanishes on the given received word. So you're given some points uh and your received word is the graph of something that is supposed to be a polinomial and we interpolate a bied polinomial q of xy that vanishes on all the points of that graph. That is what the the first step of both these algorithms is in the bicam welch case the the polinomial q of xy is a very

special form. It has this error locator polinomial time y plus some other polinomial. That's what uh yeah and in the gurus sudan case it's much more it's it's a general by variability and uh when you run this interpolation uh in in BCI case the interpolated polinomial ended up having z degree being n and why was it because well we I mean the algorithms are there we just followed the instructions in those algorithms and uh it gave us n and uh And uh I guess in BCI case what uh I mean the the proof was following the instructions of the algorithm and not

questioning it because uh I mean it's a it's a famous algorithm. Uh good. So in in uh so what the change is now is that we will make this Zderee O of one and we will make it of one by by doing some mild modification to the interpolating uh to the interpolation problem. uh that mild modification will uh introduce extra slack. It will increase the x and y degrees to some extent and this will uh you will pay for it but it you pay for it in a very in a place where you don't care. So this is the best kind of payment.

Okay. So so now I don't want to dive into the details of this. What I will now do is give you a completely isolated self-contained example showing this phenomenon where something of degree omega n becomes some something of degree constant and uh I hope everybody can understand you don't need to know anything about anything uh for this okay good so here is the problem I have an n cross n +1 matrix whose i all of whose entries are degree one polinomials in the variable Z.

Okay. And I want to find the linear combination of the columns that equal zero. Okay. So that is in other words a vector V and I want to find a vector which I write over here and multiply by A and I get zero and I want that vector V to have as low degree as possible. This is what the question is and this is exactly the kind of question that uh we face in uh in the interpolation step of these algorithms and the question is how low a degree can you get and the answer is there's basically only one answer in general when you have an n + n +1 matrix there's if it was if it's not singular or sorry it is singular we

know this uh sorry if it was random or something like that there's only one formula for the unique vector in that kernel up to scaling And that formula is given by Kramer's rule. And it's the V that you get out of it is degree N. It is some determinant of it is a various N byN determinants of this matrix. That's what the V is. And there's no other choice. Uh good. So in this problem when you have an N cross N plus1 matrix when you're looking for a V in the kernel, the V has to have degree at most. This is one fun fact. Now I'm going to give you a slightly different uh question.

This is a second example. I have a matrix A which is not N cross N + 1 but it's N cross N + lambda N. So it's 1.1 N up here instead of N plus one. And now I ask you I want a V in the kernel. Now V is slightly longer, right? It has length N plus lambda N. Uh I want a V in the kernel with low degree. How low degree can you get? And one solution to this is zoom in on N plus one of these columns. So we know that they are linearly dependent and use Kramer's rule and it will give you a v with n + one nonzero entries all of them being degree at most end and the rest of

them zero but that is an inefficient use of everything given to us we have the ability to use more v more of the coordinates of v and maybe we should and the answer is we can have degree constant only l depending on lambda and in fact it's one over lambda the degree of v can be one over. It does not have anything to do with that. And this improvement in the Z degree improves things inside the group. And I can now prove this if we have it will take one slide. Uh I think I have time. Do I have time?

>> Go ahead. >> Oh great. Okay. So good. So I'm looking for a vector V of degree D uh which such that AV is zero. Okay. So I'm going to take each entry of V. there are n plus lambda n such entries and for each one there are d + one coefficients because a polinomial degree d has d+1 coefficients and I'm going to call all of these unknown variables. So they're totally d + 1 * n plus lambda and unknown coefficients. And yeah this is how the system looks and when I multiply this with this what I get here is a polomial each entry of this polinomial if this has degree d and all the entries of a have degree 1 uh the product will have degree d plus one. So we have these

polinomials sitting here which are the coefficients of that are formal linear combinations of the unknown coefficients here and there each one is degree d plus one. So each one has degree has d plus2 coefficients and there are n of them. So totally we're asking that n * d +2 different linear combinations of these variables end up being zero. So there are n * d +2 linear equations that we need to satisfy. There are d + 1 * n plus lambda and unknown coefficients. If the number of unknown coefficients is more than the number of linear equations, then there's a non-zero solution that makes this happen. The math of that is d + 1 * 1 + lambda n is greater than n * d +2. The n cancels and d can be 1 / lambda and so there is a non-zero solution. So,

so in this uh tiny toy example, but it's not very far from what happens inside the proof. uh we see that you can get drastically lower uh z degrees for your solutions provided uh uh provided you had a little bit of extra slack your your the system of linear equations that you're solving if it is slightly under uh if it's barely underdetermined then you can't do anything but if it's slightly underdetermined then you can do much more and what this translates to in in terms of the rest of the proof of uh of bicam file chaman is that you now have interpolated a polinomial of slightly higher x and y degrees. So for example

the error locator polinomial that you would get in the bicam files decoder uh it's not of degree the number of errors it is more than that it is maybe 1.1 times the number of errors or something like that and uh and this is also okay provided the number of errors is bounded away from half the minimum distance uh and one has to work through that and see that it all works okay great so I will also quickly state our main negative result we have a bunch bunch of negative results. Uh some are more main than others. So here is one which is maybe most uh relevant to the first part of the talk. Uh it is an example where proximity gaps need a to be large. Uh if you need uh if you want

proximity gaps uh you want a large. So this is in a slightly different setting from the previous talk uh uh where uh yeah so in the previous talk uh there were right we we were talking about distances very very close to the dis uh sorry we're talking about the radi gamma being very very close to the distance delta now we're going to talk about gamas which are substantially closer as close as the Johnson radius. So if you take uh fq with q even and you take d the evaluation domain to be a random f_sub_2 subspace of size about square root q and you look at uh polinom is a degree constant fraction* n okay and consider this code then uh the

statement is that if you want proximity gaps for c with loss smaller than 1/8 and this is quite loose cruise bound or rather I mean we're we're handle we're accepting quite a lot of loss and the radius of your proximity gaps is as big as the Johnson radius then you must have a almost all of Q and in that case q is about n² and uh yeah so so this means so more concretely there are two functions f and g such that f and jointly are 1/8 far. Oh, oh, sorry, not 1/8 far. They're gamma plus

1/8 far from the code. But almost every linear combination f plus zg is gamma close to the code almost everyone. So it's really uh disturbing, right? And so this is a summary of all the negative results that we have. So we have a whole bunch of assorted examples. The two I guess most interesting ones I would say are these two highlighted ones. Uh this was the one I just mentioned about where if you go up to the Johnson radius you need n². So we saw that if you want to if you're within the Johnson radius your Johnson radius minus ea then the a can be n but the moment you reach the johnson radius it

jumped to n square. That's what this says. And the next example shows that yeah you can start getting into the tow type behavior also for any constant tow uh also within not all the way at the distance delta but at some constant distance away from delta and so so bad things are happening for proximity gaps at least for Q being even and we have some other examples which work for Q being primes. uh none of these are these do not have constant proximity loss. they have uh uh they have little or one proximity loss and so I yeah the the previous talk of uh uh diamond and ruin is here and there's also the

simultaneous work of kes and stewart who proved this and uh yeah and there's some tight connection to this decoding radius which is also done by k and great so this is so I'm happy to take questions so I see one how sensitive are for to uh the size of the domain. Uh so the choice of domain they're very sensitive here it I mean it so it turns out so the counter examples the the ones up here they I work for most subspaces but the fact that it is a subspace is extremely important for this counter example to work and as we know that random evaluation domains have good proximity gaps so yeah so there's definitely the

structure definitely matters uh great let me look at other questions I'm jumping to the latest and I'm in backwards order let's say for binary the evaluation uh it doesn't hold for every subspace it only holds for a random subspace if that subspace happened to be a sub field it would not hold uh the proof requires it to be uh I mean the proof so almost all subspaces work but uh we know examples of subspaces where our method does not work namely sub fields definitely do not work and uh Um, yeah. Okay. So, any other questions?

>> Thank you, Swastik. I don't see any more questions, but I'll give a little bit of time for people to chime in. Uh, thank you so much for your presentation. Uh, I guess I have a a question. Um, so the the N squared for the Johnson bound was improved to N and E to 7 was improved to EA to the five. like do you feel like we can go uh further either in the the numerator or the denominator? >> Yes. So the n going down cannot happen because of the first example up here. Uh it cannot happen for all choices of delta because the first example up here. But so I think the most interesting question uh is uh maybe over prime fields there's some amazing

proximity gaps that happens just because you're working over a prime. So it's potential it's potentially true that prime fields have great proximity gaps. We have no substantial counter examples. uh uh let's say uh right I mean so for example Ben and Angus' conjecture uh apart yeah I mean that may be completely true over prime fields with absolutely no loss and I think that's potentially good that to the five I know Antonio Sanso has an improvement which possibly composes with this so it might become eater to the four and uh uh yeah that that shouldn't be fundamental I it should go down I expect the the exponent to be but n has to stay there.

>> I mean interestingly we haven't seen these uh binary fields be used that much in in in production. You know one of the reasons being that they may be less friendly to GPU acceleration like are you saying here that there's a there's a separation between binary fields and prime fields and maybe binary fields are less attractive from a proximity gas perspective. >> Uh yes I think so. So we we similarly know better list decoding counter examples over uh small characteristic fields compared to prime fields. Over prime fields we don't know that list decoding up to up to uh capacity. It could be that the list size is constant independent of n while uh while uh for for fields of small characteristic we

know that the list size has to grow. it has to be polinomially big and it uh like n square or n cube as you approach capacity. Uh so so in general yeah the listic coding and the proximity gaps behavior of small characteristic fields is worse than for prime fields and for prime fields potentially everything we ever hope for modulo the recent country samples is true. Alim is asking if there's um like numerical data or experimental uh behavior that kind of uh helps us analyze these proximity gaps I guess on maybe small small fields or small examples.

>> Yeah. So these things are very very tough to test because uh yeah this the search space is not just code words but it's yeah the search space is too much. I I don't have any uh way of uh doing it but I mean there there are I mean if you already make up a plan of how you want to make a proximity gap counter example maybe you can get a more directed search. So so we have some examples of this. So this this line over here about mer prime you can do it over basically any prime by searching for the appropriate subgroup with the right additive combinatorial property. uh but this was after you do you have to put in one idea before to narrow your search space otherwise there's not much computer search that can help it >> so maybe can I just ask a question

directly um swastik you mentioned so I I think you said that maybe that there's this ideal world where we have perfect proximity gaps for prime fields or something like that right I I guess I mean I I'm biased we we have our we have our revised conjecture I'm wondering why not just let that be the ideal world, right? Because there there's nothing about characteristic or domain. All all you have to do is not let your rates go to zero and your shortfalls go to zero. But isn't that isn't that enough for for most applications? Like wouldn't that be a suitable substitute for the proximity gap theorems that we have?

>> Oh, that's a good one. So, uh yes. So by everything we ever wanted is uh is that conjecture also with the exponent being one. Let's or or >> So it's a even stronger version of your conjecture where you inst insist on the exponent being one and then I think maybe you're okay. >> Interesting. >> So n to the one or maybe even n to the zero. I actually I don't know that it can't be n to the zero. Maybe it's a constant. Why not? So but over prime fees that could still survive. that cannot hold over small characteristics because of these kinds of examples and at least we know that the the exponent has to grow as the distance approaches uh uh one.

>> Yeah. Yeah. From a practical perspective, I think that the um the fact that n is now one for the Johnson bound, you know, actually when we were looking at going to proven security, we actually were looking at the unique decoding radius in part because n's one there and the sort of field size required for the Johnson bound was much larger. Um, so similarly, it would be great if n could stay one past the Johnson bomb. But just the fact that it's gone to n equals one for the Johnson bomb with this work is like a I think a big practical improvement on the proven security side.

>> Okay, that's great to hear >> for sure. >> And it could potentially go smaller than n to the one for prime fields. We do not know that uh you need n equals you even need the n to the one for prime phase. This is >> with with with with a small proximity loss, right? which I think is another great and interesting part of of your newer work is to allow proximity loss and this seems to really strengthen what you can get just for paying a small penalty there and you can get much better exponents and things like that. Right.

>> Right. And there's also this other diamond and grooving conjectivity which every linear code might be approximate up to half the minimum distance which is yeah that's an amazing possibility. >> Sure. We're out of time. Thank you so much, Swastik, uh, for this great presentation and, uh, you know, groundbreaking results. Um, congrats to those who made it to the end, 124 participants. We're going to have one last presentation and we're going to overflow a little bit. So, it's a 20-minut uh, discussion with uh, Jako on the proximity prize.

Giacomo Fenzi: proximity prize

>> Okay. Can you guys hear me? >> Yes. So we can see your screen. >> Okay, perfect. These are two good uh starting points I think for any presentation. Uh all right, guys. Okay, so no look, we've heard a lot about the new written results about proximity prices and so I want to give like a bit of an update of what me and Dan and some other people have been working on. Let's give like a little bit of like some context about these results end up actually touching the concrete side of it. So the so the actual proof system which are deployed. So okay let me just give a reminder at an eye level what this proximity price is. So this is like this initiative by the foundation in which we want to incentivize people to work on this beautiful question that

luckily people are already working on on the read Solomon conjecture about opportunity caps and listing. And you know one natural question you might ask is what is actually going on with the price. Uh what is the status of it? What have we been doing? H there's been a lot of progress not from our side at the moment. I affectionately I wanted to call this the messes mirato an epdomous miraabilist because it's been like just a week in which a bunch of wonderful papers have been come out about uh these exact problems. So this started from like the Ben and Angus result which was then followed by Elizabeth and Alistair giving like some

negative results on like uh where these opportunity gaps can hold in general. Then there was this wonderful paper by Goyal and Gwami about showing that in fact for like a wide families of codes you can actually achieve almost optimal um mutual created agreement up to capacity. Then there was a vastic paper that was just presented about both negative and positive result regarding rich solomon code proximity gaps. There was another paper today about list coding of rich solomon code with determinism which [clears throat] is also very exciting to see. And finally there was the paper not on print yet about from z and the others about

strengthening mutual creative agreement for all kind of polomial generators. So there's been a lot of things that happened. There's been uh a lot of result and the next slide I'm going to kind of figure out I'm going to present a bit how this fit in the landscape how they go and affect the efficiency of the proof systems and some of the things that we've done been doing in the committee regarding this um regarding the proximity price. So the the big overall TLDDR you know is that we're working on writing up the results. We're trying to formulate some watertight version of the conjectures which are consistent with what we know reality is after these new results and also present a survey on how these um uh on what is

the status of what things are known at the moment. This is the big part of it. Of course, when you get this many results coming in, you know, we've had to amend our paper a few times. So, me and Dan have been working hard and you'll get more news on that front from us. soon soon. So let me give you some background. I just want to do a deep a lot of other things. So uh I'm going to actually uh so we've been talking about error correcting codes and a lot of the question we're going to be asked for the proximity price actually relate more generally to linear codes and the parameters of interest that we really care about for these linear codes are

really uh um uh two three things. One of them is the minimum distance which and the reason why minimum distance of a code is important is because it translates to very far efficiency. So the larger a code the minimum distance of a code is the more efficient we can of the verifier which impact in particular proof size. We want also the uh two other metrics of interest to be small. This is the rate of the code which is the a measure of the amount of redundancy the code has and this translate in how much ashing the prover needs to do. So the the smaller the rate the more ashing the prover will need to do.

The other metric of interest is the encoding time which directly transmit to prover to prover time because the prover needs to actually perform at least one encoding and I'm going to be talking a lot more about list encoding soon. This is also another interesting feature about the code and the code that we care about in the survey for practical deployment is that of read Solomon codes which will be evaluation of polomials of some degree less than K on a domain of a certain size. So why more some motivation of why these codes have been very influential for like practical snarks is that they achieve like this optimal rate distance trade-off over large fields over large

alphabet which is the the Johnson sorry the singleton bound. So in particular the the trade-off between how much work the prover has to do and the efficiency that the verifier can hope to achieve is optimal over a large alphabet. Further the encoding times an FFT and so while the proving time is not linear FFTs have been widely studied there's a lot of amazing algorithm and they're also very paralyzable. So this is the code that like a very sweet spot in terms of being extremely efficient and also achieving very good trade-offs and since then this has been used in a variety of works since like their

introduction in 1960. Uh here I've tried to survey all the rich Solomon based protocols that are known in the literature. So as you can see there's a bunch of them and so studying this is the reason why we focus on the read Solomon case for this proximity price. Um yeah while you know even though these questions are interesting in general for a much wider class of codes. So what maybe following the tradition of what's been going on with um with other with the the fit start things I want to present like a small toy problem

that we've been playing around while formulating the conjecture that is a a minimal example of a protocol which if we with security uh encompasses basically all that we need for the security of like larger protocol. So this is going to be a simple protocol. Uh so the claim is that you have two uh messages f_sub_1 and f_sub_2. You have encoding of them and some uh linear constraint should hold over the over the messages.

So in particular these are in a sense they're linearly constrainted codes. So I have a an encoding which has need to satisfy some constraint. I have two pairs of them and I want to find a very tiny toy problem to actually um to actually test these constraints claims. So this is kind of the setting. I have my F1 F2. This will be encoding. So this green part uh represent the redundancy that I'm going to add and I have a pro verifier and the protocol that we want to analyze is a very simple one in which what will happen is that the verifier will ask the prover to provide a random combination of the two uh messages. So this gamma is the random combination

randomness. According to this randomness, the prover will send an f_sub_1 and an f_sub_2. the sample of S12 scale val randomness and then the verifier will sample some indices and it will check two things. Of course, it will check that this um that is uh the combined function satisfies the claim and further that when you encode the the message being sent by the prover and you can query F1 and F_sub_2 you actually um you actually have agreement And what I claim is that this protocol ends up being simple enough but uh you know in particular completeness for

example is obvious but it's actually the soundness analysis of it is sufficient to encompass basically the soundness of much more complicated protocols in particular things like war can be directly like analyzed by thinking about this building block. So this is the toy protocol is relatively simple and you can give like a very nice security analysis in which um you show that the security of this protocol is the this the union bound of these three terms. One term will be distance preservation one term will be related to the list size and one term will be related this one minus delta t. This is like the spot check error in a certain

sense. In fact, you can even show that this protocol satisfies much stronger properties. So you can show that this actually has a roundaround knowledge soundness even without assuming that the code is a error tolerant error decoder. And this analysis work for every delta. So if I give you like a bound on list size and a bound on the mutual corrected agreement error, I can show a bound on the on the on the distance. So about on the soundless error.

So let me let I'll tell you a bit about what these errors are in practice. So this so in particular what their behavior as the distance goes to to one and as an thing the efficient of this protocol is only is basically determined by what this parameter t is. So what's are interesting is that to turn to make the term one minus delta to the t as small as possible we we want to turn to increase delta to go towards one and the trick about choosing soundness for this protocol is to balance between the these errors in particular the MCA error will go to one as the delta goes to one

the le size error is even worse because this term will will actually blow up exponentially as the delta goes up to one while this ladder term will go to zero as delta goes to one. obtaining efficiency in this protocol is basically finding the delicate balance between minimizing t and maintaining all the other errors small enough. And this toy problem is what we're going to be using to kind of inform our decision what problem to think about for the proximity price and what kind of regimes we can tolerate.

Good. So this is our simple toy problem and I'm going to tell you a bit about the regimes of interest. We're going to be we have heard a lot about it today but I'm going to do a little bit. So I'm going to in this case fits I'm going to fix a rate is equal to one half because this is the setting which is more of practical interest. I'm going to take this line. This is the settings of delta that we can uh choose in the previous protocol and now I'm going to partition it in regimes according to where we tend to have sharp phase transitions in these errors before. So the first area that I want to talk about is this part here.

This is the unique decoding radius which spans from delta is equal to 0 to 0.25. The next regime is that of the Johnson bound. The Johnson bound for rate is equal to one half is between 0.25 and 0.29 in this regime of interest. Then there's this new area which is after Johnson which I've put here like exundra. This is like the area where we don't have probable guarantees but we nonetheless would like to be there for like uh for efficiency and there's also another part area here which is the 1.5 Johnson bound but for

simplicity since we're in the case where rate is equal to 1/2 this is covered by unique decoding so we don't have to think about this for now okay so what we know is that in fact there's a um an area a red area which is where the sorry I cannot even see it because I have give me Just a second. Okay, there's an area which is this 0 between 0.5 and 0.49 which is where the combinatorial attacks of uh of Ben, Angus, Elizabeth and Alistister and to apply. So the area which the conjecture is really concerned is this uh area in the middle which I'm going to call informally the capacity regime for now is between the Johnson bound and where

we know that these attacks end up applying tell you a bit about what concretely this ends up this ends up mattering for like systems the rumbaron error 1 minus l to the t is what informs the number of queries that the protocol needs to do. So for the toy protocol you can see that this is the number of errors that you the number of queries that you need to do and particularly CB this is the optimistic bound in fact it will be larger due to angles Ben Elizabeth analysis attack and with proof systems such as um stir and war the argument size is dominated by this tclele path and basically you

can use this to estimate what the proof size of the protocol ends up being. So as you can see the uh the argument size uh decreases when we move towards more aggressive regimes. Good. So these are the regimes that we are only is that uh we're interested in. Good question so far. I don't know if I cannot see the chat if there's anything but uh let me know if there are questions. >> Uh there is one question. Um, if we rank the difficulty of the computer science open questions from 1 to 10 with P versus NP being 10, how hard is the proximity prize question?

>> Uh, I would say that u since since the new relation between list coding and and created agreement, this seems to be at least as hard as this coding for it Solomon codes. And this is a very hard question. So, I'm going to give it like maybe an eight or a seven. Okay. Wow. Is it because list decodability has been open for many decades? >> Indeed. Yeah. >> Okay. Got it.

>> But maybe seven is good because there's been progress towards it while for other problems we don't even know where to start. Okay, good. So let me tell you a bit about list size which is so what we're planning on doing and at the end I think this will be good place to discuss this is to conjecture two problems in this proport size well uh the question that I am asking is that I have some uh some word and I know that within like distance delta over C over two. There will be at most one single ball nearby. But once my

delta increases past this point, there might be many more balls and many more other more code words nearby. The list size question is about giving a bound for how large this list ends up being. And the intuition why we did this is because list size figures out in the toy problem and it ends up spoiling the soundness error. Particularly these are two places. One of the places where it appears is in the out samples and the other part is this constraint fold which also appear in the toy problem.

Another motivation for why this list size is an interesting problem to study is that we can most likely even if CA does not hold up to capacity. We should be able to uh obtain a slightly less efficient version of our protocols which only rely on leoding up to conjecture. So in a sense is the most fundamental of the two assumptions that we are this conjecture that we will be conjecturing and in fact thanks to the recent result by Alistister and um and Elizabeth and also from the new paper that came out this morning it does seem that like progress in corator agreement will also imply progress in in list size. So this is a um so there's a very tight relation

between these uh these two problems as I think will also be uh evident when we look back at the regimes later on again I'm going to be focusing with Solomon code but this is a exceptionally interesting question to ask also for general linear codes or even for array codes and standard codes in general. So what is known is that something quite similar to what we actually know in uh for creative agreement. So in unique coding by definition the list size is a single close word closed code word up to Johnson bound we know that the the the number of code words will also be small will be roughly linear in the evaluation domain size.

We know in a similar area to where Alistister's Elizabeth Angus and Ben attacks old that this list size will grow to a super polomial size and there's some questions about what happens in this area in the exoness one that I was talking about before and our hope is that in this area the number of code words that you end up having is something that we can handle. So we need the list size to be small with respect to the size of the field. So if this were is a small polomial in the evolution domain size is something that in the sound error we will be able to handle and there are some limitations for what we can achieve here. So for example if the for rich Solomon code over full domain the list side ends up being super

polomial not much after Johnson bound and when we're getting close to capacity there are also some other limits similar to what angles with the recent attacks on which Solomon code on MDS codes end up showing on the on the up front we know that in fact for some uh for some families of code in particularly randomly punctured solmon code over a sufficiently large alphabet with high probability we expect this list to be small and in fact this list to be optimally small which is really exciting.

What the situation with this preservation well I'm going to skip this slide because we talked about a lot about different notions of um of correct agreement but what is known is very similar to the case of the list coding. So if we look at the previous settings we know that uh we know that below uh minimum distance over three we have these errors. This was known from like early work such as legero. Then from the previous work in a in a proximity gaps we know that Solomon code up to the UDR we get linear error and in fact thanks to the new result this can be further improved.

We further know that um up to uh Johnson bound we managed to get a mutual creator agreement with a quadratic error and we also know from the attacks from the attack that I was mentioning before that after when you're close enough to see to capacity the error material agreement becomes essentially one further from just a few minutes ago we know now that the error from the UDR to JB area can actually be improved to linear dependency and the question that we ask similar to the list decoding case is what happens in this area between where the attacks apply and when the and the Johnson where we know there is also

improvables from the Johnson bout and again there are there are some limitations that we need to do most notably the new attacks that were presented there were some u there were some limitation on full domain with Solomon codes and there are some new limit ation from the paper also done but also thanks to like some other development we actually know that a similar situation to what we have in list holds up in the for the forum creator agreement in that random codes end up having new credit agreement with almost optimal error so linear error in the field size h up to very close to capacity as long

as the alphabet is large enough so this is extremely exciting to see good so this kind like the status of what we know after the past week which has been very hectic time of updating these slides and yes and the way I want to interpret this uh original result this GG25 result is that morally we are matching whatever we knew about this decoding up to capacity uh translating it to mutual creator agreement which is a very exciting uh development so just to conclude uh I think I'm almost right on So, it's been really exciting and a privilege to see all the progress so far that we've seen on the Fury side. And uh honestly, when uh when this I wasn't

expecting this much progress in so little time. This has been extremely hectic but extremely exciting. So, we're going to be uh we're going to be trying to stabilize the conjecture the survey soon of what's been going on to and hopefully we don't really get a paper every day for the past month because that's too much work. And I want to highlight some other proportionate price related efforts that we've been going on in the in the in the past months and particularly spurred from like the Cambridge workshop that has been organized by Justin and Will. So one thing is this numerical efforts that's been spared by Antonio on trying to for very small field size evaluation domains trying to numerically check

whether corrected agreement holds or find contour samples. So this has been exciting work where I think uh it should be you know we are looking for more help. I think there's a lot of ideas that are floating about and not enough time to implement all of them. So having help on this would be extremely exciting. Further uh one thing that we won't plan to really include with the proin price is to sign energize with the formal verification efforts that have been going on at the EVF at the AF. So in that there's also a lot of work about formalizing the statement of the conjectures and hopefully formalizing proofs and disproof therein. So this has been kind of like a Russian update on all that going on and I want to thank uh

Justin Bened Wagner and the OF for all the support for this proximity prize. It's really been a privilege to be able to uh see all the progress has been spurred by this and I think yeah I think now I don't know how much people have to go but I'm happy to like take question discussions about the format of the prize the conjectures and everything. >> Thank you so much Jako. Um, any questions from the audience? And I must also say it's been absolute pleasure working with you. Um, and I'm I'm so pleased that you're you're part of the the the jury.

Um, I guess uh I have a question for for Dan, who might still be on the call. I'm not sure if he made it. Uh, >> yeah. Yeah, I'm here. >> Okay, great. Um I guess Dan, do you have a few thoughts on the proximity prize and what's your take? I guess >> um yeah. Yeah, of course. Um I think the main thing is uh just uh hang hang tight in that uh we haven't formalized the actual conjectures yet and of course all the recent work has been uh causing some delays but that's this is fine. It's all super interesting. Um um yeah so I guess the one of the issues that came out of discussion today is also the the fact

that the exact field that we're using should also be incorporated into the into these uh uh challenge questions in the prize. So you know you'll see some of that in there as well. >> Right. And the exact evaluation domain as well potentially. >> Exactly. Yeah, nice. >> Can I ask you a question? So, how will you make sure that um if you specify particular parameters, particular field, you you're not kind of uh missing the most interesting results by oversp specification of the the

challenge problem. Challenge problems. Uh sorry, could you could you repeat that? >> Yeah. Um uh there there's a risk of kind of oversp specifying the um challenge problems um and sort of the resolve for that field but the but then implementers move to um another set of fields that avoid attacks. How will you avoid that problem? >> Yeah, I think that I think the challenge problems are going to be quite general.

So it will [clears throat] it will encompass basically um you know all the the the the entire design space uh and the goal so there'll be challenge problems that are very generic and then even we've been debating whether uh things should be asmtoic or concrete uh so we'll have different flavors of the of the challenge problems but uh I I wouldn't worry about this Dar it's going to be quite generic and it will encompass the entire design space And I will also maybe mention that currently I know that a lot of the techniques that we've been using for like um examples and proofs apart from the binary field case do seem to be very field agnostic seem to be very kind of

hard to to use a structure of the field efficiently when we're talking about large prime fields. Uh so the the hope is that if this trend continues is that uh any result that we get will be general enough to encompass a wide variety of fields as well. Though I have to say it would be really quite bizarre and really interesting if it turns out that there's like a very specific family of fields say a specific family of primes for which proximity gaps are especially good. Yeah, that would be that would be quite quite interesting.

The techniques we have today don't seem to go in that direction. Uh but that be that might be because our techniques are relatively weak. Uh so just throwing it out there that it might be interesting to look even for specific primes and specific domains where things are better. One question in the chat. How do you imagine the 1 million prize to be split among various partial results and the full result if and when it is proven? >> That that sounds like a a question for you Justin. Um [laughter] I mean the way that I think about it is that uh you know we have this this area of uncertainty uh stuck between the

positive and the negative results and we need to kind of find a a a way to quantify you know improvements. Um and you know roughly speaking you know the new negative results improve things by let's say 3%. on on the negative side of things. So like morally speaking, you know, that should be getting let's roughly 3% of the of the 1 million prize. Uh and hopefully, you know, we can we can squeeze this gap all the way to zero and then allocate the the the full 1 million prize and and have a basically a full full understanding of uh of these mathematical foundations.

Um but yeah, ultimately I'm I think we'll be delegating the the the rules uh to to to the the panel of judges uh which right now is is Jakan. >> Yeah, it's a good answer. Will there be uh kind of a um a process to handle disputes? Because um it's possible like the one set of researchers will claim they've solved the problem, another set of researchers will will dispute that. Um what happens then?

Uh, do you want me to answer this? >> Uh, honestly, this is still worked out. I think there have been other prizes in the past, like I guess the Millennium Prize is a good example. >> We'll probably follow uh when it comes to the actual rule, we might just follow what other prizes have have done. >> Okay. Yeah. >> Okay. Uh we've gone uh 2 hours and 20 minutes. Thank you so much uh to the the 90 people who've made it so far and see you soon for call number.

>> Real quick, >> go ahead. >> I had a just a quick note for those of you that are coming to Ether State. I dropped a note in the chat, but there's only 250 seats. There's about 500 people on the waiting list. So try to get there between 9:30 and 10 for guaranteed admission if you've been approved. If you've if you're on the wait list and you have attended an ethru call, we try to match those names up after each call. We've got a priority weight list and so we'll kind of like start letting those people in from 10 to 10:30. Um, so yeah, just come early. We're going to have coffee early. You can network, take advantage of the time, and we just have hope to have like a lot of contributors and a lot of like passionate uh

speculator or spectators in the audience. um and just try to keep it very high quality uh group and and signal. We're really looking forward to it. >> Perfect. Thank you. Well, it's going to be the one of the best events uh of Dev Connect. Bye everyone. Have a great day. >> Bye guys. Five.