{"entities":{"Q2372888":{"pageid":2383631,"ns":120,"title":"Item:Q2372888","lastrevid":43967853,"modified":"2025-11-18T14:55:02Z","type":"item","id":"Q2372888","labels":{"en":{"language":"en","value":"Information flows, graphs and their guessing numbers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5171577"}},"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":"Q2372888$1488818A-9051-434B-BF1C-83E6BEF75A0B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"300edf85199337ca5271b3ec9f9f52bb577aa624","datavalue":{"value":{"text":"Information flows, graphs and their guessing numbers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2372888$9D0A8D4E-8678-48CB-8414-462FE096E297","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cbc4fb1f4f5559564a497d5b8f48782b6ef98044","datavalue":{"value":"1122.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372888$0424EE62-50E9-4147-9BB8-B6DDCC532380","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b988aafc908ad0705db140a886cbabb24b606a94","datavalue":{"value":{"entity-type":"item","numeric-id":195146,"id":"Q195146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2372888$76680E78-86C1-4AC0-8371-F6E2E07E9537","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2372888$39FCF79E-5276-4D08-9179-A9922ADC7A1C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7e3acd577c56b212087d574010dc1f6e1c3c3b90","datavalue":{"value":{"time":"+2007-07-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2372888$4BC85BDE-0450-4E61-AE6F-91D808364CA4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9b02ad7a7b988ec26ab2a8d37e09567e155b325e","datavalue":{"value":"https://eudml.org/doc/128036","type":"string"},"datatype":"url"},"type":"statement","id":"Q2372888$4083723D-37B5-450E-83F9-0C8DA51749F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"25c91a276f5ec0c5011839a4376673fcafad5883","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_14/Abstracts/v14i1r44.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2372888$EBAF1A98-7F0B-4FF6-BB19-045CA61B3685","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b9699cd93fbb9962266294ceeb7322dc3c3b4204","datavalue":{"value":"Summary: Valiant's shift problem asks whether all \\(n\\) cyclic shifts on \\(n\\) bits can be realized if \\(n^{(1+\\varepsilon)}\\) input output pairs (\\(\\varepsilon < 1\\)) are directly connected and there are additionally \\(m\\) common bits available that can be arbitrary functions of all the inputs. If it could be shown that this is not realizable with \\(m = O({n\\over \\log \\log n})\\) common bits then a significant breakthrough in Boolean circuit complexity would follow. In this paper it is shown that in certain cases all cyclic shifts are realizable with \\(m=(n- n^{\\varepsilon})/2\\) common bits. Previously, no solution with \\(m < n - o(n)\\) was known, and Valiant had conjectured that \\(m < n/2\\) was not achievable. The construction therefore establishes a novel way of realizing communication in the manner of network coding for the shift problem, but leaves the viability of the common information approach to proving lower bounds in circuit complexity open. The construction uses the graph-theoretic notion of guessing number. As a by-product the paper also establishes an interesting link between circuit complexity and network coding, a new direction of research in multiuser information theory.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372888$5F160367-B75C-4BBF-B378-5F60E5C98383","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372888$8901964B-8A42-4922-8C0A-0FE4C2457C05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372888$B03F6B79-1408-456E-A250-C3EA032C96FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372888$B199F802-2F72-4CFF-900B-58B55BC8C033","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23eabea2f37667b79d34f4282bba7b6c227abf51","datavalue":{"value":"94A24","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372888$E9634211-1BF5-4FD8-B32B-B7A8C7C46916","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d2bad082c4eb02b58bfc98612c93258ccc55a2f","datavalue":{"value":"5171577","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372888$643988E3-1254-46B6-8EBF-6E92CD0B5AA8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec87d84b1d26e32ec91444a81fbde15fb6adfa73","datavalue":{"value":"cyclic shifts","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372888$C48E7F6B-0B75-4C46-9D6D-64249D2F2E21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a0544513bdc8f0636dda569851f6b67fd5744ee","datavalue":{"value":"communication","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372888$8C209E5D-71C7-45A7-B8F5-3BEEE384A48B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d78229b0fddceb2b4e2d2dcecc83dbd46f473da5","datavalue":{"value":"network coding","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372888$9571F670-1946-41F2-9162-5DD0430F3E4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a84e7851bbfde7825f2a30e6afb99473d2ec7d2","datavalue":{"value":"information","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372888$6727A4DC-7A9E-4C50-B081-FAF124A5950A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f0cb341ca7876bc8468eee4ea8e9008984980e7","datavalue":{"value":"circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372888$30640A53-B93A-4D70-BEA2-3CCE614FC54D","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":"Q2372888$E2CF6876-EB29-42CD-A8D8-D885035EC522","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"5f8d32332aa0692084c6798acdbda1a66d124a96","datavalue":{"value":"bafkreidtqj7ijt4z363io6cjz5zko4hwf76zgcmzfwrqtkciybtszduqqu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372888$85FC0009-A45D-4FA5-89BF-6FC62FECC688","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b72314be1162d5232be98200ae33e6ef1c0b2bff","datavalue":{"value":{"entity-type":"item","numeric-id":2366011,"id":"Q2366011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbad90ededfeecd38378c243011013f1849b2e31","datavalue":{"value":{"amount":"+0.8768701","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":"Q2372888$8A4F392A-A44D-4C0E-8991-D6E9E196DECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f402013489e95d4f22033bf8eb550a020865364","datavalue":{"value":{"entity-type":"item","numeric-id":3003351,"id":"Q3003351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fa386bafcc2c04fe8ae44768cd9aefda404e753","datavalue":{"value":{"amount":"+0.87139094","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":"Q2372888$F7942393-A8E7-42D3-A08A-E95AA3736490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebc173e5bcf6d37484242a4930104da74add2c71","datavalue":{"value":{"entity-type":"item","numeric-id":3613570,"id":"Q3613570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d81e2a29fb3024c78aad27de7ceb64701382e23f","datavalue":{"value":{"amount":"+0.84994274","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":"Q2372888$0B85F8CE-C62F-49B5-B5F0-686751094B4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80ee8ae9a82aae221adb1174c29379f8e1da1d6f","datavalue":{"value":{"entity-type":"item","numeric-id":3440935,"id":"Q3440935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"277f1d4e2f0ab6f7daa99366a7f9e06f08ef4d2c","datavalue":{"value":{"amount":"+0.84881186","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":"Q2372888$9BFF4E59-C06E-4F0E-9409-0C9B3642383F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abd6b93cf8a7a73ff9c15022ccc002430b392262","datavalue":{"value":{"entity-type":"item","numeric-id":5358568,"id":"Q5358568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d4ff72bcc15e5d03f57b136c6fd6ff1daf152dc","datavalue":{"value":{"amount":"+0.84769017","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":"Q2372888$DA5A9C37-3A76-428C-8844-312D3B37624B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"931b2228c992bb650b54bdc24e7ebff46a983e68","datavalue":{"value":{"entity-type":"item","numeric-id":3100904,"id":"Q3100904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2185d72348dbda127c43899442d3918e3f258f06","datavalue":{"value":{"amount":"+0.84654653","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":"Q2372888$644A4515-A330-4258-AB28-7ECAEB0852FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dccc218051edf89b7302f5915c3602b14dbb640d","datavalue":{"value":{"entity-type":"item","numeric-id":3638309,"id":"Q3638309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9225a72aa8906bfe1697df4184296768cad8b1d3","datavalue":{"value":{"amount":"+0.84575164","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":"Q2372888$AF61AA7F-6CBA-40B7-9226-C1DD5FECAB07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84411478da9c1327c280d163317aaf7fd3035d0f","datavalue":{"value":{"entity-type":"item","numeric-id":4206742,"id":"Q4206742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c70ca65a72ed17a247411320fa2d2edca4a7bc52","datavalue":{"value":{"amount":"+0.8401864","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":"Q2372888$E13DF85F-9483-4776-B2CC-DA6C69661E6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a081173818efd7405653f188d4b636084279de19","datavalue":{"value":{"entity-type":"item","numeric-id":5747946,"id":"Q5747946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"688faae7e55e19fcb6e068ef6887a65509b89950","datavalue":{"value":{"amount":"+0.83951515","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":"Q2372888$E24EE2D4-0897-412B-8B27-69F9DAF34FC5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2372888","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2372888"}}}}}