{"entities":{"Q4651510":{"pageid":6681091,"ns":120,"title":"Item:Q4651510","lastrevid":40917372,"modified":"2025-04-14T03:25:00Z","type":"item","id":"Q4651510","labels":{"en":{"language":"en","value":"A Switching Lemma for Small Restrictions and Lower Bounds for <i>k</i>-DNF Resolution"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2135811"}},"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":"Q4651510$4AA71F06-54F9-48FB-BBB7-3E01E1BB4022","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c1feaedb789cb4368029d5a1303606f348d5ef78","datavalue":{"value":{"text":"A Switching Lemma for Small Restrictions and Lower Bounds for <i>k</i>-DNF Resolution","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4651510$1739176A-F66F-44FC-A521-0B96908DE5FF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c66844d3260657af3ec54630fcffc2b6d62e9f49","datavalue":{"value":"1059.03063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4651510$5E1ADFE9-48D3-4E8B-AFAE-5D8BFB99CAC9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f38a9256642a9092706fbcc7435ca0cd20ff18f6","datavalue":{"value":"10.1137/S0097539703428555","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4651510$2D9147E0-2F3F-4DC9-980C-83D67D8096F8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fbac5bdf278782adae560fc980adf418ea79c9ab","datavalue":{"value":{"entity-type":"item","numeric-id":835025,"id":"Q835025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4651510$AF637120-3D60-47B2-B204-9CF245B9FA2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"afbdf0b4b75e6a0dfd1ecc76c9480c04f5fced5d","datavalue":{"value":{"entity-type":"item","numeric-id":202088,"id":"Q202088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4651510$A98EAD05-C258-4001-A3DD-23951B794019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"556b5f897f5d545f04c26b56d4624f5cc4b2661a","datavalue":{"value":{"entity-type":"item","numeric-id":195654,"id":"Q195654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4651510$2D88E8F4-4D94-48BD-A6A1-F6438B5D455C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4651510$3C9676E2-2A08-4755-B938-472F255ABECF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"19c055e4721a86221dc4ad9a18f9249f030fc51e","datavalue":{"value":{"time":"+2005-02-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4651510$AB9D17C9-4A1D-4DCB-82C9-2DBB95EBF400","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4651510$5D684BE3-87AF-4767-ACAC-7FAC5689022A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4651510$758A80D6-9BB9-4D98-B802-398C1AF953F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4651510$B06A8B35-4ED0-4890-A958-448B237709DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"10eaeaf8bbf8231bbfc812aab8956e260b5a9f12","datavalue":{"value":"03B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4651510$B8915759-F5D2-41F4-99A9-71F3CAEDD6BC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"30b78164b37f1f8fede8d9bbc12c3b378a87ce63","datavalue":{"value":"2135811","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4651510$FA37FAB9-F7F6-416F-A13D-BE993ACE2608","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"beacc345177607df4ab1f59f0170626c9d1a1d90","datavalue":{"value":"propositional proof complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4651510$995D627F-A079-4AF9-9115-974E5633CD1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e5add04c87a634dc505636ede1198ff73b02459","datavalue":{"value":"Boolean circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4651510$446A8344-E60F-4799-89F3-49EF07AA7743","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"26d52f5697eb2fe43fc46e36416961b1cd6ad29a","datavalue":{"value":"switching lemmas","type":"string"},"datatype":"string"},"type":"statement","id":"Q4651510$59CF1C6A-93A5-4124-B15B-83B7BD145F39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q4651510$F5F9D7A1-3847-4608-92A0-48531016F66C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1be3365ef3cf49376f7259c3a1b2170340f8397c","datavalue":{"value":"\\(k\\)-DNFs","type":"string"},"datatype":"string"},"type":"statement","id":"Q4651510$CA49F713-7E51-432C-B388-B8EBFFAEBD33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfac5eb6431ec88e2a6e9bafbfcf7b49dda794fc","datavalue":{"value":"resolution","type":"string"},"datatype":"string"},"type":"statement","id":"Q4651510$F2257F30-EE33-4B09-9D85-FEA00AB1C260","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"232f16c1a18bfaacbb326bb04e984698454959c0","datavalue":{"value":"circuit bottom fan-in","type":"string"},"datatype":"string"},"type":"statement","id":"Q4651510$7080FA06-8E65-4AB7-A529-EDF7CEA56D64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"920af8f45483f1a41194bf795d211bc03120f78c","datavalue":{"value":"random restriction","type":"string"},"datatype":"string"},"type":"statement","id":"Q4651510$B9F7BCCD-2AA3-4AC9-B427-712DCFFA60A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e67689532ead8090f9f04338cefff71cb5f85aa","datavalue":{"value":"Sipser functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q4651510$E209BA7A-B11A-4DB3-86A1-1C99C19EC5F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"57ca29b7c8101f21f1460dd031a6105ac2bebcf6","datavalue":{"value":"weak pigeonhole principles","type":"string"},"datatype":"string"},"type":"statement","id":"Q4651510$076FEFF5-6335-4789-B81E-FAD2BB1FA1C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"688898b7f0914fbe5b8d434554ba271e0889e596","datavalue":{"value":"random CNFs","type":"string"},"datatype":"string"},"type":"statement","id":"Q4651510$7CADFF30-A4E7-423B-8649-5530D36E9935","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":"Q4651510$4FA82D66-D250-4E2A-BE85-42EDD32921C4","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"31a27dcc22673860d4ae1af22730ac36bdf63e6d","datavalue":{"value":"Q124811179","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4651510$4D4EDD61-BB1C-4A00-82E9-D5741E72F1B8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e114303ff8c734e15c6cadff0215009ea556a9c3","datavalue":{"value":"https://doi.org/10.1137/s0097539703428555","type":"string"},"datatype":"url"},"type":"statement","id":"Q4651510$4A640A55-79BF-4344-8C65-84C5D1F80113","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"99ea718a9a275997469c60c2f331ea26b19336f8","datavalue":{"value":"W2137423523","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4651510$98872716-A2AF-4CCC-99EA-455490974FE3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2558c3bef6958a5d94d31e4cfc3d3cc9a2447820","datavalue":{"value":{"entity-type":"item","numeric-id":1641156,"id":"Q1641156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbf87a95fb303f63253bb8b7533f0bf3bae2166e","datavalue":{"value":{"amount":"+0.8713863","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":"Q4651510$6A528876-9FB5-498C-8F94-8C2CBEAEEBC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a465ea8a42e8f148d2e3ffc6f2f752b0f2a86af","datavalue":{"value":{"entity-type":"item","numeric-id":3012839,"id":"Q3012839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d93ddbe4f2f8751f35a91f0d53e2554adb22044","datavalue":{"value":{"amount":"+0.8696513","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":"Q4651510$3C5570A7-B8EF-4613-A3D9-062FF812E23B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43120432db143149af899c1013cc0765039eb2e7","datavalue":{"value":{"entity-type":"item","numeric-id":2661357,"id":"Q2661357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bf53cb3ae155ccf6013648444aac6ec361ebb5e","datavalue":{"value":{"amount":"+0.83720887","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":"Q4651510$A6FDE4C6-6B80-4651-8E5A-9B8C22EDFD89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c50e84a990e45d0edfe1df165828e3129348a518","datavalue":{"value":{"entity-type":"item","numeric-id":894453,"id":"Q894453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0be3e8012ec3ed9b8c09b2255352c9bb7dc3be8a","datavalue":{"value":{"amount":"+0.833464","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":"Q4651510$19B6D768-F747-463F-A784-87D360635462","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a78201d52a3f3cab848022f18dc228640f3e9197","datavalue":{"value":{"entity-type":"item","numeric-id":430840,"id":"Q430840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"220c2330521bbf0cfa90dbcdad258f85c2541e57","datavalue":{"value":{"amount":"+0.8270508","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":"Q4651510$A89FF64A-F8D5-4F08-9E7B-62EFF5730E1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"228cdb1129359a07bee9efe732fbc38f86d1d646","datavalue":{"value":{"entity-type":"item","numeric-id":1885907,"id":"Q1885907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e690f8e3afc0a3cd48168a190293916753596a8","datavalue":{"value":{"amount":"+0.82655555","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":"Q4651510$8C6FB80E-385E-42C2-900B-8DA7B4A8B73A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf640427fcc7ba5fd3785dce25eaa4cb961ed9c7","datavalue":{"value":{"entity-type":"item","numeric-id":1923857,"id":"Q1923857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af904c9784966e840503ae61fb3a6edbba3af46b","datavalue":{"value":{"amount":"+0.8263865","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":"Q4651510$F188A8DB-EE2D-4DBF-B765-68F03B85CD1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8263e4ae225201125f19713d76a97d681a2d7e72","datavalue":{"value":{"entity-type":"item","numeric-id":5501765,"id":"Q5501765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77b4ad984fc8a1e8aefd51112a208e24f97e4184","datavalue":{"value":{"amount":"+0.8248496","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":"Q4651510$19FA08C7-5417-48B0-AD64-44A67494F57D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ecdafcdb55549a9ea4bdb51f06ac368c5d42c008","datavalue":{"value":{"entity-type":"item","numeric-id":1604210,"id":"Q1604210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"847832d771fbbd097434c3afed5909aa46c2da5b","datavalue":{"value":{"amount":"+0.82350683","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":"Q4651510$E8F27A0A-B0CD-4D7E-987C-5A9998506802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f485824cbb35d0d953e1429024addc0480075c12","datavalue":{"value":{"entity-type":"item","numeric-id":4952609,"id":"Q4952609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36b51e5b46a8ce904c9ebce13ce60a89989d36ef","datavalue":{"value":{"amount":"+0.8227152","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":"Q4651510$AFD628E8-567E-4707-B5A6-0949B0FFC02E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4651510","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4651510"}}}}}