{"entities":{"Q1121671":{"pageid":1132420,"ns":120,"title":"Item:Q1121671","lastrevid":49283773,"modified":"2026-01-06T21:53:01Z","type":"item","id":"Q1121671","labels":{"en":{"language":"en","value":"Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4104387"}},"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":"Q1121671$8B7FD300-BB24-48B3-9DD9-AAFF049FCEBC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7b10c27727c27497c3d6ba7e7a4e5c861e21a60e","datavalue":{"value":{"text":"Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1121671$33B38B28-3D7F-4F65-856E-0073235FBA5B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f2471e7274274ba4c554b6d715acb8f32c94102a","datavalue":{"value":"0674.68033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121671$B8218019-C6E0-4B17-8D04-A1ACEE053AF5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f7505b5786c764592e4e1ada504f7aef5126ce03","datavalue":{"value":"10.1016/0890-5401(92)90046-I","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121671$38E5F906-CB1F-448F-9DCD-5AF53310BE2B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7330faa8aa9bfbfa602624605066aa6301d76b4","datavalue":{"value":{"entity-type":"item","numeric-id":208754,"id":"Q208754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121671$3D1BDD50-7096-4328-8C01-6FE9C15E9BDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a8e64cc5a49defae094d3e5672d9d5857d5e3b73","datavalue":{"value":{"entity-type":"item","numeric-id":778929,"id":"Q778929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121671$4940B45B-3ED8-4E94-9B7B-36D4C537A345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aad099f57a9ffbfe76501531fc67aa620054130c","datavalue":{"value":{"entity-type":"item","numeric-id":202501,"id":"Q202501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121671$70A5EF9E-5321-400B-8143-83531F86C7F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fc5d525b71afdf25227c4e34bdb392276b8c3c26","datavalue":{"value":{"entity-type":"item","numeric-id":233005,"id":"Q233005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121671$3EE18945-397E-4244-94F9-AEBCADFC71B3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121671$8D664E45-2236-461E-B7F5-96E95244A761","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":"Q1121671$E4E06A72-10CC-4C5E-9EAE-6601C4F69FC5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"01d3d75c35fa8b1ec44ad080b1dcea4bf0a63e2d","datavalue":{"value":"The first \\(\\Omega (n^ c)\\), for \\(c\\leq 1\\), lower bounds on the area complexity of multilective VLSI circuits computing a specific problem are obtained. Lower bounds of this kind are achieved not only for constant multiplicity of reading but also for multilectivity bounded by \\(O(\\log^ bn)\\), \\(b<1/2\\). To establish mentioned lower bounds a new simulation of (nondeterministic) multilective VLSI circuits of area A by oblivious (disjunctive) branching programs of width exp(O(A)) which have the same multiplicity of reading as the VLSI circuit is derived. This enables to apply the exponential lower bounds on the width of linear-depth oblivious branching programs obtained by Krause, Meinel and Waack for multilective VLSI circuits.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121671$6715ED2E-668F-4A94-B288-BA4167E5D2D1","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":"Q1121671$BEE722AE-4CC1-41A0-B1D3-586B7A0CE5E5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121671$E6B0CF71-6174-469F-9A68-91E5D8444904","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121671$9103F351-6FB8-4A84-9BCD-0BABC0C8800E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121671$5719EB56-99D7-4592-BFBB-E1752EB00C31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121671$8CEE6B1B-6AEF-465E-AD68-4E4D9CB0DBBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121671$051803E3-D67B-4117-A041-8CCE9A4C1088","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7ca7c2af2baafdfbd8644fb94a59e063c5131c13","datavalue":{"value":"4104387","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121671$F2E04E93-1F14-4E58-BC12-5C579DB1EDAD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121671$862F1FF1-7E5A-41A7-AE7E-866CE3ED38B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121671$E04BB88C-71E3-49D2-9EC4-90DC111BF872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec24897927a0742784fae89aed9a922bc2a81fec","datavalue":{"value":"branching programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121671$FB0131B8-D7A2-4A19-8260-6379D8D85553","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61a6b5e1b549a55bdb4020e53af4308ca42fa3db","datavalue":{"value":"multilective VLSI circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121671$4458120D-17E8-4766-9BD7-117B53B06B26","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":"Q1121671$782EB702-8385-410B-8CED-031A69B6E876","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"643b54703dafe9d83d1cb12473c945cbae1577bc","datavalue":{"value":{"entity-type":"item","numeric-id":3787930,"id":"Q3787930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121671$AA014E04-A747-42FA-8FFD-1BEACFC57EF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e51d01146af2917002a1f7981006657e192ea04","datavalue":{"value":{"entity-type":"item","numeric-id":3795232,"id":"Q3795232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121671$93676135-DE1E-47A9-9EC1-7AA07E115B78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a42da927b2ffc388f0570d4dd722d7ec6caa298b","datavalue":{"value":{"entity-type":"item","numeric-id":3751569,"id":"Q3751569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121671$A2EDB174-AC6F-40CB-8DC7-E8760391803F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43f3a6074b33ecb523f1ba01b90c0e3c84f50434","datavalue":{"value":{"entity-type":"item","numeric-id":3783568,"id":"Q3783568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121671$DF40B78F-06DE-4880-A6C5-30D603B6ABEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b7502174b8cd991b757104f1cb91cae8ae5a1fa","datavalue":{"value":{"entity-type":"item","numeric-id":1187665,"id":"Q1187665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121671$198876F1-9089-40A1-A941-33298907F464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1718c4c555927341310ae6dd516ce5e236ab892","datavalue":{"value":{"entity-type":"item","numeric-id":1069297,"id":"Q1069297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121671$713CE780-FC0E-4314-AA94-C5050C108A81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28d1d1cb66d27d2e53aba37392ad47b61e11f859","datavalue":{"value":{"entity-type":"item","numeric-id":3326832,"id":"Q3326832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121671$53B9A1E7-27CE-436F-BDB4-CE44E4FC127E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd6422e07c18aff2350e102ed958f8faa5d74dc2","datavalue":{"value":{"entity-type":"item","numeric-id":4009550,"id":"Q4009550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5220648488804a8c3cefda96710aefbe5fed8961","datavalue":{"value":{"amount":"+0.8921540379524231","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":"Q1121671$481DC31E-A46C-4278-AAC6-E57CAC7B89D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cef4e40c3be579d4b477b5e71ef85ce005e69fac","datavalue":{"value":{"entity-type":"item","numeric-id":3795232,"id":"Q3795232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48867bdffdc88bb6cf5f41bb29b808778dec6b00","datavalue":{"value":{"amount":"+0.8361392021179199","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":"Q1121671$1F489F6A-F582-4145-86F3-864C17C0E0A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e8935fc628db1d41ff0963e10f741bdd8f2578b","datavalue":{"value":{"entity-type":"item","numeric-id":1069297,"id":"Q1069297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dad6d3cb724ac975137dc4d1185690589a10a104","datavalue":{"value":{"amount":"+0.804602324962616","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":"Q1121671$D2B8E16B-C508-42B2-ADCF-613C330E6DFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ec3e3ad4b1694367f4900c553caf0f31b803bcd","datavalue":{"value":{"entity-type":"item","numeric-id":3197313,"id":"Q3197313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bfed46e4f4d60bc75407fd2c63c7d15686e3059","datavalue":{"value":{"amount":"+0.8011487722396851","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":"Q1121671$777D5C13-B1E6-449A-8627-E38B84640857","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc5d5b95be78c2d44892060775156027ad110e6f","datavalue":{"value":{"entity-type":"item","numeric-id":3827543,"id":"Q3827543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cad2fee51fcf24d38a22676f424edb19a87a96a4","datavalue":{"value":{"amount":"+0.7898380756378174","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":"Q1121671$358C522A-B55B-4F73-9E89-58BF8FB3EE76","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1121671","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1121671"}}}}}