913:
informative to talk about significant algorithmic progress "by the computational complexity theory community." It is a remarkable fact of the development of the sciences how one area impacts another, and this example deserves highlighting. Prior to this invasion of coding theory by the computational complexity theory community, the central paradigms of complexity theory (asymptotic thinking, rates of growth, "polynomial time," etc.) received very little attention in the "coding theory community." --
84:
74:
53:
273:
182:
158:
22:
903:
This article begins with representing coding theory as part of computer science ("In computer science, particularly in coding theory..."). I think this is somewhat misleading; coding theory is at the intersection of several major disciplines. Mathematics and electrical engineering have at least
907:
The article mentions several times the significant algorithmic progress "by the coding theory community." This designation of the community responsible for the recent progress on list decoding is in a way a tautology (whoever makes significant progress on coding theory is a member of the coding
912:
community. The central problems and paradigms of computational complexity theory (such as probabilistically checkable proofs), rather than those of information theory, have driven the agenda that resulted in these major contributions to information theory. It would therefore be far more
294:
908:
theory community by definition); in another way it is a serious misrepresentation. The community that made this progress is very clearly identifiable: it is the theory of computing (theoretical computer science) community; and more specifically, the
652:
318:
946:
140:
458:
375:
313:
904:
as much claim on coding theory as does computer science. I suggest to say "In mathematics, computer science, and electrical engineering, particularly in coding theory..."
729:
956:
246:
236:
686:
782:
828:
961:
802:
749:
539:
856:
198:
951:
941:
420:
222:
130:
936:
394:
259:
189:
163:
106:
483:
366:
885:
863:
347:
97:
58:
544:
439:
404:
285:
33:
414:
328:
449:
197:
related articles on
Knowledge. If you would like to participate, please visit the project page, where you can join
476:
21:
889:
867:
385:
39:
83:
918:
105:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
914:
691:
89:
73:
52:
304:
356:
194:
884:
The article has a lot of information related to
Hamming balls. Except their definition...
657:
754:
807:
430:
272:
228:
787:
734:
524:
295:
Requested articles/Applied arts and sciences/Computer science, computing, and
Internet
930:
833:
102:
79:
337:
181:
157:
922:
893:
871:
688:, but in the Sketch of proof section it is claimed that "The quantity
731:
gives a very good estimate on the volume of a
Hamming ball of radius
413:
Find pictures for the biographies of computer scientists (see
231:
in the banner shell. Please resolve this conflict if possible.
227:
This article has been given a rating which conflicts with the
15:
647:{\displaystyle H_{q}(p)=-p\log _{q}(p)-(1-p)\log _{q}(1-p)}
784:". This can't be true, as this number is increasing in
859:, but the current generalisation seems to be wrong.
837:
810:
790:
757:
737:
694:
660:
547:
527:
193:, a collaborative effort to improve the coverage of
101:, a collaborative effort to improve the coverage of
849:
822:
804:. As far as I can see, the Theorem only holds for
796:
776:
743:
723:
680:
646:
533:
319:Computer science articles needing expert attention
947:C-Class articles with conflicting quality ratings
459:WikiProject Computer science/Unreferenced BLPs
8:
376:Computer science articles without infoboxes
314:Computer science articles needing attention
19:
280:Here are some tasks awaiting attention:
254:
152:
47:
836:
809:
789:
768:
756:
736:
704:
699:
693:
670:
659:
620:
580:
552:
546:
526:
957:Low-importance Computer science articles
830:. I guess it can be generalised to all
154:
49:
207:Knowledge:WikiProject Computer science
962:WikiProject Computer science articles
210:Template:WikiProject Computer science
7:
899:What discipline? Which "community"?
187:This article is within the scope of
95:This article is within the scope of
38:It is of interest to the following
395:Timeline of computing 2020–present
229:project-independent quality rating
14:
952:C-Class Computer science articles
942:Low-priority mathematics articles
421:Computing articles needing images
115:Knowledge:WikiProject Mathematics
937:Start-Class mathematics articles
271:
180:
156:
118:Template:WikiProject Mathematics
82:
72:
51:
20:
910:computational complexity theory
241:This article has been rated as
135:This article has been rated as
765:
758:
716:
710:
641:
629:
613:
601:
595:
589:
564:
558:
1:
923:07:57, 19 December 2012 (UTC)
475:Tag all relevant articles in
201:and see a list of open tasks.
109:and see a list of open tasks.
894:09:10, 9 November 2010 (UTC)
751:centered around any word in
724:{\displaystyle q^{H_{q}(p)}}
484:WikiProject Computer science
260:WikiProject Computer science
190:WikiProject Computer science
415:List of computer scientists
978:
872:14:04, 22 March 2014 (UTC)
247:project's importance scale
477:Category:Computer science
253:
240:
226:
213:Computer science articles
175:
134:
67:
46:
479:and sub-categories with
141:project's priority scale
98:WikiProject Mathematics
852:
824:
798:
778:
745:
725:
682:
648:
535:
440:Computer science stubs
28:This article is rated
853:
850:{\displaystyle q: -->
825:
799:
779:
746:
726:
683:
681:{\displaystyle p=1/2}
649:
536:
835:
808:
788:
777:{\displaystyle ^{n}}
755:
735:
692:
658:
545:
525:
258:Things you can help
121:mathematics articles
823:{\displaystyle q=2}
847:
820:
794:
774:
741:
721:
678:
644:
531:
90:Mathematics portal
34:content assessment
797:{\displaystyle p}
744:{\displaystyle p}
534:{\displaystyle q}
514:
513:
510:
509:
506:
505:
502:
501:
498:
497:
151:
150:
147:
146:
969:
858:
855:
854:
848:
829:
827:
826:
821:
803:
801:
800:
795:
783:
781:
780:
775:
773:
772:
750:
748:
747:
742:
730:
728:
727:
722:
720:
719:
709:
708:
687:
685:
684:
679:
674:
654:is maximize for
653:
651:
650:
645:
625:
624:
585:
584:
557:
556:
540:
538:
537:
532:
488:
482:
357:Computer science
286:Article requests
275:
268:
267:
255:
215:
214:
211:
208:
205:
204:Computer science
195:Computer science
184:
177:
176:
171:
168:
164:Computer science
160:
153:
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
977:
976:
972:
971:
970:
968:
967:
966:
927:
926:
901:
882:
832:
831:
806:
805:
786:
785:
764:
753:
752:
733:
732:
700:
695:
690:
689:
656:
655:
616:
576:
548:
543:
542:
523:
522:
519:
494:
491:
486:
480:
468:Project-related
463:
444:
425:
399:
380:
361:
342:
323:
299:
212:
209:
206:
203:
202:
169:
166:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
975:
973:
965:
964:
959:
954:
949:
944:
939:
929:
928:
900:
897:
881:
880:Hamming balls?
878:
876:
846:
843:
840:
819:
816:
813:
793:
771:
767:
763:
760:
740:
718:
715:
712:
707:
703:
698:
677:
673:
669:
666:
663:
643:
640:
637:
634:
631:
628:
623:
619:
615:
612:
609:
606:
603:
600:
597:
594:
591:
588:
583:
579:
575:
572:
569:
566:
563:
560:
555:
551:
530:
518:
515:
512:
511:
508:
507:
504:
503:
500:
499:
496:
495:
493:
492:
490:
489:
472:
464:
462:
461:
455:
445:
443:
442:
436:
426:
424:
423:
418:
410:
400:
398:
397:
391:
381:
379:
378:
372:
362:
360:
359:
353:
343:
341:
340:
334:
324:
322:
321:
316:
310:
300:
298:
297:
291:
279:
277:
276:
264:
263:
251:
250:
243:Low-importance
239:
233:
232:
225:
219:
218:
216:
199:the discussion
185:
173:
172:
170:Low‑importance
161:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
974:
963:
960:
958:
955:
953:
950:
948:
945:
943:
940:
938:
935:
934:
932:
925:
924:
920:
916:
911:
905:
898:
896:
895:
891:
887:
879:
877:
874:
873:
869:
865:
860:
844:
841:
838:
817:
814:
811:
791:
769:
761:
738:
713:
705:
701:
696:
675:
671:
667:
664:
661:
638:
635:
632:
626:
621:
617:
610:
607:
604:
598:
592:
586:
581:
577:
573:
570:
567:
561:
553:
549:
528:
517:False Theorem
516:
485:
478:
474:
473:
471:
469:
465:
460:
457:
456:
454:
452:
451:
446:
441:
438:
437:
435:
433:
432:
427:
422:
419:
416:
412:
411:
409:
407:
406:
401:
396:
393:
392:
390:
388:
387:
382:
377:
374:
373:
371:
369:
368:
363:
358:
355:
354:
352:
350:
349:
344:
339:
336:
335:
333:
331:
330:
325:
320:
317:
315:
312:
311:
309:
307:
306:
301:
296:
293:
292:
290:
288:
287:
282:
281:
278:
274:
270:
269:
266:
265:
261:
257:
256:
252:
248:
244:
238:
235:
234:
230:
224:
221:
220:
217:
200:
196:
192:
191:
186:
183:
179:
178:
174:
165:
162:
159:
155:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
909:
906:
902:
886:134.58.42.46
883:
875:
864:31.54.122.93
861:
520:
467:
466:
450:Unreferenced
448:
447:
429:
428:
403:
402:
384:
383:
365:
364:
346:
345:
327:
326:
303:
302:
284:
283:
242:
188:
137:Low-priority
136:
96:
62:Low‑priority
40:WikiProjects
112:Mathematics
103:mathematics
59:Mathematics
30:Start-class
931:Categories
857:2}" /: -->
521:For fixed
338:Computing
834:2}": -->
386:Maintain
329:Copyedit
367:Infobox
305:Cleanup
245:on the
167:C‑class
139:on the
915:Lbabai
348:Expand
36:scale.
842:: -->
431:Stubs
405:Photo
262:with:
919:talk
890:talk
868:talk
618:log
578:log
237:Low
131:Low
933::
921:)
892:)
870:)
862:--
851:2}
636:−
627:
608:−
599:−
587:
571:−
541:,
487:}}
481:{{
917:(
888:(
866:(
845:2
839:q
818:2
815:=
812:q
792:p
770:n
766:]
762:q
759:[
739:p
717:)
714:p
711:(
706:q
702:H
697:q
676:2
672:/
668:1
665:=
662:p
642:)
639:p
633:1
630:(
622:q
614:)
611:p
605:1
602:(
596:)
593:p
590:(
582:q
574:p
568:=
565:)
562:p
559:(
554:q
550:H
529:q
470::
453::
434::
417:)
408::
389::
370::
351::
332::
308::
289::
249:.
223:C
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
