WEBVTT Kind: captions Language: en 00:00:01.160 --> 00:00:06.690 align:start position:0% [Music] 00:00:06.690 --> 00:00:06.700 align:start position:0% 00:00:06.700 --> 00:00:09.750 align:start position:0% [Music] 00:00:09.750 --> 00:00:09.760 align:start position:0% [Music] 00:00:09.760 --> 00:00:11.749 align:start position:0% [Music] uh<00:00:09.920> hello<00:00:10.240> everyone<00:00:10.960> uh<00:00:11.080> thank<00:00:11.240> you<00:00:11.400> so<00:00:11.559> much 00:00:11.749 --> 00:00:11.759 align:start position:0% uh hello everyone uh thank you so much 00:00:11.759 --> 00:00:14.869 align:start position:0% uh hello everyone uh thank you so much for<00:00:12.000> coming<00:00:12.280> to<00:00:12.440> my<00:00:12.639> talk<00:00:13.639> um<00:00:13.839> today<00:00:14.200> I'm<00:00:14.360> going 00:00:14.869 --> 00:00:14.879 align:start position:0% for coming to my talk um today I'm going 00:00:14.879 --> 00:00:18.670 align:start position:0% for coming to my talk um today I'm going to<00:00:15.879> uh<00:00:16.359> have<00:00:16.480> a<00:00:16.640> talk<00:00:16.960> about<00:00:17.520> the<00:00:17.920> SE<00:00:18.279> lookup 00:00:18.670 --> 00:00:18.680 align:start position:0% to uh have a talk about the SE lookup 00:00:18.680 --> 00:00:20.830 align:start position:0% to uh have a talk about the SE lookup the<00:00:18.800> lookup<00:00:19.199> argument<00:00:19.560> based<00:00:19.840> on<00:00:20.680> uh 00:00:20.830 --> 00:00:20.840 align:start position:0% the lookup argument based on uh 00:00:20.840 --> 00:00:21.830 align:start position:0% the lookup argument based on uh composite 00:00:21.830 --> 00:00:21.840 align:start position:0% composite 00:00:21.840 --> 00:00:24.230 align:start position:0% composite function<00:00:22.840> um<00:00:23.039> actually<00:00:23.400> this<00:00:23.519> is<00:00:23.640> the<00:00:23.800> first 00:00:24.230 --> 00:00:24.240 align:start position:0% function um actually this is the first 00:00:24.240 --> 00:00:27.470 align:start position:0% function um actually this is the first time<00:00:25.240> uh<00:00:25.519> that<00:00:26.119> first<00:00:26.400> time<00:00:26.599> ever<00:00:26.880> that<00:00:27.039> we<00:00:27.199> are 00:00:27.470 --> 00:00:27.480 align:start position:0% time uh that first time ever that we are 00:00:27.480 --> 00:00:31.189 align:start position:0% time uh that first time ever that we are presenting<00:00:27.960> our<00:00:28.599> work<00:00:29.599> uh<00:00:30.119> uh<00:00:30.240> so<00:00:30.439> my<00:00:30.599> name<00:00:30.800> is 00:00:31.189 --> 00:00:31.199 align:start position:0% presenting our work uh uh so my name is 00:00:31.199 --> 00:00:34.990 align:start position:0% presenting our work uh uh so my name is Li<00:00:31.960> and<00:00:32.239> researcher<00:00:32.759> at 00:00:34.990 --> 00:00:35.000 align:start position:0% 00:00:35.000 --> 00:00:37.389 align:start position:0% PSC<00:00:36.000> this<00:00:36.160> is<00:00:36.320> a<00:00:36.520> joint<00:00:36.800> work<00:00:37.079> with<00:00:37.239> my 00:00:37.389 --> 00:00:37.399 align:start position:0% PSC this is a joint work with my 00:00:37.399 --> 00:00:41.069 align:start position:0% PSC this is a joint work with my colleagues<00:00:37.840> so<00:00:38.760> I<00:00:38.920> did<00:00:39.280> this<00:00:39.480> work<00:00:39.879> with<00:00:40.239> suan 00:00:41.069 --> 00:00:41.079 align:start position:0% colleagues so I did this work with suan 00:00:41.079 --> 00:00:43.029 align:start position:0% colleagues so I did this work with suan and<00:00:41.320> dhun 00:00:43.029 --> 00:00:43.039 align:start position:0% and dhun 00:00:43.039 --> 00:00:46.590 align:start position:0% and dhun together<00:00:44.039> and<00:00:44.239> the<00:00:44.399> summary<00:00:45.120> is<00:00:45.440> that<00:00:46.440> uh 00:00:46.590 --> 00:00:46.600 align:start position:0% together and the summary is that uh 00:00:46.600 --> 00:00:51.590 align:start position:0% together and the summary is that uh given<00:00:46.920> that<00:00:47.079> we<00:00:47.280> have<00:00:47.520> a<00:00:48.360> uh<00:00:49.000> n<00:00:49.760> size<00:00:50.039> of<00:00:50.600> table 00:00:51.590 --> 00:00:51.600 align:start position:0% given that we have a uh n size of table 00:00:51.600 --> 00:00:54.470 align:start position:0% given that we have a uh n size of table and<00:00:51.879> a<00:00:52.320> witness<00:00:52.800> with<00:00:53.079> size<00:00:53.399> of 00:00:54.470 --> 00:00:54.480 align:start position:0% and a witness with size of 00:00:54.480 --> 00:00:57.990 align:start position:0% and a witness with size of M<00:00:55.480> then<00:00:55.920> if<00:00:56.920> uh 00:00:57.990 --> 00:00:58.000 align:start position:0% M then if uh 00:00:58.000 --> 00:01:01.310 align:start position:0% M then if uh the<00:00:59.000> this<00:00:59.199> size<00:00:59.480> is<00:00:59.600> much<00:01:00.160> larger<00:01:00.640> than<00:01:00.879> the 00:01:01.310 --> 00:01:01.320 align:start position:0% the this size is much larger than the 00:01:01.320 --> 00:01:06.390 align:start position:0% the this size is much larger than the table<00:01:01.760> size<00:01:02.559> we<00:01:02.760> can<00:01:03.000> accomplish<00:01:03.760> a<00:01:04.760> o<00:01:05.640> of<00:01:06.040> log 00:01:06.390 --> 00:01:06.400 align:start position:0% table size we can accomplish a o of log 00:01:06.400 --> 00:01:10.510 align:start position:0% table size we can accomplish a o of log squ<00:01:06.799> M<00:01:07.400> time<00:01:07.799> complexity<00:01:08.799> to<00:01:09.200> the<00:01:09.360> look<00:01:09.520> of 00:01:10.510 --> 00:01:10.520 align:start position:0% squ M time complexity to the look of 00:01:10.520 --> 00:01:12.710 align:start position:0% squ M time complexity to the look of argument<00:01:11.520> uh<00:01:11.640> I'm<00:01:11.759> going<00:01:11.840> to<00:01:12.000> explain<00:01:12.439> more 00:01:12.710 --> 00:01:12.720 align:start position:0% argument uh I'm going to explain more 00:01:12.720 --> 00:01:15.510 align:start position:0% argument uh I'm going to explain more about<00:01:13.360> uh<00:01:13.520> how<00:01:13.640> we<00:01:13.840> achieve 00:01:15.510 --> 00:01:15.520 align:start position:0% about uh how we achieve 00:01:15.520 --> 00:01:18.789 align:start position:0% about uh how we achieve this<00:01:16.520> uh<00:01:16.920> first<00:01:17.119> of<00:01:17.280> all<00:01:17.720> I<00:01:18.040> would<00:01:18.240> love<00:01:18.400> to 00:01:18.789 --> 00:01:18.799 align:start position:0% this uh first of all I would love to 00:01:18.799 --> 00:01:21.630 align:start position:0% this uh first of all I would love to introduce<00:01:19.520> uh<00:01:19.680> where<00:01:19.960> we<00:01:20.560> got<00:01:20.880> The 00:01:21.630 --> 00:01:21.640 align:start position:0% introduce uh where we got The 00:01:21.640 --> 00:01:24.350 align:start position:0% introduce uh where we got The Inspirations<00:01:22.640> the<00:01:22.840> first<00:01:23.040> one<00:01:23.280> was<00:01:23.520> about<00:01:23.799> the 00:01:24.350 --> 00:01:24.360 align:start position:0% Inspirations the first one was about the 00:01:24.360 --> 00:01:29.270 align:start position:0% Inspirations the first one was about the gkr<00:01:25.680> because<00:01:26.680> uh<00:01:26.960> we<00:01:27.360> notice<00:01:27.880> that<00:01:28.079> gkr<00:01:28.799> is<00:01:28.960> a 00:01:29.270 --> 00:01:29.280 align:start position:0% gkr because uh we notice that gkr is a 00:01:29.280 --> 00:01:33.590 align:start position:0% gkr because uh we notice that gkr is a very<00:01:30.000> a<00:01:30.400> one<00:01:31.000> unique<00:01:32.000> um<00:01:32.799> version<00:01:33.360> of 00:01:33.590 --> 00:01:33.600 align:start position:0% very a one unique um version of 00:01:33.600 --> 00:01:35.469 align:start position:0% very a one unique um version of composite 00:01:35.469 --> 00:01:35.479 align:start position:0% composite 00:01:35.479 --> 00:01:38.350 align:start position:0% composite function<00:01:36.479> and<00:01:36.720> the<00:01:36.880> second<00:01:37.200> was<00:01:37.439> about<00:01:37.960> hyper 00:01:38.350 --> 00:01:38.360 align:start position:0% function and the second was about hyper 00:01:38.360 --> 00:01:41.789 align:start position:0% function and the second was about hyper plong<00:01:39.079> poop2<00:01:40.079> the<00:01:40.240> permutation<00:01:40.799> argument 00:01:41.789 --> 00:01:41.799 align:start position:0% plong poop2 the permutation argument 00:01:41.799 --> 00:01:44.630 align:start position:0% plong poop2 the permutation argument poop2<00:01:42.799> uh<00:01:43.079> it<00:01:43.360> is<00:01:43.600> also<00:01:43.880> using<00:01:44.200> kind<00:01:44.399> of<00:01:44.479> a 00:01:44.630 --> 00:01:44.640 align:start position:0% poop2 uh it is also using kind of a 00:01:44.640 --> 00:01:47.030 align:start position:0% poop2 uh it is also using kind of a composite<00:01:45.119> function<00:01:46.040> it<00:01:46.159> was<00:01:46.320> very<00:01:46.520> inspiring 00:01:47.030 --> 00:01:47.040 align:start position:0% composite function it was very inspiring 00:01:47.040 --> 00:01:49.429 align:start position:0% composite function it was very inspiring for<00:01:47.200> me<00:01:47.479> to<00:01:48.360> uh<00:01:48.560> think<00:01:48.799> about<00:01:48.960> the<00:01:49.079> local 00:01:49.429 --> 00:01:49.439 align:start position:0% for me to uh think about the local 00:01:49.439 --> 00:01:50.789 align:start position:0% for me to uh think about the local argument<00:01:49.799> using 00:01:50.789 --> 00:01:50.799 align:start position:0% argument using 00:01:50.799 --> 00:01:55.749 align:start position:0% argument using that<00:01:51.799> uh<00:01:52.240> and<00:01:53.280> so<00:01:54.280> using<00:01:54.719> that<00:01:55.040> we<00:01:55.159> are<00:01:55.439> using 00:01:55.749 --> 00:01:55.759 align:start position:0% that uh and so using that we are using 00:01:55.759 --> 00:01:57.830 align:start position:0% that uh and so using that we are using some<00:01:56.000> compettive<00:01:56.520> function<00:01:57.280> just<00:01:57.479> like<00:01:57.680> in 00:01:57.830 --> 00:01:57.840 align:start position:0% some compettive function just like in 00:01:57.840 --> 00:02:01.069 align:start position:0% some compettive function just like in gk's<00:01:58.439> each<00:01:58.759> layers<00:02:00.079> actually<00:02:00.479> in<00:02:00.600> our<00:02:00.840> case<00:02:01.000> we 00:02:01.069 --> 00:02:01.079 align:start position:0% gk's each layers actually in our case we 00:02:01.079 --> 00:02:03.149 align:start position:0% gk's each layers actually in our case we are<00:02:01.200> using<00:02:01.399> only<00:02:01.600> one<00:02:01.799> layer<00:02:02.759> and<00:02:02.920> we<00:02:03.000> are 00:02:03.149 --> 00:02:03.159 align:start position:0% are using only one layer and we are 00:02:03.159 --> 00:02:07.109 align:start position:0% are using only one layer and we are achieving<00:02:03.560> the<00:02:03.719> O<00:02:04.320> of<00:02:04.960> uh<00:02:05.159> log<00:02:05.759> squared<00:02:06.600> and 00:02:07.109 --> 00:02:07.119 align:start position:0% achieving the O of uh log squared and 00:02:07.119 --> 00:02:09.669 align:start position:0% achieving the O of uh log squared and time 00:02:09.669 --> 00:02:09.679 align:start position:0% 00:02:09.679 --> 00:02:13.550 align:start position:0% complexity<00:02:10.679> uh<00:02:11.520> so<00:02:12.000> first<00:02:12.480> let's<00:02:12.920> discuss 00:02:13.550 --> 00:02:13.560 align:start position:0% complexity uh so first let's discuss 00:02:13.560 --> 00:02:16.470 align:start position:0% complexity uh so first let's discuss about<00:02:14.160> the<00:02:14.519> objective<00:02:15.360> and<00:02:15.879> let's<00:02:16.360> understand 00:02:16.470 --> 00:02:16.480 align:start position:0% about the objective and let's understand 00:02:16.480 --> 00:02:17.830 align:start position:0% about the objective and let's understand the<00:02:16.599> current 00:02:17.830 --> 00:02:17.840 align:start position:0% the current 00:02:17.840 --> 00:02:20.550 align:start position:0% the current situation<00:02:18.840> that<00:02:19.280> we<00:02:19.480> have<00:02:19.720> two 00:02:20.550 --> 00:02:20.560 align:start position:0% situation that we have two 00:02:20.560 --> 00:02:23.949 align:start position:0% situation that we have two sets<00:02:21.560> uh<00:02:21.800> first<00:02:22.040> one<00:02:22.200> is<00:02:22.360> about<00:02:22.720> witness<00:02:23.720> and 00:02:23.949 --> 00:02:23.959 align:start position:0% sets uh first one is about witness and 00:02:23.959 --> 00:02:26.350 align:start position:0% sets uh first one is about witness and the<00:02:24.080> second<00:02:24.360> is<00:02:24.519> about<00:02:24.879> the<00:02:25.640> elements<00:02:26.080> of<00:02:26.200> the 00:02:26.350 --> 00:02:26.360 align:start position:0% the second is about the elements of the 00:02:26.360 --> 00:02:27.750 align:start position:0% the second is about the elements of the given 00:02:27.750 --> 00:02:27.760 align:start position:0% given 00:02:27.760 --> 00:02:31.470 align:start position:0% given table<00:02:28.760> and<00:02:28.920> our<00:02:29.200> goal<00:02:29.680> is<00:02:30.319> is<00:02:30.480> to<00:02:30.720> prove<00:02:31.080> that 00:02:31.470 --> 00:02:31.480 align:start position:0% table and our goal is is to prove that 00:02:31.480 --> 00:02:35.710 align:start position:0% table and our goal is is to prove that for<00:02:31.800> every<00:02:32.200> element<00:02:32.840> in<00:02:33.560> uh<00:02:33.760> W<00:02:34.760> is<00:02:35.040> also<00:02:35.400> an 00:02:35.710 --> 00:02:35.720 align:start position:0% for every element in uh W is also an 00:02:35.720 --> 00:02:37.790 align:start position:0% for every element in uh W is also an element<00:02:36.560> of<00:02:36.840> a 00:02:37.790 --> 00:02:37.800 align:start position:0% element of a 00:02:37.800 --> 00:02:40.790 align:start position:0% element of a table<00:02:38.800> in<00:02:38.959> other<00:02:39.200> words<00:02:39.800> uh<00:02:39.879> we<00:02:40.000> are<00:02:40.200> verifying 00:02:40.790 --> 00:02:40.800 align:start position:0% table in other words uh we are verifying 00:02:40.800 --> 00:02:44.509 align:start position:0% table in other words uh we are verifying that<00:02:41.200> each<00:02:41.519> witness<00:02:42.239> element<00:02:43.239> is<00:02:43.560> contained 00:02:44.509 --> 00:02:44.519 align:start position:0% that each witness element is contained 00:02:44.519 --> 00:02:47.710 align:start position:0% that each witness element is contained uh<00:02:44.640> within<00:02:44.920> the 00:02:47.710 --> 00:02:47.720 align:start position:0% 00:02:47.720 --> 00:02:50.430 align:start position:0% table<00:02:48.720> and<00:02:49.000> this<00:02:49.200> implies<00:02:49.720> that<00:02:49.920> the<00:02:50.080> set<00:02:50.280> of 00:02:50.430 --> 00:02:50.440 align:start position:0% table and this implies that the set of 00:02:50.440 --> 00:02:54.790 align:start position:0% table and this implies that the set of witness<00:02:51.120> W<00:02:51.879> is<00:02:52.040> a<00:02:52.239> subset<00:02:52.680> of<00:02:52.879> the<00:02:53.239> table 00:02:54.790 --> 00:02:54.800 align:start position:0% witness W is a subset of the table 00:02:54.800 --> 00:03:00.190 align:start position:0% witness W is a subset of the table t<00:02:55.800> uh<00:02:56.159> okay<00:02:57.040> and<00:02:58.040> before<00:02:58.360> we<00:02:58.599> go<00:02:59.360> uh<00:02:59.519> deep<00:02:59.920> dive 00:03:00.190 --> 00:03:00.200 align:start position:0% t uh okay and before we go uh deep dive 00:03:00.200 --> 00:03:02.830 align:start position:0% t uh okay and before we go uh deep dive into<00:03:00.480> the<00:03:01.000> lookup<00:03:01.440> argument<00:03:02.040> C<00:03:02.400> lookup 00:03:02.830 --> 00:03:02.840 align:start position:0% into the lookup argument C lookup 00:03:02.840 --> 00:03:05.190 align:start position:0% into the lookup argument C lookup argument<00:03:03.480> protocol<00:03:04.480> I<00:03:04.560> would<00:03:04.760> love<00:03:04.959> to 00:03:05.190 --> 00:03:05.200 align:start position:0% argument protocol I would love to 00:03:05.200 --> 00:03:07.509 align:start position:0% argument protocol I would love to introduce<00:03:05.799> the<00:03:06.159> main<00:03:06.680> uh<00:03:06.799> use<00:03:07.159> case<00:03:07.360> the 00:03:07.509 --> 00:03:07.519 align:start position:0% introduce the main uh use case the 00:03:07.519 --> 00:03:10.070 align:start position:0% introduce the main uh use case the interesting<00:03:08.159> use<00:03:08.560> case<00:03:09.440> uh<00:03:09.599> if<00:03:09.680> you<00:03:09.840> have<00:03:09.959> the 00:03:10.070 --> 00:03:10.080 align:start position:0% interesting use case uh if you have the 00:03:10.080 --> 00:03:11.710 align:start position:0% interesting use case uh if you have the look<00:03:10.319> of 00:03:11.710 --> 00:03:11.720 align:start position:0% look of 00:03:11.720 --> 00:03:14.750 align:start position:0% look of argument<00:03:12.720> so<00:03:13.319> what<00:03:13.480> if<00:03:13.640> you<00:03:13.840> define<00:03:14.440> each 00:03:14.750 --> 00:03:14.760 align:start position:0% argument so what if you define each 00:03:14.760 --> 00:03:19.270 align:start position:0% argument so what if you define each witness<00:03:15.319> W<00:03:16.319> as<00:03:16.480> an<00:03:16.760> encoding<00:03:17.640> of<00:03:18.280> function 00:03:19.270 --> 00:03:19.280 align:start position:0% witness W as an encoding of function 00:03:19.280 --> 00:03:22.949 align:start position:0% witness W as an encoding of function along<00:03:19.640> with<00:03:19.879> its<00:03:20.159> input<00:03:20.799> and<00:03:21.360> output 00:03:22.949 --> 00:03:22.959 align:start position:0% along with its input and output 00:03:22.959 --> 00:03:27.509 align:start position:0% along with its input and output result<00:03:24.000> and<00:03:25.000> let<00:03:25.560> T<00:03:26.080> be<00:03:26.319> a<00:03:26.599> predefined 00:03:27.509 --> 00:03:27.519 align:start position:0% result and let T be a predefined 00:03:27.519 --> 00:03:30.589 align:start position:0% result and let T be a predefined computations 00:03:30.589 --> 00:03:30.599 align:start position:0% 00:03:30.599 --> 00:03:33.350 align:start position:0% then<00:03:30.799> we<00:03:30.920> can<00:03:31.120> formally<00:03:31.680> verify<00:03:32.239> that<00:03:32.480> f<00:03:32.720> ofx 00:03:33.350 --> 00:03:33.360 align:start position:0% then we can formally verify that f ofx 00:03:33.360 --> 00:03:37.149 align:start position:0% then we can formally verify that f ofx equals<00:03:33.760> to<00:03:34.000> Y<00:03:34.840> always<00:03:35.200> holds<00:03:36.000> true<00:03:37.000> uh 00:03:37.149 --> 00:03:37.159 align:start position:0% equals to Y always holds true uh 00:03:37.159 --> 00:03:39.390 align:start position:0% equals to Y always holds true uh provided<00:03:37.720> that<00:03:37.959> the<00:03:38.080> witness<00:03:38.519> is<00:03:38.640> a<00:03:38.799> subset<00:03:39.200> of 00:03:39.390 --> 00:03:39.400 align:start position:0% provided that the witness is a subset of 00:03:39.400 --> 00:03:44.869 align:start position:0% provided that the witness is a subset of the<00:03:40.239> predefined 00:03:44.869 --> 00:03:44.879 align:start position:0% 00:03:44.879 --> 00:03:47.789 align:start position:0% computations<00:03:45.879> um<00:03:46.120> this<00:03:46.280> means<00:03:46.840> we<00:03:46.959> can<00:03:47.200> ensure 00:03:47.789 --> 00:03:47.799 align:start position:0% computations um this means we can ensure 00:03:47.799 --> 00:03:50.670 align:start position:0% computations um this means we can ensure that<00:03:48.159> each<00:03:48.480> computed<00:03:49.040> value<00:03:49.799> corresponds<00:03:50.439> to 00:03:50.670 --> 00:03:50.680 align:start position:0% that each computed value corresponds to 00:03:50.680 --> 00:03:53.990 align:start position:0% that each computed value corresponds to a<00:03:50.920> valid<00:03:51.319> function<00:03:51.840> and<00:03:52.079> input<00:03:52.640> and<00:03:53.400> produces 00:03:53.990 --> 00:03:54.000 align:start position:0% a valid function and input and produces 00:03:54.000 --> 00:03:56.630 align:start position:0% a valid function and input and produces the<00:03:54.159> correct<00:03:54.560> output<00:03:55.400> as<00:03:55.680> specified<00:03:56.200> in<00:03:56.360> our 00:03:56.630 --> 00:03:56.640 align:start position:0% the correct output as specified in our 00:03:56.640 --> 00:04:00.069 align:start position:0% the correct output as specified in our predefined<00:03:57.480> table<00:03:57.799> of<00:03:58.000> computations 00:04:00.069 --> 00:04:00.079 align:start position:0% predefined table of computations 00:04:00.079 --> 00:04:02.670 align:start position:0% predefined table of computations and<00:04:00.239> it<00:04:00.439> becomes<00:04:00.920> a<00:04:01.560> uh<00:04:01.720> corstone<00:04:02.400> for 00:04:02.670 --> 00:04:02.680 align:start position:0% and it becomes a uh corstone for 00:04:02.680 --> 00:04:05.030 align:start position:0% and it becomes a uh corstone for formally<00:04:03.159> verifiable<00:04:03.879> computation<00:04:04.640> so<00:04:04.879> we 00:04:05.030 --> 00:04:05.040 align:start position:0% formally verifiable computation so we 00:04:05.040 --> 00:04:08.830 align:start position:0% formally verifiable computation so we can<00:04:05.480> Implement<00:04:06.079> some<00:04:07.000> like<00:04:07.200> ZK<00:04:07.680> PM<00:04:08.439> which<00:04:08.560> is 00:04:08.830 --> 00:04:08.840 align:start position:0% can Implement some like ZK PM which is 00:04:08.840 --> 00:04:11.149 align:start position:0% can Implement some like ZK PM which is also<00:04:09.200> called<00:04:09.519> The<00:04:09.640> Look<00:04:09.879> of<00:04:10.159> Singularity 00:04:11.149 --> 00:04:11.159 align:start position:0% also called The Look of Singularity 00:04:11.159 --> 00:04:18.150 align:start position:0% also called The Look of Singularity which<00:04:11.280> is<00:04:11.439> also<00:04:11.799> the<00:04:12.640> uh<00:04:13.079> jolt<00:04:13.560> and<00:04:14.040> lour<00:04:15.040> uh 00:04:18.150 --> 00:04:18.160 align:start position:0% 00:04:18.160 --> 00:04:21.870 align:start position:0% approach<00:04:19.160> um<00:04:19.680> so<00:04:20.280> I'm<00:04:20.400> going<00:04:20.519> to<00:04:21.160> uh<00:04:21.320> introduce 00:04:21.870 --> 00:04:21.880 align:start position:0% approach um so I'm going to uh introduce 00:04:21.880 --> 00:04:25.150 align:start position:0% approach um so I'm going to uh introduce our<00:04:22.199> approach<00:04:22.840> the<00:04:23.080> silic<00:04:23.720> approach<00:04:24.600> so<00:04:24.880> first 00:04:25.150 --> 00:04:25.160 align:start position:0% our approach the silic approach so first 00:04:25.160 --> 00:04:27.710 align:start position:0% our approach the silic approach so first we're<00:04:25.400> going<00:04:25.600> to<00:04:25.800> define<00:04:26.080> the<00:04:26.280> relation<00:04:27.199> silic 00:04:27.710 --> 00:04:27.720 align:start position:0% we're going to define the relation silic 00:04:27.720 --> 00:04:31.469 align:start position:0% we're going to define the relation silic up<00:04:28.680> uh<00:04:28.840> as<00:04:29.000> the<00:04:29.199> set<00:04:29.360> of<00:04:29.520> all<00:04:29.720> all<00:04:29.919> Ts<00:04:30.680> of<00:04:31.000> public 00:04:31.469 --> 00:04:31.479 align:start position:0% up uh as the set of all all Ts of public 00:04:31.479 --> 00:04:35.629 align:start position:0% up uh as the set of all all Ts of public instance<00:04:32.240> X<00:04:33.240> and<00:04:33.680> the<00:04:33.840> witness 00:04:35.629 --> 00:04:35.639 align:start position:0% instance X and the witness 00:04:35.639 --> 00:04:38.990 align:start position:0% instance X and the witness W<00:04:36.639> where<00:04:36.919> the<00:04:37.160> public<00:04:37.440> instance<00:04:37.960> X<00:04:38.240> is<00:04:38.400> a<00:04:38.600> tuple 00:04:38.990 --> 00:04:39.000 align:start position:0% W where the public instance X is a tuple 00:04:39.000 --> 00:04:42.990 align:start position:0% W where the public instance X is a tuple of<00:04:39.240> Oracles<00:04:40.160> of<00:04:40.440> functions<00:04:41.199> ft<00:04:41.960> and 00:04:42.990 --> 00:04:43.000 align:start position:0% of Oracles of functions ft and 00:04:43.000 --> 00:04:46.029 align:start position:0% of Oracles of functions ft and sigma<00:04:44.000> and<00:04:44.160> the<00:04:44.320> witness<00:04:44.880> is<00:04:45.039> a<00:04:45.320> function<00:04:45.840> of 00:04:46.029 --> 00:04:46.039 align:start position:0% sigma and the witness is a function of 00:04:46.039 --> 00:04:50.590 align:start position:0% sigma and the witness is a function of two<00:04:46.400> is<00:04:46.520> a<00:04:46.680> tle<00:04:47.199> functions<00:04:47.680> T<00:04:48.080> ft<00:04:48.520> and 00:04:50.590 --> 00:04:50.600 align:start position:0% two is a tle functions T ft and 00:04:50.600 --> 00:04:54.950 align:start position:0% two is a tle functions T ft and sigma<00:04:51.600> um<00:04:52.280> to<00:04:52.479> be<00:04:52.720> precisely<00:04:53.520> f<00:04:53.800> is<00:04:53.919> a<00:04:54.160> function 00:04:54.950 --> 00:04:54.960 align:start position:0% sigma um to be precisely f is a function 00:04:54.960 --> 00:04:57.430 align:start position:0% sigma um to be precisely f is a function that<00:04:55.280> maps<00:04:55.720> all<00:04:56.000> the<00:04:56.199> witnesses<00:04:56.880> defined<00:04:57.280> on 00:04:57.430 --> 00:04:57.440 align:start position:0% that maps all the witnesses defined on 00:04:57.440 --> 00:05:00.029 align:start position:0% that maps all the witnesses defined on the<00:04:57.639> domain<00:04:58.080> XF 00:05:00.029 --> 00:05:00.039 align:start position:0% the domain XF 00:05:00.039 --> 00:05:01.909 align:start position:0% the domain XF uh<00:05:00.240> with<00:05:00.479> range 00:05:01.909 --> 00:05:01.919 align:start position:0% uh with range 00:05:01.919 --> 00:05:05.870 align:start position:0% uh with range YF<00:05:02.919> and<00:05:03.160> T<00:05:03.400> is<00:05:03.520> a<00:05:03.759> function<00:05:04.759> that<00:05:04.919> Maps<00:05:05.360> table 00:05:05.870 --> 00:05:05.880 align:start position:0% YF and T is a function that Maps table 00:05:05.880 --> 00:05:09.710 align:start position:0% YF and T is a function that Maps table element<00:05:06.880> defined<00:05:07.320> on<00:05:07.440> a<00:05:07.600> domain<00:05:08.440> XT<00:05:09.440> with 00:05:09.710 --> 00:05:09.720 align:start position:0% element defined on a domain XT with 00:05:09.720 --> 00:05:12.710 align:start position:0% element defined on a domain XT with range 00:05:12.710 --> 00:05:12.720 align:start position:0% 00:05:12.720 --> 00:05:15.430 align:start position:0% YT<00:05:13.720> then<00:05:13.960> if<00:05:14.160> there<00:05:14.360> exists<00:05:14.720> a<00:05:15.000> domain 00:05:15.430 --> 00:05:15.440 align:start position:0% YT then if there exists a domain 00:05:15.440 --> 00:05:18.029 align:start position:0% YT then if there exists a domain transformation<00:05:16.440> function 00:05:18.029 --> 00:05:18.039 align:start position:0% transformation function 00:05:18.039 --> 00:05:24.309 align:start position:0% transformation function Sigma<00:05:19.039> uh<00:05:19.199> that<00:05:19.479> maps<00:05:20.199> elements<00:05:20.759> from<00:05:21.560> XF<00:05:22.560> to 00:05:24.309 --> 00:05:24.319 align:start position:0% Sigma uh that maps elements from XF to 00:05:24.319 --> 00:05:28.749 align:start position:0% Sigma uh that maps elements from XF to XT<00:05:25.319> also<00:05:25.759> which<00:05:26.000> satisfies<00:05:26.800> that<00:05:27.520> f<00:05:27.759> ofx 00:05:28.749 --> 00:05:28.759 align:start position:0% XT also which satisfies that f ofx 00:05:28.759 --> 00:05:33.230 align:start position:0% XT also which satisfies that f ofx equals<00:05:29.319> to<00:05:30.000> T<00:05:30.280> of<00:05:30.520> Sigma<00:05:31.160> of<00:05:31.400> X<00:05:31.720> for<00:05:32.039> all<00:05:32.360> the<00:05:32.560> X 00:05:33.230 --> 00:05:33.240 align:start position:0% equals to T of Sigma of X for all the X 00:05:33.240 --> 00:05:37.270 align:start position:0% equals to T of Sigma of X for all the X in<00:05:33.360> the<00:05:33.600> domain 00:05:37.270 --> 00:05:37.280 align:start position:0% 00:05:37.280 --> 00:05:41.390 align:start position:0% XF<00:05:38.280> then<00:05:38.759> the<00:05:38.960> range<00:05:39.360> of<00:05:39.680> f<00:05:40.440> is<00:05:40.560> a<00:05:40.800> subset<00:05:41.240> of 00:05:41.390 --> 00:05:41.400 align:start position:0% XF then the range of f is a subset of 00:05:41.400 --> 00:05:43.029 align:start position:0% XF then the range of f is a subset of the<00:05:41.560> range<00:05:41.919> of 00:05:43.029 --> 00:05:43.039 align:start position:0% the range of 00:05:43.039 --> 00:05:46.430 align:start position:0% the range of T<00:05:44.039> and<00:05:44.199> we<00:05:44.360> say<00:05:44.639> that<00:05:44.800> the<00:05:44.919> Tuple<00:05:45.440> of<00:05:45.960> uh<00:05:46.120> public 00:05:46.430 --> 00:05:46.440 align:start position:0% T and we say that the Tuple of uh public 00:05:46.440 --> 00:05:54.550 align:start position:0% T and we say that the Tuple of uh public inance<00:05:46.880> and<00:05:47.000> witness<00:05:47.479> is<00:05:47.720> in<00:05:48.680> the<00:05:49.360> C<00:05:49.800> lookup 00:05:54.550 --> 00:05:54.560 align:start position:0% 00:05:54.560 --> 00:05:58.629 align:start position:0% relation<00:05:55.639> okay<00:05:56.639> uh<00:05:57.360> first<00:05:58.000> I'm<00:05:58.160> going<00:05:58.280> to<00:05:58.440> show 00:05:58.629 --> 00:05:58.639 align:start position:0% relation okay uh first I'm going to show 00:05:58.639 --> 00:06:01.629 align:start position:0% relation okay uh first I'm going to show you<00:05:58.840> the<00:05:59.039> knife<00:05:59.720> approach 00:06:01.629 --> 00:06:01.639 align:start position:0% you the knife approach 00:06:01.639 --> 00:06:05.230 align:start position:0% you the knife approach version<00:06:02.639> we'll<00:06:03.000> consider<00:06:03.440> a<00:06:03.680> polom<00:06:04.520> f<00:06:04.840> and<00:06:05.039> T 00:06:05.230 --> 00:06:05.240 align:start position:0% version we'll consider a polom f and T 00:06:05.240 --> 00:06:08.070 align:start position:0% version we'll consider a polom f and T and<00:06:05.479> sigma<00:06:06.360> over<00:06:06.680> a<00:06:06.919> finite<00:06:07.319> field<00:06:07.840> and<00:06:07.960> we're 00:06:08.070 --> 00:06:08.080 align:start position:0% and sigma over a finite field and we're 00:06:08.080 --> 00:06:11.150 align:start position:0% and sigma over a finite field and we're going<00:06:08.199> to<00:06:08.360> use<00:06:08.759> univariate<00:06:09.759> polinomial 00:06:11.150 --> 00:06:11.160 align:start position:0% going to use univariate polinomial 00:06:11.160 --> 00:06:13.230 align:start position:0% going to use univariate polinomial approach<00:06:12.160> uh<00:06:12.319> then<00:06:12.479> we're<00:06:12.599> going<00:06:12.680> to<00:06:12.840> map<00:06:13.080> the 00:06:13.230 --> 00:06:13.240 align:start position:0% approach uh then we're going to map the 00:06:13.240 --> 00:06:15.589 align:start position:0% approach uh then we're going to map the witness<00:06:13.840> and<00:06:14.120> element<00:06:14.599> using<00:06:15.000> the 00:06:15.589 --> 00:06:15.599 align:start position:0% witness and element using the 00:06:15.599 --> 00:06:17.909 align:start position:0% witness and element using the corresponding<00:06:16.599> root<00:06:16.880> of 00:06:17.909 --> 00:06:17.919 align:start position:0% corresponding root of 00:06:17.919 --> 00:06:19.790 align:start position:0% corresponding root of unity<00:06:18.919> and<00:06:19.080> the 00:06:19.790 --> 00:06:19.800 align:start position:0% unity and the 00:06:19.800 --> 00:06:23.309 align:start position:0% unity and the relation<00:06:20.800> that<00:06:21.080> F<00:06:21.319> ofx<00:06:22.000> always<00:06:22.360> equals<00:06:22.759> to<00:06:23.080> T 00:06:23.309 --> 00:06:23.319 align:start position:0% relation that F ofx always equals to T 00:06:23.319 --> 00:06:26.070 align:start position:0% relation that F ofx always equals to T of<00:06:23.599> Sigma<00:06:24.120> of<00:06:24.360> X<00:06:24.680> for<00:06:24.880> all<00:06:25.160> the<00:06:25.280> roots<00:06:25.520> of<00:06:25.639> unity 00:06:26.070 --> 00:06:26.080 align:start position:0% of Sigma of X for all the roots of unity 00:06:26.080 --> 00:06:29.950 align:start position:0% of Sigma of X for all the roots of unity holds<00:06:26.479> true<00:06:26.960> if<00:06:27.080> and<00:06:27.319> only<00:06:28.199> if<00:06:29.199> there<00:06:29.360> EX<00:06:29.639> is<00:06:29.759> a 00:06:29.950 --> 00:06:29.960 align:start position:0% holds true if and only if there EX is a 00:06:29.960 --> 00:06:34.150 align:start position:0% holds true if and only if there EX is a quo<00:06:30.440> polinomial<00:06:31.160> Q<00:06:32.080> such<00:06:32.400> that<00:06:32.599> F<00:06:32.840> ofx<00:06:33.479> minus<00:06:33.880> t 00:06:34.150 --> 00:06:34.160 align:start position:0% quo polinomial Q such that F ofx minus t 00:06:34.160 --> 00:06:38.510 align:start position:0% quo polinomial Q such that F ofx minus t of<00:06:34.360> Sigma<00:06:34.759> of<00:06:34.919> x<00:06:35.280> =<00:06:35.639> to<00:06:36.080> Z<00:06:36.319> of<00:06:36.479> x<00:06:36.720> *<00:06:37.160> Q<00:06:37.360> of<00:06:37.479> X<00:06:38.280> for 00:06:38.510 --> 00:06:38.520 align:start position:0% of Sigma of x = to Z of x * Q of X for 00:06:38.520 --> 00:06:41.629 align:start position:0% of Sigma of x = to Z of x * Q of X for the<00:06:38.680> vanishing<00:06:39.520> polinomial 00:06:41.629 --> 00:06:41.639 align:start position:0% the vanishing polinomial 00:06:41.639 --> 00:06:45.830 align:start position:0% the vanishing polinomial Z<00:06:42.639> actually<00:06:43.160> here<00:06:43.440> exists<00:06:43.800> a<00:06:44.199> caveat 00:06:45.830 --> 00:06:45.840 align:start position:0% Z actually here exists a caveat 00:06:45.840 --> 00:06:49.110 align:start position:0% Z actually here exists a caveat that 00:06:49.110 --> 00:06:49.120 align:start position:0% 00:06:49.120 --> 00:06:53.390 align:start position:0% um<00:06:50.120> the<00:06:50.400> degree<00:06:51.840> explodes<00:06:52.840> the<00:06:53.039> degree 00:06:53.390 --> 00:06:53.400 align:start position:0% um the degree explodes the degree 00:06:53.400 --> 00:06:56.150 align:start position:0% um the degree explodes the degree explores<00:06:54.000> if<00:06:54.160> we<00:06:54.520> have<00:06:54.680> the<00:06:54.840> univ<00:06:55.479> polinomial 00:06:56.150 --> 00:06:56.160 align:start position:0% explores if we have the univ polinomial 00:06:56.160 --> 00:06:57.830 align:start position:0% explores if we have the univ polinomial and<00:06:56.280> if<00:06:56.479> if<00:06:56.599> we<00:06:56.759> compute<00:06:57.120> the<00:06:57.360> composite 00:06:57.830 --> 00:06:57.840 align:start position:0% and if if we compute the composite 00:06:57.840 --> 00:07:00.029 align:start position:0% and if if we compute the composite function<00:06:58.800> the<00:06:58.960> degree<00:06:59.280> of<00:06:59.400> the<00:06:59.599> the<00:06:59.720> whole 00:07:00.029 --> 00:07:00.039 align:start position:0% function the degree of the the whole 00:07:00.039 --> 00:07:03.150 align:start position:0% function the degree of the the whole system<00:07:00.840> uh<00:07:00.960> becomes<00:07:01.240> a<00:07:01.479> degree<00:07:01.800> of<00:07:02.000> T<00:07:02.400> times 00:07:03.150 --> 00:07:03.160 align:start position:0% system uh becomes a degree of T times 00:07:03.160 --> 00:07:06.749 align:start position:0% system uh becomes a degree of T times degree<00:07:03.560> of<00:07:04.080> the<00:07:05.199> uh 00:07:06.749 --> 00:07:06.759 align:start position:0% degree of the uh 00:07:06.759 --> 00:07:11.749 align:start position:0% degree of the uh Sigma<00:07:07.759> so<00:07:07.960> which<00:07:08.080> means<00:07:08.440> like<00:07:08.840> n<00:07:09.400> * 00:07:11.749 --> 00:07:11.759 align:start position:0% Sigma so which means like n * 00:07:11.759 --> 00:07:14.830 align:start position:0% Sigma so which means like n * m<00:07:12.759> but<00:07:12.960> if<00:07:13.080> we<00:07:13.240> use<00:07:13.520> multivari<00:07:14.240> polinomial 00:07:14.830 --> 00:07:14.840 align:start position:0% m but if we use multivari polinomial 00:07:14.840 --> 00:07:16.909 align:start position:0% m but if we use multivari polinomial approach<00:07:15.560> it<00:07:15.720> changes<00:07:16.160> a 00:07:16.909 --> 00:07:16.919 align:start position:0% approach it changes a 00:07:16.919 --> 00:07:20.749 align:start position:0% approach it changes a lot<00:07:17.919> we<00:07:18.039> will<00:07:18.240> Define<00:07:18.599> the<00:07:19.080> domain<00:07:20.080> uh<00:07:20.319> on<00:07:20.560> the 00:07:20.749 --> 00:07:20.759 align:start position:0% lot we will Define the domain uh on the 00:07:20.759 --> 00:07:23.950 align:start position:0% lot we will Define the domain uh on the vector<00:07:21.240> space<00:07:22.240> uh<00:07:22.360> for<00:07:22.639> the<00:07:22.840> witness<00:07:23.800> we're 00:07:23.950 --> 00:07:23.960 align:start position:0% vector space uh for the witness we're 00:07:23.960 --> 00:07:26.589 align:start position:0% vector space uh for the witness we're going<00:07:24.080> to<00:07:24.840> uh<00:07:25.000> Define<00:07:25.360> its<00:07:25.599> domain<00:07:25.960> as<00:07:26.199> bullan 00:07:26.589 --> 00:07:26.599 align:start position:0% going to uh Define its domain as bullan 00:07:26.599 --> 00:07:30.550 align:start position:0% going to uh Define its domain as bullan hyper<00:07:27.199> Cube<00:07:28.199> uh<00:07:28.639> over<00:07:29.039> a<00:07:29.520> log<00:07:29.800> M<00:07:30.080> dimensional 00:07:30.550 --> 00:07:30.560 align:start position:0% hyper Cube uh over a log M dimensional 00:07:30.560 --> 00:07:32.950 align:start position:0% hyper Cube uh over a log M dimensional space<00:07:31.520> and<00:07:31.680> for<00:07:31.879> the<00:07:32.080> table<00:07:32.520> we're<00:07:32.639> going<00:07:32.759> to 00:07:32.950 --> 00:07:32.960 align:start position:0% space and for the table we're going to 00:07:32.960 --> 00:07:37.749 align:start position:0% space and for the table we're going to define<00:07:33.240> the<00:07:33.759> domain<00:07:34.759> uh<00:07:35.120> over<00:07:35.520> the<00:07:35.919> log<00:07:36.319> n<00:07:37.000> uh 00:07:37.749 --> 00:07:37.759 align:start position:0% define the domain uh over the log n uh 00:07:37.759 --> 00:07:40.469 align:start position:0% define the domain uh over the log n uh dimensional<00:07:38.759> uh 00:07:40.469 --> 00:07:40.479 align:start position:0% dimensional uh 00:07:40.479 --> 00:07:44.469 align:start position:0% dimensional uh space<00:07:41.479> and<00:07:41.879> then<00:07:42.879> uh<00:07:43.039> defining<00:07:43.639> the<00:07:44.080> domain 00:07:44.469 --> 00:07:44.479 align:start position:0% space and then uh defining the domain 00:07:44.479 --> 00:07:47.550 align:start position:0% space and then uh defining the domain transformation<00:07:45.199> function<00:07:46.120> Sigma<00:07:47.120> uh<00:07:47.280> as<00:07:47.400> a 00:07:47.550 --> 00:07:47.560 align:start position:0% transformation function Sigma uh as a 00:07:47.560 --> 00:07:49.550 align:start position:0% transformation function Sigma uh as a tuple<00:07:48.000> of<00:07:48.159> all<00:07:48.319> the<00:07:48.479> domain<00:07:48.840> transformation 00:07:49.550 --> 00:07:49.560 align:start position:0% tuple of all the domain transformation 00:07:49.560 --> 00:07:52.749 align:start position:0% tuple of all the domain transformation functions<00:07:50.319> then<00:07:50.479> the<00:07:50.680> relation<00:07:51.639> that<00:07:52.319> the<00:07:52.520> F 00:07:52.749 --> 00:07:52.759 align:start position:0% functions then the relation that the F 00:07:52.759 --> 00:07:57.749 align:start position:0% functions then the relation that the F ofx<00:07:53.319> always<00:07:54.120> T<00:07:54.440> of<00:07:54.680> Sigma<00:07:55.400> of<00:07:55.599> X<00:07:55.960> holds<00:07:56.599> true<00:07:57.599> if 00:07:57.749 --> 00:07:57.759 align:start position:0% ofx always T of Sigma of X holds true if 00:07:57.759 --> 00:08:00.350 align:start position:0% ofx always T of Sigma of X holds true if and<00:07:57.960> only<00:07:58.360> if<00:07:58.720> there<00:07:59.000> exist<00:07:59.680> auxiliary 00:08:00.350 --> 00:08:00.360 align:start position:0% and only if there exist auxiliary 00:08:00.360 --> 00:08:03.909 align:start position:0% and only if there exist auxiliary polinomial<00:08:01.120> H<00:08:02.120> uh<00:08:02.800> which<00:08:03.039> satisfies<00:08:03.680> some 00:08:03.909 --> 00:08:03.919 align:start position:0% polinomial H uh which satisfies some 00:08:03.919 --> 00:08:07.990 align:start position:0% polinomial H uh which satisfies some zero<00:08:04.240> check<00:08:04.479> Pol<00:08:05.000> zero<00:08:05.319> check<00:08:06.159> uh<00:08:06.319> Pro<00:08:06.599> piop 00:08:07.990 --> 00:08:08.000 align:start position:0% zero check Pol zero check uh Pro piop 00:08:08.000 --> 00:08:11.790 align:start position:0% zero check Pol zero check uh Pro piop protocol<00:08:09.319> precisely<00:08:10.319> here<00:08:10.560> the<00:08:10.720> r<00:08:11.039> and<00:08:11.319> RP 00:08:11.790 --> 00:08:11.800 align:start position:0% protocol precisely here the r and RP 00:08:11.800 --> 00:08:15.790 align:start position:0% protocol precisely here the r and RP Prime<00:08:12.199> and<00:08:12.479> GMA<00:08:12.960> are<00:08:13.199> the<00:08:13.440> randomly<00:08:14.319> chosen<00:08:15.319> uh 00:08:15.790 --> 00:08:15.800 align:start position:0% Prime and GMA are the randomly chosen uh 00:08:15.800 --> 00:08:17.869 align:start position:0% Prime and GMA are the randomly chosen uh Vector<00:08:16.720> from<00:08:16.960> the 00:08:17.869 --> 00:08:17.879 align:start position:0% Vector from the 00:08:17.879 --> 00:08:21.309 align:start position:0% Vector from the verifier<00:08:18.879> and<00:08:19.479> the<00:08:19.639> auxiliary<00:08:20.319> polinomial 00:08:21.309 --> 00:08:21.319 align:start position:0% verifier and the auxiliary polinomial 00:08:21.319 --> 00:08:23.550 align:start position:0% verifier and the auxiliary polinomial gives<00:08:21.560> you<00:08:21.720> the<00:08:21.919> Rel<00:08:22.199> gives<00:08:22.440> us<00:08:22.639> the<00:08:22.800> relation 00:08:23.550 --> 00:08:23.560 align:start position:0% gives you the Rel gives us the relation 00:08:23.560 --> 00:08:27.309 align:start position:0% gives you the Rel gives us the relation that<00:08:24.560> the<00:08:24.840> there<00:08:25.120> exist<00:08:25.560> mapping<00:08:26.319> correctly 00:08:27.309 --> 00:08:27.319 align:start position:0% that the there exist mapping correctly 00:08:27.319 --> 00:08:30.029 align:start position:0% that the there exist mapping correctly and<00:08:27.680> the<00:08:27.840> domain<00:08:28.280> transformation<00:08:29.759> is 00:08:30.029 --> 00:08:30.039 align:start position:0% and the domain transformation is 00:08:30.039 --> 00:08:37.110 align:start position:0% and the domain transformation is actually<00:08:30.400> bound<00:08:31.039> to<00:08:32.039> uh<00:08:32.200> the<00:08:32.399> zero<00:08:32.719> and<00:08:33.120> one 00:08:37.110 --> 00:08:37.120 align:start position:0% 00:08:37.120 --> 00:08:39.790 align:start position:0% correctly<00:08:38.120> as<00:08:38.200> a<00:08:38.399> result<00:08:39.360> uh<00:08:39.479> we<00:08:39.599> could 00:08:39.790 --> 00:08:39.800 align:start position:0% correctly as a result uh we could 00:08:39.800 --> 00:08:42.269 align:start position:0% correctly as a result uh we could achieve<00:08:40.120> the<00:08:40.279> log<00:08:40.599> squar<00:08:41.120> of<00:08:41.320> M<00:08:41.760> against<00:08:42.120> the 00:08:42.269 --> 00:08:42.279 align:start position:0% achieve the log squar of M against the 00:08:42.279 --> 00:08:46.030 align:start position:0% achieve the log squar of M against the witness<00:08:42.680> size<00:08:43.320> or<00:08:44.320> uh<00:08:44.519> log<00:08:45.000> of<00:08:45.160> the<00:08:45.320> table<00:08:45.720> size 00:08:46.030 --> 00:08:46.040 align:start position:0% witness size or uh log of the table size 00:08:46.040 --> 00:08:49.790 align:start position:0% witness size or uh log of the table size and<00:08:46.560> complexity<00:08:47.560> time 00:08:49.790 --> 00:08:49.800 align:start position:0% and complexity time 00:08:49.800 --> 00:08:51.750 align:start position:0% and complexity time complexity<00:08:50.800> if<00:08:50.920> we<00:08:51.160> think<00:08:51.360> about<00:08:51.560> the 00:08:51.750 --> 00:08:51.760 align:start position:0% complexity if we think about the 00:08:51.760 --> 00:08:53.670 align:start position:0% complexity if we think about the protocol<00:08:52.680> uh<00:08:52.839> let's<00:08:53.040> go<00:08:53.240> through<00:08:53.519> the 00:08:53.670 --> 00:08:53.680 align:start position:0% protocol uh let's go through the 00:08:53.680 --> 00:08:56.870 align:start position:0% protocol uh let's go through the protocol<00:08:54.200> quickly<00:08:55.120> so<00:08:55.959> let's<00:08:56.240> assume<00:08:56.640> we<00:08:56.760> have 00:08:56.870 --> 00:08:56.880 align:start position:0% protocol quickly so let's assume we have 00:08:56.880 --> 00:09:00.030 align:start position:0% protocol quickly so let's assume we have a<00:08:57.320> witness<00:08:58.320> witness<00:08:58.760> f<00:08:59.480> with<00:08:59.640> with<00:08:59.839> this 00:09:00.030 --> 00:09:00.040 align:start position:0% a witness witness f with with this 00:09:00.040 --> 00:09:04.150 align:start position:0% a witness witness f with with this Vector<00:09:00.320> F<00:09:00.720> and<00:09:00.959> the<00:09:01.160> table<00:09:01.480> Vector<00:09:01.959> T<00:09:02.959> 2<00:09:03.240> 3<00:09:03.519> 5<00:09:03.760> 7 00:09:04.150 --> 00:09:04.160 align:start position:0% Vector F and the table Vector T 2 3 5 7 00:09:04.160 --> 00:09:07.710 align:start position:0% Vector F and the table Vector T 2 3 5 7 11<00:09:04.600> 5<00:09:04.920> like<00:09:05.120> blah<00:09:05.360> blah<00:09:05.959> blah<00:09:06.959> and<00:09:07.160> the<00:09:07.399> first 00:09:07.710 --> 00:09:07.720 align:start position:0% 11 5 like blah blah blah and the first 00:09:07.720 --> 00:09:10.269 align:start position:0% 11 5 like blah blah blah and the first step<00:09:07.959> is<00:09:08.440> preparation<00:09:09.440> so<00:09:09.680> we're<00:09:09.839> going<00:09:09.959> to 00:09:10.269 --> 00:09:10.279 align:start position:0% step is preparation so we're going to 00:09:10.279 --> 00:09:13.230 align:start position:0% step is preparation so we're going to compute<00:09:10.680> the<00:09:10.920> table<00:09:11.600> polom<00:09:12.600> but<00:09:12.760> for<00:09:13.000> a 00:09:13.230 --> 00:09:13.240 align:start position:0% compute the table polom but for a 00:09:13.240 --> 00:09:16.630 align:start position:0% compute the table polom but for a efficient<00:09:14.240> uh<00:09:14.440> some<00:09:15.440> parallelization<00:09:16.440> we're 00:09:16.630 --> 00:09:16.640 align:start position:0% efficient uh some parallelization we're 00:09:16.640 --> 00:09:19.110 align:start position:0% efficient uh some parallelization we're going<00:09:16.760> to<00:09:16.920> use<00:09:17.160> the<00:09:17.360> coefficient<00:09:17.920> form<00:09:18.800> but<00:09:19.000> it 00:09:19.110 --> 00:09:19.120 align:start position:0% going to use the coefficient form but it 00:09:19.120 --> 00:09:22.069 align:start position:0% going to use the coefficient form but it doesn't<00:09:20.040> actually<00:09:20.399> actually<00:09:20.760> does<00:09:21.000> not<00:09:21.240> a<00:09:21.480> big 00:09:22.069 --> 00:09:22.079 align:start position:0% doesn't actually actually does not a big 00:09:22.079 --> 00:09:26.389 align:start position:0% doesn't actually actually does not a big uh<00:09:22.320> thing<00:09:22.720> because<00:09:23.519> it's<00:09:23.680> a<00:09:24.040> pre-processing 00:09:26.389 --> 00:09:26.399 align:start position:0% uh thing because it's a pre-processing 00:09:26.399 --> 00:09:29.949 align:start position:0% uh thing because it's a pre-processing period<00:09:27.399> and<00:09:27.600> then<00:09:28.120> we<00:09:28.320> interpolate<00:09:28.880> the<00:09:29.040> with 00:09:29.949 --> 00:09:29.959 align:start position:0% period and then we interpolate the with 00:09:29.959 --> 00:09:33.389 align:start position:0% period and then we interpolate the with so<00:09:30.440> just<00:09:30.680> say<00:09:30.880> for<00:09:31.040> your<00:09:31.680> uh<00:09:31.880> easier<00:09:32.880> uh 00:09:33.389 --> 00:09:33.399 align:start position:0% so just say for your uh easier uh 00:09:33.399 --> 00:09:35.110 align:start position:0% so just say for your uh easier uh understanding<00:09:33.680> I<00:09:33.800> just<00:09:34.000> expressed<00:09:34.440> this<00:09:34.600> in<00:09:34.760> a 00:09:35.110 --> 00:09:35.120 align:start position:0% understanding I just expressed this in a 00:09:35.120 --> 00:09:37.829 align:start position:0% understanding I just expressed this in a coefficient<00:09:35.760> form<00:09:36.760> and<00:09:36.920> then<00:09:37.079> we<00:09:37.360> also<00:09:37.640> need 00:09:37.829 --> 00:09:37.839 align:start position:0% coefficient form and then we also need 00:09:37.839 --> 00:09:39.750 align:start position:0% coefficient form and then we also need to<00:09:38.000> find<00:09:38.279> the<00:09:38.480> domain<00:09:38.839> transformation 00:09:39.750 --> 00:09:39.760 align:start position:0% to find the domain transformation 00:09:39.760 --> 00:09:42.470 align:start position:0% to find the domain transformation functions<00:09:40.640> this<00:09:40.800> is<00:09:41.000> just<00:09:41.240> a<00:09:41.600> mapping<00:09:42.079> between 00:09:42.470 --> 00:09:42.480 align:start position:0% functions this is just a mapping between 00:09:42.480 --> 00:09:45.630 align:start position:0% functions this is just a mapping between the<00:09:43.320> uh<00:09:43.480> table<00:09:43.959> domain<00:09:44.640> witness<00:09:45.079> domain<00:09:45.480> to 00:09:45.630 --> 00:09:45.640 align:start position:0% the uh table domain witness domain to 00:09:45.640 --> 00:09:46.750 align:start position:0% the uh table domain witness domain to the<00:09:45.839> table 00:09:46.750 --> 00:09:46.760 align:start position:0% the table 00:09:46.760 --> 00:09:49.949 align:start position:0% the table domain<00:09:47.760> so<00:09:48.040> if<00:09:48.160> we<00:09:48.399> express<00:09:48.880> that<00:09:49.640> in<00:09:49.800> the 00:09:49.949 --> 00:09:49.959 align:start position:0% domain so if we express that in the 00:09:49.959 --> 00:09:51.710 align:start position:0% domain so if we express that in the coefficient<00:09:50.440> form<00:09:50.920> actually<00:09:51.160> we<00:09:51.279> are<00:09:51.399> using 00:09:51.710 --> 00:09:51.720 align:start position:0% coefficient form actually we are using 00:09:51.720 --> 00:09:54.230 align:start position:0% coefficient form actually we are using only<00:09:51.959> the<00:09:52.120> evaluation 00:09:54.230 --> 00:09:54.240 align:start position:0% only the evaluation 00:09:54.240 --> 00:09:57.550 align:start position:0% only the evaluation form<00:09:55.240> and<00:09:55.440> then<00:09:56.399> uh<00:09:56.480> we<00:09:56.640> use<00:09:56.959> public<00:09:57.240> coin 00:09:57.550 --> 00:09:57.560 align:start position:0% form and then uh we use public coin 00:09:57.560 --> 00:10:03.150 align:start position:0% form and then uh we use public coin protocol<00:09:58.519> to<00:09:59.680> uh<00:10:00.600> run<00:10:00.920> some<00:10:01.240> check<00:10:01.519> only<00:10:02.160> once 00:10:03.150 --> 00:10:03.160 align:start position:0% protocol to uh run some check only once 00:10:03.160 --> 00:10:06.509 align:start position:0% protocol to uh run some check only once uh<00:10:03.320> by<00:10:03.560> patching<00:10:04.120> every<00:10:04.680> everything<00:10:05.519> together 00:10:06.509 --> 00:10:06.519 align:start position:0% uh by patching every everything together 00:10:06.519 --> 00:10:10.030 align:start position:0% uh by patching every everything together so<00:10:06.839> we<00:10:07.120> we<00:10:07.600> choose<00:10:08.600> uh<00:10:08.720> the<00:10:08.839> verifier<00:10:09.480> choose 00:10:10.030 --> 00:10:10.040 align:start position:0% so we we choose uh the verifier choose 00:10:10.040 --> 00:10:13.389 align:start position:0% so we we choose uh the verifier choose chooses<00:10:10.560> the<00:10:10.839> r<00:10:11.240> RP<00:10:11.600> Prime<00:10:11.880> and 00:10:13.389 --> 00:10:13.399 align:start position:0% chooses the r RP Prime and 00:10:13.399 --> 00:10:16.150 align:start position:0% chooses the r RP Prime and Gamma<00:10:14.399> and<00:10:14.560> in<00:10:14.720> this<00:10:14.959> case<00:10:15.200> let's<00:10:15.519> say<00:10:15.959> we 00:10:16.150 --> 00:10:16.160 align:start position:0% Gamma and in this case let's say we 00:10:16.160 --> 00:10:20.069 align:start position:0% Gamma and in this case let's say we chose<00:10:16.519> 31<00:10:17.000> 37<00:10:17.519> for<00:10:17.839> R<00:10:18.680> and<00:10:18.880> 5<00:10:19.160> and<00:10:19.320> 7<00:10:19.600> for<00:10:19.760> RP 00:10:20.069 --> 00:10:20.079 align:start position:0% chose 31 37 for R and 5 and 7 for RP 00:10:20.079 --> 00:10:22.949 align:start position:0% chose 31 37 for R and 5 and 7 for RP Prime<00:10:20.440> and<00:10:20.600> 9<00:10:20.880> and<00:10:21.000> 11<00:10:21.399> 13<00:10:21.760> for<00:10:22.000> the 00:10:22.949 --> 00:10:22.959 align:start position:0% Prime and 9 and 11 13 for the 00:10:22.959 --> 00:10:26.990 align:start position:0% Prime and 9 and 11 13 for the comma<00:10:23.959> run<00:10:24.440> some<00:10:25.000> check<00:10:26.000> the<00:10:26.200> first<00:10:26.440> R<00:10:26.800> will 00:10:26.990 --> 00:10:27.000 align:start position:0% comma run some check the first R will 00:10:27.000 --> 00:10:30.389 align:start position:0% comma run some check the first R will look<00:10:27.240> like<00:10:27.480> this<00:10:28.079> and<00:10:28.240> you<00:10:28.399> can<00:10:28.600> see<00:10:29.120> here<00:10:29.399> here 00:10:30.389 --> 00:10:30.399 align:start position:0% look like this and you can see here here 00:10:30.399 --> 00:10:33.030 align:start position:0% look like this and you can see here here uh<00:10:30.680> the<00:10:30.959> intermediate<00:10:31.600> univ<00:10:32.240> polinomial<00:10:32.839> is 00:10:33.030 --> 00:10:33.040 align:start position:0% uh the intermediate univ polinomial is 00:10:33.040 --> 00:10:36.190 align:start position:0% uh the intermediate univ polinomial is not<00:10:33.320> a<00:10:33.480> linear<00:10:34.000> function<00:10:34.880> it<00:10:35.120> has<00:10:35.279> some 00:10:36.190 --> 00:10:36.200 align:start position:0% not a linear function it has some 00:10:36.200 --> 00:10:41.190 align:start position:0% not a linear function it has some degrees<00:10:37.440> um<00:10:38.440> and<00:10:38.600> we<00:10:38.760> run<00:10:39.560> the<00:10:40.240> following 00:10:41.190 --> 00:10:41.200 align:start position:0% degrees um and we run the following 00:10:41.200 --> 00:10:43.509 align:start position:0% degrees um and we run the following round<00:10:42.200> and<00:10:42.399> as<00:10:42.519> a 00:10:43.509 --> 00:10:43.519 align:start position:0% round and as a 00:10:43.519 --> 00:10:48.710 align:start position:0% round and as a result<00:10:44.519> uh<00:10:45.440> we<00:10:45.560> need<00:10:45.760> to<00:10:45.959> check<00:10:46.760> the<00:10:47.760> resulting 00:10:48.710 --> 00:10:48.720 align:start position:0% result uh we need to check the resulting 00:10:48.720 --> 00:10:50.990 align:start position:0% result uh we need to check the resulting eval<00:10:49.120> random<00:10:49.560> evaluation<00:10:50.200> from<00:10:50.480> this<00:10:50.680> Su 00:10:50.990 --> 00:10:51.000 align:start position:0% eval random evaluation from this Su 00:10:51.000 --> 00:10:55.069 align:start position:0% eval random evaluation from this Su check<00:10:51.360> equals<00:10:51.839> to<00:10:52.120> the<00:10:52.760> thing<00:10:53.760> uh<00:10:54.360> that<00:10:54.560> we<00:10:54.680> can 00:10:55.069 --> 00:10:55.079 align:start position:0% check equals to the thing uh that we can 00:10:55.079 --> 00:10:56.629 align:start position:0% check equals to the thing uh that we can query<00:10:55.600> from<00:10:55.880> the 00:10:56.629 --> 00:10:56.639 align:start position:0% query from the 00:10:56.639 --> 00:10:59.350 align:start position:0% query from the Oracle<00:10:57.639> uh<00:10:57.839> which<00:10:58.120> was<00:10:58.399> the<00:10:58.639> one<00:10:58.800> of<00:10:58.959> the 00:10:59.350 --> 00:10:59.360 align:start position:0% Oracle uh which was the one of the 00:10:59.360 --> 00:11:02.949 align:start position:0% Oracle uh which was the one of the public<00:10:59.760> instance<00:11:00.279> X<00:11:01.160> so<00:11:01.399> we<00:11:01.839> carry<00:11:02.360> the 00:11:02.949 --> 00:11:02.959 align:start position:0% public instance X so we carry the 00:11:02.959 --> 00:11:05.710 align:start position:0% public instance X so we carry the evaluations<00:11:03.959> through<00:11:04.200> the<00:11:04.399> oracles<00:11:05.399> and<00:11:05.560> we 00:11:05.710 --> 00:11:05.720 align:start position:0% evaluations through the oracles and we 00:11:05.720 --> 00:11:08.710 align:start position:0% evaluations through the oracles and we check<00:11:06.120> this<00:11:06.800> uh<00:11:07.320> they<00:11:07.440> are<00:11:07.760> hold<00:11:08.399> they<00:11:08.600> the 00:11:08.710 --> 00:11:08.720 align:start position:0% check this uh they are hold they the 00:11:08.720 --> 00:11:11.389 align:start position:0% check this uh they are hold they the relation<00:11:09.160> holds<00:11:09.480> true<00:11:10.279> by<00:11:10.480> checking<00:11:10.920> this 00:11:11.389 --> 00:11:11.399 align:start position:0% relation holds true by checking this 00:11:11.399 --> 00:11:15.190 align:start position:0% relation holds true by checking this condition<00:11:11.639> and 00:11:15.190 --> 00:11:15.200 align:start position:0% 00:11:15.200 --> 00:11:18.150 align:start position:0% consistency<00:11:16.200> one<00:11:16.440> important<00:11:16.920> thing<00:11:17.079> is<00:11:17.279> that 00:11:18.150 --> 00:11:18.160 align:start position:0% consistency one important thing is that 00:11:18.160 --> 00:11:20.389 align:start position:0% consistency one important thing is that the<00:11:18.720> uh<00:11:18.880> main<00:11:19.200> advantage<00:11:19.639> of<00:11:19.800> this<00:11:20.000> approach 00:11:20.389 --> 00:11:20.399 align:start position:0% the uh main advantage of this approach 00:11:20.399 --> 00:11:23.269 align:start position:0% the uh main advantage of this approach is<00:11:20.600> that<00:11:20.800> it<00:11:20.920> is<00:11:21.160> very<00:11:21.399> easy<00:11:21.720> to<00:11:22.279> decompose 00:11:23.269 --> 00:11:23.279 align:start position:0% is that it is very easy to decompose 00:11:23.279 --> 00:11:27.590 align:start position:0% is that it is very easy to decompose into<00:11:23.560> smaller<00:11:24.240> tables<00:11:25.240> so<00:11:25.839> we<00:11:26.000> have<00:11:26.160> a<00:11:27.120> t 00:11:27.590 --> 00:11:27.600 align:start position:0% into smaller tables so we have a t 00:11:27.600 --> 00:11:32.069 align:start position:0% into smaller tables so we have a t polinomial<00:11:28.440> here<00:11:29.639> and<00:11:29.839> we<00:11:30.240> can<00:11:31.240> uh<00:11:31.519> decompos 00:11:32.069 --> 00:11:32.079 align:start position:0% polinomial here and we can uh decompos 00:11:32.079 --> 00:11:36.470 align:start position:0% polinomial here and we can uh decompos it<00:11:32.279> into<00:11:32.639> two<00:11:32.920> smaller<00:11:33.839> pieces<00:11:34.839> T1<00:11:35.720> and 00:11:36.470 --> 00:11:36.480 align:start position:0% it into two smaller pieces T1 and 00:11:36.480 --> 00:11:42.230 align:start position:0% it into two smaller pieces T1 and T2<00:11:37.480> in<00:11:37.639> T1<00:11:38.200> is<00:11:38.399> just<00:11:38.600> say<00:11:39.079> t<00:11:40.079> of<00:11:40.560> 0<00:11:41.279> comma<00:11:41.639> X2 00:11:42.230 --> 00:11:42.240 align:start position:0% T2 in T1 is just say t of 0 comma X2 00:11:42.240 --> 00:11:48.470 align:start position:0% T2 in T1 is just say t of 0 comma X2 comma<00:11:42.760> X3<00:11:43.760> and<00:11:43.959> T2<00:11:44.680> is<00:11:45.200> actually<00:11:46.200> T<00:11:46.880> of<00:11:47.600> 1<00:11:48.200> comma 00:11:48.470 --> 00:11:48.480 align:start position:0% comma X3 and T2 is actually T of 1 comma 00:11:48.480 --> 00:11:52.670 align:start position:0% comma X3 and T2 is actually T of 1 comma X2<00:11:49.079> comma<00:11:49.560> X3<00:11:50.560> so<00:11:50.760> we<00:11:50.920> can<00:11:51.720> decompose<00:11:52.240> a<00:11:52.360> table 00:11:52.670 --> 00:11:52.680 align:start position:0% X2 comma X3 so we can decompose a table 00:11:52.680 --> 00:11:54.069 align:start position:0% X2 comma X3 so we can decompose a table very 00:11:54.069 --> 00:11:54.079 align:start position:0% very 00:11:54.079 --> 00:11:57.590 align:start position:0% very easily<00:11:55.079> we<00:11:55.240> can<00:11:56.160> uh<00:11:56.440> de<00:11:56.600> composite<00:11:57.279> more 00:11:57.590 --> 00:11:57.600 align:start position:0% easily we can uh de composite more 00:11:57.600 --> 00:12:00.190 align:start position:0% easily we can uh de composite more smaller<00:11:58.040> pieces 00:12:00.190 --> 00:12:00.200 align:start position:0% smaller pieces 00:12:00.200 --> 00:12:02.949 align:start position:0% smaller pieces also<00:12:00.519> we<00:12:00.639> can<00:12:00.880> utilize<00:12:01.639> this<00:12:02.160> uh<00:12:02.440> composite 00:12:02.949 --> 00:12:02.959 align:start position:0% also we can utilize this uh composite 00:12:02.959 --> 00:12:07.190 align:start position:0% also we can utilize this uh composite function<00:12:03.800> approach<00:12:04.800> with<00:12:05.079> a<00:12:05.399> a<00:12:05.880> some<00:12:06.880> we<00:12:07.000> can 00:12:07.190 --> 00:12:07.200 align:start position:0% function approach with a a some we can 00:12:07.200 --> 00:12:08.550 align:start position:0% function approach with a a some we can tweak<00:12:07.480> a<00:12:07.600> little 00:12:08.550 --> 00:12:08.560 align:start position:0% tweak a little 00:12:08.560 --> 00:12:12.190 align:start position:0% tweak a little bit<00:12:09.560> uh<00:12:09.880> if<00:12:10.160> if<00:12:10.279> we<00:12:10.440> tweak<00:12:10.920> this<00:12:11.120> a<00:12:11.279> little<00:12:11.519> bit 00:12:12.190 --> 00:12:12.200 align:start position:0% bit uh if if we tweak this a little bit 00:12:12.200 --> 00:12:16.389 align:start position:0% bit uh if if we tweak this a little bit then<00:12:12.600> we<00:12:12.760> can<00:12:13.120> also<00:12:13.600> compute<00:12:14.600> the<00:12:15.240> two 00:12:16.389 --> 00:12:16.399 align:start position:0% then we can also compute the two 00:12:16.399 --> 00:12:19.470 align:start position:0% then we can also compute the two intersection<00:12:17.399> I<00:12:17.480> mean<00:12:17.800> size<00:12:18.160> of<00:12:18.480> two 00:12:19.470 --> 00:12:19.480 align:start position:0% intersection I mean size of two 00:12:19.480 --> 00:12:21.910 align:start position:0% intersection I mean size of two intersection<00:12:20.120> of<00:12:20.320> two<00:12:20.920> given 00:12:21.910 --> 00:12:21.920 align:start position:0% intersection of two given 00:12:21.920 --> 00:12:25.110 align:start position:0% intersection of two given set<00:12:22.920> and<00:12:23.079> actually<00:12:24.079> the<00:12:24.320> result<00:12:24.760> for<00:12:24.959> the 00:12:25.110 --> 00:12:25.120 align:start position:0% set and actually the result for the 00:12:25.120 --> 00:12:28.150 align:start position:0% set and actually the result for the computational<00:12:25.839> results<00:12:26.480> also<00:12:27.440> uh<00:12:27.600> shows<00:12:28.000> the 00:12:28.150 --> 00:12:28.160 align:start position:0% computational results also uh shows the 00:12:28.160 --> 00:12:32.990 align:start position:0% computational results also uh shows the same<00:12:28.440> result 00:12:32.990 --> 00:12:33.000 align:start position:0% 00:12:33.000 --> 00:12:35.949 align:start position:0% uh<00:12:33.279> one<00:12:33.440> of<00:12:33.600> the<00:12:33.839> key<00:12:34.120> thesis<00:12:34.639> we<00:12:34.839> had<00:12:35.240> here<00:12:35.680> is 00:12:35.949 --> 00:12:35.959 align:start position:0% uh one of the key thesis we had here is 00:12:35.959 --> 00:12:39.710 align:start position:0% uh one of the key thesis we had here is that<00:12:36.959> if<00:12:37.240> we<00:12:37.959> uh<00:12:38.399> use<00:12:38.639> the<00:12:38.839> composite<00:12:39.320> function 00:12:39.710 --> 00:12:39.720 align:start position:0% that if we uh use the composite function 00:12:39.720 --> 00:12:40.910 align:start position:0% that if we uh use the composite function using 00:12:40.910 --> 00:12:40.920 align:start position:0% using 00:12:40.920 --> 00:12:43.990 align:start position:0% using multivariate<00:12:41.920> uh<00:12:42.160> setup<00:12:43.120> then<00:12:43.399> the<00:12:43.600> Cod 00:12:43.990 --> 00:12:44.000 align:start position:0% multivariate uh setup then the Cod 00:12:44.000 --> 00:12:46.550 align:start position:0% multivariate uh setup then the Cod becomes<00:12:44.560> to<00:12:45.560> uh 00:12:46.550 --> 00:12:46.560 align:start position:0% becomes to uh 00:12:46.560 --> 00:12:50.069 align:start position:0% becomes to uh logarithmic<00:12:47.560> and<00:12:47.920> if<00:12:48.040> we<00:12:48.320> maximize<00:12:48.800> the 00:12:50.069 --> 00:12:50.079 align:start position:0% logarithmic and if we maximize the 00:12:50.079 --> 00:12:52.430 align:start position:0% logarithmic and if we maximize the parallelization<00:12:51.079> uh<00:12:51.199> we<00:12:51.399> thought<00:12:51.760> that<00:12:52.079> okay 00:12:52.430 --> 00:12:52.440 align:start position:0% parallelization uh we thought that okay 00:12:52.440 --> 00:12:55.150 align:start position:0% parallelization uh we thought that okay here's<00:12:52.760> the<00:12:53.079> composite<00:12:53.519> function<00:12:53.959> cost<00:12:54.959> and 00:12:55.150 --> 00:12:55.160 align:start position:0% here's the composite function cost and 00:12:55.160 --> 00:12:57.829 align:start position:0% here's the composite function cost and in<00:12:55.320> Univar<00:12:56.000> function<00:12:56.399> it<00:12:56.560> was<00:12:56.839> the<00:12:57.120> really 00:12:57.829 --> 00:12:57.839 align:start position:0% in Univar function it was the really 00:12:57.839 --> 00:13:00.389 align:start position:0% in Univar function it was the really high<00:12:58.399> because<00:12:58.639> the<00:12:58.760> degree<00:12:59.199> was<00:12:59.399> exploding 00:13:00.389 --> 00:13:00.399 align:start position:0% high because the degree was exploding 00:13:00.399 --> 00:13:03.829 align:start position:0% high because the degree was exploding but<00:13:00.639> in<00:13:01.440> a<00:13:01.720> multivariate<00:13:02.720> setup<00:13:03.519> we<00:13:03.639> can 00:13:03.829 --> 00:13:03.839 align:start position:0% but in a multivariate setup we can 00:13:03.839 --> 00:13:06.990 align:start position:0% but in a multivariate setup we can actually<00:13:04.279> log<00:13:05.160> Lo<00:13:05.600> logarithmically<00:13:06.600> change 00:13:06.990 --> 00:13:07.000 align:start position:0% actually log Lo logarithmically change 00:13:07.000 --> 00:13:09.670 align:start position:0% actually log Lo logarithmically change that<00:13:07.760> and<00:13:07.920> the<00:13:08.120> result<00:13:08.600> is<00:13:08.839> actually<00:13:09.240> like 00:13:09.670 --> 00:13:09.680 align:start position:0% that and the result is actually like 00:13:09.680 --> 00:13:12.389 align:start position:0% that and the result is actually like okay<00:13:10.480> it<00:13:10.680> depends<00:13:11.040> on<00:13:11.199> the<00:13:11.360> number<00:13:11.600> of<00:13:11.800> rounds 00:13:12.389 --> 00:13:12.399 align:start position:0% okay it depends on the number of rounds 00:13:12.399 --> 00:13:15.269 align:start position:0% okay it depends on the number of rounds Times<00:13:13.240> uh<00:13:13.480> the<00:13:13.680> composite<00:13:14.240> function<00:13:14.639> cost 00:13:15.269 --> 00:13:15.279 align:start position:0% Times uh the composite function cost 00:13:15.279 --> 00:13:20.189 align:start position:0% Times uh the composite function cost evaluation<00:13:15.920> of<00:13:16.079> the<00:13:16.240> composite<00:13:16.639> function 00:13:20.189 --> 00:13:20.199 align:start position:0% 00:13:20.199 --> 00:13:24.389 align:start position:0% cost<00:13:21.199> and<00:13:21.800> once<00:13:22.600> again<00:13:23.600> composite<00:13:24.040> function 00:13:24.389 --> 00:13:24.399 align:start position:0% cost and once again composite function 00:13:24.399 --> 00:13:27.350 align:start position:0% cost and once again composite function is<00:13:24.560> a<00:13:24.920> very<00:13:25.199> very<00:13:25.480> generalized<00:13:26.199> version<00:13:26.800> of<00:13:27.160> a 00:13:27.350 --> 00:13:27.360 align:start position:0% is a very very generalized version of a 00:13:27.360 --> 00:13:32.670 align:start position:0% is a very very generalized version of a gkr<00:13:28.000> is<00:13:28.360> approach 00:13:32.670 --> 00:13:32.680 align:start position:0% 00:13:32.680 --> 00:13:35.590 align:start position:0% um<00:13:33.680> and<00:13:33.839> to<00:13:34.079> demonstrate<00:13:34.680> our<00:13:34.959> thesis 00:13:35.590 --> 00:13:35.600 align:start position:0% um and to demonstrate our thesis 00:13:35.600 --> 00:13:38.110 align:start position:0% um and to demonstrate our thesis actually<00:13:35.880> we<00:13:36.120> implemented<00:13:36.760> the<00:13:36.959> ca<00:13:37.320> based<00:13:37.560> Su 00:13:38.110 --> 00:13:38.120 align:start position:0% actually we implemented the ca based Su 00:13:38.120 --> 00:13:41.110 align:start position:0% actually we implemented the ca based Su protocol<00:13:38.600> first<00:13:39.120> in<00:13:39.839> this 00:13:41.110 --> 00:13:41.120 align:start position:0% protocol first in this 00:13:41.120 --> 00:13:44.750 align:start position:0% protocol first in this repository<00:13:42.120> so<00:13:42.320> it<00:13:42.440> was<00:13:42.680> a<00:13:43.360> highly<00:13:44.000> paralyzing 00:13:44.750 --> 00:13:44.760 align:start position:0% repository so it was a highly paralyzing 00:13:44.760 --> 00:13:47.189 align:start position:0% repository so it was a highly paralyzing all<00:13:45.000> the<00:13:45.519> evaluations<00:13:46.519> polinomial 00:13:47.189 --> 00:13:47.199 align:start position:0% all the evaluations polinomial 00:13:47.199 --> 00:13:50.430 align:start position:0% all the evaluations polinomial evaluations<00:13:47.959> using 00:13:50.430 --> 00:13:50.440 align:start position:0% 00:13:50.440 --> 00:13:53.670 align:start position:0% GPU<00:13:51.440> and<00:13:51.600> then<00:13:51.800> we<00:13:52.000> utilize<00:13:52.600> this<00:13:52.800> CA<00:13:53.160> Su<00:13:53.399> check 00:13:53.670 --> 00:13:53.680 align:start position:0% GPU and then we utilize this CA Su check 00:13:53.680 --> 00:13:57.150 align:start position:0% GPU and then we utilize this CA Su check to<00:13:53.800> see<00:13:54.000> the<00:13:54.160> results<00:13:54.519> in<00:13:54.759> this<00:13:55.360> uh<00:13:55.639> ccal<00:13:56.440> cical 00:13:57.150 --> 00:13:57.160 align:start position:0% to see the results in this uh ccal cical 00:13:57.160 --> 00:13:59.590 align:start position:0% to see the results in this uh ccal cical repository<00:13:58.160> we<00:13:58.399> just<00:13:58.560> use 00:13:59.590 --> 00:13:59.600 align:start position:0% repository we just use 00:13:59.600 --> 00:14:02.189 align:start position:0% repository we just use just<00:13:59.800> for<00:14:00.240> easier<00:14:00.920> implementation<00:14:01.920> but 00:14:02.189 --> 00:14:02.199 align:start position:0% just for easier implementation but 00:14:02.199 --> 00:14:03.590 align:start position:0% just for easier implementation but definitely<00:14:02.600> you<00:14:02.680> can<00:14:02.839> change<00:14:03.240> this 00:14:03.590 --> 00:14:03.600 align:start position:0% definitely you can change this 00:14:03.600 --> 00:14:06.389 align:start position:0% definitely you can change this commitment<00:14:04.000> scheme<00:14:04.279> to 00:14:06.389 --> 00:14:06.399 align:start position:0% commitment scheme to 00:14:06.399 --> 00:14:09.150 align:start position:0% commitment scheme to others<00:14:07.399> uh<00:14:07.600> and<00:14:07.839> successfully<00:14:08.560> we<00:14:08.680> could<00:14:08.880> see 00:14:09.150 --> 00:14:09.160 align:start position:0% others uh and successfully we could see 00:14:09.160 --> 00:14:11.189 align:start position:0% others uh and successfully we could see our<00:14:09.440> result<00:14:10.160> approach<00:14:10.519> shows<00:14:10.959> the 00:14:11.189 --> 00:14:11.199 align:start position:0% our result approach shows the 00:14:11.199 --> 00:14:13.389 align:start position:0% our result approach shows the logarithmic<00:14:11.920> increase<00:14:12.519> compared<00:14:13.000> to<00:14:13.199> the 00:14:13.389 --> 00:14:13.399 align:start position:0% logarithmic increase compared to the 00:14:13.399 --> 00:14:15.430 align:start position:0% logarithmic increase compared to the classical<00:14:13.920> approach<00:14:14.920> actually<00:14:15.279> the 00:14:15.430 --> 00:14:15.440 align:start position:0% classical approach actually the 00:14:15.440 --> 00:14:17.949 align:start position:0% classical approach actually the implementation<00:14:16.120> and<00:14:16.360> Benchmark<00:14:17.040> data<00:14:17.399> is<00:14:17.800> is 00:14:17.949 --> 00:14:17.959 align:start position:0% implementation and Benchmark data is is 00:14:17.959 --> 00:14:22.790 align:start position:0% implementation and Benchmark data is is still<00:14:18.320> being<00:14:18.560> fleshed<00:14:19.040> out<00:14:20.279> so<00:14:21.279> uh<00:14:21.639> but<00:14:22.240> we<00:14:22.399> are 00:14:22.790 --> 00:14:22.800 align:start position:0% still being fleshed out so uh but we are 00:14:22.800 --> 00:14:25.790 align:start position:0% still being fleshed out so uh but we are pretty<00:14:23.600> optimistic<00:14:24.440> for<00:14:24.720> about<00:14:25.120> the<00:14:25.320> result 00:14:25.790 --> 00:14:25.800 align:start position:0% pretty optimistic for about the result 00:14:25.800 --> 00:14:28.710 align:start position:0% pretty optimistic for about the result that<00:14:26.279> it's<00:14:26.519> showing<00:14:26.959> the<00:14:27.160> sub<00:14:27.560> linear<00:14:28.560> uh 00:14:28.710 --> 00:14:28.720 align:start position:0% that it's showing the sub linear uh 00:14:28.720 --> 00:14:31.910 align:start position:0% that it's showing the sub linear uh result<00:14:29.519> not<00:14:29.720> only<00:14:30.519> against<00:14:30.920> the<00:14:31.079> witness<00:14:31.519> side 00:14:31.910 --> 00:14:31.920 align:start position:0% result not only against the witness side 00:14:31.920 --> 00:14:35.350 align:start position:0% result not only against the witness side but<00:14:32.120> also<00:14:32.440> against<00:14:32.720> the<00:14:32.880> table 00:14:35.350 --> 00:14:35.360 align:start position:0% 00:14:35.360 --> 00:14:37.710 align:start position:0% side<00:14:36.360> uh<00:14:36.519> the 00:14:37.710 --> 00:14:37.720 align:start position:0% side uh the 00:14:37.720 --> 00:14:40.870 align:start position:0% side uh the conclusion<00:14:38.720> this<00:14:39.279> approach<00:14:39.959> is<00:14:40.160> a<00:14:40.560> very 00:14:40.870 --> 00:14:40.880 align:start position:0% conclusion this approach is a very 00:14:40.880 --> 00:14:42.389 align:start position:0% conclusion this approach is a very simple<00:14:41.240> to 00:14:42.389 --> 00:14:42.399 align:start position:0% simple to 00:14:42.399 --> 00:14:44.550 align:start position:0% simple to understand<00:14:43.399> uh<00:14:43.560> comparing<00:14:43.920> to<00:14:44.079> other<00:14:44.240> look<00:14:44.440> of 00:14:44.550 --> 00:14:44.560 align:start position:0% understand uh comparing to other look of 00:14:44.560 --> 00:14:45.509 align:start position:0% understand uh comparing to other look of argument 00:14:45.509 --> 00:14:45.519 align:start position:0% argument 00:14:45.519 --> 00:14:48.189 align:start position:0% argument approach<00:14:46.519> and<00:14:47.120> it<00:14:47.279> supports<00:14:47.800> table 00:14:48.189 --> 00:14:48.199 align:start position:0% approach and it supports table 00:14:48.199 --> 00:14:49.590 align:start position:0% approach and it supports table decomposition 00:14:49.590 --> 00:14:49.600 align:start position:0% decomposition 00:14:49.600 --> 00:14:51.910 align:start position:0% decomposition gracefully<00:14:50.600> and<00:14:50.839> also<00:14:51.279> it<00:14:51.440> achieves 00:14:51.910 --> 00:14:51.920 align:start position:0% gracefully and also it achieves 00:14:51.920 --> 00:14:53.550 align:start position:0% gracefully and also it achieves sublinear<00:14:52.519> proving 00:14:53.550 --> 00:14:53.560 align:start position:0% sublinear proving 00:14:53.560 --> 00:14:56.470 align:start position:0% sublinear proving time<00:14:54.560> uh<00:14:54.680> my<00:14:54.880> toe<00:14:55.120> was<00:14:55.279> a<00:14:55.399> little<00:14:55.600> bit<00:14:55.800> longer 00:14:56.470 --> 00:14:56.480 align:start position:0% time uh my toe was a little bit longer 00:14:56.480 --> 00:14:59.030 align:start position:0% time uh my toe was a little bit longer than<00:14:57.279> uh<00:14:57.839> compared<00:14:58.160> to<00:14:58.240> the<00:14:58.320> given<00:14:58.560> time<00:14:58.759> so<00:14:58.920> I 00:14:59.030 --> 00:14:59.040 align:start position:0% than uh compared to the given time so I 00:14:59.040 --> 00:15:01.470 align:start position:0% than uh compared to the given time so I I<00:14:59.160> cannot<00:14:59.560> have<00:14:59.720> some<00:15:00.079> enough<00:15:00.360> Q&A<00:15:00.880> time<00:15:01.360> I'm 00:15:01.470 --> 00:15:01.480 align:start position:0% I cannot have some enough Q&A time I'm 00:15:01.480 --> 00:15:03.550 align:start position:0% I cannot have some enough Q&A time I'm going<00:15:01.600> to<00:15:01.720> be<00:15:01.880> out<00:15:02.120> there<00:15:02.560> so<00:15:03.079> thank<00:15:03.240> you<00:15:03.399> so 00:15:03.550 --> 00:15:03.560 align:start position:0% going to be out there so thank you so 00:15:03.560 --> 00:15:07.189 align:start position:0% going to be out there so thank you so much<00:15:04.160> uh<00:15:04.279> coming<00:15:04.519> to<00:15:04.680> my 00:15:07.189 --> 00:15:07.199 align:start position:0% 00:15:07.199 --> 00:15:09.749 align:start position:0% talk<00:15:08.199> thank<00:15:08.360> you<00:15:08.480> very<00:15:08.680> much<00:15:08.880> man<00:15:09.320> for<00:15:09.480> your 00:15:09.749 --> 00:15:09.759 align:start position:0% talk thank you very much man for your 00:15:09.759 --> 00:15:11.550 align:start position:0% talk thank you very much man for your wonderful<00:15:10.279> presentation<00:15:10.759> and<00:15:10.920> teaching<00:15:11.360> us 00:15:11.550 --> 00:15:11.560 align:start position:0% wonderful presentation and teaching us 00:15:11.560 --> 00:15:14.230 align:start position:0% wonderful presentation and teaching us about<00:15:11.800> C<00:15:12.120> lookup<00:15:12.839> thank<00:15:13.040> you<00:15:13.399> and<00:15:13.839> uh<00:15:14.040> we're 00:15:14.230 --> 00:15:14.240 align:start position:0% about C lookup thank you and uh we're 00:15:14.240 --> 00:15:18.279 align:start position:0% about C lookup thank you and uh we're going<00:15:14.320> to<00:15:14.519> start<00:15:14.839> at<00:15:15.120> 350<00:15:15.880> with<00:15:16.000> the