{"entities":{"Q2366719":{"pageid":2377462,"ns":120,"title":"Item:Q2366719","lastrevid":46346571,"modified":"2025-12-24T14:58:13Z","type":"item","id":"Q2366719","labels":{"en":{"language":"en","value":"On lower bounds for read-\\(k\\)-times branching programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 227469"}},"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":"Q2366719$05E111B9-ACAF-4583-9721-F231A567F21E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"74ed8e876db0cbbeb9ca7c3459bae31991261e24","datavalue":{"value":{"text":"On lower bounds for read-\\(k\\)-times branching programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2366719$F8974C9B-41D3-4E64-9E56-624CF84679BC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"88f8ec8328497e777ed6731f297b301543d82c02","datavalue":{"value":"0777.68043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366719$78CFE344-2372-4306-AE5B-37721071F608","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dbb495b4e87c1b640a4dd89235a549afd89d035c","datavalue":{"value":"10.1007/BF01200404","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366719$F3ACB358-E5A3-4122-9B6D-89306E94C9B7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bafe71e5b991a8bf89ef6acecffbc39fc3714598","datavalue":{"value":{"entity-type":"item","numeric-id":430835,"id":"Q430835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$A90F7159-E7B8-475E-BEAC-C4C62D625708","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c0bcfb4eb9a7ab6903b269f394ffde6834d9319","datavalue":{"value":{"entity-type":"item","numeric-id":1370854,"id":"Q1370854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$7990DFDD-C6A8-4345-B674-EF321050B253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9d3e8d1887ecdc83148e98b7bfdcdb9a9622cf00","datavalue":{"value":{"entity-type":"item","numeric-id":1377569,"id":"Q1377569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$66E22AD8-9C7C-4638-98F5-2111ACD3F7D0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$F98E7930-CB9F-430B-B94E-771D66E1753B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca925aef735ee73d86c6a323015bc1282d85f7d8","datavalue":{"value":{"time":"+1993-08-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2366719$93162395-505E-4D77-9A6F-98F624FF855F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"734a49da2af28d2a5e41274dd3e8d0a18b490f4a","datavalue":{"value":"Proving nontrivial lower bounds for read-\\(k\\)-times switching networks (called also, nondeterministic branching programs) is a long standing problem. Such bounds were obtained only for oblivious read-\\(k\\)-times schemes. The authors consider another restriction: they require that no variable occurs more than \\(k\\) times on any path (whether or not consistent). An explicit Boolean function is exhibited which requires such ``syntactic'' read-\\(k\\)-times contact schemes of size \\(\\exp\\left(\\Omega\\left({n\\over 4^ kk^ 3}\\right)\\right)\\). The proof is based on the following combinatorial result concerning Sylvester matrices, i.e. \\(n\\times n\\) matrices \\(A=\\{a_{S,T}\\}\\) over \\(GF(3)\\) with rows and columns indexed by the subsets \\(T,S\\subseteq\\{1,2,\\dots,\\log n\\}\\) and entries \\(a_{S,T}=(-1)^{| S\\cap T|}\\).   It is proved that the rank of any \\(u\\times t\\) submatrix of \\(A\\) is at least \\(ut/(2n\\ln(2n/u))\\). For nonsyntactic read-\\(k\\)-times networks (with no restrictions on inconsistent paths) the problem remains open even for \\(k=2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366719$6B41D51D-F4BB-4819-BA15-CA2043D1BF14","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366719$808207C8-6036-44D8-AD59-2E8EC3BED8B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366719$69B5A39F-594E-4626-9892-5232070B08FF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b88a94f25ba64a2bdcb88343f674ca309601d1c0","datavalue":{"value":"227469","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366719$20770D5D-7582-4B03-821F-B81D364FA6A5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e5c86c6ac9f6c9f58655971be819ed856d14a08","datavalue":{"value":"read-\\(k\\)-times networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366719$19CD012C-2224-4176-83A4-A446229ACF63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e323acca35e53891a7b7be05f4b8f0300bd89941","datavalue":{"value":"generalized Fourier transforms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366719$C56EA2EC-67DB-43F7-9323-340B95C86FB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366719$940CC3E9-419B-4789-B06E-8E57CE8C394F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec24897927a0742784fae89aed9a922bc2a81fec","datavalue":{"value":"branching programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366719$3DF1E77D-0848-4E3A-A5F1-86CAF1F8EC91","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1833d190eb6492ca84e0c93a6ff12de5694705d3","datavalue":{"value":{"entity-type":"item","numeric-id":1109753,"id":"Q1109753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$562225B9-21F1-4802-9EBB-7D7D1152363A","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":"Q2366719$CCBAB5EB-6DB5-4414-9D4A-EB7E8FA0518E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe1806742d8bdb7f1e88779a2c5629b608d36a03","datavalue":{"value":{"entity-type":"item","numeric-id":3790661,"id":"Q3790661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$C03200B6-09E8-4291-AA2A-B23E3A1CCDF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b2cb4894c9300ce14e43ee0bcd37557703e3535","datavalue":{"value":{"entity-type":"item","numeric-id":1176102,"id":"Q1176102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$1D1BAE20-70D3-4D81-9035-8DB6D924C81D","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":"Q2366719$011E006D-B223-4A27-9227-4048E1B97C0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5c31e8d2807d1ce4f8ab6661996ea0ee3ab237a","datavalue":{"value":{"entity-type":"item","numeric-id":1107323,"id":"Q1107323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$CAD13F2E-69A8-431C-8F65-5574DBFF63BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bed5a89ddfefb21bf7d440fe67cd3e228cd1385e","datavalue":{"value":{"entity-type":"item","numeric-id":914382,"id":"Q914382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$7E592CE6-2E0D-463B-AD59-5A1B5C6011DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c20124943b4ae822aeddc78e4872182bf0c5a98","datavalue":{"value":{"entity-type":"item","numeric-id":1894446,"id":"Q1894446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$273E9197-9625-41EF-8183-ED41496EA3C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"197c225799e487294a747ce7acf284840e35974d","datavalue":{"value":{"entity-type":"item","numeric-id":3210181,"id":"Q3210181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$8B476879-8DFF-49E8-B287-1E1B90B475BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfda1aaef4d74a55b724a4e4b97259bc5a577f06","datavalue":{"value":{"entity-type":"item","numeric-id":3936210,"id":"Q3936210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$AF7C30B7-6742-424D-99CD-5353488A20D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c767919e94a3332b8d198174b1921d5e4026fe","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$06538A4E-B9A0-4AC1-86F8-38624F2F698E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c959b34df4e4ce5a3dcb3c44885ef547d04acf","datavalue":{"value":{"entity-type":"item","numeric-id":4362278,"id":"Q4362278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$9D07B7B2-5557-475A-A2AB-24889C5C5E98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07d45518b00f2b918d0b4ca12dd1eff0acf8b14a","datavalue":{"value":{"entity-type":"item","numeric-id":4020492,"id":"Q4020492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$F92FD75C-62D8-4961-BC8D-C82AC316DAA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8363d01136465dcc8e95edeca2492460de094946","datavalue":{"value":{"entity-type":"item","numeric-id":1178711,"id":"Q1178711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$1F04D9B5-8633-4109-AD37-596FE35E3AB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"464796b3d7fe846d1db7baf0e2ae3ec55ec86321","datavalue":{"value":{"entity-type":"item","numeric-id":1208411,"id":"Q1208411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$8C020DA2-04C0-4F4D-A349-86FD47196A1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$851454F4-AC34-4C50-ACE7-A5A853BE47F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0962521a64e4c207ee4c6274955735371b352ef8","datavalue":{"value":{"entity-type":"item","numeric-id":4287364,"id":"Q4287364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$2D5D70A0-F418-42BF-9DB8-5832AEA66081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67ed33de7061de4d7d8391bea59c71fda756b59c","datavalue":{"value":{"entity-type":"item","numeric-id":3815544,"id":"Q3815544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$0AC058F8-E57A-4DC9-A6A5-CD77C4C62CF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8624ac8b08c43bff2290ca70392ccbd3bba72141","datavalue":{"value":{"entity-type":"item","numeric-id":3762226,"id":"Q3762226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$6C1A49FE-2738-4B25-B13C-B7B900C45D2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c731fd97fc54301a48fb801be9df90976d0215da","datavalue":{"value":{"entity-type":"item","numeric-id":1065546,"id":"Q1065546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366719$E6E97F56-1BC7-4762-B870-263DC3A23065","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d3e1244c03b295fdddd10d8121d2a1dae5f2230d","datavalue":{"value":"https://doi.org/10.1007/bf01200404","type":"string"},"datatype":"url"},"type":"statement","id":"Q2366719$A4207C3D-1D76-4208-B247-761C1F7B9A7C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"df3b50274b9f6aa693b8084c7b72aa08b94fd72d","datavalue":{"value":"W2095012419","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366719$B7014C97-8DB9-473A-8892-E68E198D62C7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77df406c66710d2387ea1933c1422407ef2da619","datavalue":{"value":{"entity-type":"item","numeric-id":4362278,"id":"Q4362278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c05dbb357c82da514cab44888a1f7877b31ea9f9","datavalue":{"value":{"amount":"+0.8384762406349182","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":"Q2366719$93DF8608-0E3B-4671-A989-E74CA37A48EC","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":"009cb6247b9fbe8848bba78ce80d20c1b5e33323","datavalue":{"value":{"amount":"+0.8207547664642334","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":"Q2366719$ADABB9F9-9FF3-4CA0-9273-30B18DC6B995","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":"bffaf9d8a5a80952ca988f338022a0b2d669a523","datavalue":{"value":{"amount":"+0.8108988404273987","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":"Q2366719$9F86AEE0-1949-4220-8CAC-6FA9005F58CD","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":"416de9dd16c4296de14aa591d92425c814ccbeca","datavalue":{"value":{"amount":"+0.8081130385398865","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":"Q2366719$3F4183D9-AC6D-4251-95A7-4D214143E1B5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2366719","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2366719"}}}}}