{"entities":{"Q1107323":{"pageid":1118072,"ns":120,"title":"Item:Q1107323","lastrevid":69835788,"modified":"2026-04-13T10:40:23Z","type":"item","id":"Q1107323","labels":{"en":{"language":"en","value":"A lower bound for read-once-only branching programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4064493"}},"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":"Q1107323$6C369525-E0A7-4387-9D4E-E26854A9ED0A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bb47b8aff5616b79d865ff60f4aa6c609182b2bb","datavalue":{"value":{"text":"A lower bound for read-once-only branching programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1107323$597D76D8-0BED-48B3-986A-6631B785EB20","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a7f38f1e30885435c8e73097ebe031dc2545ca53","datavalue":{"value":"0652.68062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107323$80160620-153F-45FA-A7A9-D19CD6591AA7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2b6d85a9339d379cc8d4dd48ab8c6562b013bcf2","datavalue":{"value":"10.1016/0022-0000(87)90010-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107323$9A218D72-CA78-4D30-A795-9232A6F00C8A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6ef2648e3dc785999c15fc8670736a5ed79a5826","datavalue":{"value":{"entity-type":"item","numeric-id":215793,"id":"Q215793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107323$BA846C0B-B0E4-4C42-921B-7D69A9835ABC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c66a437d74ae466cacad614cef92f8e5d71204e6","datavalue":{"value":{"entity-type":"item","numeric-id":239429,"id":"Q239429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107323$516793ED-8837-489C-AAEA-81BEE38835F9","rank":"normal"},{"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":"Q1107323$E79ABD85-5026-4B74-AE0C-8E6EC3F69E0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"11ae3d44052578af232f86664e60399b2eea5845","datavalue":{"value":{"entity-type":"item","numeric-id":6480429,"id":"Q6480429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107323$4BE9F28B-36AF-42F8-84CF-590D8DE5F7BA","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":"Q1107323$AD234FAA-EDC6-4378-9621-86432FFA2844","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1107323$4F9E68F2-50BE-4D43-BB79-452D56D82D48","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7c115509bdc1340a6effeb2641321c70dd62b77c","datavalue":{"value":"The authors present an exponential lower bound for read-once-only branching programs computing an explicit function. The function is defined as follows. For any natural number v, binary strings of length \\(n=\\left( \\begin{matrix} v\\\\ 2\\end{matrix} \\right)\\) represent graphs with v vertices. Each position in such a string corresponds to a pair of vertices and 0 or 1 on the position encodes the absence or presence, respectively, of an edge between the vertices. G(x) denotes the graph encoded by a string x. Let \\(f(x)=number\\) of triangles in G(x) (mod 2).    The main result of the paper then reads as follows: There exists a positive constant c such that every read-once-only branching program computing \\(f_ n\\) has size at least \\(2^{c\\cdot n}.\\)    The result implies a linear lower bound for the eraser RAM space complexity of the above defined Boolean function. Eraser RAM can specify the order in which the symbols from the input are read, but once an input square has been read, it is erased.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107323$A35580E0-7685-4FD8-8791-7FB4AB2D726B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107323$6165DE3E-4A57-448A-A48B-1D94ED2AE30E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107323$7908D736-EC7F-415E-A5FF-392AA05B46F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107323$2F052E0B-ABD6-43BE-9945-DFD5C85D41C2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e72875fd253c93a9331a7de9e8f759e0324aa469","datavalue":{"value":"4064493","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107323$5FDDA5B8-1319-4EAD-9E93-D9B509BFFA32","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107323$1AC32A36-7F56-4BBA-ACA5-39DCD6F213B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec24897927a0742784fae89aed9a922bc2a81fec","datavalue":{"value":"branching programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107323$A19B90CC-4D56-4E7E-8F00-48D861FD0566","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff48da794199231c5c2de147eb480bb33ff85c79","datavalue":{"value":"eraser RAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107323$645F0E9E-7B0A-438C-88A1-F3A11EF3E4D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107323$BC9B9BB0-D4B6-40B5-AB07-F5E397D48AEA","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":"Q1107323$D78E487E-12A8-46C4-A770-BF8332E913E5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"85062e35754cbf3a8cad65189034844af0fe8a80","datavalue":{"value":"https://doi.org/10.1016/0022-0000(87)90010-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1107323$7984D842-2BC2-4B25-88BF-074F7EFE4840","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0339b920b8b850fe961f7089d176b5812b4352e8","datavalue":{"value":"W2048768180","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107323$A80FECC8-17CA-41FD-A136-8DE040F73E08","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2ca04c59b1468ff9eb03a30febcf55d98359908","datavalue":{"value":{"entity-type":"item","numeric-id":1094870,"id":"Q1094870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107323$794F4BC0-A512-4C85-A231-A6641C16A00D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce25b6e3a78e9a3f320205259f9976f9eabd886a","datavalue":{"value":{"entity-type":"item","numeric-id":4726174,"id":"Q4726174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107323$DF994212-48B2-479D-9B39-DE8FAF831C53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1a52569f4723473b14a228edfd70f44f49aae34","datavalue":{"value":{"entity-type":"item","numeric-id":1152950,"id":"Q1152950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107323$F9105F74-D72C-4BE1-B226-C66692874EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f67782435c81856906476d249cbb89a86efd5732","datavalue":{"value":{"entity-type":"item","numeric-id":4160379,"id":"Q4160379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107323$A241FE9E-EBC9-4D15-B606-AE067C0D3633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0755527dc26ccf06e69cd62ec76a91e4b8d0335c","datavalue":{"value":{"entity-type":"item","numeric-id":3903002,"id":"Q3903002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107323$6D691254-E53B-4480-A85B-645FAC8D7B7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0ec4868dba1b37d1adb8bb9f6a23d6c0a862f5","datavalue":{"value":{"entity-type":"item","numeric-id":3880849,"id":"Q3880849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107323$5E7D858A-0C48-4937-9745-3789270369E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"514b291bcc18717499c847de12de372fe9e5cca0","datavalue":{"value":{"entity-type":"item","numeric-id":5545524,"id":"Q5545524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107323$4D0CE301-EA3A-474B-B91F-2BBAD3B7CBB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5f4d447f65bfc71d38aaff97bfbb5c0156be618","datavalue":{"value":{"entity-type":"item","numeric-id":3690219,"id":"Q3690219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107323$BD9C14A6-4896-4066-B1D7-B3D61FBB70A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0942c3ffeac8339c20eccc6667aba9b8af08cc5f","datavalue":{"value":{"entity-type":"item","numeric-id":3758729,"id":"Q3758729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107323$DCEBAD45-8C1B-4A09-8531-686D4D90B66E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c43b242e8d2a6febe28b4e1a41898561ecb7a1a8","datavalue":{"value":{"entity-type":"item","numeric-id":4138141,"id":"Q4138141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107323$761E80EC-AFA3-4D0F-B812-3686AB7B057E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc58250a14130624ee44036696d58021695c27ec","datavalue":{"value":{"entity-type":"item","numeric-id":3334079,"id":"Q3334079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107323$9222B1C9-19DA-419E-8C87-6E200766E5F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21bc7c146c515de56380f9786cb8389fb225ca92","datavalue":{"value":{"entity-type":"item","numeric-id":3347300,"id":"Q3347300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107323$DF7C962B-2695-4BA8-B209-68D49C85A418","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cdbb96a6d7163dc90b53bbb3513478ae0d571593","datavalue":{"value":{"entity-type":"item","numeric-id":4287364,"id":"Q4287364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f41fee59a1c1e36a95fc6857c45a1bcb8777dbc","datavalue":{"value":{"amount":"+0.799614429473877","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":"Q1107323$A19DFA87-FB64-4771-A8A9-0B86BE054448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"feda851e7a9cb8019d6d83459596927963504a0b","datavalue":{"value":{"entity-type":"item","numeric-id":963361,"id":"Q963361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f41fee59a1c1e36a95fc6857c45a1bcb8777dbc","datavalue":{"value":{"amount":"+0.799614429473877","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":"Q1107323$D3565F03-ECC7-4466-B124-AC1824A1E414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ab1ae0c304b14826b69082646672782b648c1bc","datavalue":{"value":{"entity-type":"item","numeric-id":2583538,"id":"Q2583538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85fc21f945d2e95b9c66c93d93665e2186e88515","datavalue":{"value":{"amount":"+0.7874228954315186","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":"Q1107323$2C66E1A4-CBF7-4E17-94DB-1CA58B6CBCA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99f2b00b22d54fc0a058b94b1177d9cc01760198","datavalue":{"value":{"entity-type":"item","numeric-id":1575258,"id":"Q1575258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acd998eff3af1ab2deef58c75239fcd21f470e59","datavalue":{"value":{"amount":"+0.7857071161270142","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":"Q1107323$8C5C9E6D-013D-459E-95A6-09472929315F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e18b97629bce32596095561f2a2815dce7a01c84","datavalue":{"value":{"entity-type":"item","numeric-id":3347300,"id":"Q3347300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b5eb7e1acb6fe19f5f53caf0fe621ff6fc9207e","datavalue":{"value":{"amount":"+0.785379946231842","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":"Q1107323$5795ED15-B420-4952-A9A4-F2863D24FC02","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A lower bound for read-once-only branching programs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_lower_bound_for_read-once-only_branching_programs"}}}}}