{"entities":{"Q1063574":{"pageid":1074326,"ns":120,"title":"Item:Q1063574","lastrevid":66181776,"modified":"2026-04-12T08:05:25Z","type":"item","id":"Q1063574","labels":{"en":{"language":"en","value":"Bounded-depth, polynomial-size circuits for symmetric functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3918273"}},"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":"Q1063574$7073B83C-F140-48B9-B650-8E5F4A4FCB5E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"496b824560043378624fa9a5461074ca9dadd641","datavalue":{"value":{"text":"Bounded-depth, polynomial-size circuits for symmetric functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1063574$F37CB5D0-E760-44CC-A78E-130DA8DC8C58","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3f456bc4ec3040ab792eae4b449a26f50b3e3b6e","datavalue":{"value":"0574.94024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063574$36233EE2-398B-487A-BE31-116909C6E90D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"66847df0066c8774fa3e52192c5f9a89723f1f31","datavalue":{"value":"10.1016/0304-3975(85)90045-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063574$DDA53556-0F53-473C-9938-FCE4F0EC2C1F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"501919793d5a7682fe5d33dabd63127f0c90af27","datavalue":{"value":{"entity-type":"item","numeric-id":388219,"id":"Q388219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063574$5BEFF827-918B-4D07-ACB0-12266D0D4B24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a25d6c9ed2c7d3c838dcd849030b5593bce4a77","datavalue":{"value":{"entity-type":"item","numeric-id":1058850,"id":"Q1058850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063574$505EA450-5AAD-419D-910B-5C179C2D2AE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"307c4d439b55aca8f278981eb5d6ad01231c11b6","datavalue":{"value":{"entity-type":"item","numeric-id":489753,"id":"Q489753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063574$605AC825-B3F0-46AE-AC10-BDD28AD09CEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"355a32c186d9586aa82df09b9eb223d278a9aacd","datavalue":{"value":{"entity-type":"item","numeric-id":1134519,"id":"Q1134519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063574$7B900D78-032C-4809-8670-D1004293B41E","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":"Q1063574$47061F34-C5C2-4094-9EBE-5F3A8030603B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1063574$C3C2DBDF-96E9-46F8-B4FD-3C54A42FD030","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"07742b298549da43c67aa3b488431c5a989bef55","datavalue":{"value":"Let \\(\\{f_ 1,f_ 2,...\\}\\) be a family of symmetric Boolean functions, where \\(f_ n\\) has n variables. For this family the minimum number of variables of \\(f_ n\\) is considered that have to be set to constant values so that the resulting function is a constant function. It is shown that the growth rate of this minimum completely determines whether or not the given family if ''good'', that is, can be realized by a family of constant-depth, polynomial-size circuits (with unbounded fan-in), and explicit growth rates, which define good respectively bad families, are given. The authors' results provide a unifying framework to show why the families of parity and majority functions are bad. (From the text).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063574$6769597E-C79B-499B-9529-AB736E187FB7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063574$50AA2976-122B-4D8D-BCB4-0FB7BFB98B93","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3756a9c8e8b7317addd76970f2d8b65c8dd0b0b4","datavalue":{"value":"3918273","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063574$2E73A236-DE93-4DB7-A8F9-A56A5437C722","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f499971506bb7d13eebf3a41582911b6f7a30bdf","datavalue":{"value":"spectrum","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063574$032E6124-B388-4741-80C5-B3B8C557FAF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d13b05f1c57ccfe636a5ac98af15c43ecfabd8","datavalue":{"value":"measure function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063574$80313240-5EE6-4476-9BA1-7399B4F13D13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0999fcf122767626d408353fc24f2df8184573b4","datavalue":{"value":"parity functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063574$CB3DAB27-33A9-465F-AC45-0DD23EC03F82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ede060d74497e79ada8c8a1d4afbebe25589dd0","datavalue":{"value":"symmetric Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063574$6EA3297B-975F-4484-8CA6-FE996B87F21A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b93d3494f85ffbd9ecfd0f615aa170077e6235b","datavalue":{"value":"growth rate","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063574$1EF2EB7B-63FB-438A-AFB7-9D8CBD9AEE85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c2975e6375f8ac058e7b6c0b432fe30746eee1b","datavalue":{"value":"majority functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063574$C21F5580-178C-440F-ADE1-90B555843060","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"19731b52ec6f6780f9739de7ae6a6ae15351eb00","datavalue":{"value":{"entity-type":"item","numeric-id":589305,"id":"Q589305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063574$1AC6FA53-802C-4BC3-A021-E2E60FA65C9D","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":"Q1063574$B1CCA0B6-FC89-4CAE-B4F0-FEC417D96B7D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3b3aa50977e253d6c6a433ae92d1bd7078577e7b","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90045-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1063574$D3ECCB01-4F0B-4E4B-85E0-2E0379CEE028","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d46c78d2b6d35f3dc2550d745da9d67f176a2754","datavalue":{"value":"W2063584607","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063574$7F4FECC5-5BED-482A-A4BC-DB859A76392B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"957892286a77298fd7faca30f1f60dbb53f94696","datavalue":{"value":{"entity-type":"item","numeric-id":1054720,"id":"Q1054720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063574$22100CD0-A1A8-4FE8-95D4-C3C07E63522F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3aa57810f0528ce2438cd0f484c242c53bb4e54","datavalue":{"value":{"entity-type":"item","numeric-id":3325043,"id":"Q3325043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063574$837C89AF-39EF-4C4D-A4A7-D2B1E953C8B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ed42a67ea4a489bc2843c16fc36181e4361fce2","datavalue":{"value":{"entity-type":"item","numeric-id":5606602,"id":"Q5606602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063574$B66309FB-75E5-4E30-8B15-4651E9D01F3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff1f9a2420043f24c8557f0fa8bbd5638c3d8bb4","datavalue":{"value":{"entity-type":"item","numeric-id":3290963,"id":"Q3290963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063574$90391B0A-6941-4D5B-872D-A9D73166CFF9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0b3b83aa487483083c8baf1718f7836cd64182f","datavalue":{"value":{"entity-type":"item","numeric-id":1322486,"id":"Q1322486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdcc7e5398d16745c8bf3cb9970007690dc43e71","datavalue":{"value":{"amount":"+0.8487972617149353","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":"Q1063574$87016513-A4C4-4AAA-A97E-B356C6EBADFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a9c636428a28c6469f3c50ed2f5ec05b56bb05b","datavalue":{"value":{"entity-type":"item","numeric-id":4036705,"id":"Q4036705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6927b87a1dc8a4185aace74873b57f215d62e79","datavalue":{"value":{"amount":"+0.8458490967750549","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":"Q1063574$87CCF656-B5AE-404C-AE21-2F5D31E3D359","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65fbad1a797b1a096f0850da4789673c5c71741d","datavalue":{"value":{"entity-type":"item","numeric-id":3357542,"id":"Q3357542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a4b2d05e37007a85dd93cbbc85b2186729747b4","datavalue":{"value":{"amount":"+0.8449562191963196","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":"Q1063574$EEEBDBBF-FAD0-4F17-B8A3-C43B5EB32F23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4cfcac0c5ff3e465be0e3cb34503213d54261c5","datavalue":{"value":{"entity-type":"item","numeric-id":1107987,"id":"Q1107987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25cd4ee9388f16cd7a5b1dad56c12c4c86e58df4","datavalue":{"value":{"amount":"+0.8448585867881775","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":"Q1063574$994E9E54-0938-44DC-B5B0-A9E2F37CE9DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd284f2db7476bf22b7eb108c9c7c4b6b8d80ce7","datavalue":{"value":{"entity-type":"item","numeric-id":1193637,"id":"Q1193637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79c4e578bf5e8a252b9474ac7476df4bacfbe80e","datavalue":{"value":{"amount":"+0.8447498679161072","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":"Q1063574$58EE9A8E-4198-432A-BBB9-B522A1DF82B4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounded-depth, polynomial-size circuits for symmetric functions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounded-depth,_polynomial-size_circuits_for_symmetric_functions"}}}}}