{"entities":{"Q1066866":{"pageid":1077618,"ns":120,"title":"Item:Q1066866","lastrevid":66074205,"modified":"2026-04-12T07:21:53Z","type":"item","id":"Q1066866","labels":{"en":{"language":"en","value":"On the complexity of slice functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3926817"}},"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":"Q1066866$897FDE10-1166-4505-9C78-D78A93CCD059","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"85ac84ad50dee40dde20322ba861318469ef7e62","datavalue":{"value":{"text":"On the complexity of slice functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1066866$550C4D47-2109-4188-8208-3AFB783C453C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c721260f41e9f51efed2d5e7c407ab3477971cbf","datavalue":{"value":"0578.94031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1066866$708B3971-C00E-4874-92FC-4DC81056842C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c94023fe331500586122e5b8aecb3d8cc4fd24f3","datavalue":{"value":"10.1016/0304-3975(85)90209-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1066866$8573AA6B-FEB7-4B35-8B85-95CC290282ED","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"00b3e57da97cbc00a7ce7385e258f05ae9a6ec6b","datavalue":{"value":{"entity-type":"item","numeric-id":171935,"id":"Q171935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1066866$73F85868-9634-42A0-A9E8-4A040304B170","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":"Q1066866$FF1A4612-A786-42C8-9E4C-33CCFA941A02","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":"Q1066866$EFB509EF-76CE-4740-B540-DC84A1E13C14","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e9d709a02b88e311e5744c7bc62425d973f0cc0d","datavalue":{"value":"By results of Razborov negations can be very powerful for Boolean circuits. But for the class of slice functions negations are almost powerless. Hence each hard function has a hard slice. Lower bounds on the monotone circuit complexity of slice functions imply lower bounds on the circuit complexity of these functions. The structure of slice functions is investigated and efficient algorithms for some slice functions are presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1066866$149759AF-68D6-4C43-B60B-7A389A5C9B00","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1066866$A80346C7-EBCF-4565-ADB7-6EC3F4C53736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1066866$EDDFE0A8-0507-43A9-91EA-A6C1D9B61651","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"957f4ad0d90b043e00aa43848ab21e648e88ffd3","datavalue":{"value":"3926817","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1066866$DFB4D071-0E0B-476F-BBC2-AC9AD807C4D5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51aa0ac6fdb8b8dd714950fc4d56a37396a0427a","datavalue":{"value":"relations between complexity measures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1066866$71160907-42D6-4C42-8C38-C00841950BB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d463b247e815798d799459507ebd3bcfc87bfad","datavalue":{"value":"Boolean circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q1066866$188C50BD-8807-441D-AD86-1D1404453A69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c601bd810a5a1256b1b65c8bd40ab071ba901b55","datavalue":{"value":"monotone circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1066866$F0DA60A1-FD2E-430E-9FED-30D452654BE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff9f78089affef06c072081bb824e40f99a75bd9","datavalue":{"value":"efficient algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1066866$9E7500D7-C8DF-4D45-9EBB-E3387BADB8D4","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":"Q1066866$7FF7CDE7-B302-4F47-ABF8-4E29B3FF0E7B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"02d6d71d1108ec12ff944bfa8d6db2807aeb6abc","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90209-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1066866$591CA368-2E25-4693-BFA2-EEF418EB0D25","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3388f8e1a70fd8d82718591914b66ac05f59e992","datavalue":{"value":"W2054417980","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1066866$F60D88B2-EFA1-4C37-9797-1702CB244669","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b44ed555aed1fbc544de1802074fd0df13fb2c0","datavalue":{"value":{"entity-type":"item","numeric-id":1056541,"id":"Q1056541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1066866$D8B8A576-9245-42A1-8C50-89CCF7FBF547","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"febe18a8bb8e7377d5dd6f028103ec1a3068042d","datavalue":{"value":{"entity-type":"item","numeric-id":1224550,"id":"Q1224550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1066866$DE668505-6005-48AA-A6BB-266562EF1701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d13a9d860864d84f1bfa831466640ce30d9351b","datavalue":{"value":{"entity-type":"item","numeric-id":5656695,"id":"Q5656695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1066866$0D845FBB-CA2F-41C9-A659-753190A7DEF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bcea5dd1838c0d984c13b6934f789fdae7a8f76","datavalue":{"value":{"entity-type":"item","numeric-id":4138140,"id":"Q4138140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1066866$EB258700-94D9-42B4-8BAF-5C8B73F77966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c43b242e8d2a6febe28b4e1a41898561ecb7a1a8","datavalue":{"value":{"entity-type":"item","numeric-id":4138141,"id":"Q4138141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1066866$E6D10380-13AA-4B21-AC85-CD5F1AF491D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51e06cd08b21ba41692bb65b88d6aafecf32e6a8","datavalue":{"value":{"entity-type":"item","numeric-id":4726175,"id":"Q4726175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1066866$BE997DEF-58D2-4560-BDF4-9718FF80D536","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f570b901946254e7e256906c632b0bf64e27f322","datavalue":{"value":{"entity-type":"item","numeric-id":1166489,"id":"Q1166489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1066866$6BB23D4E-3C1F-48F9-B32D-F07CE076AE29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3be5e45126f38fc3d7370208ed2fc708c7f1bb45","datavalue":{"value":{"entity-type":"item","numeric-id":3698705,"id":"Q3698705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1066866$4D97F35F-B936-461B-A0C5-6EEA4F059340","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17980287b4aff10463631316346dae81267a0f62","datavalue":{"value":{"entity-type":"item","numeric-id":3221885,"id":"Q3221885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dc46660a5f61a39fe23b79fcf9ec8497afbe488","datavalue":{"value":{"amount":"+0.99999976","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1066866$D9DB0CA2-2E62-469E-83D7-D5A1AB6CED21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49f389d6009550bbc5f2de2c54600e6d8cda5155","datavalue":{"value":{"entity-type":"item","numeric-id":1079365,"id":"Q1079365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54af33a16efaef7bb3eeeea2dc49e244d789ab1f","datavalue":{"value":{"amount":"+0.9636124","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1066866$8C467689-DD17-4163-B19C-ED418C6C4064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce8e2672852bf322759f1f5de8095ff18a6c8013","datavalue":{"value":{"entity-type":"item","numeric-id":1084375,"id":"Q1084375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6880151fd4ccae382210cb5a62dde8246abcae3c","datavalue":{"value":{"amount":"+0.92597073","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1066866$37DDAE9B-6C7A-4434-8AF9-C5F59A5AB317","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca5faaac8dd9f0febd41da15979d82d53a1addc0","datavalue":{"value":{"entity-type":"item","numeric-id":1405800,"id":"Q1405800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f246fe26b0117a56cc6193179047c33e92cab800","datavalue":{"value":{"amount":"+0.9194523","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1066866$1D108D0E-8245-4B58-9CCC-1B0DD8C6F376","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bd30a920e756ebbb4d182010d9c3a1422f854db","datavalue":{"value":{"entity-type":"item","numeric-id":4436042,"id":"Q4436042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d88a8ca65ce71442d39f331c9e4e01400e0ca3ca","datavalue":{"value":{"amount":"+0.8709179","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1066866$24C4A537-DE0B-4727-B46F-0D9E289A37B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cec02cd8de6f99cf22ef1f0f503f7f1a06cac239","datavalue":{"value":{"entity-type":"item","numeric-id":1180632,"id":"Q1180632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"906dc972c0b228e16a73818ab29ef0131874746c","datavalue":{"value":{"amount":"+0.86667174","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1066866$8B0E294A-8446-4C81-8EAB-54F304695489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5918473e6984cd41d9dac108a33dd5b556855f96","datavalue":{"value":{"entity-type":"item","numeric-id":636310,"id":"Q636310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a75a4055e577717f4835eb08ff86f66a3dd9ceb","datavalue":{"value":{"amount":"+0.86259294","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1066866$50EDD4B1-1CD9-4B67-99DF-B20ABDB79EA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b105c28342569f9d86dab6baf90faafa40f77c80","datavalue":{"value":{"entity-type":"item","numeric-id":1953245,"id":"Q1953245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a5c765aead0b95cbdf8273ab5ef4398cc50ec60","datavalue":{"value":{"amount":"+0.85926235","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1066866$A87B64CF-AEE8-44BE-930E-CDDA57CF45ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"300036f39badec008165dd06011e8325085930e7","datavalue":{"value":{"entity-type":"item","numeric-id":3744217,"id":"Q3744217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6b750031a188d1311abfa353aab5ec2ae733651","datavalue":{"value":{"amount":"+0.8550665","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1066866$A82B9BF4-7F37-4637-A6DB-40F9D1C2FEA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ecd5b5dc13ddedbbc22d19e66c3d6eda3d766803","datavalue":{"value":{"entity-type":"item","numeric-id":2702139,"id":"Q2702139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d1e5f7df31d3faebe25ce3e007c11e58a642393","datavalue":{"value":{"amount":"+0.85091424","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1066866$C0E079E9-6079-4A58-AF18-0C0FABBA6009","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of slice functions","badges":[]}}}}}