{"entities":{"Q2408558":{"pageid":2419301,"ns":120,"title":"Item:Q2408558","lastrevid":57910275,"modified":"2026-04-03T01:26:26Z","type":"item","id":"Q2408558","labels":{"en":{"language":"en","value":"On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6790464"}},"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":"Q2408558$08D5D272-E962-496F-85F4-8E77D90625E2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8d06abdc999f028f4dc32afe96b08a66a774ff34","datavalue":{"value":{"text":"On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2408558$F1A520BB-5D07-4331-8006-24D299A97B04","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e97651cfd5306732a98b0526599971d4cb322c67","datavalue":{"value":"1378.68035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408558$CFD46711-AE17-46B1-AF04-7B7EC2BB6B8F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4baf1246ca3bd7d8e2e3b31627e33d8d26846674","datavalue":{"value":{"entity-type":"item","numeric-id":309787,"id":"Q309787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408558$0F8B95F4-F468-4C02-83BA-22DDA5592E2E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408558$64BC9D39-B955-4025-BE8E-EC6118343506","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9c0381aec861f5a199f46f1776607b0e02f2cdf4","datavalue":{"value":{"time":"+2017-10-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2408558$0532D400-6B2B-4209-9062-9A94816BE98B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5d8373364450e1d2c09796eafd1e46144358e033","datavalue":{"value":"https://arxiv.org/abs/1510.02951","type":"string"},"datatype":"url"},"type":"statement","id":"Q2408558$D521829F-C4E6-4115-AF56-5C426249CE5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"79617f004f7d7a7e9ac3065ce81c85dd2a91f1c0","datavalue":{"value":"https://eprints.bbk.ac.uk/id/eprint/17098/1/17098.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q2408558$CDABCEE9-6295-46C2-8870-943EC611913A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408558$72A5B6DE-C121-47B1-A710-85A7312A3AAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408558$027D6BD7-A205-4DD5-AF74-AB544AFCAE28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408558$EB8AE1F8-8A5F-443C-9275-A847114E2E1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408558$993F84EB-EE9F-40D2-AB13-55B11D386BBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408558$FEDB504A-0731-4309-8453-0343CC65EA28","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8a7c8e75df8691426d8f096db962cc849336d2dd","datavalue":{"value":"6790464","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408558$C5872540-F12A-4A58-B96A-E6500825CEB9","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":"Q2408558$3F4A0AEE-D9A1-4B43-BFD4-3DEB9C2E2AEC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"19223fffc654a27cd4df718e1d91eabf4ac96b14","datavalue":{"value":"W2963024702","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408558$401F596E-E4D7-4D58-8F7A-749EB63D8DB1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bd354608c7598a4ad85b60840d02f453818a047","datavalue":{"value":{"entity-type":"item","numeric-id":353910,"id":"Q353910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408558$5C9A1AC1-F2D3-4526-BA65-43678883C3CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb77facc02f21ad2f21d191c8d7a4263305b54d1","datavalue":{"value":{"entity-type":"item","numeric-id":1115606,"id":"Q1115606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408558$9F231D9A-862B-41A1-8E1D-7DC4B81855B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d351ae6c2156438a7cf2ef1e070f6ff81014314b","datavalue":{"value":{"entity-type":"item","numeric-id":1275068,"id":"Q1275068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408558$704B52DF-D720-4C40-B6D9-6C96203BEBB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f4150d4584eafb8457c578c72e61f86894bc805","datavalue":{"value":{"entity-type":"item","numeric-id":2366719,"id":"Q2366719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408558$4487E4E0-A989-497E-A02C-208ED51399CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9aa01315b500d5b7246dc1c5497390eae0b9b821","datavalue":{"value":{"entity-type":"item","numeric-id":2476243,"id":"Q2476243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408558$7B17A46F-E339-4936-86A3-50144539F48F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb831a926f4740f70cbc7d7c440aa3f25cfdd945","datavalue":{"value":{"entity-type":"item","numeric-id":1173954,"id":"Q1173954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408558$4377183C-EFB1-42B1-9BDA-A046B37E9157","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"971ba83d7d765f79fbaf732cdd687bed4bd634fb","datavalue":{"value":{"entity-type":"item","numeric-id":5387860,"id":"Q5387860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408558$99DAA430-30B4-45E6-9FAE-507D6588C8A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e42c9128d887844233caee1df2a5e2ba33f6baa","datavalue":{"value":{"entity-type":"item","numeric-id":642463,"id":"Q642463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408558$6CACB2F2-FAF4-4D4D-BD0F-A14C2AD1507F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01915f9ec818c5847937b6b5f8535459ffd3b32b","datavalue":{"value":{"entity-type":"item","numeric-id":748240,"id":"Q748240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408558$7ADB3D70-49F6-466C-9B01-2FE70E6FD712","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2a27ac1359142dc877e852fc55fbeb35704441f","datavalue":{"value":{"entity-type":"item","numeric-id":2946031,"id":"Q2946031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408558$9E95403F-BADE-425C-9D6F-58C5AFF2C1A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80f94c357cde2b4f18340db99582ef961b69ec90","datavalue":{"value":{"entity-type":"item","numeric-id":309788,"id":"Q309788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408558$7DDBB63E-13FE-4A1E-A6FB-6021472DC4D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ee9bdbd9786926088840fd488fe60b509eb451c","datavalue":{"value":{"entity-type":"item","numeric-id":4485697,"id":"Q4485697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408558$B57E2B26-2DA2-4E7E-AF53-BDF66E8689E2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b19efc2284d3e88205fba9ea5a1b41a09a82c694","datavalue":{"value":"10.1007/S00224-016-9714-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408558$0625BB2C-42C0-4E62-9FDA-AA2CFE5B14AE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73e244f358b2e7951a14c546829e3f1de5cf9fd6","datavalue":{"value":{"entity-type":"item","numeric-id":309788,"id":"Q309788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3696e9c2cee723b3389e0f664ece27d9b756efa7","datavalue":{"value":{"amount":"+0.8402209877967834","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":"Q2408558$A0E87B09-FDD5-444F-B6DE-E9F5E3F8D7A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b84c71f0d4e493bc7f5a362f69439942e3a46c41","datavalue":{"value":{"entity-type":"item","numeric-id":2946031,"id":"Q2946031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f9a1df55b21c2ea7997dd4ffc6b420717268f85","datavalue":{"value":{"amount":"+0.8326804041862488","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":"Q2408558$1109B1A2-F00D-4BFC-A3DD-F786E491C34F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cdfc2a5a7d43da48b32ffa86120243e08e430973","datavalue":{"value":{"entity-type":"item","numeric-id":3499725,"id":"Q3499725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a664149f92f3945fd9f6983da222f71765f359f","datavalue":{"value":{"amount":"+0.7787941098213196","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":"Q2408558$F3A57603-103D-4AAE-9448-C1B78FF5177A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95f7944585aa19ecc078506a2988dadb82be7fb6","datavalue":{"value":{"entity-type":"item","numeric-id":2411046,"id":"Q2411046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6c66e694a0add200dc1ffeeb12d9d82fe93c92c","datavalue":{"value":{"amount":"+0.7771257758140564","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":"Q2408558$44FC8218-4AA2-42D7-B970-EEA4FC36AA77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6cf869ef5740178e34eece1a8555e28b50a0ddd","datavalue":{"value":{"entity-type":"item","numeric-id":3194709,"id":"Q3194709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93187c8cd870be9c3194689c5ae8791ab1ade6bd","datavalue":{"value":{"amount":"+0.7749433517456055","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":"Q2408558$ED2BE25F-7DF0-4F26-8DF7-DF4E29E4FCFE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2408558","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2408558"}}}}}