{"entities":{"Q1977413":{"pageid":1988155,"ns":120,"title":"Item:Q1977413","lastrevid":71201205,"modified":"2026-04-13T20:22:43Z","type":"item","id":"Q1977413","labels":{"en":{"language":"en","value":"Superpolynomial lower bounds for monotone span programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1446737"}},"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":"Q1977413$90641A51-0F1D-458E-A703-6D174400FB1C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"08fb9113eab6d58f974f7a7cb90411150483dedd","datavalue":{"value":{"text":"Superpolynomial lower bounds for monotone span programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1977413$9303AF41-86CF-4441-8932-D48A03799B62","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0e68472d92e34019627abfb538b7a1841bb235e3","datavalue":{"value":"0990.68077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1977413$91A08235-EB5A-4E3F-99D7-D5C2B93CAAA8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cb810284579fca70d13987c395247bb8f287f16c","datavalue":{"value":{"entity-type":"item","numeric-id":196035,"id":"Q196035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1977413$A3395CD6-FD3D-4837-B1F0-38A4AA1F9C1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9af34c68de603f5df190f791003241dc07c602c6","datavalue":{"value":{"entity-type":"item","numeric-id":247136,"id":"Q247136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1977413$D0C7126B-9A9A-4215-88D0-030FDF195028","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a028a6348dcfc7b43c17e257a75b67ed9a2b7db","datavalue":{"value":{"entity-type":"item","numeric-id":178716,"id":"Q178716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1977413$CD7DB54A-1D9B-432B-91E1-99A3CB96E3FC","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":"Q1977413$4C772235-94AD-4FB6-8136-8C65B3236AAA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b45badacdf195d066b770e2f5edfdcc6faaa5c05","datavalue":{"value":{"time":"+2000-05-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1977413$42B93E9A-F7CF-4334-8DA6-56778429FB7F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"47a3dd1f3d565e86bbc1b20d34a347cd56486e28","datavalue":{"value":"Span programs are a linear algebraic model for computing Boolean functions. A span program consists of a vector \\(w \\neq 0\\) in a linear space and of \\(2n\\) linear subspaces associated to the set of \\(n\\) variables \\(x_1, \\ldots, x_n\\) and to their negations. The program defines a Boolean function \\(f(x_1, \\ldots, x_n)\\) by \\(f(\\alpha_1, \\ldots, \\alpha_n) = 1\\) exactly when \\(w\\) belongs to the span of the subspaces associated to \\(\\alpha_1, \\ldots, \\alpha_n\\) in the natural way. A span program is monotone if the subspaces associated to the negated variables are all equal to the null subspace. The size of a span program is the sum of the dimensions of the subspaces associated to literals. The main result shows that there is a family of monotone Boolean functions \\(\\{f_n\\}\\), \\(f_n\\) having \\(n\\) variables and computable in NP, that requires monotone span programs of size at least \\(n^{\\Omega(\\log n / \\log \\log n)}.\\) The proof is based on an analysis of Paley-type bipartite graphs via Weil character sum estimates.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1977413$FB121462-6BAD-4D32-8AAB-6451C2D5FBFB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1977413$6400CE01-87EE-4838-9163-1F01EFD72B3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1977413$3C79570A-388B-4C98-AEE2-F76F056168B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9bd9af688c0b97c53a0660570659cd00420d9c9b","datavalue":{"value":"05D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1977413$52AA94BE-1894-4510-959B-D1F1AD978090","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1977413$E278D088-FFD9-469B-B324-0045042C5787","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b0a9f7f7ed1de01e9a756b73760e1774102a0dd0","datavalue":{"value":"1446737","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1977413$991EF62C-8AC6-406A-B10A-95085F571643","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb5a830579b475e59eaac799be7398a9142f423b","datavalue":{"value":"Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1977413$B2F15415-97FF-43B0-A226-82FDC15613A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1977413$E3CEE802-75DD-425E-ADC0-E8BC7EDAB1BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0557d552fd0b504894dac18da34f597b8fece7d2","datavalue":{"value":"span programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1977413$DE1D65CA-16D2-43E0-93C6-14C74B64762C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2fc8522c6547fe483c0d1ae4eec1b8d9306e5db1","datavalue":{"value":{"entity-type":"item","numeric-id":290243,"id":"Q290243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1977413$7F6B81E0-EB29-42CD-8A9B-8128305FC960","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":"Q1977413$74B14705-2FA2-40F7-8379-CA761099AF72","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7cf682c5bf0de4d87c7270e2c09df5e3b5aeef07","datavalue":{"value":"https://doi.org/10.1007/s004930050058","type":"string"},"datatype":"url"},"type":"statement","id":"Q1977413$5C3A9DCE-5892-45A6-B310-1A323BE06CF6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9c603b6bd27d292b0e70958677ae13e161fe9ace","datavalue":{"value":"W2571456248","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1977413$2633B53A-0641-48DE-A30E-A34B6B14D95B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"82f644c620a6951293384d1adc5baa9b666e3a18","datavalue":{"value":"10.1007/S004930050058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1977413$95E6EE7D-828E-44CC-86B1-D5B8A750B057","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b42f0fb455986cb374c97c6c9016eb4600e0bcb","datavalue":{"value":{"entity-type":"item","numeric-id":677989,"id":"Q677989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bd3d4b694addcbb342d4cd0106f16d0e7bb3a93","datavalue":{"value":{"amount":"+0.9445411","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1977413$FC11A7AC-9446-4CDC-988A-A65075849ABA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"425d2bb3d10386678b3cdb58c2a2a5065c3e3e50","datavalue":{"value":{"entity-type":"item","numeric-id":4228516,"id":"Q4228516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47c5f92a4022498abf7855756bd00337adbbf32e","datavalue":{"value":{"amount":"+0.93210745","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1977413$54123005-3B23-4396-B5DD-163346BBBB8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1b5669d0206ec53f127956f63295cbba76be658","datavalue":{"value":{"entity-type":"item","numeric-id":5491703,"id":"Q5491703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"859467df51878067a2d11032ba014f3fa1002f18","datavalue":{"value":{"amount":"+0.89751655","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1977413$CFFC573B-8D0E-4BA3-93F6-190AC3BF7434","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"536f136ee76183bbf799e3b06b12c44a2dd52b20","datavalue":{"value":{"entity-type":"item","numeric-id":1405737,"id":"Q1405737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e52154d244fe26bebdcc685dbf6efec454aad0a1","datavalue":{"value":{"amount":"+0.8879245","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1977413$7FF859B9-702F-4B36-B7DD-1422A7DD81EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21ba1d97681d00c074fdf4c304d05eebf8870a41","datavalue":{"value":{"entity-type":"item","numeric-id":4542561,"id":"Q4542561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd1281a4c3149ea98f8144a4aaab6ac207863c58","datavalue":{"value":{"amount":"+0.88792443","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1977413$97AFD4BC-07B1-4648-AFB8-7E82FDBDB5B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e07fe4fb03f4242993c1355d09814befc6b11df2","datavalue":{"value":{"entity-type":"item","numeric-id":3569022,"id":"Q3569022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80fe92db9f0514a6623d1428c046eb115091d8a4","datavalue":{"value":{"amount":"+0.8673439","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1977413$CB612CA4-8337-47CC-85DB-76C6E394D815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc02c8ba741ea2362ada024b90354aa33f5078e4","datavalue":{"value":{"entity-type":"item","numeric-id":2885641,"id":"Q2885641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4c6005920e0d67ec465c4b566542c413432a452","datavalue":{"value":{"amount":"+0.8605135","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1977413$8D6C171F-46B0-4C25-985B-082BAAE47001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab3fa293a6b4469f25952f5f23b61e461d6061e7","datavalue":{"value":{"entity-type":"item","numeric-id":4926982,"id":"Q4926982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a35eeddff59d3feaecda09d1e5aae7500bdd2a27","datavalue":{"value":{"amount":"+0.8594081","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1977413$D7081B91-E699-4D11-BEA1-B86554AB4290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f38d7fad026b6451616bf3a4759e564a558eb6a","datavalue":{"value":{"entity-type":"item","numeric-id":5317192,"id":"Q5317192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7166b84072dea67c3f439d355f850a7a82b0ddd2","datavalue":{"value":{"amount":"+0.85796094","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1977413$C9B5BF35-C0DA-45C5-80E6-DE89D9D7709A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d884dc3410b75eeab7c4645cf680c45a767a0ef1","datavalue":{"value":{"entity-type":"item","numeric-id":1894446,"id":"Q1894446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"406d61b72a7f9b7e21c2451b544e9ffde04854fc","datavalue":{"value":{"amount":"+0.84733903","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1977413$736CD3CF-6B8C-45DF-B704-5FB5F468461B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Superpolynomial lower bounds for monotone span programs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Superpolynomial_lower_bounds_for_monotone_span_programs"}}}}}