{"entities":{"Q1894446":{"pageid":1905188,"ns":120,"title":"Item:Q1894446","lastrevid":71088867,"modified":"2026-04-13T19:24:38Z","type":"item","id":"Q1894446","labels":{"en":{"language":"en","value":"Superlinear lower bounds for bounded-width branching programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 777959"}},"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":"Q1894446$C4BBD42F-6303-4673-BD13-91BF796D05D4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dec72749184bf4bb658b085b4eb54e1c91644a82","datavalue":{"value":{"text":"Superlinear lower bounds for bounded-width branching programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1894446$87E4C183-E399-4221-8B9F-F8966256BCD9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"393692ba5047cb2ca41a03f40fbd9f2a69fe48af","datavalue":{"value":"0837.68056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894446$A544B1AE-7AF7-41C7-86C2-9BB7DEA0B20F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"795e5af62cffee265773a4ab5f77af480f86d75e","datavalue":{"value":{"entity-type":"item","numeric-id":386052,"id":"Q386052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894446$A52C6F45-C3D0-432B-8E19-3C629F76EC7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9fb8d4872513e25b3cb2ee4b054caa1dd9caebba","datavalue":{"value":{"entity-type":"item","numeric-id":599181,"id":"Q599181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894446$DE6E41A6-587C-441F-83EB-B9C41BCF49BD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894446$EF105BB5-0B5B-4F8F-8706-C7426900856F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1e4da7e231d49ddcf0d3d0ef54adba15a2d34363","datavalue":{"value":{"time":"+1995-08-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":"Q1894446$745FD777-F229-4C9C-8B60-EDB2C67ACFC4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894446$595C42DF-0C94-4C62-ADE7-C236A726773A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894446$92705307-866E-4C0F-A639-637C834F2FFD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"85351237a3db6c5c43c608ae1bb5b0be811ff330","datavalue":{"value":"777959","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894446$122C94CE-CAE0-4EC3-9993-D6C3103C6538","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7b604f8cd08381831eb49f06f6012b2df623018","datavalue":{"value":"bounded-width branching program","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894446$DAD9624B-43F4-44E8-8B97-7F256BA0B63F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f958f1f1caf56a0e3143111463ca67fa81df9aa5","datavalue":{"value":"threshold functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894446$8601E6C5-41FA-4393-8A5D-BD2101B024B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f0cb341ca7876bc8468eee4ea8e9008984980e7","datavalue":{"value":"circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894446$9C3FBC6C-896D-45A3-A483-67CD3E5B1636","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":"Q1894446$844058FC-83F3-4C85-A155-E833E8209601","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2d6dae25e91d49c49149ff9799fc4c11db8f6439","datavalue":{"value":"https://doi.org/10.1006/jcss.1995.1029","type":"string"},"datatype":"url"},"type":"statement","id":"Q1894446$9179E50A-B344-4C38-B65B-8053E8BC979F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fbc1246f1567b3ca707b4eb6e206a9b19142636e","datavalue":{"value":"W2025481592","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894446$B7FC5CD1-7F2F-4303-93B0-31503E568938","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2efc62a2bb6cb6aea48b28ea603e9a144b83000f","datavalue":{"value":"10.1006/JCSS.1995.1029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894446$AE4B542E-8EDB-47EA-B860-BECAA7C46AD9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d780ece8df5153523c0cd7b137316b722f11889","datavalue":{"value":{"entity-type":"item","numeric-id":4318222,"id":"Q4318222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95d300f64a32c0658013329f68f36a6ddf82934f","datavalue":{"value":{"amount":"+0.91834354","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":"Q1894446$CA34CFCB-036D-4BA1-84F3-8144D6BA8407","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":"f6d1d51ccd7ef9531d44efa53682137e92b04dd5","datavalue":{"value":{"amount":"+0.91276705","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":"Q1894446$1BB779E1-8580-4B4F-9BD7-32FD9695B90E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"790a13e529330f03f7a7f9443b8f8b2740756d59","datavalue":{"value":{"entity-type":"item","numeric-id":3690219,"id":"Q3690219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f752a2b5510c8654de621d07455d1a6b0f90ce5","datavalue":{"value":{"amount":"+0.9058032","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":"Q1894446$8AE60998-EE07-434B-A9A2-7F260B656A05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19ed83dfbeab17745bf3d1361bf73d3cc0f6eac7","datavalue":{"value":{"entity-type":"item","numeric-id":3718153,"id":"Q3718153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afab182a8ae562bd968edf40c448408212a9810a","datavalue":{"value":{"amount":"+0.90151787","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":"Q1894446$04BC27A9-F23F-47E0-9F75-6026C4A821EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30e8ca2ccce0019f00dde64e81fabd3119796a72","datavalue":{"value":{"entity-type":"item","numeric-id":3991212,"id":"Q3991212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc8e3fa7cb6ad357193301b6c7abc8ddec7cb916","datavalue":{"value":{"amount":"+0.8883674","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":"Q1894446$254391C1-7868-457C-BEBC-56613475CAD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d34bffca204837b687155ec32630ddb690ca5a5","datavalue":{"value":{"entity-type":"item","numeric-id":3002761,"id":"Q3002761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"727b1fe7747beaeda94f2e37f2815648835dbf48","datavalue":{"value":{"amount":"+0.88717735","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":"Q1894446$A85A5B33-252A-4DAD-913E-EB8F2D6B4F25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"631d532687e859f2d3becae1d6f01bdb59f2b87d","datavalue":{"value":{"entity-type":"item","numeric-id":5493360,"id":"Q5493360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6953fed215c4ab09247c7406add64fb7513a112d","datavalue":{"value":{"amount":"+0.8865507","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":"Q1894446$E879F5ED-D92A-4118-9BF2-73ED05722963","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d554a1536ccaaa7d3d3465ae7f417441fd2db7e1","datavalue":{"value":{"entity-type":"item","numeric-id":3599145,"id":"Q3599145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4b8ba23f534e6d856c2726be04cb5378ded4f86","datavalue":{"value":{"amount":"+0.88293856","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":"Q1894446$1C3C5985-E27B-40DC-9A89-968252A01A5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2051f95e319f1309481c420d048c4b62ebbe7566","datavalue":{"value":{"entity-type":"item","numeric-id":4736860,"id":"Q4736860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f585f955d7379e3bebfd6b53357019a7bbf5423d","datavalue":{"value":{"amount":"+0.8827141","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":"Q1894446$8DBD5C45-0EFF-43CC-AEE0-CD7B7E9660BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8669cbcf37c61d9bffb64756c4a730e7f95140a0","datavalue":{"value":{"entity-type":"item","numeric-id":1816743,"id":"Q1816743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d162a22cd194866576fa59cee3576e1ab975056b","datavalue":{"value":{"amount":"+0.881019","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":"Q1894446$A7E4A72D-34BA-4F5D-A523-056045DF6D34","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Superlinear lower bounds for bounded-width branching programs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Superlinear_lower_bounds_for_bounded-width_branching_programs"}}}}}