The Cayley Semigroup Membership Problem

by Lukas Fleischer

Theory of Computing, Volume 18(8), pp. 1-18, 2022

Bibliography with links to cited articles

[1]   Jorge Almeida: Some pseudovariety joins involving the pseudovariety of finite groups. Semigroup Forum, 37(1):53–57, 1988. [doi:10.1007/BF02573123]

[2]   László Babai: Trading group theory for randomness. In Proc. 17th STOC, pp. 421–429. ACM Press, 1985. [doi:10.1145/22145.22192]

[3]   László Babai: Local expansion of vertex-transitive graphs and random generation in finite groups. In Proc. 23rd STOC, pp. 164–174. ACM Press, 1991. [doi:10.1145/103418.103440]

[4]   László Babai, Robert Beals, Jin-Yi Cai, Gábor Ivanyos, and Eugene M. Luks: Multiplicative equations over commuting matrices. In Proc. 7th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’96), pp. 498–507. SIAM, 1996. ACM DL.

[5]   László Babai, Eugene M. Luks, and Ákos Seress: Permutation groups in NC. In Proc. 19th STOC, pp. 409–420. ACM Press, 1987. [doi:10.1145/28395.28439]

[6]   László Babai and Endre Szemerédi: On the complexity of matrix group problems I. In Proc. 25th FOCS, pp. 229–240. IEEE Comp. Soc., 1984. [doi:10.1109/SFCS.1984.715919]

[7]   David A. Mix Barrington: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. System Sci., 38(1):150–164, 1989. Preliminary version in STOC’86. [doi:10.1016/0022-0000(89)90037-8]

[8]   David A. Mix Barrington and Pierre McKenzie: Oracle branching programs and Logspace versus P. Inform. Comput., 95(1):96–115, 1991. Preliminary version in MFCS’89. [doi:10.1016/0890-5401(91)90017-V]

[9]   David A. Mix Barrington and Denis Thérien: Finite monoids and the fine structure of NC1. J. ACM, 35(4):941–952, 1988. Preliminary version in STOC’87. [doi:10.1145/48014.63138]

[10]   David Mix Barrington, Peter Kadau, Klaus-Jörn Lange, and Pierre McKenzie: On the complexity of some problems on groups input as multiplication tables. J. Comput. System Sci., 63(2):186–200, 2001. Preliminary version in CCC’00. [doi:10.1006/jcss.2001.1764]

[11]   Martin Beaudry: Membership Testing in Transformation Monoids. Ph. D. thesis, McGill University, 1987. eScholarship@McGill.

[12]   Martin Beaudry: Membership testing in commutative transformation semigroups. Inform. Comput., 79(1):84–93, 1988. Preliminary version in ICALP’87. [doi:10.1016/0890-5401(88)90018-1]

[13]   Martin Beaudry: Membership testing in threshold one transformation monoids. Inform. Comput., 113(1):1–25, 1994. [doi:10.1006/inco.1994.1062]

[14]   Martin Beaudry, Pierre McKenzie, and Denis Thérien: The membership problem in aperiodic transformation monoids. J. ACM, 39(3):599–616, 1992. [doi:10.1145/146637.146661]

[15]   Ravi B. Boppana: The average sensitivity of bounded-depth circuits. Inform. Process. Lett., 63(5):257–261, 1997. [doi:10.1016/S0020-0190(97)00131-2]

[16]   Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio, and Li-Yang Tan: Near-optimal small-depth lower bounds for small distance connectivity. In Proc. 48th STOC, pp. 612–625. ACM Press, 2016. [doi:10.1145/2897518.2897534, arXiv:1509.07476]

[17]   Lukas Fleischer: On the complexity of the Cayley semigroup membership problem. In Proc. 33rd Comput. Complexity Conf. (CCC’18), pp. 25:1–12. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.CCC.2018.25]

[18]   Merrick L. Furst, John E. Hopcroft, and Eugene M. Luks: Polynomial-time algorithms for permutation groups. In Proc. 21st FOCS, pp. 36–41. IEEE Comp. Soc., 1980. [doi:10.1109/SFCS.1980.34]

[19]   Johan Håstad: Almost optimal lower bounds for small depth circuits. In Proc. 18th STOC, pp. 6–20. ACM Press, 1986. [doi:10.1145/12130.12132]

[20]   John M. Howie: Fundamentals of Semigroup Theory. Clarendon Press, 1995.

[21]   Neil D. Jones and William T. Laaser: Complete problems for deterministic polynomial time. Theoret. Comput. Sci., 3(1):105–117, 1976. Preliminary version in STOC’74. [doi:10.1016/0304-3975(76)90068-2]

[22]   Neil D. Jones, Y. Edmund Lien, and William T. Laaser: New problems complete for nondeterministic log space. Math. Sys. Theory, 10(1):1–17, 1976. [doi:10.1007/BF01683259]

[23]   Friedrich Levi: Über die Untergruppen der freien Gruppen. (2. Mitteilung). Mathematische Zeitschrift, 37:90–97, 1933. EuDML.

[24]   Roger C. Lyndon and Paul E. Schupp: Combinatorial Group Theory. Springer, 2001. [doi:10.1007/978-3-642-61896-3]

[25]   Jean-Éric Pin: Varieties of Formal Languages. North Oxford Academic, 1986.

[26]   Omer Reingold: Undirected connectivity in Log-space. J. ACM, 55(4):17:1–24, 2008. Preliminary version in STOC’05. [doi:10.1145/1391289.1391291]

[27]   Charles C. Sims: Computational methods in the study of permutation groups. In Computational Problems in Abstract Algebra, pp. 169–183. Pergamon, 1970. See also SYMSAC’71. [doi:10.1016/B978-0-08-012975-4.50020-5]

[28]   Heribert Vollmer: Introduction to Circuit Complexity. Springer, 1999. [doi:10.1007/978-3-662-03927-4]

[29]   Andrew Chi-Chih Yao: Separating the polynomial-time hierarchy by oracles. In Proc. 26th FOCS, pp. 1–10. IEEE Comp. Soc., 1985. [doi:10.1109/SFCS.1985.49]