{"entities":{"Q2073019":{"pageid":2083761,"ns":120,"title":"Item:Q2073019","lastrevid":78406628,"modified":"2026-05-06T11:31:06Z","type":"item","id":"Q2073019","labels":{"en":{"language":"en","value":"Coset decision trees and the Fourier algebra"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7465189"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$86AA9A40-EB8F-41AA-8FD8-BE17E9FD198F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a43f5d3bfcd445aab77dd256c312b7acaa1edc3f","datavalue":{"value":{"text":"Coset decision trees and the Fourier algebra","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2073019$9F854917-F380-43DB-BB72-0BEA450B4391","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4cd95362a35c8c2b9d1490c7595edf7ef344ec25","datavalue":{"value":"1497.43004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2073019$1F187A03-BBA1-4DD1-B02B-212B450AEF85","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e006a000ffb78f66a5837a0fcea1c8c12e3a1e30","datavalue":{"value":{"entity-type":"item","numeric-id":351353,"id":"Q351353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$5B377B66-B436-4228-AC74-D1B4934DFEBF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e7cb94b734d7b2835c194481178a8cd8e8a59783","datavalue":{"value":{"entity-type":"item","numeric-id":163291,"id":"Q163291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$33048595-51E1-4BDD-8069-D780EF33F28F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"65c9e6e397b1a20fdb52cef8c05fd7e566e4b623","datavalue":{"value":{"time":"+2022-01-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2073019$C6884A4E-F798-4A38-8339-F4A08865DAFA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"056ec4e74b0b22be67a04c60f39230930b3362c6","datavalue":{"value":"https://arxiv.org/abs/1805.02168","type":"string"},"datatype":"url"},"type":"statement","id":"Q2073019$D0C82405-7757-4FAC-BC73-CCDFF3A6B3E3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5a8e46dae5a8ffeb023d0cda6f6e30e38b5bdc96","datavalue":{"value":"This paper extends to more general finite groups some results in abelian group theory. The results melt computer science, combinatorics and harmonic analysis (mainly Fourier algebras). Most of them are related to the complexity of the computation of an integer-valued function defined on a finite group. Among other results, we point out the following. The author proves that if a \\(\\lbrace 0,1\\rbrace\\)-valued function defined on a finite group is such that its Fourier algebra norm is less than \\(M\\), then there is a coset decision tree with \\(\\exp (\\exp (\\exp (O(M^2))))\\) leaves that computes \\(f\\). Furthermore, the author proves that if \\(f\\) is an integer-valued function on a finite group with Fourier algebra norm less than \\(M\\), then \\(f\\) is a finite combinaison of some integer-valued functions \\(z^{(i)}\\) related to some subgroups \\(K_i\\), \\(1\\le i\\le L=O(M)\\), with \\(\\|z^{(i)}\\|_{l^1(G/K_i)}\\le \\exp (\\exp (\\exp (O(M^2))))\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2073019$1CA43310-886C-4D31-9121-344BA852CD06","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2a72e4aa974383f04f4fda5c7412016e34967a69","datavalue":{"value":{"entity-type":"item","numeric-id":426215,"id":"Q426215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$D5172086-B3E7-4582-B058-A2B6A0699191","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bb43a808be311368e987aa708d28b6350ae1ca2b","datavalue":{"value":"43A25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2073019$9BEA1721-A52D-473B-8E1D-F171C937E274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2073019$8C68521A-D7EE-44AF-9FC3-A75F3784B077","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"635c77a39b27ee22a5bfcde299ab7a563c7614e1","datavalue":{"value":"20D60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2073019$CC2883E7-E845-4D42-B8E3-01BA36D52115","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"14d45a2f0b968357e2391e141309f08ffdcc0d76","datavalue":{"value":"7465189","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2073019$3F510CDA-0123-4B50-B7BC-09D92296DFAF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"98980fdedb7e749a0d2ee7140de6408f0b5ec20f","datavalue":{"value":"coset decision tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2073019$9DDDE957-C815-45E3-B8C9-23F637239A87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18c42de41f3c94716175d79e3c102bb7e3ce2cb4","datavalue":{"value":"finite group","type":"string"},"datatype":"string"},"type":"statement","id":"Q2073019$E0262226-F101-4352-8D30-095856DEE630","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aadb237b402372abe12c3a31f39cf5f060daa91b","datavalue":{"value":"Fourier algebra norm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2073019$A1A50275-2DDF-407B-83A0-A0F5CD7B5E50","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$BF1EE257-A1E7-4D9A-B411-5F12F96D5B8F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9d4a97ed328a978ae35f5fb697a0a4bedbf666b9","datavalue":{"value":"W4205843339","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2073019$E5591223-0DEE-4231-85B7-60A36BBAD3BC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f20b8d9a2de6b31313622445b70a40f9625371a9","datavalue":{"value":{"entity-type":"item","numeric-id":2986494,"id":"Q2986494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$F6828FB8-9660-45FB-893C-15D7DD17F4D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76d09f4ed7c7c11c7e15a02e797e3482ca45fb7b","datavalue":{"value":{"entity-type":"item","numeric-id":2015154,"id":"Q2015154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$E0979E2E-3DB4-424E-BF2B-26422EB910B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34dada87b028cd27441ba62ac9eb81f682c5b3d2","datavalue":{"value":{"entity-type":"item","numeric-id":1927933,"id":"Q1927933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$C71489E5-9E77-402D-9293-EACEF2B6A457","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e0c63b378156a361d7e2694b90b54e33872dd39","datavalue":{"value":{"entity-type":"item","numeric-id":4921566,"id":"Q4921566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$5EFDEC8A-07EF-4195-9848-0B6FFF98CA9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"154439074181bd2a3be3989823dddd641727b49b","datavalue":{"value":{"entity-type":"item","numeric-id":3280170,"id":"Q3280170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$FC9A42C8-252E-454C-A076-DE9AE2B0B005","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9ab9bbd7409fff4b7cce4a55544bf09f9475608","datavalue":{"value":{"entity-type":"item","numeric-id":616150,"id":"Q616150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$9D0CA8B8-FAE4-4CA0-97D0-D4F55699E8F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5989a5ad4beb1ff69c9ca40872671b4416059e30","datavalue":{"value":{"entity-type":"item","numeric-id":5556773,"id":"Q5556773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$7BE0DC83-A5DC-41B3-9132-8239CA1E1931","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"264a2ea83137381c2d7cc3f98c9011dcc007d949","datavalue":{"value":{"entity-type":"item","numeric-id":1410562,"id":"Q1410562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$D7CF9993-ADDE-412D-B927-B6D7268EC89C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c8aad5a00d0d75e8b534ef5c175dbb51fa2e0c4","datavalue":{"value":{"entity-type":"item","numeric-id":2574914,"id":"Q2574914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$1D61E148-F119-4DE1-A0EE-337E678112FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5658979b849fe15b1149cbadf283465c7026681f","datavalue":{"value":{"entity-type":"item","numeric-id":3624524,"id":"Q3624524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$A30668B8-DD09-4B74-AB6D-18FA676505C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbd9f14f34e3cfa8809109dfc40bc2f4ddb3674e","datavalue":{"value":{"entity-type":"item","numeric-id":2427039,"id":"Q2427039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$4099A5BD-FF60-483E-B567-68E24C0AF991","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a83c4fdb69d759c2db0833164406726c59280fc1","datavalue":{"value":{"entity-type":"item","numeric-id":2389132,"id":"Q2389132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$677D7AD7-3D22-495C-84C3-E27A6D02EE9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"489c1b740f2d9cbe8b21e9be82757fcdaa53f2f2","datavalue":{"value":{"entity-type":"item","numeric-id":3744668,"id":"Q3744668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$6AEEC431-F622-45B9-B9D7-1A52325618A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49172515abb1787109c970b5001f0a76a4d18de1","datavalue":{"value":{"entity-type":"item","numeric-id":4277547,"id":"Q4277547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$1F910653-15C3-4268-BCA5-15485B922786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ff876eb40cc6911a82d26e0141b48fe7be2953a","datavalue":{"value":{"entity-type":"item","numeric-id":341713,"id":"Q341713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$07D6FE60-049C-40CB-B4BD-52530CDEA628","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66cfb4f4c9aaa5b939e8195636b8c5941874d7bb","datavalue":{"value":{"entity-type":"item","numeric-id":5660121,"id":"Q5660121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$90EB9A29-1B5F-412A-A4A1-52EA3CD07855","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae6fa1fbfe4f453f21ee5b79394b50518ee71db0","datavalue":{"value":{"entity-type":"item","numeric-id":3969357,"id":"Q3969357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$7E6021E8-87F8-4947-BEB6-DE2F2F348B02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"574a6599f545ec08b9afa71a7573eae29e700904","datavalue":{"value":{"entity-type":"item","numeric-id":5166888,"id":"Q5166888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$A3FCD997-96D4-4353-9CA5-EF10E2202C97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"638f6c9e88b8fa882626757671e003448213dd06","datavalue":{"value":{"entity-type":"item","numeric-id":3293614,"id":"Q3293614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$9E9984D5-B6D2-4717-8DD9-39ABDE0DA0B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8b55eb6d90e85fa7e0903b67f2614079541a6c8","datavalue":{"value":{"entity-type":"item","numeric-id":868821,"id":"Q868821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$25AFD874-AF05-4638-BBD5-8DFBBC1A384D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e239830de26ac38d6cfef112eff4bcf48aa53539","datavalue":{"value":{"entity-type":"item","numeric-id":633235,"id":"Q633235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$0F0D9E42-6F5A-4B49-A250-04CC3C1EBE66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb5681efe97e1ef4e990dba462e76f3759f9a2fe","datavalue":{"value":{"entity-type":"item","numeric-id":1951735,"id":"Q1951735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$55F426C2-F941-4211-A68C-E3D104EF87ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c451ebd49df7a4cce39c10d200808e69ab4811a8","datavalue":{"value":{"entity-type":"item","numeric-id":5393666,"id":"Q5393666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$9EC32922-3956-4BBF-91A4-03C5CDDA201A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e799232779267c635b4a6d9afdfd8f4ae322b2e2","datavalue":{"value":{"entity-type":"item","numeric-id":3995204,"id":"Q3995204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$BFC8D47B-D4CE-491B-960D-639001B18A8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f792d1db3f54b54819d285370f142bc944a7381","datavalue":{"value":{"entity-type":"item","numeric-id":3002212,"id":"Q3002212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$A6E5DA26-8482-4CA0-A722-FFDEF5B846C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e544d2ea6ae1ebb52fa3d19e5a8d1a3a33fb66c7","datavalue":{"value":{"entity-type":"item","numeric-id":3151171,"id":"Q3151171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2073019$FCC4531B-EE1F-4A17-BD54-13977DCFF062","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bfc875145d7221ea4a07b2b8323d1d1c23b0a538","datavalue":{"value":"10.1007/S11854-021-0179-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2073019$28684BDC-AF9B-40E5-927A-EA1EA46CEEB6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9879a5ff9d25ac0f5af0febeade5d78192369df2","datavalue":{"value":{"entity-type":"item","numeric-id":2310830,"id":"Q2310830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7eaf0b63fd27cb0561bed460d1a54d4000edce52","datavalue":{"value":{"amount":"+0.7392879724502563","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2073019$CEB84312-A859-4D8F-8BB7-1D743E9D95A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24e30f59bde28743f35c79117aef34d49a9759a6","datavalue":{"value":{"entity-type":"item","numeric-id":4277547,"id":"Q4277547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19f741755ac8420448b3f74aca6cc8bdfe7dbdcb","datavalue":{"value":{"amount":"+0.7286223769187927","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2073019$BBABA0BD-2FE3-40AA-80ED-E2ACA6083128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d622b9440f3bf0298178ac2b14e13984ceb6e013","datavalue":{"value":{"entity-type":"item","numeric-id":4211459,"id":"Q4211459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80f3e28e8e044445a3be633608bff8a42fc33112","datavalue":{"value":{"amount":"+0.7136634588241577","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2073019$BCECD763-359F-4D8E-A0B6-2989A88523C2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Coset decision trees and the Fourier algebra","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Coset_decision_trees_and_the_Fourier_algebra"}}}}}