{"entities":{"Q4036701":{"pageid":6066419,"ns":120,"title":"Item:Q4036701","lastrevid":108772697,"modified":"2026-11-10T05:39:36Z","type":"item","id":"Q4036701","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 176870"}},"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":"Q4036701$1F4955CF-8926-40A6-9B50-ED623CA272BB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"010769421e67ec6d8edf8595cff62c6455b7e3de","datavalue":{"value":"0770.68073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4036701$7B3D61B6-4F46-4D61-876B-CB1DED7EE169","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"abd8d5e490ea4daf6d00f9dd2f897565e059b6cc","datavalue":{"value":{"time":"+1993-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4036701$AFF88125-BEB9-4C58-921C-1FC9631E2406","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4036701$54BE31C1-11AE-46BC-9582-37497475CBAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4036701$368AF9B9-F321-44EB-9E1E-79D80D7E46A0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bff1b98d22753de36969ec240157ab35dedd72d8","datavalue":{"value":"176870","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4036701$D77BE41D-70C9-4616-BF33-2EFDC38FBE5A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e54c3b818fb22dae19db360e7abf74ff6422001","datavalue":{"value":"lower bounds on complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4036701$1E453BCE-969A-457B-9212-5483B7AE1783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c2773dc0449ebf96bb1747bc4f2b2f0a2faa889","datavalue":{"value":"circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q4036701$D35B12E2-92A2-45D5-B07D-8221A3E92119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb5a830579b475e59eaac799be7398a9142f423b","datavalue":{"value":"Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q4036701$52EBB99C-7537-4FED-8796-8AA65A1F2947","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":"Q4036701$621C19C9-DD9E-49D1-9BDD-44F1F0202F50","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":"Q4036701$4723371C-012C-40A6-B3D1-929FBA6C39BE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d32fb592ac6359c6294580b99c3dc7b920afabb","datavalue":{"value":{"entity-type":"item","numeric-id":3786412,"id":"Q3786412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f93994109f60998e0c415bc92953ec5a0a94c61","datavalue":{"value":{"amount":"+0.8533164858818054","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":"Q4036701$72C42876-1201-4C9B-ABA9-3B58519CD16D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b5aece2e1829009f5d8050d27aec6d6866ec830","datavalue":{"value":{"entity-type":"item","numeric-id":3496294,"id":"Q3496294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"087890b529f72f0199b9cac86631f8febc5389b0","datavalue":{"value":{"amount":"+0.8332371115684509","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":"Q4036701$9F594517-1761-4CFC-AC04-583186247537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"809a1a994c93dfd0c8821bac90be655ec382bab3","datavalue":{"value":{"entity-type":"item","numeric-id":3356246,"id":"Q3356246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea9c584a50397c3c5d3362ddaf01562d80c37513","datavalue":{"value":{"amount":"+0.8224701881408691","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":"Q4036701$9975340F-FE02-4951-B4C6-212CD4CBAD23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a63c85571ec1de4afc57a1cb7c3b5eb9a062c47","datavalue":{"value":{"entity-type":"item","numeric-id":3335688,"id":"Q3335688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2af46c01ea45fae5e1fec540fcf137d7cc661e32","datavalue":{"value":{"amount":"+0.8202780485153198","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":"Q4036701$D427164A-BEE2-4462-99B9-349BA99C9901","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4165cdb5316f6e4ddb3f4394288b208b17a03f90","datavalue":{"value":{"entity-type":"item","numeric-id":3795613,"id":"Q3795613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63ece79c645307cc8553a3fd5c88f7f62cc9cf7d","datavalue":{"value":{"amount":"+0.8035019040107727","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":"Q4036701$B898A9AB-B145-4F7E-9D4F-B668BBACAA50","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"91a703daa9137ef3e0035d68461e333d1a76641c","datavalue":{"value":"[For the entire collection see Zbl 0754.00019.] The paper is devoted to the lower bound proof methods on the size of Boolean circuits computing specific Boolean functions. In recent years a big process has been done in obtaining superpolynomial lower bounds on the monotone formula and circuit size by the following three algebraic methods: (i) method of approximation introduced by \\textit{A. E. Andreev} in [Sov. Math. Dokl. 31, 530-534 (1985; Zbl 0616.94019)] and \\textit{A. A. Razborov} in [Sov. Math. Dokl. 31, 354-357 (1985; Zbl 0621.94027)]. (ii) method of communication complexity by \\textit{R. Raz} and \\textit{A. Wigderson} [Probabilistic communication complexity of Boolean relations. In: Proc. 30th IEEE FOCS, 562-567 (1989)], and (iii) method of matrix ranks introduced by \\textit{A. A. Razborov} [Combinatorica 10, No. 1, 81-93 (1990; Zbl 0717.68049)]. The author of the paper discusses the impossibility to extend these methods to yield nontrivial lower bounds for the size of circuits of formulae over a complete basis. The main contribution of the paper is the proof that the last method (iii) cannot help to get nonlinear lower bounds on Boolean circuits over the standard basis with negations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4036701$D0576F9D-ABB1-4CD8-88C1-4E80E184A42E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4036701","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4036701"}}}}}