{"entities":{"Q1853071":{"pageid":1863813,"ns":120,"title":"Item:Q1853071","lastrevid":73896978,"modified":"2026-04-14T17:39:33Z","type":"item","id":"Q1853071","labels":{"en":{"language":"en","value":"Improved bounds for asymmetric communication protocols."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856411"}},"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":"Q1853071$B0CEF7A7-109F-48FA-8B1B-B25114776874","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"60f3e39cb0fb1a8d537b1b685d7d115513d24f0c","datavalue":{"value":{"text":"Improved bounds for asymmetric communication protocols.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853071$4C6E5B8D-4A75-424C-A6CA-586E541E53EA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f9cfbbefc6f99f5abe44925031ca34b9cc2ac0c3","datavalue":{"value":"1043.68015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853071$2CBBF4E7-9D6B-4E0B-904B-2D82EE23FBEC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6947dad2fedc31a0a1df3312d4b3170e58c8cacc","datavalue":{"value":"10.1016/S0020-0190(01)00332-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853071$4BC522B8-F278-4D0C-A9CA-7D0F4D02E8CF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"96c336c47481eefdf3bf8537c9af3521411ea42d","datavalue":{"value":{"entity-type":"item","numeric-id":935153,"id":"Q935153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853071$454E28F6-73F4-490B-ADC0-B154859C0433","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"72d004d81098c2d1577ebc1fd4b3c0c27efac079","datavalue":{"value":{"entity-type":"item","numeric-id":1853070,"id":"Q1853070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853071$1F3F785A-A38F-4542-818E-107F890D7ED9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853071$F4373B9D-E809-4D9E-97E8-5E3F9006AF83","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-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":"Q1853071$15969B92-2A0D-4FE3-A2FA-1928388E8036","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"09976610054ec28cf4962c023f3dfc9b95d7f28f","datavalue":{"value":"\\textit{M. Adler} and \\textit{B. M. Maggs} [FOCS'98, 522 (1998)] introduced some protocols for asymmetric communication channels. For one of them, the ``computational efficient'' one, they prove that the expected number of bits sent by the client to the server is at most \\(1.71H(D)+1,\\) where \\(H(D)\\) is the entropy of the distribution of probability \\(D\\) maintained by the server. In this paper, we show that their protocol is much better. In fact, we prove that the expected number of bits sent by the client is at most \\(H(D)/(\\log_{2}3\\frac23)+ 1\\approx1.089H(D)+1\\). We also argue that this upper bound is tight in the sense that there is a distribution for which this protocol does not perform any better.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853071$5A16DCC8-BC55-44AF-9A3F-979AA9BE5D0D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f100e7e9b912dd320a0f918ece3ef4edbbe567fd","datavalue":{"value":"68M12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853071$1E55324D-A391-4B4C-AAEF-54D77EAFEBE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"99e75c38935b147cca2a0eac1e86993c645e76a5","datavalue":{"value":"94A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853071$D1815B1B-F6EC-4BE8-AE58-0957556779B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23eabea2f37667b79d34f4282bba7b6c227abf51","datavalue":{"value":"94A24","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853071$FAE44DC5-60F6-43E0-A913-9B4DC32238CA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6560c61c5f719727f678ae6c015fd4d879002c9c","datavalue":{"value":"1856411","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853071$22C73760-BD1A-4428-BA40-C001F6CED855","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a362ce090b25a564d589edc558e4bd1266d9df9e","datavalue":{"value":"Analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853071$5FE8B8D1-FF0E-41FE-AAC6-F3D18ACEBF9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b34200cd77e653898b1e569b4c9af222b1b3dbd5","datavalue":{"value":"Asymmetric communication","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853071$44C6AB5C-EF4B-4D2B-AA88-AFE69F0C4735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2cef510bf0fceaee7845effcc15dbe0738e4462","datavalue":{"value":"Data compression","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853071$97F8A001-CDA8-49B2-B30A-3F843549725D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"543fe15d17bc913a167932361796358a40a4406b","datavalue":{"value":"Wireless networking","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853071$5F09D132-51F3-40C1-8C0B-0CE98440FBD5","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":"Q1853071$725169D9-13E7-401E-9148-A44705BA3F7D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"031221cd0777491011b7dbf54a39aeedcf02257b","datavalue":{"value":{"entity-type":"item","numeric-id":1604209,"id":"Q1604209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853071$A9092F42-2086-4654-B65A-4FD862F38C34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f51ab68fb93638e8648c08fc21c5c749fc87f3e4","datavalue":{"value":{"entity-type":"item","numeric-id":5510070,"id":"Q5510070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853071$163004F0-B5A3-409E-8B54-FBB75B5B1996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78f0cf2b8270f6087b7bc3862da42dbac9e1bf1f","datavalue":{"value":{"entity-type":"item","numeric-id":88168,"id":"Q88168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853071$62F71071-9835-4D8F-9D96-3F2A0941BC19","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"023f9463e91bee6ed534af540e3fb2f2600875ba","datavalue":{"value":{"entity-type":"item","numeric-id":2741453,"id":"Q2741453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02a1c15678f24e314f682a153a45566df8a88aa0","datavalue":{"value":{"amount":"+0.9789666533470154","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":"Q1853071$D304769F-6D8A-4606-969B-E4B3F8F67952","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95863ad1bfc51f1d99c9a375186e9fe5dcc4fd5d","datavalue":{"value":{"entity-type":"item","numeric-id":1604209,"id":"Q1604209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af1bc7522334c7b5760799559d87764fce9d37ae","datavalue":{"value":{"amount":"+0.9032703638076782","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":"Q1853071$9EA3EA4B-032E-4BB0-9AC2-3D4C33CB93B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0afe78bb81eb0a9781f4835d84390ea3a3a07c2","datavalue":{"value":{"entity-type":"item","numeric-id":4234056,"id":"Q4234056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af1bc7522334c7b5760799559d87764fce9d37ae","datavalue":{"value":{"amount":"+0.9032703638076782","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":"Q1853071$0E2C998A-BF52-4066-A827-AB1922045434","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d558a6a199c7ff6cdc1323b9abbcaf59f2276a16","datavalue":{"value":{"entity-type":"item","numeric-id":3613660,"id":"Q3613660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba2e22064c0f7b930b96cce1ac1f82834bc86c27","datavalue":{"value":{"amount":"+0.8250908851623535","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":"Q1853071$6E9CC06B-CF89-4B06-8822-7748332A48FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c1dbb50d719eb40e1179da8dac587b69af9786a","datavalue":{"value":{"entity-type":"item","numeric-id":975489,"id":"Q975489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98cc08d44cbd65106ac92baed54a7cad3b2de384","datavalue":{"value":{"amount":"+0.8148223161697388","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":"Q1853071$23082B98-4606-4EFE-A0E3-8978E10165E8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Improved bounds for asymmetric communication protocols.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Improved_bounds_for_asymmetric_communication_protocols."}}}}}