{"entities":{"Q1069701":{"pageid":1080453,"ns":120,"title":"Item:Q1069701","lastrevid":48894739,"modified":"2026-01-06T02:46:15Z","type":"item","id":"Q1069701","labels":{"en":{"language":"en","value":"Communication complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3936521"}},"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":"Q1069701$A9E557E3-E90B-450B-8E24-A66A522CF6DE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f27d471d53f8df006f51b53ae66676a4a7d21d39","datavalue":{"value":{"text":"Communication complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1069701$C17FF6F3-2697-4753-BF63-6BF62EC56A1F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c47506578c2e0d1cf3419e3f92109883ad6e1edf","datavalue":{"value":"0584.68064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069701$F6E0F62B-3936-4567-9B21-64D5D8CC707B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5d2a9e80f08b22bea980d15a00e91a6bef37b0ae","datavalue":{"value":"10.1016/0022-0000(84)90069-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069701$98758969-4CE8-4733-B242-B0D7C810F247","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6cebb39622b69e383ce0b14ff064561e8abcf454","datavalue":{"value":{"entity-type":"item","numeric-id":1069700,"id":"Q1069700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069701$D835A45C-9A93-45AD-B780-A4346169A90A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4703623e4fcbefcd3931d7b75f8faed8c58b1ed6","datavalue":{"value":{"entity-type":"item","numeric-id":222484,"id":"Q222484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069701$C8F14E18-D4EC-4CD2-A9F7-BF730EC6C82E","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":"Q1069701$694DC7C8-C862-48D7-9AC0-7C1D3A0F16E9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q1069701$102372BE-BA34-4C03-8229-A8CC8F08747D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d355549fee128855ed979e6060aadcd589400f54","datavalue":{"value":"Suppose that a language \\(L\\subseteq \\{0,1\\}^*\\) must be recognized by two distant computers. Each computer receives half of the input bits, and the computation proceeds using some protocol for communication between the two computers (obviously, most interesting languages cannot be recognized with any communication). The minimum number of bits that has to be exchanged in order to successfully recognize \\(L\\cap \\{0,1\\}^{2n}\\), minimized over all partitions of the input bits into two equal parts, and considered as a function of n, is called the communication complexity of L.    In this paper we prove several results concerning this complexity measure.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069701$399F8501-C419-45F4-978C-10AE4E8BBE53","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069701$F266C3E7-02B3-4C89-A781-2DA4E54C27D4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f27658e54de1008d34616724d8f9a026aa0d7336","datavalue":{"value":"3936521","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069701$6182EA67-2E7D-4E0B-A6D3-5F4994A04964","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":"Q1069701$DBFDA63F-9B0D-4895-9DFF-2142D4D4309E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7f97e5a597c5de796db6cf99075b629f4804a1a2","datavalue":{"value":"https://doi.org/10.1016/0022-0000(84)90069-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1069701$3F6C207F-B327-4AF6-A5A0-8A8E60CFBB18","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"649330392d5f78efb81bd29922f199128240aa28","datavalue":{"value":"W4211003473","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069701$2B580EAF-0A4C-4555-AF9D-40591ED43C49","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ca4131870a3b5a835a02181541b534e2d87f87c","datavalue":{"value":{"entity-type":"item","numeric-id":3880279,"id":"Q3880279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069701$AD77F66E-FD23-4AA4-A6F4-D9B8ECEA7177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95b43a6c4c4e31e641d94a071098874a458bb3af","datavalue":{"value":{"entity-type":"item","numeric-id":1151751,"id":"Q1151751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069701$3330735E-734D-4421-8861-D323E889DB44","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0371f72a0cbec23d25fe3a49a367f57cd062111d","datavalue":{"value":{"entity-type":"item","numeric-id":3339318,"id":"Q3339318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1e852e571af06680847da7b416d6aca10b0e3dd","datavalue":{"value":{"amount":"+0.8923154473304749","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":"Q1069701$7E1D0BEE-8B6F-4D4F-ACD7-9110CEF7111E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0538e0eb82a88e94d08e36851aed8ca43991ff71","datavalue":{"value":{"entity-type":"item","numeric-id":3216143,"id":"Q3216143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39767e12c7d369d35fa52fe4c396bb10f3c91785","datavalue":{"value":{"amount":"+0.808993399143219","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":"Q1069701$A3061A51-306D-4A79-A7E5-39B7C5CCE534","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"baadbfc8b9141006898e92d1228ea7e80f622d85","datavalue":{"value":{"entity-type":"item","numeric-id":4875692,"id":"Q4875692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5940187e3dce08628a407e39d8166aef78752aff","datavalue":{"value":{"amount":"+0.8023042678833008","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":"Q1069701$39A6F135-07DD-4C43-BD89-15C10B026CCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc0ee0fb6910de1426a43e8611fe7239307c3162","datavalue":{"value":{"entity-type":"item","numeric-id":1097691,"id":"Q1097691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5940187e3dce08628a407e39d8166aef78752aff","datavalue":{"value":{"amount":"+0.8023042678833008","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":"Q1069701$D5A4EC56-21CF-428E-8752-27D7AFFED249","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"628041dd3b0a471241847c16bc797fa10b983359","datavalue":{"value":{"entity-type":"item","numeric-id":4699286,"id":"Q4699286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0aadcf971ba9dd894cf9f7063d317ed0202507ba","datavalue":{"value":{"amount":"+0.800730288028717","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":"Q1069701$29CB1B5C-2392-459D-B417-D62C65057444","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1069701","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1069701"}}}}}