{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:39:48Z","timestamp":1750307988036,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2006,5,21]],"date-time":"2006-05-21T00:00:00Z","timestamp":1148169600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2006,5,21]]},"DOI":"10.1145\/1132516.1132603","type":"proceedings-article","created":{"date-parts":[[2006,7,24]],"date-time":"2006-07-24T16:53:01Z","timestamp":1153759981000},"page":"604-617","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":42,"title":["Limitations of quantum coset states for graph isomorphism"],"prefix":"10.1145","author":[{"given":"Sean","family":"Hallgren","sequence":"first","affiliation":[{"name":"NEC Laboratories America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cristopher","family":"Moore","sequence":"additional","affiliation":[{"name":"University of New Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"R\u00f6tteler","sequence":"additional","affiliation":[{"name":"NEC Laboratories America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Russell","sequence":"additional","affiliation":[{"name":"University of Connecticut"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pranab","family":"Sen","sequence":"additional","affiliation":[{"name":"NEC Laboratories America"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,5,21]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780546"},{"key":"e_1_3_2_1_2_1","volume-title":"Strong Fourier sampling fails over Gn. ArXiv preprint quant-ph\/0511054","author":"Alagic G.","year":"2005","unstructured":"G. Alagic , C. Moore , and A. Russell . Strong Fourier sampling fails over Gn. ArXiv preprint quant-ph\/0511054 , 2005 .]] G. Alagic, C. Moore, and A. Russell. Strong Fourier sampling fails over Gn. ArXiv preprint quant-ph\/0511054, 2005.]]"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.38"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258548"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300933"},{"key":"e_1_3_2_1_6_1","series-title":"Translations of Mathematical Monographs","volume-title":"Characters of finite groups, part 2","author":"Berkovich Y. G.","year":"1999","unstructured":"Y. G. Berkovich and E. M. Zhmud . Characters of finite groups, part 2 , volume 181 of Translations of Mathematical Monographs . American Mathematical Society , 1999 .]] Y. G. Berkovich and E. M. Zhmud. Characters of finite groups, part 2, volume 181 of Translations of Mathematical Monographs. American Mathematical Society, 1999.]]"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/523986.857978"},{"key":"e_1_3_2_1_8_1","volume-title":"On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems. ArXiv preprint quant--ph\/0510185","author":"Childs A.","year":"2005","unstructured":"A. Childs and P. Wocjan . On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems. ArXiv preprint quant--ph\/0510185 , 2005 .]] A. Childs and P. Wocjan. On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems. ArXiv preprint quant--ph\/0510185, 2005.]]"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/aama.2000.0699"},{"key":"e_1_3_2_1_10_1","volume-title":"A quantum observable for the graph isomorphism problem. ArXiv preprint quant--ph\/9901029","author":"Ettinger M.","year":"1999","unstructured":"M. Ettinger , P. Hoyer , and E. Knill . A quantum observable for the graph isomorphism problem. ArXiv preprint quant--ph\/9901029 , 1999 .]] M. Ettinger, P. Hoyer, and E. Knill. A quantum observable for the graph isomorphism problem. ArXiv preprint quant--ph\/9901029, 1999.]]"},{"key":"e_1_3_2_1_11_1","volume-title":"Hidden subgroup states are almost orthogonal. ArXiv preprint quant--ph\/9901034","author":"Ettinger M.","year":"1999","unstructured":"M. Ettinger , P. Hoyer , and E. Knill . Hidden subgroup states are almost orthogonal. ArXiv preprint quant--ph\/9901034 , 1999 .]] M. Ettinger, P. Hoyer, and E. Knill. Hidden subgroup states are almost orthogonal. ArXiv preprint quant--ph\/9901034, 1999.]]"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780544"},{"key":"e_1_3_2_1_13_1","series-title":"Graduate Texts in Mathematics","volume-title":"Representation theory: A first course","author":"Fulton W.","year":"1991","unstructured":"W. Fulton and J. Harris . Representation theory: A first course , volume 129 of Graduate Texts in Mathematics . Springer , 1991 .]] W. Fulton and J. Harris. Representation theory: A first course, volume 129 of Graduate Texts in Mathematics. Springer, 1991.]]"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1994-1185260-1"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0009-8"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510001"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060660"},{"key":"e_1_3_2_1_19_1","unstructured":"S. Hallgren M. R\u00f6tteler and P. Sen. Limitations of quantum coset states for graph isomorphism. arXiv preprint quant-ph\/0511148.]]  S. Hallgren M. R\u00f6tteler and P. Sen. Limitations of quantum coset states for graph isomorphism. arXiv preprint quant-ph\/0511148.]]"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970139450X"},{"key":"e_1_3_2_1_21_1","volume-title":"Character theory of finite groups","author":"Isaacs I. M.","year":"1976","unstructured":"I. M. Isaacs . Character theory of finite groups . Academic Press , 1976 .]] I. M. Isaacs. Character theory of finite groups. Academic Press, 1976.]]"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103001996"},{"key":"e_1_3_2_1_23_1","volume-title":"The representation theory of the symmetric group","author":"James G.","year":"1981","unstructured":"G. James and A. Kerber . The representation theory of the symmetric group . Addison-Wesley , Reading , 1981 .]] G. James and A. Kerber. The representation theory of the symmetric group. Addison-Wesley, Reading, 1981.]]"},{"key":"e_1_3_2_1_24_1","volume-title":"ArXiv preprint quant--ph\/9511026","author":"Kitaev A. Y.","year":"1995","unstructured":"A. Y. Kitaev . Quantum measurements and the abelian stabilizer problem. ArXiv preprint quant--ph\/9511026 , 1995 .]] A. Y. Kitaev. Quantum measurements and the abelian stabilizer problem. ArXiv preprint quant--ph\/9511026, 1995.]]"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0333-9"},{"key":"e_1_3_2_1_26_1","volume-title":"A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. ArXiv preprint quant--ph\/0302112","author":"Kuperberg G.","year":"2003","unstructured":"G. Kuperberg . A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. ArXiv preprint quant--ph\/0302112 , 2003 .]] G. Kuperberg. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. ArXiv preprint quant--ph\/0302112, 2003.]]"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.1992.10504252"},{"key":"e_1_3_2_1_28_1","first-page":"1113","volume-title":"Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Moore C.","year":"2004","unstructured":"C. Moore , D. Rockmore , A. Russell , and L. Schulman . The power of basis selection in fourier sampling: Hidden subgroup problems in affine groups . In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1113 -- 1122 , 2004 . Journal version in preparation. Also : ArXiv preprint quant--ph\/0503095.]] C. Moore, D. Rockmore, A. Russell, and L. Schulman. The power of basis selection in fourier sampling: Hidden subgroup problems in affine groups. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1113--1122, 2004. Journal version in preparation. Also: ArXiv preprint quant--ph\/0503095.]]"},{"key":"e_1_3_2_1_29_1","volume-title":"The symmetric group defies strong Fourier sampling: Part II. ArXiv preprint quant--ph\/0501066","author":"Moore C.","year":"2005","unstructured":"C. Moore and A. Russell . The symmetric group defies strong Fourier sampling: Part II. ArXiv preprint quant--ph\/0501066 , 2005 .]] C. Moore and A. Russell. The symmetric group defies strong Fourier sampling: Part II. ArXiv preprint quant--ph\/0501066, 2005.]]"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.73"},{"key":"e_1_3_2_1_31_1","series-title":"Lecture Notes in Computer Science","first-page":"174","volume-title":"Quantum Computing and Quantum Communications","author":"Mosca M.","year":"1998","unstructured":"M. Mosca and A. Ekert . The hidden subgroup problem and eigenvalue estimation on a quantum computer . In Quantum Computing and Quantum Communications , volume 1509 of Lecture Notes in Computer Science , pages 174 -- 188 . Springer-Verlag , 1998 .]] M. Mosca and A. Ekert. The hidden subgroup problem and eigenvalue estimation on a quantum computer. In Quantum Computing and Quantum Communications, volume 1509 of Lecture Notes in Computer Science, pages 174--188. Springer-Verlag, 1998.]]"},{"key":"e_1_3_2_1_32_1","volume-title":"Quantum computation and quantum information","author":"Nielsen M.","year":"2000","unstructured":"M. Nielsen and I. Chuang . Quantum computation and quantum information . Cambridge University Press , 2000 .]] M. Nielsen and I. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000.]]"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_113"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002220050083"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060661"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.37"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9458-7"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365701"}],"event":{"name":"STOC06: Symposium on Theory of Computing","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Seattle WA USA","acronym":"STOC06"},"container-title":["Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132603","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132516.1132603","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:13Z","timestamp":1750259173000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132603"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5,21]]},"references-count":39,"alternative-id":["10.1145\/1132516.1132603","10.1145\/1132516"],"URL":"https:\/\/doi.org\/10.1145\/1132516.1132603","relation":{},"subject":[],"published":{"date-parts":[[2006,5,21]]},"assertion":[{"value":"2006-05-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}