{"entities":{"Q1106661":{"pageid":1117410,"ns":120,"title":"Item:Q1106661","lastrevid":69656523,"modified":"2026-04-13T08:30:17Z","type":"item","id":"Q1106661","labels":{"en":{"language":"en","value":"The advantages of a new approach to defining the communication complexity for VLSI"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4062570"}},"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":"Q1106661$980E944F-D301-4EF9-941D-171F558D4B1E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3cbb570bfc98d9ba19798fe1b6dbbfad584f471e","datavalue":{"value":{"text":"The advantages of a new approach to defining the communication complexity for VLSI","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1106661$0C911C67-623A-4EE9-B4CE-5646FF203F0F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e78ede54c87d0ba1199aa662253e2d024aecd63c","datavalue":{"value":"0651.68035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106661$125DCB58-3557-4B16-AE51-19F6D76F866A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e99d847e69a671e90650b24a31a0107f4090381d","datavalue":{"value":"10.1016/0304-3975(88)90165-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106661$BB9CC488-CA51-420D-9D98-B87E67000A7A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7330faa8aa9bfbfa602624605066aa6301d76b4","datavalue":{"value":{"entity-type":"item","numeric-id":208754,"id":"Q208754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106661$030C793C-8B7C-43B9-98DA-92C34C72C22D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106661$411177A6-ECD5-4347-A1C2-C81A552C3883","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1106661$7BF0F508-A172-49A0-9210-70FF6AFB8996","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"75f60b0a261e506ffaa16573f6a786d80e23d056","datavalue":{"value":"Communication complexity is a complexity measure which is useful for proving lower bounds on area complexity and area-time squared complexity of VLSI computations. In this paper a formal definition of S- communication complexity based on the idea of \\textit{A. V. Aho}, \\textit{J. D. Ullman} and \\textit{M. Yannakakis} [On notions of information transfer in VLSI circuits. In: Proc. 14th Ann. ACM Symp. Theory Comput. 133-139 (1983)] is given, and its properties are compared with the original communication complexity defined by \\textit{Ch. H. Papadimitriou} and \\textit{M. Sipser} [J. Comput. Syst. Sci. 28, 260-269 (1984; Zbl 0584.68064)]. The basic advantages of S-communication complexity presented here are the following two:    (1) S-communication complexity provides the strongest lower bound \\(\\Omega (n^ 2)\\) on \\(AT^ 2\\) complexity of VLSI circuits in most cases in which the communication complexity grants only smaller (for example, constant) lower bounds.    (2) Proving lower bounds for S-communication complexity is technically not so hard as obtaining lower bounds for communication complexity.    Further, some basic results including the properties of S-communication complexity considered as an abstract complexity measure are established.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106661$0BFBFB9B-BEB9-4A44-9C78-0B83A943E4E0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"633fdcabf2e644e3cc3929da0924cb1d112f41ed","datavalue":{"value":{"entity-type":"item","numeric-id":208754,"id":"Q208754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106661$1982533C-8DB8-4751-A8FE-F6DE3A69BA97","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106661$8143FBE9-3FE5-489D-AB3E-29D5E3CD5798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2d65091154bcdcd55b19c17aadaa169aee2e3523","datavalue":{"value":"94C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106661$DD601CE2-05DD-4517-909C-9D44B074585F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ef6cb2be470b6535f3049256dc1b054dfab51434","datavalue":{"value":"4062570","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106661$A961FDFD-824A-45C4-BC09-A3171ECCBC87","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0062bff246f10874c360cb4d691bf5c2195f236c","datavalue":{"value":"Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106661$F2D218C3-0773-4050-9707-5F0CB6BAFDE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c8a3771d592253533a2e546c05e00722cd3a680","datavalue":{"value":"languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106661$B4DB524F-DFB3-4FDF-B984-F2F7C7C50DAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7f9dea029953fca6ed884e334765fc050bbc0bc","datavalue":{"value":"VLSI computations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106661$BECBC48E-4530-4AD4-AAF1-163C52CB1B50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d59f9270ba2c0b3161162dab212fcc774a42eba","datavalue":{"value":"communication complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106661$1151E597-A800-449D-BC8A-443C64E69272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25df60e3c85cd7cb604ca83b5557e00756af12cd","datavalue":{"value":"VLSI circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106661$4B38D174-43B6-451E-8568-7C5B75846143","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":"Q1106661$5DD91B56-D56A-45F7-B172-52C8991BB1CF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ae4a9af94926badf70eb2cf7639fa06896d4e4b","datavalue":{"value":{"entity-type":"item","numeric-id":3216143,"id":"Q3216143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106661$7E4A2900-BCA2-49C4-BDB2-7F42E7740A0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9de4db290fd523263db35b3c5cf7053c379fc8a5","datavalue":{"value":{"entity-type":"item","numeric-id":3339318,"id":"Q3339318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106661$DDE61A9B-5334-45DE-A639-781AA1698117","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dbe8ba4f9c2d0bcb477d85ce0593f7bd39fe5cf","datavalue":{"value":{"entity-type":"item","numeric-id":1090456,"id":"Q1090456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106661$CFA09F4A-6727-4798-BEFC-940B6F2E7912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"525dd668e08001e4b2c3fca881ad93164bc52ad3","datavalue":{"value":{"entity-type":"item","numeric-id":1069701,"id":"Q1069701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106661$3DFA91B0-3935-493C-9E29-D6CB0C156891","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"48b9e3f398381bed5d352573d685b21603412040","datavalue":{"value":"https://doi.org/10.1016/0304-3975(88)90165-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1106661$88774D9D-A940-4AFC-956C-9EF9332DBEA7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ab67856e85f3dd59dee296db4b0f7aa74108703b","datavalue":{"value":"W1992687353","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106661$04B84E0C-BBD9-4652-B5F4-305915AEA678","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"989694a4823c1695d2204ac85074de2339f2f580","datavalue":{"value":{"entity-type":"item","numeric-id":5966473,"id":"Q5966473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11b40a658d521ab3ce401037f4521679ce4c240b","datavalue":{"value":{"amount":"+0.9995332","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106661$FB74EA4D-826F-4CF0-8145-82F6679095EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f179ca0fd54a455634e3e44dfadbc30ec240421","datavalue":{"value":{"entity-type":"item","numeric-id":3753482,"id":"Q3753482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65f2a81efad2c8662578938a6a06b9670e565423","datavalue":{"value":{"amount":"+0.92553854","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106661$2D3B2415-BB1D-47EF-9D88-44DBF4225AD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fdd4f349d35593fe1de6902fe2f6b1d6efbccfd7","datavalue":{"value":{"entity-type":"item","numeric-id":3979282,"id":"Q3979282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"925ad65993bf4613ed8fced8732011f7a2a3f733","datavalue":{"value":{"amount":"+0.862117","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106661$B7A95B64-D8A7-4F47-8677-2892D7C8B1B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5d5b4bdb2ca4d2a382e829f8db6628574016015","datavalue":{"value":{"entity-type":"item","numeric-id":1090456,"id":"Q1090456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc02f96f6e70aa969b3ef3d0bccb8a728be43a8f","datavalue":{"value":{"amount":"+0.8450815","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106661$4C0ACFBF-5D1E-40C5-8CD8-59D97F6B0BEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"448854d0473ecd5e32b0c0d014cd145d396d8990","datavalue":{"value":{"entity-type":"item","numeric-id":4337605,"id":"Q4337605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5566715e704911cc030cb330f5d334a15585aa53","datavalue":{"value":{"amount":"+0.8392583","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106661$D6948A1C-41FB-42D1-A3A6-BCD834BCB37E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e08e91b06fad5de4f5482cc879c562b47c718ec1","datavalue":{"value":{"entity-type":"item","numeric-id":5203681,"id":"Q5203681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d02a1c5f705a8f2cf4d3dfa5bd3a868072eed047","datavalue":{"value":{"amount":"+0.81856096","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106661$476C63E4-0A1C-47AF-92F0-04201DDBA8E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ed39277d7287fd8695663b8ae59c62027b30076","datavalue":{"value":{"entity-type":"item","numeric-id":3527016,"id":"Q3527016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"329166f191cf5953d189dce4973b493d71a6b521","datavalue":{"value":{"amount":"+0.8181806","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106661$60FC12CD-40E7-4F20-9EDA-C5F359D3FA7C","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":"a2b8cc0f8b8518eb60a14a2403182b04769af6c8","datavalue":{"value":{"amount":"+0.8073725","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106661$C62D72FC-3808-4EFF-8822-5227EC7C793D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b856aee0765baa526ae785b2e4aa41ad1cc4d4a","datavalue":{"value":{"entity-type":"item","numeric-id":3832044,"id":"Q3832044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d41debfbe2802c0283b29a205014deb7720bf0e","datavalue":{"value":{"amount":"+0.8071429","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106661$B6D99662-E5B9-4C4B-963B-DF1F32D3878B","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":"e9ed89b7da8fb07ebe3f9211dcfac9267bbd8d74","datavalue":{"value":{"amount":"+0.80544853","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106661$52F04BC2-0A9B-42CF-9C89-E22A18B1BFFD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The advantages of a new approach to defining the communication complexity for VLSI","badges":[]}}}}}