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]