615:
384:
769:
1013:
945:
477:
221:
99:
522:
682:
1045:
416:
1200:
635:
133:
1154:
1107:
1072:
862:
827:
800:
716:
71:
1174:
1127:
882:
161:
1202:. Among all codes that do not contain repetitions, the long code has the longest possible output. Moreover, it contains all non-repeating codes as a subcode.
1242:
245:
527:
293:
725:
271:
259:
238:
950:
279:
887:
425:
1237:
275:
231:
174:
76:
482:
640:
688:
1018:
389:
1179:
620:
112:
1132:
1085:
1050:
835:
805:
778:
694:
49:
719:
1220:
Limits of
Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
1159:
1112:
867:
278:. Long codes have an extremely poor rate, but play a fundamental role in the theory of
146:
1231:
263:
832:
An equivalent definition of the long code is as follows: The Long code encoding of
772:
167:
139:
105:
42:
35:
864:
is defined to be the truth table of the
Boolean dictatorship function on the
1082:
The long code does not contain repetitions, in the sense that the function
691:
is a subcode of the long code, and can be obtained by only using functions
610:{\displaystyle f_{1}(x)\circ f_{2}(x)\circ \dots \circ f_{2^{n}}(x)}
1219:
802:
such functions, the block length of the Walsh-Hadamard code is
379:{\displaystyle f_{1},\dots ,f_{2^{n}}:\{0,1\}^{k}\to \{0,1\}}
637:
denotes concatenation of strings. This string has length
764:{\displaystyle \mathbb {F} _{2}^{k}\to \mathbb {F} _{2}}
1182:
1162:
1135:
1115:
1088:
1053:
1021:
953:
890:
870:
838:
808:
781:
728:
697:
643:
623:
530:
485:
428:
392:
296:
177:
149:
115:
79:
52:
1129:
th bit of the output is different from any function
166:
138:
104:
41:
31:
26:
21:
1194:
1168:
1148:
1121:
1101:
1066:
1039:
1007:
939:
876:
856:
821:
794:
763:
710:
676:
629:
609:
516:
471:
410:
378:
215:
155:
127:
93:
65:
239:
8:
934:
922:
910:
897:
505:
492:
466:
454:
442:
429:
373:
361:
349:
336:
1008:{\displaystyle f(x_{1},\dots ,x_{n})=x_{j}}
479:. Then the long code encoding of a message
246:
232:
1181:
1161:
1140:
1134:
1114:
1093:
1087:
1058:
1052:
1020:
999:
983:
964:
952:
913:
889:
869:
837:
813:
807:
786:
780:
755:
751:
750:
740:
735:
731:
730:
727:
702:
696:
666:
661:
648:
642:
622:
590:
585:
557:
535:
529:
508:
484:
445:
427:
391:
352:
325:
320:
301:
295:
207:
185:
176:
148:
114:
87:
86:
78:
57:
51:
940:{\displaystyle f:\{0,1\}^{n}\to \{0,1\}}
884:th coordinate, i.e., the truth table of
775:with two elements. Since there are only
1211:
472:{\displaystyle \{0,1\}^{k}\to \{0,1\}}
18:
7:
216:{\displaystyle (2^{n},\log n)_{2}}
14:
94:{\displaystyle n\in \mathbb {N} }
1015:. Thus, the Long code encodes a
517:{\displaystyle x\in \{0,1\}^{k}}
677:{\displaystyle 2^{n}=2^{2^{k}}}
1243:Error detection and correction
1034:
1022:
989:
957:
919:
851:
845:
746:
722:when interpreted as functions
604:
598:
569:
563:
547:
541:
451:
358:
204:
178:
1:
260:theoretical computer science
1259:
1176:th bit of the output for
280:hardness of approximation
227:
1040:{\displaystyle (\log n)}
411:{\displaystyle k=\log n}
1195:{\displaystyle j\neq i}
1196:
1170:
1150:
1123:
1103:
1068:
1041:
1009:
941:
878:
858:
823:
796:
765:
712:
678:
631:
630:{\displaystyle \circ }
611:
518:
473:
412:
380:
217:
157:
129:
128:{\displaystyle \log n}
95:
67:
1197:
1171:
1151:
1149:{\displaystyle f_{j}}
1124:
1104:
1102:{\displaystyle f_{i}}
1069:
1067:{\displaystyle 2^{n}}
1042:
1010:
942:
879:
859:
857:{\displaystyle j\in }
824:
822:{\displaystyle 2^{k}}
797:
795:{\displaystyle 2^{k}}
766:
713:
711:{\displaystyle f_{i}}
679:
632:
612:
519:
474:
413:
381:
272:error-correcting code
218:
158:
130:
96:
68:
66:{\displaystyle 2^{n}}
1218:Definition 7.3.1 in
1180:
1160:
1133:
1113:
1086:
1051:
1019:
951:
888:
868:
836:
806:
779:
726:
695:
641:
621:
528:
483:
426:
390:
294:
175:
147:
113:
77:
50:
16:Computational theory
745:
689:Walsh-Hadamard code
1192:
1166:
1146:
1119:
1099:
1064:
1037:
1005:
937:
874:
854:
819:
792:
761:
729:
708:
674:
627:
607:
514:
469:
408:
376:
213:
153:
125:
91:
63:
1169:{\displaystyle j}
1122:{\displaystyle i}
1047:-bit string as a
877:{\displaystyle j}
276:locally decodable
256:
255:
156:{\displaystyle 2}
1250:
1222:
1216:
1201:
1199:
1198:
1193:
1175:
1173:
1172:
1167:
1155:
1153:
1152:
1147:
1145:
1144:
1128:
1126:
1125:
1120:
1108:
1106:
1105:
1100:
1098:
1097:
1073:
1071:
1070:
1065:
1063:
1062:
1046:
1044:
1043:
1038:
1014:
1012:
1011:
1006:
1004:
1003:
988:
987:
969:
968:
946:
944:
943:
938:
918:
917:
883:
881:
880:
875:
863:
861:
860:
855:
828:
826:
825:
820:
818:
817:
801:
799:
798:
793:
791:
790:
770:
768:
767:
762:
760:
759:
754:
744:
739:
734:
720:linear functions
717:
715:
714:
709:
707:
706:
683:
681:
680:
675:
673:
672:
671:
670:
653:
652:
636:
634:
633:
628:
616:
614:
613:
608:
597:
596:
595:
594:
562:
561:
540:
539:
523:
521:
520:
515:
513:
512:
478:
476:
475:
470:
450:
449:
417:
415:
414:
409:
385:
383:
382:
377:
357:
356:
332:
331:
330:
329:
306:
305:
248:
241:
234:
222:
220:
219:
214:
212:
211:
190:
189:
162:
160:
159:
154:
134:
132:
131:
126:
100:
98:
97:
92:
90:
72:
70:
69:
64:
62:
61:
19:
1258:
1257:
1253:
1252:
1251:
1249:
1248:
1247:
1228:
1227:
1226:
1225:
1217:
1213:
1208:
1178:
1177:
1158:
1157:
1136:
1131:
1130:
1111:
1110:
1089:
1084:
1083:
1080:
1054:
1049:
1048:
1017:
1016:
995:
979:
960:
949:
948:
909:
886:
885:
866:
865:
834:
833:
809:
804:
803:
782:
777:
776:
749:
724:
723:
698:
693:
692:
662:
657:
644:
639:
638:
619:
618:
586:
581:
553:
531:
526:
525:
504:
481:
480:
441:
424:
423:
422:functions from
418:be the list of
388:
387:
348:
321:
316:
297:
292:
291:
288:
252:
203:
181:
173:
172:
145:
144:
111:
110:
75:
74:
53:
48:
47:
17:
12:
11:
5:
1256:
1254:
1246:
1245:
1240:
1230:
1229:
1224:
1223:
1210:
1209:
1207:
1204:
1191:
1188:
1185:
1165:
1156:computing the
1143:
1139:
1118:
1109:computing the
1096:
1092:
1079:
1076:
1061:
1057:
1036:
1033:
1030:
1027:
1024:
1002:
998:
994:
991:
986:
982:
978:
975:
972:
967:
963:
959:
956:
936:
933:
930:
927:
924:
921:
916:
912:
908:
905:
902:
899:
896:
893:
873:
853:
850:
847:
844:
841:
816:
812:
789:
785:
758:
753:
748:
743:
738:
733:
705:
701:
669:
665:
660:
656:
651:
647:
626:
606:
603:
600:
593:
589:
584:
580:
577:
574:
571:
568:
565:
560:
556:
552:
549:
546:
543:
538:
534:
524:is the string
511:
507:
503:
500:
497:
494:
491:
488:
468:
465:
462:
459:
456:
453:
448:
444:
440:
437:
434:
431:
407:
404:
401:
398:
395:
375:
372:
369:
366:
363:
360:
355:
351:
347:
344:
341:
338:
335:
328:
324:
319:
315:
312:
309:
304:
300:
287:
284:
254:
253:
251:
250:
243:
236:
228:
225:
224:
210:
206:
202:
199:
196:
193:
188:
184:
180:
170:
164:
163:
152:
142:
136:
135:
124:
121:
118:
108:
106:Message length
102:
101:
89:
85:
82:
60:
56:
45:
39:
38:
33:
29:
28:
27:Classification
24:
23:
15:
13:
10:
9:
6:
4:
3:
2:
1255:
1244:
1241:
1239:
1238:Coding theory
1236:
1235:
1233:
1221:
1215:
1212:
1205:
1203:
1189:
1186:
1183:
1163:
1141:
1137:
1116:
1094:
1090:
1077:
1075:
1074:-bit string.
1059:
1055:
1031:
1028:
1025:
1000:
996:
992:
984:
980:
976:
973:
970:
965:
961:
954:
931:
928:
925:
914:
906:
903:
900:
894:
891:
871:
848:
842:
839:
830:
814:
810:
787:
783:
774:
756:
741:
736:
721:
703:
699:
690:
685:
667:
663:
658:
654:
649:
645:
624:
601:
591:
587:
582:
578:
575:
572:
566:
558:
554:
550:
544:
536:
532:
509:
501:
498:
495:
489:
486:
463:
460:
457:
446:
438:
435:
432:
421:
405:
402:
399:
396:
393:
370:
367:
364:
353:
345:
342:
339:
333:
326:
322:
317:
313:
310:
307:
302:
298:
285:
283:
281:
277:
273:
269:
265:
264:coding theory
261:
249:
244:
242:
237:
235:
230:
229:
226:
208:
200:
197:
194:
191:
186:
182:
171:
169:
165:
150:
143:
141:
140:Alphabet size
137:
122:
119:
116:
109:
107:
103:
83:
80:
58:
54:
46:
44:
40:
37:
34:
30:
25:
20:
1214:
1081:
831:
773:finite field
686:
419:
289:
267:
257:
43:Block length
1232:Categories
1206:References
1078:Properties
286:Definition
36:Block code
22:Math logic
1187:≠
1029:
974:…
920:→
843:∈
747:→
718:that are
625:∘
579:∘
576:⋯
573:∘
551:∘
490:∈
452:→
403:
359:→
311:…
268:long code
198:
120:
84:∈
73:for some
274:that is
168:Notation
771:on the
617:where
270:is an
266:, the
947:with
223:-code
687:The
386:for
290:Let
262:and
32:Type
1026:log
420:all
400:log
258:In
195:log
117:log
1234::
829:.
684:.
282:.
1190:i
1184:j
1164:j
1142:j
1138:f
1117:i
1095:i
1091:f
1060:n
1056:2
1035:)
1032:n
1023:(
1001:j
997:x
993:=
990:)
985:n
981:x
977:,
971:,
966:1
962:x
958:(
955:f
935:}
932:1
929:,
926:0
923:{
915:n
911:}
907:1
904:,
901:0
898:{
895::
892:f
872:j
852:]
849:n
846:[
840:j
815:k
811:2
788:k
784:2
757:2
752:F
742:k
737:2
732:F
704:i
700:f
668:k
664:2
659:2
655:=
650:n
646:2
605:)
602:x
599:(
592:n
588:2
583:f
570:)
567:x
564:(
559:2
555:f
548:)
545:x
542:(
537:1
533:f
510:k
506:}
502:1
499:,
496:0
493:{
487:x
467:}
464:1
461:,
458:0
455:{
447:k
443:}
439:1
436:,
433:0
430:{
406:n
397:=
394:k
374:}
371:1
368:,
365:0
362:{
354:k
350:}
346:1
343:,
340:0
337:{
334::
327:n
323:2
318:f
314:,
308:,
303:1
299:f
247:e
240:t
233:v
209:2
205:)
201:n
192:,
187:n
183:2
179:(
151:2
123:n
88:N
81:n
59:n
55:2
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.