{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:31:55Z","timestamp":1750221115905,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T00:00:00Z","timestamp":1573776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["Investigator award"],"award-info":[{"award-number":["Investigator award"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1423544, CCF-1423544"],"award-info":[{"award-number":["CCF-1423544, CCF-1423544"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,1,31]]},"abstract":"<jats:p>\n            We give an new arithmetic algorithm to compute the generalized Discrete Fourier Transform (DFT) over finite groups\n            <jats:italic>G<\/jats:italic>\n            . The new algorithm uses\n            <jats:italic>O<\/jats:italic>\n            (\u2223\n            <jats:italic>G<\/jats:italic>\n            \u2223\n            <jats:sup>\n              \u03c9 \/2 +\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            ) operations to compute the generalized DFT over finite groups of Lie type, including the linear, orthogonal, and symplectic families and their variants, as well as all finite simple groups of Lie type. Here \u03c9 is the exponent of matrix multiplication, so the exponent \u03c9\/2 is optimal if \u03c9 = 2.\n          <\/jats:p>\n          <jats:p>\n            Previously, \u201cexponent one\u201d algorithms were known for supersolvable groups and the symmetric and alternating groups. No exponent one algorithms were known, even under the assumption \u03c9 = 2, for families of linear groups of fixed dimension, and indeed the previous best-known algorithm for SL\n            <jats:sub>2<\/jats:sub>\n            (F\n            <jats:sub>q<\/jats:sub>\n            ) had exponent 4\/3 despite being the focus of significant effort. We unconditionally achieve exponent at most 1.19 for this group and exponent one if \u03c9 = 2.\n          <\/jats:p>\n          <jats:p>\n            Our algorithm also yields an improved exponent for computing the generalized DFT over general finite groups\n            <jats:italic>G<\/jats:italic>\n            , which beats the longstanding previous best upper bound for any \u03c9. In particular, assuming \u03c9 = 2, we achieve exponent \u221a 2, while the previous best was 3\/2.\n          <\/jats:p>","DOI":"10.1145\/3301313","type":"journal-article","created":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T21:16:57Z","timestamp":1573852617000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A New Algorithm for Fast Generalized DFTs"],"prefix":"10.1145","volume":"16","author":[{"given":"Chloe Ching-Yun","family":"Hsu","sequence":"first","affiliation":[{"name":"Caltech, CA, USA"}]},{"given":"Chris","family":"Umans","sequence":"additional","affiliation":[{"name":"Caltech, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,11,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Ulrich Baum. 1991. Existence and efficient construction of fast Fourier transforms on supersolvable groups. Comput. Complex. 1 3 (1 Sep. 1991) 235--256.  Ulrich Baum. 1991. Existence and efficient construction of fast Fourier transforms on supersolvable groups. Comput. Complex. 1 3 (1 Sep. 1991) 235--256.","DOI":"10.1007\/BF01200062"},{"key":"e_1_2_1_2_1","unstructured":"Thomas Beth. 1984. Verfahren der schnellen Fourier-Transformation. Teubner.  Thomas Beth. 1984. Verfahren der schnellen Fourier-Transformation. Teubner."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser M. Clausen and M. A. Shokrollahi. 1997. Algebraic Complexity Theory. Grundlehren der mathematischen Wissenschaften Vol. 315. Springer-Verlag.  P. B\u00fcrgisser M. Clausen and M. A. Shokrollahi. 1997. Algebraic Complexity Theory. Grundlehren der mathematischen Wissenschaften Vol. 315. Springer-Verlag.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"e_1_2_1_4_1","unstructured":"Roger W. Carter. 1989. Simple Groups of Lie Type. Vol. 22. John Wiley 8 Sons.  Roger W. Carter. 1989. Simple Groups of Lie Type. Vol. 22. John Wiley 8 Sons."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90021-2"},{"key":"e_1_2_1_6_1","unstructured":"Michael Clausen and Ulrich Baum. 1993. Fast Fourier Transforms. Wissenschaftsverlag.  Michael Clausen and Ulrich Baum. 1993. Fast Fourier Transforms. Wissenschaftsverlag."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087604.3087628"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Roger A. Horn and Charles R. Johnson. 1991. Topics in Matrix Analysis. Cambridge University Press.  Roger A. Horn and Charles R. Johnson. 1991. Topics in Matrix Analysis. Cambridge University Press.","DOI":"10.1017\/CBO9780511840371"},{"volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918)","year":"2018","author":"Ching-Yun Hsu Chloe","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.1992.10504252"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(92)90041-J"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-97-00219-1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-017-9555-5"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-016-9516-4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-98-00964-8"},{"volume":"28","volume-title":"Groups and Computation II","author":"David","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02510144"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/028\/19"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/acha.1995.1020"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.2002.1197284"},{"volume-title":"Retrieved","year":"2017","key":"e_1_2_1_22_1"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301313","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3301313","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3301313","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:04Z","timestamp":1750208524000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301313"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,15]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1,31]]}},"alternative-id":["10.1145\/3301313"],"URL":"https:\/\/doi.org\/10.1145\/3301313","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2019,11,15]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}