{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:18:43Z","timestamp":1758269923613,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,12,31]],"date-time":"2015-12-31T00:00:00Z","timestamp":1451520000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek, project \u201cSpace and Time Efficient Structural Improvements of Dynamic Programming Algorithms\u201d"},{"name":"Swedish Research Council, project \u201cExact Algorithms\u201d (A.B., T.H.), by the Academy of Finland","award":["252083 (P.K.), 256287 (P.K.), and 125637 (M.K.)"],"award-info":[{"award-number":["252083 (P.K.), 256287 (P.K.), and 125637 (M.K.)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,2,8]]},"abstract":"<jats:p>\n            We investigate fast algorithms for changing between the standard basis and an orthogonal basis of idempotents for M\u00f6bius algebras of finite lattices. We show that every lattice with\n            <jats:italic>v<\/jats:italic>\n            elements,\n            <jats:italic>n<\/jats:italic>\n            of which are nonzero and join-irreducible (or, by a dual result, nonzero and meet-irreducible), has arithmetic circuits of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>vn<\/jats:italic>\n            ) for computing the zeta transform and its inverse, thus enabling fast multiplication in the M\u00f6bius algebra. Furthermore, the circuit construction in fact gives optimal (up to constants) monotone circuits for several lattices of combinatorial and algebraic relevance, such as the lattice of subsets of a finite set, the lattice of set partitions of a finite set, the lattice of vector subspaces of a finite vector space, and the lattice of positive divisors of a positive integer.\n          <\/jats:p>","DOI":"10.1145\/2629429","type":"journal-article","created":{"date-parts":[[2016,2,8]],"date-time":"2016-02-08T22:37:07Z","timestamp":1454971027000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Fast Zeta Transforms for Lattices with Few Irreducibles"],"prefix":"10.1145","volume":"12","author":[{"given":"Andreas","family":"Bj\u00f6rklund","sequence":"first","affiliation":[{"name":"Department of Computer Science, Lund University, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thore","family":"Husfeldt","sequence":"additional","affiliation":[{"name":"IT University of Copenhagen, Denmark, and Lund University Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petteri","family":"Kaski","sequence":"additional","affiliation":[{"name":"Helsinki Institute for Information Technology HIIT, Department of Information and Computer Science, Aalto University, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikko","family":"Koivisto","sequence":"additional","affiliation":[{"name":"Helsinki Institute for Information Technology HIIT, Department of Computer Science, University of Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[{"name":"Department of Information and Computing Sciences, Utrecht University, the Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pekka","family":"Parviainen","sequence":"additional","affiliation":[{"name":"Science for Life Laboratory and School of Computer Science and Communication, Royal Institute of Technology (KTH), Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,12,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-99-09906-4"},{"key":"e_1_2_1_2_1","volume-title":"Lattice Theory","author":"Birkhoff Garrett","unstructured":"Garrett Birkhoff . 1979. Lattice Theory ( 3 rd ed.). American Mathematical Society Colloquium Publications, Vol . 25. American Mathematical Society , Providence, RI. Garrett Birkhoff. 1979. Lattice Theory (3rd ed.). American Mathematical Society Colloquium Publications, Vol. 25. American Mathematical Society, Providence, RI.","edition":"3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250801"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9185-7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683933"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007822931408"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1022855884"},{"key":"#cr-split#-e_1_2_1_8_1.1","doi-asserted-by":"crossref","unstructured":"Michael Clausen and Ulrich Baum. 1993. Fast Fourier transforms for symmetric groups: Theory and implementation. Mathematics of Computation 61 204 833--847. DOI:http:\/\/dx.doi.org\/10.2307\/2153256 10.2307\/2153256","DOI":"10.1090\/S0025-5718-1993-1192969-X"},{"key":"#cr-split#-e_1_2_1_8_1.2","doi-asserted-by":"crossref","unstructured":"Michael Clausen and Ulrich Baum. 1993. Fast Fourier transforms for symmetric groups: Theory and implementation. Mathematics of Computation 61 204 833--847. DOI:http:\/\/dx.doi.org\/10.2307\/2153256","DOI":"10.1090\/S0025-5718-1993-1192969-X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"e_1_2_1_10_1","unstructured":"Henry Crapo and Geoffrey Roulet (Eds.). 1971. M\u00f6bius Algebras. University of Waterloo Waterloo Ontario Canada.  Henry Crapo and Geoffrey Roulet (Eds.). 1971. M\u00f6bius Algebras. University of Waterloo Waterloo Ontario Canada."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1970-12372-2"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-0018-1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(73)90106-0"},{"volume-title":"Ordered Sets","author":"Greene Curtis","key":"e_1_2_1_14_1","unstructured":"Curtis Greene . 1982. The M\u00f6bius function of a partially ordered set . In Ordered Sets . NATO Advanced Study Institute Series, Vol . 83. Springer , 555--581. Curtis Greene. 1982. The M\u00f6bius function of a partially ordered set. In Ordered Sets. NATO Advanced Study Institute Series, Vol. 83. Springer, 555--581."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392520"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/21.148425"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70708-8"},{"key":"e_1_2_1_18_1","first-page":"58","article-title":"Endliche Verb\u00e4nde","volume":"247","author":"Klotz Walter","year":"1971","unstructured":"Walter Klotz and Lutz Lucht . 1971 . Endliche Verb\u00e4nde . Journal fur die reine und angewandte Mathematik 247 , 58 -- 68 . Walter Klotz and Lutz Lucht. 1971. Endliche Verb\u00e4nde. Journal fur die reine und angewandte Mathematik 247, 58--68.","journal-title":"Journal fur die reine und angewandte Mathematik"},{"key":"e_1_2_1_19_1","volume-title":"The Art of Computer Programming","author":"Knuth Donald E.","unstructured":"Donald E. Knuth . 1998. The Art of Computer Programming ( 3 rd ed.; Vol. 2 , Seminumerical Algorithms). Addison-Wesley , Upper Saddle River, NJ. Donald E. Knuth. 1998. The Art of Computer Programming (3rd ed.; Vol. 2, Seminumerical Algorithms). Addison-Wesley, Upper Saddle River, NJ.","edition":"3"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_47"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_54"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-09-04838-7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2009.11.031"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-98-00964-8"},{"key":"e_1_2_1_25_1","volume-title":"Rockmore","author":"Maslen David K.","year":"1997","unstructured":"David K. Maslen and Daniel N . Rockmore . 1997 . Generalized FFTs\u2014a survey of some recent results. In Groups and Computation , II. DIMACS : Series in Discrete Mathematics and Theoretical Computer Science, Vol. 28 . American Mathematical Society, Providence, RI, 183--237. David K. Maslen and Daniel N. Rockmore. 1997. Generalized FFTs\u2014a survey of some recent results. In Groups and Computation, II. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, Vol. 28. American Mathematical Society, Providence, RI, 183--237."},{"volume-title":"Proceedings of the 13th International Conference on Artificial Intelligence and Statistics (AISTATS\u201910)","author":"Parviainen P.","key":"e_1_2_1_26_1","unstructured":"P. Parviainen and M. Koivisto . 2010. Bayesian structure discovery in Bayesian networks with less space . In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics (AISTATS\u201910) . 589--596. P. Parviainen and M. Koivisto. 2010. Bayesian structure discovery in Bayesian networks with less space. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics (AISTATS\u201910). 589--596."},{"volume-title":"Monoids and Semigroups with Applications","author":"Rhodes John","key":"e_1_2_1_27_1","unstructured":"John Rhodes and Yechezkel Zalcstein . 1991. Elementary representation and character theory of finite semigroups and its application . In Monoids and Semigroups with Applications . World Scientific Publishing , River Edge, NJ , 334--367. John Rhodes and Yechezkel Zalcstein. 1991. Elementary representation and character theory of finite semigroups and its application. In Monoids and Semigroups with Applications. World Scientific Publishing, River Edge, NJ, 334--367."},{"volume-title":"Computational Noncommutative Algebra and Applications. NATO Science Series II: Mathematics, Physics and Chemistry","author":"Rockmore Daniel N.","key":"e_1_2_1_28_1","unstructured":"Daniel N. Rockmore . 2004. Recent progress and applications in group FFTs . In Computational Noncommutative Algebra and Applications. NATO Science Series II: Mathematics, Physics and Chemistry , Vol. 136 . Springer , 227--254. Daniel N. Rockmore. 2004. Recent progress and applications in group FFTs. In Computational Noncommutative Algebra and Applications. NATO Science Series II: Mathematics, Physics and Chemistry, Vol. 136. Springer, 227--254."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00531932"},{"volume-title":"Studies in Pure Mathematics","author":"Rota Gian-Carlo","key":"e_1_2_1_30_1","unstructured":"Gian-Carlo Rota . 1971. On the combinatorics of the Euler characteristic . In Studies in Pure Mathematics . Academic Press, London , England , 221--233. Gian-Carlo Rota. 1971. On the combinatorics of the Euler characteristic. In Studies in Pure Mathematics. Academic Press, London, England, 221--233."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1954.100110"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(67)80064-4"},{"volume-title":"Cambridge Studies in Advanced Mathematics","author":"Stanley Richard P.","key":"e_1_2_1_33_1","unstructured":"Richard P. Stanley . 1997. Enumerative Combinatorics . Vol. 1. Cambridge Studies in Advanced Mathematics , Vol. 49 . Cambridge University Press , Cambridge, UK . Richard P. Stanley. 1997. Enumerative Combinatorics. Vol. 1. Cambridge Studies in Advanced Mathematics, Vol. 49. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2005.08.004"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2007.12.001"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215037"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.11.004"},{"volume-title":"The Design and Analysis of Factorial Experiments","author":"Yates F.","key":"e_1_2_1_38_1","unstructured":"F. Yates . 1937. The Design and Analysis of Factorial Experiments . Imperial Bureau of Soil Science , Harpenden, England . F. Yates. 1937. The Design and Analysis of Factorial Experiments. Imperial Bureau of Soil Science, Harpenden, England."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629429","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629429","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:30Z","timestamp":1750231170000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629429"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,31]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,2,8]]}},"alternative-id":["10.1145\/2629429"],"URL":"https:\/\/doi.org\/10.1145\/2629429","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2015,12,31]]},"assertion":[{"value":"2012-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}