Fetching the paper…
Reading the bibliography…
To determine if two lists of numbers are the same set, we sort both lists and see if we get the same result.
William W. Boone, Certain simple, unsolvable problems of group theory. V, VI , Nederl. Akad. Wetensch. Proc. Ser. A. 60 = Indag. Math. 19
1957
Earlier work this paper cites.
P. S. Novikov, Ob algoritmičeskoĭ nerazrešimosti problemy toždestva slov v teorii grupp , Trudy Mat. Inst. im. Steklov. no. 44, Izdat. Akad. Nauk SSSR, Moscow, 1955, English translation: On the algorithmic insolvability of the word problem in group theory, in: American Mathematical Society Translations, Ser. 2, Vol. 9, AMS, 1958, pp. 1–122
1958
Earlier work this paper cites.
Charles C. Sims, Computational methods in the study of permutation groups , Computational Problems in Abstract Algebra (Oxford, 1967), Pergamon, Oxford, 1970, pp. 169–183
1970
Earlier work this paper cites.
Robert M. Solovay, A model of set-theory in which every set of reals is Lebesgue measurable , Ann. of Math. (2) 92
1970
Earlier work this paper cites.
Charles C. Sims, Computation with permutation groups , SYMSAC ’71: Proceedings of the Second ACM Symposium on Symbolic and Algebraic Manipulation, ACM, 1971, pp. 23–28
1971
Earlier work this paper cites.
J. E. Hopcroft and R. E. Tarjan, Isomorphism of planar graphs , Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N. Y., 1972), Plenum, New York, 1972, pp. 131–152, 187–212
1972
Earlier work this paper cites.
John Hopcroft and J. K. Wong, Linear time algorithm for isomorphism of planar graphs (preliminary report) , STOC ’74: 6th Annual ACM Symposium on Theory of Computing, ACM, 1974, pp. 172–184
1974
Earlier work this paper cites.
Ted Baker, John Gill, and Robert Solovay, Relativizations of the P =? NP question , SIAM J. Comput. 4
1975
Earlier work this paper cites.
Richard J. Lipton and Yechezkel Zalcstein, Word problems solvable in logspace , J. ACM 24
1977
Earlier work this paper cites.
Robert M. Solovay and Volker Strassen, A fast Monte-Carlo test for primality , SIAM J. Comput. 6
1977
Earlier work this paper cites.
László Babai and Ludik Kučera, Canonical labelling of graphs in linear average time , FOCS ’79: 20th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 1979, pp. 39–46
1979
Earlier work this paper cites.
Hans-Ulrich Simon, Word problems for groups and contextfree recognition , Fundamentals of computation theory (Proc. Conf. Algebraic, Arith. and Categorical Methods in Comput. Theory, Berlin/Wendisch-Rietz, 1979), Math. Res., vol. 2, Akademie-Verlag, Berlin, 1979, pp. 417–422
1979
Earlier work this paper cites.
Merrick Furst, John Hopcroft, and Eugene Luks, Polynomial-time algorithms for permutation groups , FOCS ’80: 21st Annual IEEE Symposium on Foundations of Computer Science, IEEE, 1980, pp. 36–41
1980
Earlier work this paper cites.
Gary Miller, Isomorphism testing for graphs of bounded genus , STOC ’80: 12th Annual ACM Symposium on Theory of Computing, ACM, 1980, pp. 225–235
1980
Earlier work this paper cites.
Michael O. Rabin, Probabilistic algorithm for testing primality , J. Number Theory 12
1980
Earlier work this paper cites.
László Babai, D. Yu. Grigoryev, and David M. Mount, Isomorphism of graphs with bounded eigenvalue multiplicity , STOC ’82: 14th Annual ACM Symposium on Theory of Computing, ACM, 1982, pp. 310–324
1982
Earlier work this paper cites.
Richard M. Karp and Richard J. Lipton, Turing machines that take advice , Enseign. Math. (2) 28
1982
Earlier work this paper cites.
László Babai and Eugene M. Luks, Canonical labeling of graphs , STOC ’83: 15th Annual ACM Symposium on Theory of Computing, ACM, 1983, pp. 171–183
1983
Earlier work this paper cites.
Martin Fürer, Walter Schnyder, and Ernst Specker, Normal forms for trivalent graphs and graphs of bounded valence , STOC ’83: 15th Annual ACM Symposium on Theory of Computing, ACM, 1983, pp. 161–170
1983
Earlier work this paper cites.
Ker-I Ko, On self-reducibility and weak P {\rm P} -selectivity , J. Comput. System Sci. 26
1983
Earlier work this paper cites.
Clemens Lautemann, BPP and the polynomial hierarchy , Inform. Process. Lett. 17
1983
Earlier work this paper cites.
Michael Sipser, A complexity theoretic approach to randomness , STOC ’83: 15th Annual ACM Symposium on Theory of Computing, ACM, 1983, pp. 330–335
1983
Earlier work this paper cites.
Alan L. Selman, Mei Rui Xu, and Ronald V. Book, Positive relativizations of complexity classes , SIAM J. Comput. 12
1983
Earlier work this paper cites.
Andreas Blass and Yuri Gurevich, Equivalence relations, invariants, and normal forms , SIAM J. Comput. 13
1984
Earlier work this paper cites.
Andreas Blass and Yuri Gurevich, Equivalence relations, invariants, and normal forms, II , Logic and Machines: Decision Problems and Complexity, Lecture Notes in Computer Science, vol. 171, Springer, 1984, pp. 24–42
1984
Earlier work this paper cites.
László Babai, Trading group theory for randomness , STOC ’85: 17th Annual ACM Symposium on Theory of Computing, ACM, 1985, pp. 421–429
1985
Earlier work this paper cites.
J. Howard Johnson, Rational equivalence relations , ICALP ’86: Proceedings of the 13nd International Colloquium on Automata, Languages and Programming (Laurent Kott, ed.), Lecture Notes in Computer Science, vol. 226, Springer, 1986, pp. 167–176
1986
Cited alongside, same era.
Klaus-Jörn Lange, Two characterizations of the logarithmic alternation hierarchy , Proceedings of the 12th Symposium on Mathematical Foundations of Computer Science 1986, Lecture Notes in Computer Science, vol. 233, Springer-Verlag, 1986, pp. 518–526
1986
Cited alongside, same era.
Leslie G. Valiant and Vijay V. Vazirani, NP is as easy as detecting unique solutions , Theoret. Comput. Sci. 47
1986
Cited alongside, same era.
Stathis Zachos, Probabilistic quantifiers and games , J. Comput. System Sci. 36
1986
Cited alongside, same era.
Ravi Boppana, Johan Håstad, and Stathis Zachos, Does co-NP have short interactive proofs? , Inform. Process. Lett. 25
Harry Buhrman and Lance Fortnow, Two queries , J. Comput. System Sci. 59
1998
Later among the works it cites.
Mark Ettinger and Peter Høyer, A quantum observable for the graph isomorphism problem , arXiv:quant-ph/9901029, 1999
1999
Later among the works it cites.
Johannes Köbler and Osamu Watanabe, New collapse consequences of NP having small circuits , SIAM J. Comput. 28
1999
Later among the works it cites.
Eugene M. Luks, Hypergraph isomorphism and structural equivalence of Boolean functions , STOC ’99: 31st Annual ACM Symposium on Theory of Computing, ACM, 1999, pp. 652–658
1999
Later among the works it cites.
Manindra Agrawal and Thomas Thierauf, The formula isomorphism problem , SIAM J. Comput. 30
2000
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
1987
Cited alongside, same era.
Lance Fortnow, The complexity of perfect zero-knowledge , STOC ’87: 19th Annual ACM Symposium on Theory of Computing, ACM, 1987, pp. 204–209
1987
Cited alongside, same era.
Ivan Damgård, Collision free hash functions and public key signature schemes , EuroCrypt87, Lecture Notes in Computer Science, vol. 304, Springer, 1988, pp. 203–216
1988
Cited alongside, same era.
William Aiello and Johan Håstad, Statistical zero-knowledge languages can be recognized in two rounds , J. Comput. System Sci. 42
1991
Cited alongside, same era.
Donald E. Knuth, Efficient representation of perm groups , Combinatorica 11
1991
Cited alongside, same era.
Jun Tarui, Randomized polynomials, threshold circuits, and the polynomial hierarchy , STACS ’91: Proceedings of the 8th Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, 1991, pp. 238–250
1991
Cited alongside, same era.
Richard Beigel, Perceptrons, PP {\rm PP} , and the polynomial hierarchy , Comput. Complexity 4
1992
Cited alongside, same era.
Alan L. Selman, A survey of one-way functions in complexity theory , Math. Systems Theory 25
1992
Cited alongside, same era.
V. Arvind and N. V. Vinodchandran, The counting complexity of group-definable languages , Theoret. Comput. Sci. 242
2000
Later among the works it cites.
Michael A. Nielson and Isaac L. Chuang, Quantum computation and quantum information , Cambridge University Press, 2000
2000
Later among the works it cites.
Thomas Thierauf, The computational complexity of equivalence and isomorphism problems , Lecture Notes in Computer Science, vol. 1852, Springer, New York, 2000
2000
Later among the works it cites.
Scott Aaronson, Quantum lower bound for the collision problem , STOC ’02: 34th Annual ACM Symposium on Theory of Computing, ACM, 2002, pp. 635–642
2002
Later among the works it cites.
Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman, Exponential algorithmic speedup by a quantum walk , STOC ’03: 35th Annual ACM Symposium on Theory of Computing, ACM, 2003, pp. 59–68 (electronic)
2003
Later among the works it cites.
Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, and Lide Li, An oracle builder’s toolkit , Inform. and Comput. 182
2003
Later among the works it cites.
Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, and Pranab Sen, Hidden translation and orbit coset in quantum computing , STOC ’03: 35th Annual ACM Symposium on Theory of Computing, ACM, 2003, pp. 1–9
2003
Later among the works it cites.
Gábor Ivanyos, Frédéric Magniez, and Miklos Santha, Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem , Internat. J. Found. Comput. Sci. 14
2003
Later among the works it cites.
Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P , Ann. of Math. (2) 160
2004
Later among the works it cites.
Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, and Umesh Vazirani, Quantum mechanical algorithms for the nonabelian hidden subgroup problem , Combinatorica 24
2004
Later among the works it cites.
Oded Regev, Quantum computation and lattice problems , SIAM J. Comput. 33
2004
Later among the works it cites.
Jin-Yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, and Mitsunori Ogihara, Competing provers yield improved Karp-Lipton collapse results , Inform. and Comput. 198
2005
Later among the works it cites.
Greg Kuperberg, A subexponential-time quantum algorithm for the dihedral hidden subgroup problem , SIAM J. Comput. 35
2005
Later among the works it cites.
Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub, and Klaus W. Wagner, The complexity of computing the size of an interval , SIAM J. Comput. 36
2006
Later among the works it cites.
Omer Reingold, Luca Trevisan, and Salil Vadhan, Pseudorandom walks on regular digraphs and the 𝐑𝐋 \bf RL vs. 𝐋 \bf L problem , STOC ’06: 38th Annual ACM Symposium on Theory of Computing, ACM, 2006, pp. 457–466
2006
Later among the works it cites.
Jin-Yi Cai, S 2 p ⊆ ZPP NP {\rm S}^{p}_{2}\subseteq{\rm ZPP}^{\rm NP} , J. Comput. System Sci. 73
2007
Later among the works it cites.
László Babai, May 2008, personal communication
2008
Later among the works it cites.
Christian Glaßer, Christian Reitwießner, and Victor Selivanov, The shrinking property for NP and coNP , Tech. Report TR08-029, Electronic Colloquium on Computational Complexity, 2008
2008
Later among the works it cites.
Scott Aaronson, November 2009, personal communication
2009
Closest in time.
Sanjeev Arora and Boaz Barak, Computational complexity: a modern approach , Cambridge University Press, Cambridge, 2009, Draft available online at http://www.cs.princeton.edu/theory/complexity/
2009
Closest in time.