{"entities":{"Q1280280":{"pageid":1291030,"ns":120,"title":"Item:Q1280280","lastrevid":70063857,"modified":"2026-04-13T12:11:15Z","type":"item","id":"Q1280280","labels":{"en":{"language":"en","value":"Boolean functions with low average sensitivity depend on few coordinates"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1261186"}},"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":"Q1280280$E8740E0A-A3BA-4386-B532-A5A60935D3A2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f2b46ccfefad0268632c94dabfcdd7cfcb4443c3","datavalue":{"value":{"text":"Boolean functions with low average sensitivity depend on few coordinates","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1280280$779ED209-2009-4D61-A4FF-D7354A3B8DC9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"459752c15c2aec94feafcff419e8cf026cc97b55","datavalue":{"value":"0909.06008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1280280$933B7379-FB39-4228-A5D4-96F9C22B52BE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7408cb44223055dacf10de6d13afc2b7f604ebca","datavalue":{"value":"10.1007/PL00009809","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1280280$87A5B437-6675-4B24-819F-CC1CAC12F14E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4c1f35623768681f408e62bdd351d6201b9df65","datavalue":{"value":{"entity-type":"item","numeric-id":220703,"id":"Q220703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1280280$A49009B2-2EBD-4409-BB50-36F8A60C4B5F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1280280$A823D6A9-3D6B-41E8-A98D-324B70FADAC4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ccb0389d49d9dccc22d89b86cf8dea63356eb4b","datavalue":{"value":{"time":"+1999-03-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1280280$E4E73BD0-09F3-45FD-9129-D45087BF35B4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b046ff0237cb40ab43ff2fe4338939923e0d7a8d","datavalue":{"value":"The main topic is the approximation of a Boolean function \\(f:\\{0,1\\}^n\\to \\{0,1\\}\\) by a function \\(g\\) depending on only a few coordinates \\(i_1,\\dots,i_m\\), i.e. we always have \\(g(x_1,\\dots,x_n)=g(x_1',\\dots,x_n')\\) if \\(x_{i_j}=x_{i_j}'\\) for each index \\(j\\). Approximation means that the probability of \\(f=g\\) is large.    The author introduces the sensitivity of a point \\(v\\in\\{0,1\\}^n\\), which is the number of points \\(v'\\in\\{0,1\\}^n\\) with \\(f(v')\\neq f(v)\\) that differ from \\(v\\) in exactly one coordinate. The average sensitivity of \\(f\\) is the average of the sensitivities of all points in \\(\\{0,1\\}^n\\). A related concept is that of influence: The influence of the coordinate \\(i\\) with respect to a probability measure \\(\\mu\\) on \\(\\{0,1\\}^n\\) is the \\(\\mu\\)-probability of \\(f(x_1,\\dots,x_{i-1},0,x_{i+1},\\dots,x_n)\\neq f(x_1,\\dots,x_{i-1},1,x_{i+1}, \\dots,x_n)\\) by choosing \\(x_1,\\dots,x_{i-1},x_{i+1},\\dots,x_n\\) randomly. Let \\(\\text{av}_\\mu(f)\\) denote the sum of the influences of all coordinates. Then the average sensitivity of \\(f\\) is \\(\\text{av}_\\mu(f)\\) where \\(\\mu\\) is the uniform measure on \\(\\{0,1\\}^n\\) (i.e. \\(\\mu (\\{v\\})=2^{-n}\\) for each point \\(v\\in \\{0,1\\}^n)\\).    For \\(0<p<1\\), define the measure \\(\\mu_p\\) by \\(\\mu_p(\\{v\\})=p^{| v| }(1-p)^{n-| v| }\\) for each \\(v \\in \\{0,1\\}^n\\) (\\(| v| \\) is the number of ones in \\(v\\)). It is proved that \\(f\\) can be approximated by a function depending on only a few variables if \\(\\text{av}_{\\mu_p}(f)\\) is small. More precisely: There exists a constant \\(c>0\\) (only depending on \\(p\\)) such that for each function \\(f:\\{0,1\\}^n\\to \\{0,1\\}\\) and \\(\\varepsilon >0\\), there is a function \\(g:\\{0,1\\}^n\\to \\{0,1\\}\\) depending on at most \\(c^{\\text{av}_{\\mu_p}(f)/\\varepsilon}\\) coordinates such that the \\(\\mu_p\\)-probability of \\(f\\neq g\\) is at most \\(\\varepsilon\\). For the uniform measure (i.e. for \\(p=1/2\\)), an upper bound for the number of coordinates is explicitly given and its tightness is discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1280280$4FEE4A8B-8765-42CD-ABE5-6F0C4D39D032","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d99ab9d3449b46e71cca008f41754141256e0f11","datavalue":{"value":{"entity-type":"item","numeric-id":175589,"id":"Q175589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1280280$711998A3-771A-4AC0-857A-7F3E7299E11F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1280280$2F3920CC-3947-4F02-BC71-499CCEE93C74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"89fb1fcee055c06e8463e077f43859e4e2c01d9a","datavalue":{"value":"28A35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1280280$84ABFF21-5009-4DEE-BDE0-E480907BBA30","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8305072789542907d0df3ef0aef03f4192327379","datavalue":{"value":"1261186","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1280280$2C664946-AA9E-4722-A6CA-BF50AB4C0863","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb5a830579b475e59eaac799be7398a9142f423b","datavalue":{"value":"Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1280280$0CA4BB6A-A7E2-445B-A1AB-C9F8D3CB56B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1280280$5FDB52EB-5065-4CE7-B026-E5140C2B5EFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8407e07d57e25cfb22288c0a890434657d4a7141","datavalue":{"value":"probability measure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1280280$77EE7238-5483-4800-A369-CEDCCD562064","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7d7f54e4314cb66b453218298e81a5417b89537d","datavalue":{"value":"Q62111466","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1280280$7E6AE9C4-80A2-4122-B024-9F48F031342B","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":"Q1280280$CF6ADC8F-2DA6-4C46-94D0-23A96D20768B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5334efbd1658de6aad5976d2d7aa928fa110b89c","datavalue":{"value":"https://doi.org/10.1007/pl00009809","type":"string"},"datatype":"url"},"type":"statement","id":"Q1280280$AD86A699-CC17-4217-B9A8-384F0D8E8413","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ebf60d693a92e77843aefa5c24dba5d3ef5bc38c","datavalue":{"value":"W1986296546","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1280280$DEA7B43E-C089-430D-8BC6-9628F60D38A1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9e3444f79914c27450dd26de8c1fe04f32a7e0c","datavalue":{"value":{"entity-type":"item","numeric-id":1334688,"id":"Q1334688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b569cbe1544f443e3789f557213a1efca781a6bf","datavalue":{"value":{"amount":"+0.86739177","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1280280$246E4634-CC2D-4D0B-B4E3-4BA4ED12B197","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65966d0ca47743ed63a2213c8daf77218129d0f1","datavalue":{"value":{"entity-type":"item","numeric-id":4608008,"id":"Q4608008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec1e8f3b11299f5ebc56a478b52be5a0fa5af48c","datavalue":{"value":{"amount":"+0.8567562","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1280280$E91FC180-2A4D-47D2-BAF9-8F213B717744","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f330b74d26d56391ccf317ef85bfa490d4739c71","datavalue":{"value":{"entity-type":"item","numeric-id":1944916,"id":"Q1944916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e6a5d711e027e0a4cf501898fe1f2254f4febc1","datavalue":{"value":{"amount":"+0.847","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1280280$AD3EC7F1-79E2-4594-AECB-D4C6F7652594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1cba541e8779fd7404f046a86a1388900e692690","datavalue":{"value":{"entity-type":"item","numeric-id":1950376,"id":"Q1950376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6836026b94926fd9a61d0ba78074e536eaa9e910","datavalue":{"value":{"amount":"+0.8426333","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1280280$94BCDC72-3EC4-4F12-9F80-CEF0E0849CDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21d522f90834c4c796ded8eb4ce960bcdaeb5671","datavalue":{"value":{"entity-type":"item","numeric-id":2800553,"id":"Q2800553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1990399318726743d5a36d6529ca88a6f95e1e38","datavalue":{"value":{"amount":"+0.8363948","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1280280$4C5B929E-9B4A-45A1-84F9-DEE9A7D4FE64","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":"e450aa168d8d653fa5810642c4c8935adf328a86","datavalue":{"value":{"amount":"+0.83504","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1280280$7D67D851-A075-4D6E-BC83-5AA7ABA75F34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f2787c0ff134e04d02e87d2bc0267ee740e1b0e","datavalue":{"value":{"entity-type":"item","numeric-id":4321530,"id":"Q4321530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2cfa33bd5b4b054699829c4fee886962012d0d7","datavalue":{"value":{"amount":"+0.8346491","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1280280$1774C269-1F7B-4FBE-AF5F-12C111B9C439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b697aacc0912447427ed99b5e5b2b28874e8e37","datavalue":{"value":{"entity-type":"item","numeric-id":3583651,"id":"Q3583651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"435597508b59f97688bc00f74a5078c06a240909","datavalue":{"value":{"amount":"+0.83315974","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1280280$FE2519E3-8469-4474-A3D4-3E602FEC3F18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0ef9ca7dafab96da8e33a3488f620e70f84436c","datavalue":{"value":{"entity-type":"item","numeric-id":1943387,"id":"Q1943387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05295645426b661c7f940a0fa662bfb6698636ff","datavalue":{"value":{"amount":"+0.83155835","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1280280$36497EDB-5DC2-492A-ADDC-3EB04BFF86ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27472b0b5d0a402d8232bbbfe5ea22e4a09d4955","datavalue":{"value":{"entity-type":"item","numeric-id":4459079,"id":"Q4459079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"087b5e71dfe7e03ef08de851c1130aeb65704e68","datavalue":{"value":{"amount":"+0.8301585","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1280280$245030C1-413F-4D16-86B0-909795B86748","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Boolean functions with low average sensitivity depend on few coordinates","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Boolean_functions_with_low_average_sensitivity_depend_on_few_coordinates"}}}}}