{"entities":{"Q1095871":{"pageid":1106623,"ns":120,"title":"Item:Q1095871","lastrevid":66679935,"modified":"2026-04-12T11:52:35Z","type":"item","id":"Q1095871","labels":{"en":{"language":"en","value":"Lower bounds on the size of bounded depth circuits over a complete basis with logical addition"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4029460"}},"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":"Q1095871$71F82DB0-BC8A-41D2-9B69-B8610A908953","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7eb22efd98d61f9d469f2df051d18feef7bf3b6c","datavalue":{"value":{"text":"Lower bounds on the size of bounded depth circuits over a complete basis with logical addition","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1095871$6A8715BF-D279-4841-8AF7-8E1597067D69","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"95720e923a9fde9bdf335955abf5a00ab5f66f01","datavalue":{"value":"0632.94030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095871$4E255A13-50E0-4760-A42B-B08F6CE27245","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cfd4633da6764a436460722c0ca1be5d9895fce6","datavalue":{"value":"10.1007/BF01137685","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095871$E5DEFC4B-8475-4EC2-859E-FE3FD0720185","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"00de3e6b6cfff0576fe0e1d6bc63c05579d2cb43","datavalue":{"value":{"entity-type":"item","numeric-id":173953,"id":"Q173953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095871$7D1FDCF6-1C55-42B6-847B-C9309DFFF1E9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1095871$3D46CF1D-74CD-4B36-AD9A-25B6E11B54A2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"371249dfeebf3c14c23b00e486cf240b6cd23fb0","datavalue":{"value":"Lower bounds for bounded depth circuits over \\(\\{\\) \\&,\\(\\vee,\\oplus \\}\\) are given using a special structure of families of Boolean functions called regular models. The construction of bounded degree is described. These models are then used to deduce exponential lower bounds in the basis \\(\\{\\) \\&,\\(\\oplus \\}\\), and it is shown that they also hold in the basis \\(\\{\\) \\&,\\(\\vee,\\oplus \\}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095871$058FBDBA-5325-4228-AFFA-41C90383DE41","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095871$5965AC03-63B3-44C4-B13E-61BC8E6F4B05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095871$8C73D1C0-2434-4631-B535-FC5486F4575D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d4f06e8a31611e550dd9c5cc38faca730a3c4d71","datavalue":{"value":"4029460","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095871$FFCA3B11-A7D4-4714-A88A-69A418DC7E6F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddf32c59a20ef404a25c50fc3c4e2d5b5ad42d75","datavalue":{"value":"circuit complexity of Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095871$33059B44-82E0-4097-94AC-1FCA7FCC5ED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ccaa38602274406841b760836939033250e916a","datavalue":{"value":"bounded depth circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095871$229E8116-9613-4AF5-9000-6D4D57B2A595","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f5d5c403c7f175c3df49bd436848c46eef41188","datavalue":{"value":"regular models","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095871$362A347D-E539-4D7A-998F-464E78B863A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb539388cb15cc8716b894ca26cb723f56f9ba4f","datavalue":{"value":"exponential lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095871$35BA2843-47FF-4635-AF7F-3B5D4BC160A4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c0bcfb4eb9a7ab6903b269f394ffde6834d9319","datavalue":{"value":{"entity-type":"item","numeric-id":1370854,"id":"Q1370854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095871$C774B4B4-046D-4FB8-8DF5-2D83A25A87A6","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":"Q1095871$8181B067-029B-490C-87ED-A46566D01C5C","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":"Q1095871$D315E0E9-7123-4339-89A6-C8D5C0B2B4CB","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"8678bc741f169ad802a4c5ebcb40ec06332314cf","datavalue":{"value":"Q29042011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095871$DA01CA01-6FD5-4288-BF44-1A9D34EE6AF0","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":"Q1095871$58C41272-1DDC-4F27-9774-110125BC21A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e39951d487d3bf563c62341ed381ea5be4f484","datavalue":{"value":{"entity-type":"item","numeric-id":3318683,"id":"Q3318683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095871$FAF98581-2066-482C-A07B-38F9976BE3CC","rank":"normal"},{"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":"Q1095871$B17A66AC-0A2C-417F-AEF4-A7ABFFA0704A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0942c3ffeac8339c20eccc6667aba9b8af08cc5f","datavalue":{"value":{"entity-type":"item","numeric-id":3758729,"id":"Q3758729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095871$E84A157B-6540-447C-B649-8549732E4177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce25b6e3a78e9a3f320205259f9976f9eabd886a","datavalue":{"value":{"entity-type":"item","numeric-id":4726174,"id":"Q4726174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095871$0AE5328D-3DEA-42D9-9DE6-7C452F55B76A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2ca04c59b1468ff9eb03a30febcf55d98359908","datavalue":{"value":{"entity-type":"item","numeric-id":1094870,"id":"Q1094870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095871$FE7586F2-79CB-494F-8959-70EDFD72842A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82f0958994907d9d0238749004a52b6fb840c4b8","datavalue":{"value":{"entity-type":"item","numeric-id":4724549,"id":"Q4724549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095871$B29E29F7-1032-42E7-BD97-5C3476EDE795","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"afb1066df79f2bfbc2943af890d673a6bcb701d9","datavalue":{"value":"https://doi.org/10.1007/bf01137685","type":"string"},"datatype":"url"},"type":"statement","id":"Q1095871$76483FAB-683F-4202-A902-320723828166","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b49437f2b3aab97e84c5fbd1c21dc7a3fefd0137","datavalue":{"value":"W2009994177","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095871$B0A0261F-8C49-4D2B-95DA-7A84ACA2F688","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e41e1247f0fd833b7501690ce913d36d9b9bb8d1","datavalue":{"value":{"entity-type":"item","numeric-id":413295,"id":"Q413295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eabf483490db3ac1705d7460ef981b5ceae0443d","datavalue":{"value":{"amount":"+0.8184471130371094","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":"Q1095871$8B62CEF7-4597-4724-9951-3162C6E5BEB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e112ffa0cc7d7e08c958e91be14dfb2115c8a0a6","datavalue":{"value":{"entity-type":"item","numeric-id":3503631,"id":"Q3503631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"764c345fa4b7677405916bee6ab3b83290db59b4","datavalue":{"value":{"amount":"+0.8149059414863586","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":"Q1095871$F51ADBDB-EAF4-4273-A5F1-C43BB21AD5AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"145f7cceb45815bc761af49b2e607198c63d3f49","datavalue":{"value":{"entity-type":"item","numeric-id":4526973,"id":"Q4526973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04a9f018c272713a8e6bdcd66899d058e8d7740d","datavalue":{"value":{"amount":"+0.8037129640579224","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":"Q1095871$C610B9A7-832E-408D-9B9E-91576E546145","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d497d15e07e2674e31b6c5f985e7d2011b720817","datavalue":{"value":{"entity-type":"item","numeric-id":1377575,"id":"Q1377575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d27e13de0f18f1df17aacd34764a636031c18907","datavalue":{"value":{"amount":"+0.8020143508911133","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":"Q1095871$B21944C9-22C0-4A6B-B4BB-CA4A564C28C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc8ab1c634003262bb1947e44e47882b2a4cdc40","datavalue":{"value":{"entity-type":"item","numeric-id":1327392,"id":"Q1327392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"480aa281257d83c92859de9b0eeecc269eadc387","datavalue":{"value":{"amount":"+0.7989888191223145","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":"Q1095871$8EB711B3-6746-465E-A3E6-DA47ECC3189F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bounds on the size of bounded depth circuits over a complete basis with logical addition","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lower_bounds_on_the_size_of_bounded_depth_circuits_over_a_complete_basis_with_logical_addition"}}}}}