{"entities":{"Q2638784":{"pageid":2649527,"ns":120,"title":"Item:Q2638784","lastrevid":49453498,"modified":"2026-01-07T04:42:28Z","type":"item","id":"Q2638784","labels":{"en":{"language":"en","value":"Applications of matrix methods to the theory of lower bounds in computational complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4182827"}},"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":"Q2638784$8895D594-C285-463A-B1DA-9FDB4A12BFB8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c2ed645ba6c71c5488dff36e94f296cc84e3729d","datavalue":{"value":{"text":"Applications of matrix methods to the theory of lower bounds in computational complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2638784$A6C9F65D-25B2-42F6-BC1C-BA4DAC829DA8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2d942db267d41f6eb7fc6ae3290cca67bc3c807b","datavalue":{"value":"0717.68049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638784$7AED5466-4DCD-4D96-83CD-F839071BEDC4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"42b30b9a0f5afaef81d83f7c98e071630a21f380","datavalue":{"value":"10.1007/BF02122698","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638784$ECC210FC-316B-48BB-82AE-692987BEC608","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":"Q2638784$88F3594C-27D1-4D98-AA2A-112BB67D2C49","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638784$42003C90-7BDC-4041-8615-65413B36D3C5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q2638784$F28B9AC7-255D-4DBE-9ED4-604EE10A7205","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8456778e3a9db2535cae4ed13f699fbe24cfef52","datavalue":{"value":"One of the hardest tasks of the complexity theory is to discover some combinatorial or algebraic properties of Boolean functions which would imply high complexity in interesting computing models. A contribution in this direction is made here by proving nonpolynomial lower bound on the monotone formula size for the function ``minimum cover''. Nonpolynomial lower bounds for monotone complexity were already known, and so the main contribution of this paper is in the presentation of new, essential simpler methods than the previous ones for this task. Some connections between this method on one side, and communication complexity for VLSI and graph complexity on other side are also shown.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2638784$A7C35A7F-BADF-4C7D-8249-96C8262CAF6B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638784$36889EBD-F517-41ED-8DCF-4D3D58EB9300","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638784$E312D9C4-967E-409D-9DB1-3F78FE6A7D85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638784$E26965F7-39D6-4700-A753-DECDFB93741C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638784$C54F6FE1-9FC3-4A25-ABD1-1CB9D114A559","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"921bd752b8034096ea9312cd61779491276670a0","datavalue":{"value":"4182827","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638784$18041033-E0D4-4283-B6F4-1AE98FC5A6C9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q2638784$9F3BA9B8-B7C8-4D83-9936-BCCE1BEA9966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb5a830579b475e59eaac799be7398a9142f423b","datavalue":{"value":"Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2638784$EEDC5EFE-C7C9-45FA-BA51-5319E65F2191","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c584c6597af95afe07683013418dc4c91500351c","datavalue":{"value":"monotone formula","type":"string"},"datatype":"string"},"type":"statement","id":"Q2638784$54BDE4FE-BDC9-4E93-95C6-2E4058A6966F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d59f9270ba2c0b3161162dab212fcc774a42eba","datavalue":{"value":"communication complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2638784$D8744AC2-0D0A-4939-81F7-8017EACC8914","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"633fdcabf2e644e3cc3929da0924cb1d112f41ed","datavalue":{"value":{"entity-type":"item","numeric-id":208754,"id":"Q208754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638784$29379772-8B0C-417D-8B76-0D0C5EF17554","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":"Q2638784$A1BFB0DF-9545-49DC-A10E-8702846E49A6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e2c59f623961c0546ef9ca9945d77ef79c3bac2","datavalue":{"value":{"entity-type":"item","numeric-id":4109656,"id":"Q4109656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638784$434F8492-203F-4A1E-83EF-02018AFF1DE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52ff54b18fa1fec0697ec7172157585af96a73e7","datavalue":{"value":{"entity-type":"item","numeric-id":3091953,"id":"Q3091953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638784$A5D0A16F-9F35-49AC-89B3-EDE27CBA7F24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6f38ff966350be19068835b6a1502cc0a672c99","datavalue":{"value":{"entity-type":"item","numeric-id":3506242,"id":"Q3506242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638784$1F221686-BDD9-4E43-9D39-1F5117C5C476","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":"Q2638784$39FDB323-DFE1-4F23-94C7-A9D739714313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a6b13b2ba37a9810801d8784e6422607a5338cc","datavalue":{"value":{"entity-type":"item","numeric-id":4745254,"id":"Q4745254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638784$B0370D88-8089-48ED-BE23-7C450E8ED8B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ad1714db201637d748b47ebbaf99f9008bc5160","datavalue":{"value":{"entity-type":"item","numeric-id":3472058,"id":"Q3472058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638784$83B248F7-EC2A-4DF8-8390-138C2A0ED959","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"593629de5e6afa07f2b6cd56c6209f7ab13aa5e3","datavalue":{"value":{"entity-type":"item","numeric-id":5522940,"id":"Q5522940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638784$A9B886A2-9432-4C8F-BBDB-9412F516EEE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b2e8fdbd72d4413672bdc0a2c0dcc9057a5f41e","datavalue":{"value":{"entity-type":"item","numeric-id":1813126,"id":"Q1813126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638784$9EACD209-DF06-4AAB-875A-9A28704F2ABF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f08aea2375da56a8a7d87cd0bcc8ed91b9c89ac9","datavalue":{"value":{"entity-type":"item","numeric-id":1835900,"id":"Q1835900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638784$A57FD758-D012-426D-A857-39E5F766342D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f4350da757290e3feaf32a96ac3ed4770c69cd26","datavalue":{"value":"https://doi.org/10.1007/bf02122698","type":"string"},"datatype":"url"},"type":"statement","id":"Q2638784$6A339724-28BC-45BA-95DA-2AA2466FE638","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aeda74e01df0776a9fa56202cf0ede804ed888ee","datavalue":{"value":"W1995365759","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638784$C4A1298B-ED49-41BB-A05E-F909E9D744F9","rank":"normal"}],"P1643":[{"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":"35b237422121f1a0cde095bb8825670d69d23056","datavalue":{"value":{"amount":"+0.814669132232666","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":"Q2638784$5D77A112-A898-4A35-8437-FBD93A13FCE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec19861ef37ec865bde58c6e39faa1926c17f7f3","datavalue":{"value":{"entity-type":"item","numeric-id":4036701,"id":"Q4036701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6cb7454efd3e6cc31b43586b40836b24a90a062","datavalue":{"value":{"amount":"+0.8004358410835266","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":"Q2638784$B6EB5EB7-B2F0-4636-BABB-BCCAC2603166","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":"b6cb7454efd3e6cc31b43586b40836b24a90a062","datavalue":{"value":{"amount":"+0.8004358410835266","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":"Q2638784$BCDA8065-9D22-4BBB-99B0-069634E84142","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8363279776e211ffc95505756c80e7156a3934fb","datavalue":{"value":{"entity-type":"item","numeric-id":3822100,"id":"Q3822100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ec4c1544c83aa02b7602e6aabebfbd8e886eb3f","datavalue":{"value":{"amount":"+0.7932111024856567","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":"Q2638784$B49D3671-D79E-41D9-9295-8F163533EA8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0074d3e1482d2291b46ba2d08f3e736061ae14f7","datavalue":{"value":{"entity-type":"item","numeric-id":4029623,"id":"Q4029623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33376f0f9577e0ec4cfb485b4ffd0f779ae966ff","datavalue":{"value":{"amount":"+0.7903434634208679","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":"Q2638784$935DCE0E-C476-4F72-991C-2731B94D31C1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2638784","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2638784"}}}}}