Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields

by Swastik Kopparty, Mrinal Kumar, and Michael Saks

Theory of Computing, Volume 12(7), pp. 1-27, 2016

Bibliography with links to cited articles

[1]   Leonard M. Adleman and Hendrik W. Lenstra, Jr.: Finding irreducible polynomials over finite fields. In Proc. 18th STOC, pp. 350–355. ACM Press, 1986. [doi:10.1145/12130.12166]

[2]   Manindra Agrawal and Somenath Biswas: Primality and identity testing via Chinese remaindering. J. ACM, 50(4):429–443, 2003. Preliminary version in FOCS’99. [doi:10.1145/792538.792540]

[3]   Noga Alon, Oded Goldreich, Johan Hĺstad, and René Peralta: Simple construction of almost k-wise independent random variables. Random Structures and Algorithms, 3(3):289–304, 1992. Preliminary version in FOCS’90. [doi:10.1002/rsa.3240030308]

[4]   Alexandr Andoni, Assaf Goldberger, Andrew McGregor, and Ely Porat: Homomorphic fingerprints under misalignments: sketching edit and shift distances. In Proc. 45th STOC, pp. 931–940. ACM Press, 2013. [doi:10.1145/2488608.2488726]

[5]   Jörg Arndt: Matters Computational. Springer, 2011. [doi:10.1007/978-3-642-14764-7]

[6]   Jean Berstel and Michel Pocchiola: Average cost of Duval’s algorithm for generating Lyndon words. Theoret. Comput. Sci., 132(1-2):415–425, 1994. [doi:10.1016/0304-3975(94)00013-1]

[7]   Kevin Cattell, Frank Ruskey, Joe Sawada, Micaela Serra, and C. Robert Miers: Fast algorithms to generate necklaces, unlabeled necklaces, and irreducible polynomials over GF(2). J. Algorithms, 37(2):267–282, 2000. [doi:10.1006/jagm.2000.1108]

[8]   Jean-Pierre Duval: Génération d’une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée. Theoret. Comput. Sci., 60(3):255–283, 1988. [doi:10.1016/0304-3975(88)90113-2]

[9]    Aryeh Dvoretzky and Theodore S. Motzkin: A problem of arrangements. Duke Math. J., 14(2):305–313, 1947. [doi:10.1215/S0012-7094-47-01423-3]

[10]   Harold Fredricksen and Irving J. Kessler: An algorithm for generating necklaces of beads in two colors. Discrete Math., 61(2-3):181–188, 1986. [doi:10.1016/0012-365X(86)90089-0]

[11]   Harold Fredricksen and James A. Maiorana: Necklaces of beads in k colors and k-ary de Bruijn sequences. Discrete Math., 23(3):207–210, 1978. [doi:10.1016/0012-365X(78)90002-X]

[12]   Solomon W. Golomb: Irreducible polynomials, synchronization codes, primitive necklaces and the cyclotomic algebra. In Combinatorial Math. and Its Appl., pp. 358–370. Univ. N. Carolina Press, Chapel Hill, NC., 1969.

[13]   Venkatesan Guruswami and Swastik Kopparty: Explicit subspace designs. In Proc. 54th FOCS, pp. 608–617. IEEE Comp. Soc. Press, 2013. Preliminary version in ECCC.

[14]   Donald E. Knuth: Generating all trees, history of combinatorial generation. In The Art of Computer Programming, volume 4. Addison-Wesley Professional, 2006. ACM DL.

[15]   Tomasz Kociumaka, Jakub Radoszewski, and Wojciech Rytter: Computing k-th Lyndon word and decoding lexicographically minimal de Bruijn sequence. In Combinat. Pattern Matching, volume 8486 of LNCS, pp. 202–211. Springer, 2014. [doi:10.1007/978-3-319-07566-2_21, arXiv:1510.02637]

