{"entities":{"Q1068792":{"pageid":1079544,"ns":120,"title":"Item:Q1068792","lastrevid":66076635,"modified":"2026-04-12T07:22:50Z","type":"item","id":"Q1068792","labels":{"en":{"language":"en","value":"Linear lower bounds on unbounded fan-in Boolean circuits"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3930902"}},"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":"Q1068792$4637254D-58AB-44F6-A5D4-4692716E341E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f2d36484adff6bffea69ca9d21551505333efe0a","datavalue":{"value":{"text":"Linear lower bounds on unbounded fan-in Boolean circuits","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1068792$11833D33-5BE9-4233-A24A-C64C92D8B8E3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8c0cf6a7b618da9217ea1560e197e5d88d7aff8b","datavalue":{"value":"0581.94026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068792$190E42C8-FE68-4B0C-97CE-BC8711FC5540","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"214927cb6c30443cca6c4aba5980b45553aa4a81","datavalue":{"value":"10.1016/0020-0190(85)90035-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068792$594B4367-DEEF-4FF6-B1F6-283DA032AFB6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7330faa8aa9bfbfa602624605066aa6301d76b4","datavalue":{"value":{"entity-type":"item","numeric-id":208754,"id":"Q208754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068792$5E2349C3-D049-42B9-98CF-B13DA3448E00","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068792$8BAE3947-FA00-4ED5-AB6F-6FC86763FA36","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":"Q1068792$F84FB11E-96AA-44EA-BD0E-11556F17BFE7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3e42e611a9918220713abcaef9efe1a230184494","datavalue":{"value":"A computing model called CA-circuit is introduced as a generalisation of the unbounded fan-in Boolean circuit. Defining the communication complexity of CA-circuits a method for proving lower bounds on the number of gates in CA-circuits is obtained. The use of the method is presented to establish linear lower bounds for specific Boolean functions. It is proved that the communication complexity of CA-circuits is a special case of the communication complexity for VLSI, i.e. that the communication complexity of VLSI circuits provides lower bounds on the communication complexity of CA-circuits. A Boolean function with zero VLSI communication complexity and linear CA-circuit communication complexity is shown.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068792$8DBFF478-DD1B-46C2-8B65-B3A2D236694F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068792$0D2849BB-51A8-42BA-8E6F-A76674CD3FAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068792$D21F8C4E-F080-4E2B-885E-77B51F658EB3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b3ba2c0bb4bfbf01f6b1b758c55f43f8a85958f0","datavalue":{"value":"3930902","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068792$C25FD56A-412F-4160-AC9B-551CCCD3B873","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f25e35fc42cf13b8289b2fa1c7d8b546d4d2ade8","datavalue":{"value":"combinational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068792$20331238-066E-4CDC-A1C1-06A6B6372129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f09a9e0d3de3a267c9898b12f8aba769bc6a42e5","datavalue":{"value":"CA-circuit","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068792$B4C928B0-9E09-4DB6-ACE2-972979DE170A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd19784719617bcd2be9dde753435f29e8b75967","datavalue":{"value":"unbounded fan-in Boolean circuit","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068792$6E387D5D-59FF-4F7D-B696-47BAC675BEC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d59f9270ba2c0b3161162dab212fcc774a42eba","datavalue":{"value":"communication complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068792$04140A47-8A10-4215-94AB-D5B6546A197E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a1efedced75f5cd34615bfcd0a1968bc968a9c0","datavalue":{"value":"lower bounds on the number of gates","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068792$1823454E-9646-40FB-A9C1-2B32347FFBE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb5a830579b475e59eaac799be7398a9142f423b","datavalue":{"value":"Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068792$E19EBB73-CD11-4510-AA6A-492836233EB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25df60e3c85cd7cb604ca83b5557e00756af12cd","datavalue":{"value":"VLSI circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068792$3B425481-06FC-4D5F-ADCF-5222E2FC67B1","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":"Q1068792$1DCE5B23-C469-4177-BBA0-996B7AE616CB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f02a6ff5d500c7db6561d82d20ca3786b4f148f2","datavalue":{"value":"https://doi.org/10.1016/0020-0190(85)90035-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1068792$9472997D-E63F-4207-A06C-09EE86306F36","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5a606439337b9a40f2a4054b0a259f66b41a6ffc","datavalue":{"value":"W2047621224","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068792$F4EF0533-9639-42CC-BA3E-1EEF29558615","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"58af9a438ca79f17e01d4568050919b82873e432","datavalue":{"value":{"entity-type":"item","numeric-id":794625,"id":"Q794625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068792$4096F023-B4C4-451C-9D88-4699108194A1","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":"Q1068792$E4E4687C-AD2B-47CD-B0CE-7BF8966309EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"192d335ebbfcbbb2526f892a6a15d14342e5ba9d","datavalue":{"value":{"entity-type":"item","numeric-id":1223937,"id":"Q1223937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068792$122C3D54-227F-4718-8011-FE411F857C40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ae4a9af94926badf70eb2cf7639fa06896d4e4b","datavalue":{"value":{"entity-type":"item","numeric-id":3216143,"id":"Q3216143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068792$D9F7191B-5F03-4998-A0F4-4C541BD05CD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a85d4b204b5b0ba9ab5c4d608875f21b39557902","datavalue":{"value":{"entity-type":"item","numeric-id":3768423,"id":"Q3768423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068792$55143B15-7FE1-4729-B974-8B310BA339C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cff99543aad71165c9e3d4313856d67b3143372f","datavalue":{"value":{"entity-type":"item","numeric-id":3288996,"id":"Q3288996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068792$CD03DC89-1D2E-438F-B237-7B77D02E925C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e266c332c8c722703a0d32ad33eb1d65fa4f734","datavalue":{"value":{"entity-type":"item","numeric-id":4131019,"id":"Q4131019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068792$9E68580A-A0BA-4A1E-96B8-7ADA793C34E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0be07caf9e848c641ba91e5af6add50499139e44","datavalue":{"value":{"entity-type":"item","numeric-id":5684582,"id":"Q5684582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068792$9C63A396-F154-4CC5-BFEA-412244134169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6036bf43f265b8908f5fed788c1a5dda8ab233cc","datavalue":{"value":{"entity-type":"item","numeric-id":1220384,"id":"Q1220384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068792$8B523B2D-675F-4F01-B830-1EF4F0B30022","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fab0be9a740208b5992a5b6d794dacd40f808511","datavalue":{"value":{"entity-type":"item","numeric-id":1142030,"id":"Q1142030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068792$D7AE1284-8AA9-4B92-A251-DA6E7A5EAD0F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"444d4cb400728564c7c9faa9955e58883a2a6076","datavalue":{"value":{"entity-type":"item","numeric-id":3829071,"id":"Q3829071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"362f9fb4548606303984173829f3843b3cecdf39","datavalue":{"value":{"amount":"+0.8233019113540649","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":"Q1068792$2547CCB1-BFC1-4D73-8518-47FF31201004","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"555a0085722890333b271dc67fe7bb64cc6aed26","datavalue":{"value":{"entity-type":"item","numeric-id":1193877,"id":"Q1193877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"576b01b4c471a087348f76ecf2cb01547120187a","datavalue":{"value":{"amount":"+0.816339373588562","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":"Q1068792$EFE77052-3D4A-45FB-9267-D5C7135A1E6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2839174df485bef22affe5e188f6aacb7159a779","datavalue":{"value":{"entity-type":"item","numeric-id":1104301,"id":"Q1104301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c67b315fbb19a742582c103c75417cde285df843","datavalue":{"value":{"amount":"+0.810309886932373","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":"Q1068792$AD40F864-596C-475C-9CEE-DB8A8FA8D4C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"448854d0473ecd5e32b0c0d014cd145d396d8990","datavalue":{"value":{"entity-type":"item","numeric-id":4337605,"id":"Q4337605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75ac899edad119132731e73d845350355d5e3bf0","datavalue":{"value":{"amount":"+0.791871190071106","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":"Q1068792$E321DF91-9786-44A9-9E98-D6EF471A4344","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"058b5a0b26b354b27a2d9077d2cc0178360b0140","datavalue":{"value":{"entity-type":"item","numeric-id":3225912,"id":"Q3225912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75ac899edad119132731e73d845350355d5e3bf0","datavalue":{"value":{"amount":"+0.791871190071106","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":"Q1068792$E7A9C400-D60C-47A2-9C50-6B3D00FB0B36","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Linear lower bounds on unbounded fan-in Boolean circuits","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Linear_lower_bounds_on_unbounded_fan-in_Boolean_circuits"}}}}}