{"entities":{"Q2382286":{"pageid":2393029,"ns":120,"title":"Item:Q2382286","lastrevid":78614951,"modified":"2026-05-06T12:01:21Z","type":"item","id":"Q2382286","labels":{"en":{"language":"en","value":"Block sensitivity of weakly symmetric functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5196811"}},"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":"Q2382286$95F53295-5870-486D-9B14-C94985BFD01F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1662b122e54c94a98763b40d658bb0bccaae8ee1","datavalue":{"value":{"text":"Block sensitivity of weakly symmetric functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2382286$6A3885F0-F679-4EFA-8D20-EEFA4A07FFC7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5056090457015667dc2c7121e423c457c3bb21f0","datavalue":{"value":"1124.06009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382286$DDCA8479-9B12-4DB5-8037-0406A0AF1D37","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a82fb6baae5459035c24cf8543210318cc9df255","datavalue":{"value":{"entity-type":"item","numeric-id":369427,"id":"Q369427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382286$A2AFDDF0-0411-49F3-A3ED-E30260C58580","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382286$4E6075AB-D4B8-418D-BC14-91C6C31A4D61","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0f3bb612485fd64be80be5677ab1cdc0f4709762","datavalue":{"value":{"time":"+2007-09-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2382286$8BA4CED2-713A-4943-A0D1-50680D5CA3EA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bbb602f1846df625bb34af7bd2293b6f8bc8a08a","datavalue":{"value":"\\textit{N. Nisan} [SIAM J. Comput. 20, No. 6, 999--1007 (1991; Zbl 0737.68028)] introduced the concept of block sensitivity of a Boolean function \\(f\\), denoted by \\(\\text{bs}(f)\\), proved tight bounds for computing \\(\\text{bs}(f)\\) on a CREW PRAM and showed that block sensitivity is polynomially related to many other measures of complexity. This is one of the most useful measures of Boolean functions. In this paper the block sensitivity of weakly symmetric functions (functions invariant under some transitive group action) is investigated and it is proved that for any nontrivial weakly symmetric function \\(f\\), \\(\\text{bs}(f)\\geq N^{\\frac{1}{3}}\\) and there exists a cyclically invariant function \\(f\\) such that \\(\\text{bs}(f)=O(N^{\\frac{3}{7}}\\log N)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382286$2E38BD08-CC4E-452B-88AF-FB3941E12407","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382286$90D75BA9-A362-406A-913F-D10140773FFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382286$9A6D657F-3D3D-439A-97D3-90494975341F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382286$B9DD5430-2727-4CC4-A590-C19CDD98375C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"912e263734af9e687440f2e60f72351d195400f6","datavalue":{"value":"5196811","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382286$80796C35-645E-4A46-9CC5-27F8BCDA270E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0062bff246f10874c360cb4d691bf5c2195f236c","datavalue":{"value":"Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382286$15360340-9ABD-4A05-8F36-62BC22970B4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8cb29242d978228f594dee86805a95652c77664c","datavalue":{"value":"block sensitivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382286$C2ED16E5-FC14-4D14-84BD-3B514746A3A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"398743adb21d0970227e07b20b555b67b64224ed","datavalue":{"value":"weakly symmetric function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382286$8B0F4217-954B-4768-87DF-46093428DDF4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382286$61ECD5AD-D3DD-4E0B-949E-A4BC04D0E2D2","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":"Q2382286$EEEA94A4-3E67-49AA-9817-CB2E9488F328","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dc21f3a6067400707370a7bfa6ce1cff3ae2c05e","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2007.05.020","type":"string"},"datatype":"url"},"type":"statement","id":"Q2382286$79A13B5B-EEF8-45A9-9D18-5DB5ED3E267B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4699675736c23d3fcd640fb21683ee1a40f08388","datavalue":{"value":"W4210418148","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382286$9FB879A0-8CC4-4C0D-B0E0-0CA3FF85992D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c81ee2ca0256eec06c7cc1d6395ec3f796ec9064","datavalue":{"value":{"entity-type":"item","numeric-id":5441359,"id":"Q5441359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382286$ADC50A26-43C6-46EE-9EFF-A7104E5EA062","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9872d1e5b694c452e067c737826bed9fab5fdb53","datavalue":{"value":{"entity-type":"item","numeric-id":1853508,"id":"Q1853508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382286$39FCF25B-1934-43EE-9656-C5BD1299DA51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63fa412b16fa1d1bf50cd43213a92001117a77bb","datavalue":{"value":{"entity-type":"item","numeric-id":3985804,"id":"Q3985804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382286$AC9C72F4-E2DA-4950-85C1-F02BB0C1B46D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33c78c20459dff182618761f69f8bfcf22d8fe9d","datavalue":{"value":{"entity-type":"item","numeric-id":1346612,"id":"Q1346612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382286$B7DC8278-2F5B-4F69-A2AB-5D43FCE37EBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7be7ec776afc6ad8ad178675a434e62027116713","datavalue":{"value":{"entity-type":"item","numeric-id":1238421,"id":"Q1238421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382286$DF3D6858-5B2C-443A-A1C4-7D66E31355B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c169d56fea024411edfd210e329309c0be5b819","datavalue":{"value":{"entity-type":"item","numeric-id":795503,"id":"Q795503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382286$86738C1D-1A70-48CD-948D-F5BF2348AC71","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a855325cf4d2d8eea7e80056d5c4e530a1ca82fe","datavalue":{"value":"10.1016/J.TCS.2007.05.020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382286$9D5C99CA-E023-4D41-872C-6B65389442F8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d4b341d3989f0b1e7cfc7dcb6cb3697454a3f87","datavalue":{"value":{"entity-type":"item","numeric-id":5898888,"id":"Q5898888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad852758c22341bb17147b096a96d436c4d1df47","datavalue":{"value":{"amount":"+0.9699642062187196","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":"Q2382286$6993E26F-8C5B-475C-A110-E01D5720884E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce98def24397fb1d0d4e24ed2a6185424ff80761","datavalue":{"value":{"entity-type":"item","numeric-id":719324,"id":"Q719324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db7e966bea42c19f3c845fe36e0cd3c5f77829ec","datavalue":{"value":{"amount":"+0.8503544926643372","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":"Q2382286$B0594175-9DC3-4E6E-AE62-242EF8DD1988","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3bc07d3012e1625e7eab04e58b0388997b649fd3","datavalue":{"value":{"entity-type":"item","numeric-id":2048184,"id":"Q2048184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d9642de011c138a557dd2092757735881e77802","datavalue":{"value":{"amount":"+0.8485029339790344","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":"Q2382286$E6D5C40F-A86B-4CE8-9C46-3848AAE5125E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05a37904c07d582df2841883374a7aa9d5c492b4","datavalue":{"value":{"entity-type":"item","numeric-id":1887146,"id":"Q1887146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9948686b1481e915817800b41a757f480a6d5bb","datavalue":{"value":{"amount":"+0.8447902798652649","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":"Q2382286$DA0858BC-1929-4248-ACED-CC5977D872C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b0332f4eb176865a664258aea8d85eda7c17eaf","datavalue":{"value":{"entity-type":"item","numeric-id":1894709,"id":"Q1894709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"871d6af05e1b7d1576ed5b18df5f442777a1a83d","datavalue":{"value":{"amount":"+0.827179491519928","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":"Q2382286$1E2E04E8-0EC3-4FA1-B1C1-1AE486D4362E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Block sensitivity of weakly symmetric functions","badges":[]}}}}}