[16]   Swastik Kopparty, Mrinal Kumar, and Michael E. Saks: Efficient indexing of necklaces and irreducible polynomials over finite fields. In Proc. 41st Internat. Colloq. on Automata, Languages and Programming (ICALP’14), volume 8572, pp. 726–737. Springer, 2014. [doi:10.1007/978-3-662-43948-7_60, arXiv:1504.00572]

[17]   Donald L. Kreher and Douglas Robert Stinson: Combinatorial Algorithms: Generation, Enumeration, and Search. Volume 7 of Discrete Math. and its Appl. CRC Press, 1999.

[18]   Hendrik W. Lenstra, Jr.: Finding isomorphisms between finite fields. Math. Comput., 56(193):329–347, 1991. [doi:10.2307/2008545]

[19]   F. Jessica MacWilliams and Neil J. A. Sloane: The Theory of Error-Correcting Codes. North-Holland Publ. Co., 2nd edition, 1978.

[20]   Conrado Martínez and Xavier Molinero: An efficient generic algorithm for the generation of unlabelled cycles. In Math. and Comput. Sci. III, Trends in Math., pp. 187–197. Springer, 2004. [doi:10.1007/978-3-0348-7915-6_19]

[21]   Wendy J. Myrvold and Frank Ruskey: Ranking and unranking permutations in linear time. Inf. Process. Lett., 79(6):281–284, 2001. [doi:10.1016/S0020-0190(01)00141-7]

[22]   Albert Nijenhuis and Herbert S. Wilf: Combinatorial Algorithms for Computers and Calculators. Volume 1. Academic Press, 1978.

[23]   Grigoriĭ Iosifovich Perel’muter and Igor Evgen’evich Shparlinski: On the distribution of primitive roots in finite fields. Russ. Math. Surv. (Uspekhi Mat. Nauk), 45(1):223–224 (original pp. 185–186), 1990. Russian original freely downloadable from Math-Net.Ru. [doi:10.1070/RM1990v045n01ABEH002330]

[24]   Michael O. Rabin: Fingerprinting by Random Polynomials. Center for Research in Comput. Techn., Aiken Comput. Lab., Harvard Univ., 1981. 24 pp. See also at Harvard CS Tech Report version TR 15-81 (12 pp).

[25]   Frank Ruskey: Combinatorial Generation, 2003. Draft available at http://www.1stworks.com/ref/RuskeyCombGen.pdf.

[26]   Frank Ruskey, Carla D. Savage, and Terry Min Yih Wang: Generating necklaces. J. Algorithms, 13(3):414–430, 1992. [doi:10.1016/0196-6774(92)90047-G]

[27]   Frank Ruskey and Joe Sawada: An efficient algorithm for generating necklaces with fixed density. SIAM J. Comput., 29(2):671–684, 1999. Preliminary version in SODA’99. [doi:10.1137/S0097539798344112]

[28]   Victor Shoup: New algorithms for finding irreducible polynomials over finite fields. Math. Comput., 54(189):435–447, 1990. Preliminary version in FOCS’88. [doi:10.1090/S0025-5718-1990-0993933-0]

[29]   Victor Shoup: Searching for primitive roots in finite fields. Math. Comput., 58(197):369–380, 1992. Preliminary version in STOC’90. [doi:10.1090/S0025-5718-1992-1106981-9]

[30]   Igor Evgen’evich Shparlinski: On primitive elements in finite fields and on elliptic curves. Math. USSR Sb., 71(1):41–50, 1992. [doi:10.1070/SM1992v071n01ABEH001389]

[31]   Richard P. Stanley: Enumerative Combinatorics: Volume 1. Cambridge Univ. Press, 2011.

[32]   Seinosuke Toda: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865–877, 1991. Preliminary version in FOCS’89. [doi:10.1137/0220053]

[33]    Leslie G. Valiant: The complexity of computing the permanent. Theoret. Comput. Sci., 8(2):189–201, 1979. [doi:10.1016/0304-3975(79)90044-6]