184:
first player into another pattern (or, possibly, leaving it unchanged). The goal of the first player is to have as many lights remaining lit at the end of the game as possible, and the goal of the second player is to have as few lights remaining lit as possible. Therefore, the first player should choose a pattern of lights for which the second player cannot turn off many lights.
1953:
that is as far as possible from the linear subspace. The set of bulbs whose state is changed by the second player, with best play, gives the closest point in the linear subspace. The set of bulbs that remain lit after these choices are the ones whose number defines the
Hamming distance between these
183:
The game is played in two rounds. In the first round, the first player uses the switches that control individual lights, to set the lights on or off arbitrarily. In the second round, the second player uses the switches that control rows or columns of lights, changing the pattern of lights set by the
179:
switches, one for each row or column of lightbulbs. Whenever any of these switches is flipped, every lightbulb in the row or column that it controls changes from off to on or from on to off, depending on its previous state. When flipping more than one switch, the order in which the switches are
1778:
operation on the sets of lit bulbs). One can define a linear subspace consisting of all patterns that the second player can turn completely off, or equivalently of all patterns that the second player could create starting with a board that is completely off. Although the second player has
152:
switches on one side of the room controls each lightbulb individually. Flipping one of these switches changes its lightbulb from off to on or from on to off, depending on its previous state. On the other side of the room is another bank of
990:
1391:
1205:, but if it is larger the second player can flip all row switches to get a value that is smaller by the same amount. This random strategy for the second player can be made non-random using the
47:
controlled by two banks of switches, with one game player trying to turn many lightbulbs on and the other trying to keep as many as possible off. It can be used to demonstrate the concept of
1087:
2036:. CBMS-NSF Regional Conference Series in Applied Mathematics. Vol. 64 (Second ed.). Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics. pp. 45–50.
1951:
1746:
1619:
1532:
312:
1203:
1123:
476:
1318:
1565:
1292:
1167:
261:
224:
1849:
1772:
1260:
737:
618:
87:
707:
644:
1917:
1810:
1712:
856:
681:
509:
478:. Beyond the question of how to play well in an individual game, a broader question that has been the object of mathematical research is to characterize the value of
2462:
2175:
1881:
1674:
418:
369:
177:
150:
2237:
1642:
1585:
1495:
1471:
1451:
1431:
1018:
760:
589:
569:
549:
529:
389:
340:
127:
107:
180:
flipped does not make a difference to the outcome: the same lightbulbs will be lit at the end of the sequence of flips no matter what order they are flipped.
1774:
array of lightbulbs, with a vector addition operation that combines two patterns by lighting the bulbs that appear in exactly one of the two patterns (the
2354:
2537:
1000:
Because there are exponentially many choices for which switches to flip, an exhaustive search for the optimal choice is not possible for large
2251:. Proceedings of Symposia in Applied Mathematics. Vol. 10. Providence, Rhode Island: American Mathematical Society. pp. 175–178.
1233:
1206:
2414:
Pellegrino, D.; Raposo Jr, A. (2021). "Upper bounds for the constants of
Bennett's inequality and the Gale-Berlekamp switching game".
2438:
2129:
2075:
2049:
420:. Therefore, one can describe the largest number of lights that can be achieved by the best play for the first player as a number
2580:
2575:; Schudy, Warren (2009). "Linear time approximation schemes for the Gale–Berlekamp game and related minimization problems". In
2307:
1228:
Finding the optimal choice for the second player in the game, once the first player has chosen which bulbs to light, is an
2244:
929:
2582:
Proceedings of the 41st Annual ACM Symposium on Theory of
Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009
1323:
1919:
is the covering radius of this code. The set of lit bulbs chosen by the first player, with best play, gives a point of
2624:
2369:
Pellegrino, D.; Raposo Jr, A. (2022). "Constants of the Kahane–Salem–Zygmund inequality asymptotically bounded by 1".
226:
in the
Mathematics Department commons room. David Gale also invented the game independently, some time prior to 1971.
263:
game, how well the second player can do against a first player who plays randomly, and by J. W. Moon and
1026:
2073:
Araújo, Gustavo; Pellegrino, Daniel (2019). "A Gale–Berlekamp permutation-switching problem in higher dimensions".
2492:
63:
The equipment for playing the game consists of a room containing rectangular array of lightbulbs, of dimensions
342:, and the smallest number of lights that can be achieved by the best play for the second player as a number
197:
2349:"Sequence A005311 (Solution to Berlekamp's switching game (or lightbulb game) on an n X n board)"
2619:
1922:
1717:
1590:
1503:
278:
1172:
1092:
2535:
Roth, Ron M.; Viswanathan, Krishnamurthy (2008). "On the hardness of decoding the Gale–Berlekamp code".
275:
choices of the first player, in the limit of large game board sizes, the optimal game value is close to
1297:
423:
1541:
1265:
1128:
2576:
1775:
1567:. The elements of the subspace are called codewords, and the covering radius is the smallest number
923:
1883:, because flipping all of the second player's switches has no effect on the pattern of lit bulbs.
1089:
by playing randomly. Similarly, the second player can obtain a value whose expected distance from
2586:
2517:
2415:
2396:
2378:
2240:
2110:
2084:
1218:
551:, to determine its behavior as a function, or to calculate its value for as many combinations of
240:
203:
1966:, a different puzzle involving turning off lightbulbs using switches that control multiple bulbs
1815:
1751:
1239:
716:
597:
66:
2216:
2045:
1963:
686:
623:
230:
24:
2029:
1889:
1782:
1679:
828:
653:
481:
200:
from 1966 to 1971. While there, he constructed a physical instance of this game for the case
2596:
2546:
2501:
2388:
2316:
2188:
2094:
2037:
2000:
1622:
2558:
2513:
2473:
2444:
2330:
2287:
2256:
2202:
2157:
2106:
2059:
1854:
2572:
2554:
2509:
2469:
2326:
2283:
2252:
2198:
2102:
2055:
1992:
1650:
1474:
1406:
1222:
1214:
1210:
1020:, setting up the question of how well computationally-limited players can play this game.
394:
345:
322:
Mathematically, one can describe the lights turned on by the first player's move as a set
48:
28:
156:
132:
2222:
1627:
1570:
1480:
1456:
1436:
1416:
1003:
745:
574:
554:
534:
514:
374:
325:
112:
92:
2613:
2487:
2400:
1402:
52:
2521:
2114:
2025:
1498:
2466:
Combinatorial theory and its applications, II (Proc. Colloq., BalatonfĂĽred, 1969)
2004:
2344:
1988:
1410:
647:
2321:
2302:
2505:
2392:
2098:
272:
36:
2600:
2550:
2271:
2193:
2153:
2041:
264:
193:
44:
1991:(1987). "Unsolved problems related to the covering radius of codes". In
1229:
1213:
algorithm that obtains the same solution value guarantees. A different
1169:
by playing randomly; this value might either be larger or smaller than
1812:
choices for how to set the second bank of switches, this subspace has
2420:
237:), whose computer experiments can be interpreted as asking, for the
2383:
2089:
1262:
game that can find a choice for the second player that leaves only
2591:
1535:
271:), who address Gleason's question theoretically, showing that for
2275:
2130:"Elwyn Berlekamp, game theorist and coding pioneer, dies at 78"
229:
Early research on related problems included publications by
2348:
1023:
The first player can cause the expected game value to be
1294:
times the minimum possible number of lit bulbs, for any
371:. The best play for the first player is to choose a set
1177:
1097:
1031:
934:
426:
283:
2447:
2225:
2160:
1925:
1892:
1857:
1818:
1785:
1754:
1720:
1682:
1653:
1630:
1593:
1573:
1544:
1506:
1483:
1459:
1439:
1419:
1326:
1300:
1268:
1242:
1175:
1131:
1095:
1029:
1006:
932:
831:
748:
719:
689:
656:
626:
600:
577:
557:
537:
517:
484:
397:
377:
348:
328:
281:
243:
206:
159:
135:
115:
95:
69:
39:, who discovered the same game independently, or the
2303:"The correct solution to Berlekamp's switching game"
1748:
describes all possible patterns of lit bulbs on the
985:{\displaystyle {\tfrac {n^{2}}{2}}-\Theta (n^{3/2})}
2301:Carlson, Jordan; Stolarski, Daniel (October 2004).
2456:
2231:
2169:
1945:
1911:
1875:
1843:
1804:
1766:
1740:
1706:
1668:
1636:
1613:
1579:
1559:
1526:
1489:
1465:
1445:
1425:
1386:{\displaystyle O(n^{2})+2^{O(1/\varepsilon ^{2})}}
1385:
1312:
1286:
1254:
1197:
1161:
1117:
1081:
1012:
984:
850:
754:
731:
701:
675:
638:
612:
583:
563:
543:
523:
503:
470:
412:
383:
363:
334:
306:
255:
218:
171:
144:
121:
101:
81:
2441:; Sulyok, M. (1970). "On the sum of elements of
447:
1714:. For these parameter values, the vector space
1997:Open Problems in Communication and Computation
1082:{\displaystyle {\tfrac {n^{2}}{2}}-O(n^{3/2})}
8:
1401:The Berlekamp switching game can be used in
2152:Brown, Thomas A.; Spencer, Joel H. (1971).
2590:
2446:
2433:
2431:
2419:
2382:
2355:On-Line Encyclopedia of Integer Sequences
2320:
2224:
2192:
2159:
2088:
2020:
2018:
2016:
2014:
1937:
1932:
1928:
1927:
1924:
1897:
1891:
1856:
1823:
1817:
1790:
1784:
1753:
1732:
1727:
1723:
1722:
1719:
1681:
1652:
1629:
1605:
1600:
1596:
1595:
1592:
1572:
1551:
1547:
1546:
1543:
1518:
1513:
1509:
1508:
1505:
1482:
1458:
1438:
1418:
1372:
1363:
1353:
1337:
1325:
1299:
1267:
1241:
1183:
1176:
1174:
1146:
1142:
1130:
1103:
1096:
1094:
1066:
1062:
1037:
1030:
1028:
1005:
969:
965:
940:
933:
931:
836:
830:
747:
718:
688:
661:
655:
625:
599:
576:
556:
536:
516:
489:
483:
450:
431:
425:
396:
376:
347:
327:
298:
282:
280:
268:
242:
205:
158:
134:
114:
94:
68:
2147:
2145:
2143:
2034:Ten Lectures on the Probabilistic Method
1983:
1981:
1979:
711:
2538:IEEE Transactions on Information Theory
1975:
234:
2276:"An extremal problem in matrix theory"
1999:. New York: Springer. pp. 51–56.
2136:. University of California, Berkeley.
7:
2490:(1997). "The fourth moment method".
1946:{\displaystyle \mathbb {F} _{2}^{n}}
1741:{\displaystyle \mathbb {F} _{2}^{n}}
1614:{\displaystyle \mathbb {F} _{2}^{n}}
1527:{\displaystyle \mathbb {F} _{2}^{n}}
1234:polynomial-time approximation scheme
307:{\displaystyle {\tfrac {1}{2}}n^{2}}
1207:method of conditional probabilities
1198:{\displaystyle {\tfrac {n^{2}}{2}}}
1118:{\displaystyle {\tfrac {n^{2}}{2}}}
27:proposed by American mathematician
2128:Sanders, Robert (April 18, 2019).
1132:
955:
471:{\textstyle R_{a,b}=\max _{S}f(S)}
14:
2219:(1960). "A search problem in the
2076:European Journal of Combinatorics
1413:. A binary linear code of length
1313:{\displaystyle \varepsilon >0}
1560:{\displaystyle \mathbb {F} _{2}}
1287:{\displaystyle (1+\varepsilon )}
1162:{\displaystyle \Omega (n^{3/2})}
2371:Journal of Functional Analysis
1851:elements, giving it dimension
1536:finite field with two elements
1378:
1357:
1343:
1330:
1281:
1269:
1156:
1135:
1076:
1055:
979:
958:
465:
459:
407:
401:
358:
352:
31:. It has also been called the
1:
2030:"Lecture 6: Chaos from order"
1232:problem. However, there is a
511:in general, as a function of
33:Gale–Berlekamp switching game
2005:10.1007/978-1-4612-4808-8_11
2177:matrices under line shifts"
1397:Connection to coding theory
256:{\displaystyle 15\times 15}
219:{\displaystyle 10\times 10}
2641:
2345:Sloane, N. J. A.
2322:10.1016/j.disc.2004.06.015
1405:as a demonstration of the
620:array has been solved for
43:. It involves a system of
2585:. ACM. pp. 313–322.
2506:10.1137/S0097539792240005
2493:SIAM Journal on Computing
2393:10.1016/j.jfa.2021.109293
2099:10.1016/j.ejc.2018.10.007
1844:{\displaystyle 2^{a+b-1}}
1767:{\displaystyle a\times b}
1587:such that every point of
1255:{\displaystyle n\times n}
732:{\displaystyle n\times n}
613:{\displaystyle n\times n}
82:{\displaystyle a\times b}
1221:in the complexity class
996:Computational complexity
926:, these numbers grow as
702:{\displaystyle n\leq 20}
639:{\displaystyle n\leq 12}
21:Berlekamp switching game
2601:10.1145/1536414.1536458
2551:10.1109/TIT.2007.915716
2282:. 3(18) (37): 209–211.
2194:10.4064/cm-23-1-165-171
2181:Colloquium Mathematicum
2042:10.1137/1.9781611970074
1995:; Gopinath, B. (eds.).
1912:{\displaystyle R_{a,b}}
1805:{\displaystyle 2^{a+b}}
1707:{\displaystyle d=a+b-1}
851:{\displaystyle R_{n,n}}
676:{\displaystyle R_{n,n}}
504:{\displaystyle R_{a,b}}
198:Murray Hill, New Jersey
41:unbalancing lights game
2458:
2249:Combinatorial Analysis
2233:
2171:
1947:
1913:
1877:
1845:
1806:
1768:
1742:
1708:
1670:
1638:
1615:
1581:
1561:
1528:
1491:
1467:
1447:
1427:
1387:
1314:
1288:
1256:
1199:
1163:
1119:
1083:
1014:
986:
852:
756:
733:
703:
677:
640:
614:
585:
565:
545:
525:
505:
472:
414:
385:
365:
336:
308:
257:
220:
173:
146:
123:
103:
83:
2577:Mitzenmacher, Michael
2459:
2457:{\displaystyle \pm 1}
2234:
2172:
2170:{\displaystyle \pm 1}
1948:
1914:
1878:
1876:{\displaystyle a+b-1}
1846:
1807:
1769:
1743:
1709:
1671:
1639:
1616:
1582:
1562:
1529:
1492:
1468:
1448:
1428:
1388:
1315:
1289:
1257:
1200:
1164:
1120:
1084:
1015:
987:
853:
757:
734:
709:. These numbers are:
704:
678:
641:
615:
594:The case of a square
586:
566:
546:
526:
506:
473:
415:
386:
366:
337:
309:
258:
231:Andrew M. Gleason
221:
174:
147:
124:
104:
84:
2468:. pp. 721–728.
2445:
2308:Discrete Mathematics
2223:
2158:
1923:
1890:
1855:
1816:
1783:
1776:symmetric difference
1752:
1718:
1680:
1669:{\displaystyle n=ab}
1651:
1628:
1591:
1571:
1542:
1504:
1481:
1457:
1437:
1417:
1409:of a certain binary
1324:
1298:
1266:
1240:
1173:
1129:
1093:
1027:
1004:
930:
829:
746:
717:
687:
683:have been found for
654:
624:
598:
575:
555:
535:
515:
482:
424:
413:{\displaystyle f(S)}
395:
375:
364:{\displaystyle f(S)}
346:
326:
279:
241:
204:
192:Berlekamp worked at
157:
133:
113:
93:
67:
1942:
1737:
1610:
1523:
739:
172:{\displaystyle a+b}
2625:Mathematical games
2454:
2358:. OEIS Foundation.
2280:MatematiÄŤki Vesnik
2245:Hall, Marshall Jr.
2229:
2217:Gleason, Andrew M.
2167:
1943:
1926:
1909:
1873:
1841:
1802:
1764:
1738:
1721:
1704:
1666:
1634:
1611:
1594:
1577:
1557:
1524:
1507:
1487:
1463:
1443:
1423:
1383:
1310:
1284:
1252:
1219:parallel algorithm
1195:
1193:
1159:
1115:
1113:
1079:
1047:
1010:
982:
950:
848:
752:
729:
712:
699:
673:
636:
610:
581:
561:
541:
521:
501:
468:
455:
410:
381:
361:
332:
304:
292:
253:
216:
169:
145:{\displaystyle ab}
142:
119:
99:
79:
2232:{\displaystyle n}
2154:"Minimization of
1964:Lights Out (game)
1637:{\displaystyle r}
1580:{\displaystyle r}
1490:{\displaystyle n}
1466:{\displaystyle d}
1446:{\displaystyle d}
1426:{\displaystyle n}
1192:
1112:
1046:
1013:{\displaystyle n}
949:
921:
920:
755:{\displaystyle n}
584:{\displaystyle b}
564:{\displaystyle a}
544:{\displaystyle b}
524:{\displaystyle a}
446:
384:{\displaystyle S}
335:{\displaystyle S}
291:
122:{\displaystyle b}
102:{\displaystyle a}
89:for some numbers
25:mathematical game
16:Mathematical game
2632:
2605:
2604:
2594:
2573:Karpinski, Marek
2569:
2563:
2562:
2545:(3): 1050–1060.
2532:
2526:
2525:
2500:(4): 1188–1207.
2484:
2478:
2477:
2463:
2461:
2460:
2455:
2435:
2426:
2425:
2423:
2411:
2405:
2404:
2386:
2366:
2360:
2359:
2341:
2335:
2334:
2324:
2315:(1–3): 145–150.
2298:
2292:
2291:
2267:
2261:
2260:
2241:Bellman, Richard
2238:
2236:
2235:
2230:
2213:
2207:
2206:
2196:
2187:: 165–171, 177.
2176:
2174:
2173:
2168:
2149:
2138:
2137:
2125:
2119:
2118:
2092:
2070:
2064:
2063:
2022:
2009:
2008:
1993:Cover, Thomas M.
1989:Sloane, N. J. A.
1985:
1952:
1950:
1949:
1944:
1941:
1936:
1931:
1918:
1916:
1915:
1910:
1908:
1907:
1882:
1880:
1879:
1874:
1850:
1848:
1847:
1842:
1840:
1839:
1811:
1809:
1808:
1803:
1801:
1800:
1773:
1771:
1770:
1765:
1747:
1745:
1744:
1739:
1736:
1731:
1726:
1713:
1711:
1710:
1705:
1675:
1673:
1672:
1667:
1643:
1641:
1640:
1635:
1623:Hamming distance
1620:
1618:
1617:
1612:
1609:
1604:
1599:
1586:
1584:
1583:
1578:
1566:
1564:
1563:
1558:
1556:
1555:
1550:
1533:
1531:
1530:
1525:
1522:
1517:
1512:
1496:
1494:
1493:
1488:
1472:
1470:
1469:
1464:
1453:is defined as a
1452:
1450:
1449:
1444:
1432:
1430:
1429:
1424:
1392:
1390:
1389:
1384:
1382:
1381:
1377:
1376:
1367:
1342:
1341:
1319:
1317:
1316:
1311:
1293:
1291:
1290:
1285:
1261:
1259:
1258:
1253:
1204:
1202:
1201:
1196:
1194:
1188:
1187:
1178:
1168:
1166:
1165:
1160:
1155:
1154:
1150:
1124:
1122:
1121:
1116:
1114:
1108:
1107:
1098:
1088:
1086:
1085:
1080:
1075:
1074:
1070:
1048:
1042:
1041:
1032:
1019:
1017:
1016:
1011:
991:
989:
988:
983:
978:
977:
973:
951:
945:
944:
935:
857:
855:
854:
849:
847:
846:
761:
759:
758:
753:
740:
738:
736:
735:
730:
708:
706:
705:
700:
682:
680:
679:
674:
672:
671:
646:. Additionally,
645:
643:
642:
637:
619:
617:
616:
611:
590:
588:
587:
582:
570:
568:
567:
562:
550:
548:
547:
542:
530:
528:
527:
522:
510:
508:
507:
502:
500:
499:
477:
475:
474:
469:
454:
442:
441:
419:
417:
416:
411:
390:
388:
387:
382:
370:
368:
367:
362:
341:
339:
338:
333:
313:
311:
310:
305:
303:
302:
293:
284:
262:
260:
259:
254:
225:
223:
222:
217:
178:
176:
175:
170:
151:
149:
148:
143:
128:
126:
125:
120:
108:
106:
105:
100:
88:
86:
85:
80:
2640:
2639:
2635:
2634:
2633:
2631:
2630:
2629:
2610:
2609:
2608:
2571:
2570:
2566:
2534:
2533:
2529:
2486:
2485:
2481:
2443:
2442:
2437:
2436:
2429:
2413:
2412:
2408:
2368:
2367:
2363:
2343:
2342:
2338:
2300:
2299:
2295:
2269:
2268:
2264:
2221:
2220:
2215:
2214:
2210:
2156:
2155:
2151:
2150:
2141:
2127:
2126:
2122:
2072:
2071:
2067:
2052:
2024:
2023:
2012:
1987:
1986:
1977:
1973:
1960:
1921:
1920:
1893:
1888:
1887:
1853:
1852:
1819:
1814:
1813:
1786:
1781:
1780:
1750:
1749:
1716:
1715:
1678:
1677:
1649:
1648:
1644:of a codeword.
1626:
1625:
1589:
1588:
1569:
1568:
1545:
1540:
1539:
1502:
1501:
1479:
1478:
1475:linear subspace
1455:
1454:
1435:
1434:
1415:
1414:
1407:covering radius
1399:
1368:
1349:
1333:
1322:
1321:
1296:
1295:
1264:
1263:
1238:
1237:
1215:derandomization
1211:polynomial time
1179:
1171:
1170:
1138:
1127:
1126:
1099:
1091:
1090:
1058:
1033:
1025:
1024:
1002:
1001:
998:
961:
936:
928:
927:
832:
827:
826:
744:
743:
715:
714:
685:
684:
657:
652:
651:
622:
621:
596:
595:
573:
572:
553:
552:
533:
532:
513:
512:
485:
480:
479:
427:
422:
421:
393:
392:
391:that maximizes
373:
372:
344:
343:
324:
323:
320:
294:
277:
276:
239:
238:
202:
201:
190:
155:
154:
131:
130:
111:
110:
91:
90:
65:
64:
61:
49:covering radius
29:Elwyn Berlekamp
17:
12:
11:
5:
2638:
2636:
2628:
2627:
2622:
2612:
2611:
2607:
2606:
2564:
2527:
2488:Berger, Bonnie
2479:
2453:
2450:
2427:
2406:
2361:
2336:
2293:
2262:
2228:
2208:
2166:
2163:
2139:
2120:
2065:
2050:
2010:
1974:
1972:
1969:
1968:
1967:
1959:
1956:
1940:
1935:
1930:
1906:
1903:
1900:
1896:
1872:
1869:
1866:
1863:
1860:
1838:
1835:
1832:
1829:
1826:
1822:
1799:
1796:
1793:
1789:
1763:
1760:
1757:
1735:
1730:
1725:
1703:
1700:
1697:
1694:
1691:
1688:
1685:
1665:
1662:
1659:
1656:
1633:
1608:
1603:
1598:
1576:
1554:
1549:
1521:
1516:
1511:
1486:
1462:
1442:
1433:and dimension
1422:
1398:
1395:
1380:
1375:
1371:
1366:
1362:
1359:
1356:
1352:
1348:
1345:
1340:
1336:
1332:
1329:
1309:
1306:
1303:
1283:
1280:
1277:
1274:
1271:
1251:
1248:
1245:
1191:
1186:
1182:
1158:
1153:
1149:
1145:
1141:
1137:
1134:
1111:
1106:
1102:
1078:
1073:
1069:
1065:
1061:
1057:
1054:
1051:
1045:
1040:
1036:
1009:
997:
994:
981:
976:
972:
968:
964:
960:
957:
954:
948:
943:
939:
924:Asymptotically
919:
918:
915:
912:
909:
906:
903:
900:
897:
894:
891:
888:
885:
882:
879:
876:
873:
870:
867:
864:
861:
858:
845:
842:
839:
835:
823:
822:
819:
816:
813:
810:
807:
804:
801:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
768:
765:
762:
751:
728:
725:
722:
713:Solutions for
698:
695:
692:
670:
667:
664:
660:
635:
632:
629:
609:
606:
603:
580:
560:
540:
520:
498:
495:
492:
488:
467:
464:
461:
458:
453:
449:
445:
440:
437:
434:
430:
409:
406:
403:
400:
380:
360:
357:
354:
351:
331:
319:
316:
301:
297:
290:
287:
252:
249:
246:
215:
212:
209:
189:
186:
168:
165:
162:
141:
138:
118:
98:
78:
75:
72:
60:
57:
15:
13:
10:
9:
6:
4:
3:
2:
2637:
2626:
2623:
2621:
2620:Coding theory
2618:
2617:
2615:
2602:
2598:
2593:
2588:
2584:
2583:
2578:
2574:
2568:
2565:
2560:
2556:
2552:
2548:
2544:
2540:
2539:
2531:
2528:
2523:
2519:
2515:
2511:
2507:
2503:
2499:
2495:
2494:
2489:
2483:
2480:
2475:
2471:
2467:
2451:
2448:
2440:
2434:
2432:
2428:
2422:
2417:
2410:
2407:
2402:
2398:
2394:
2390:
2385:
2380:
2377:(2): 109293.
2376:
2372:
2365:
2362:
2357:
2356:
2350:
2346:
2340:
2337:
2332:
2328:
2323:
2318:
2314:
2310:
2309:
2304:
2297:
2294:
2289:
2285:
2281:
2277:
2273:
2270:Moon, J. W.;
2266:
2263:
2258:
2254:
2250:
2246:
2242:
2226:
2218:
2212:
2209:
2204:
2200:
2195:
2190:
2186:
2182:
2178:
2164:
2161:
2148:
2146:
2144:
2140:
2135:
2134:Berkeley News
2131:
2124:
2121:
2116:
2112:
2108:
2104:
2100:
2096:
2091:
2086:
2082:
2078:
2077:
2069:
2066:
2061:
2057:
2053:
2051:0-89871-325-0
2047:
2043:
2039:
2035:
2031:
2027:
2026:Spencer, Joel
2021:
2019:
2017:
2015:
2011:
2006:
2002:
1998:
1994:
1990:
1984:
1982:
1980:
1976:
1970:
1965:
1962:
1961:
1957:
1955:
1938:
1933:
1904:
1901:
1898:
1894:
1884:
1870:
1867:
1864:
1861:
1858:
1836:
1833:
1830:
1827:
1824:
1820:
1797:
1794:
1791:
1787:
1777:
1761:
1758:
1755:
1733:
1728:
1701:
1698:
1695:
1692:
1689:
1686:
1683:
1663:
1660:
1657:
1654:
1645:
1631:
1624:
1606:
1601:
1574:
1552:
1537:
1519:
1514:
1500:
1497:-dimensional
1484:
1476:
1473:-dimensional
1460:
1440:
1420:
1412:
1408:
1404:
1403:coding theory
1396:
1394:
1373:
1369:
1364:
1360:
1354:
1350:
1346:
1338:
1334:
1327:
1307:
1304:
1301:
1278:
1275:
1272:
1249:
1246:
1243:
1235:
1231:
1226:
1224:
1220:
1216:
1212:
1208:
1189:
1184:
1180:
1151:
1147:
1143:
1139:
1109:
1104:
1100:
1071:
1067:
1063:
1059:
1052:
1049:
1043:
1038:
1034:
1021:
1007:
995:
993:
974:
970:
966:
962:
952:
946:
941:
937:
925:
916:
913:
910:
907:
904:
901:
898:
895:
892:
889:
886:
883:
880:
877:
874:
871:
868:
865:
862:
859:
843:
840:
837:
833:
825:
824:
820:
817:
814:
811:
808:
805:
802:
799:
796:
793:
790:
787:
784:
781:
778:
775:
772:
769:
766:
763:
749:
742:
741:
726:
723:
720:
710:
696:
693:
690:
668:
665:
662:
658:
649:
633:
630:
627:
607:
604:
601:
592:
591:as possible.
578:
558:
538:
518:
496:
493:
490:
486:
462:
456:
451:
443:
438:
435:
432:
428:
404:
398:
378:
355:
349:
329:
317:
315:
299:
295:
288:
285:
274:
270:
266:
250:
247:
244:
236:
232:
227:
213:
210:
207:
199:
195:
187:
185:
181:
166:
163:
160:
139:
136:
116:
96:
76:
73:
70:
58:
56:
54:
53:coding theory
50:
46:
42:
38:
34:
30:
26:
22:
2581:
2567:
2542:
2536:
2530:
2497:
2491:
2482:
2465:
2421:2111.00445v3
2409:
2374:
2370:
2364:
2352:
2339:
2312:
2306:
2296:
2279:
2265:
2248:
2211:
2184:
2180:
2133:
2123:
2080:
2074:
2068:
2033:
1996:
1954:two points.
1885:
1646:
1499:vector space
1400:
1227:
1022:
999:
922:
648:lower bounds
593:
321:
228:
191:
182:
129:. A bank of
62:
40:
32:
20:
18:
2464:matrices".
2239:-cube". In
1411:linear code
1209:, giving a
2614:Categories
2439:KomlĂłs, J.
2384:2006.12892
2090:1801.09194
1971:References
1621:is within
1320:, in time
273:almost all
45:lightbulbs
37:David Gale
2592:0811.3244
2449:±
2401:231895733
2272:Moser, L.
2162:±
2083:: 17–30.
1868:−
1834:−
1759:×
1699:−
1534:over the
1370:ε
1302:ε
1279:ε
1247:×
1133:Ω
1050:−
956:Θ
953:−
724:×
694:≤
631:≤
605:×
265:Leo Moser
248:×
211:×
194:Bell Labs
74:×
2522:14313557
2274:(1966).
2247:(eds.).
2115:57760841
2028:(1994).
1958:See also
1236:for the
1217:gives a
318:Analysis
35:, after
2579:(ed.).
2559:2445050
2514:1460721
2474:0299500
2347:(ed.).
2331:2094708
2288:0207570
2257:0114323
2203:0307944
2107:3872901
2060:1249485
1477:of the
1230:NP-hard
267: (
233: (
188:History
2557:
2520:
2512:
2472:
2399:
2329:
2286:
2255:
2201:
2113:
2105:
2058:
2048:
917:≥ 148
2587:arXiv
2518:S2CID
2416:arXiv
2397:S2CID
2379:arXiv
2111:S2CID
2085:arXiv
1886:Then
1676:and
1647:Let
914:≥ 139
911:≥ 122
908:≥ 107
59:Rules
23:is a
2353:The
2046:ISBN
1305:>
905:≥ 96
902:≥ 83
899:≥ 71
896:≥ 60
650:for
571:and
531:and
269:1966
235:1960
109:and
19:The
2597:doi
2547:doi
2502:doi
2389:doi
2375:282
2317:doi
2313:287
2189:doi
2095:doi
2038:doi
2001:doi
1125:is
821:20
448:max
196:in
51:in
2616::
2595:.
2555:MR
2553:.
2543:54
2541:.
2516:.
2510:MR
2508:.
2498:26
2496:.
2470:MR
2430:^
2395:.
2387:.
2373:.
2351:.
2327:MR
2325:.
2311:.
2305:.
2284:MR
2278:.
2253:MR
2243:;
2199:MR
2197:.
2185:23
2183:.
2179:.
2142:^
2132:.
2109:.
2103:MR
2101:.
2093:.
2081:77
2079:.
2056:MR
2054:.
2044:.
2032:.
2013:^
1978:^
1538:,
1393:.
1225:.
1223:NC
992:.
893:54
890:43
887:35
884:27
881:22
878:16
875:11
818:19
815:18
812:17
809:16
806:15
803:14
800:13
797:12
794:11
791:10
697:20
634:12
314:.
251:15
245:15
214:10
208:10
55:.
2603:.
2599::
2589::
2561:.
2549::
2524:.
2504::
2476:.
2452:1
2424:.
2418::
2403:.
2391::
2381::
2333:.
2319::
2290:.
2259:.
2227:n
2205:.
2191::
2165:1
2117:.
2097::
2087::
2062:.
2040::
2007:.
2003::
1939:n
1934:2
1929:F
1905:b
1902:,
1899:a
1895:R
1871:1
1865:b
1862:+
1859:a
1837:1
1831:b
1828:+
1825:a
1821:2
1798:b
1795:+
1792:a
1788:2
1762:b
1756:a
1734:n
1729:2
1724:F
1702:1
1696:b
1693:+
1690:a
1687:=
1684:d
1664:b
1661:a
1658:=
1655:n
1632:r
1607:n
1602:2
1597:F
1575:r
1553:2
1548:F
1520:n
1515:2
1510:F
1485:n
1461:d
1441:d
1421:n
1379:)
1374:2
1365:/
1361:1
1358:(
1355:O
1351:2
1347:+
1344:)
1339:2
1335:n
1331:(
1328:O
1308:0
1282:)
1276:+
1273:1
1270:(
1250:n
1244:n
1190:2
1185:2
1181:n
1157:)
1152:2
1148:/
1144:3
1140:n
1136:(
1110:2
1105:2
1101:n
1077:)
1072:2
1068:/
1064:3
1060:n
1056:(
1053:O
1044:2
1039:2
1035:n
1008:n
980:)
975:2
971:/
967:3
963:n
959:(
947:2
942:2
938:n
872:7
869:4
866:2
863:1
860:0
844:n
841:,
838:n
834:R
788:9
785:8
782:7
779:6
776:5
773:4
770:3
767:2
764:1
750:n
727:n
721:n
691:n
669:n
666:,
663:n
659:R
628:n
608:n
602:n
579:b
559:a
539:b
519:a
497:b
494:,
491:a
487:R
466:)
463:S
460:(
457:f
452:S
444:=
439:b
436:,
433:a
429:R
408:)
405:S
402:(
399:f
379:S
359:)
356:S
353:(
350:f
330:S
300:2
296:n
289:2
286:1
167:b
164:+
161:a
140:b
137:a
117:b
97:a
77:b
71:a
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.