{"entities":{"Q5966473":{"pageid":8143269,"ns":120,"title":"Item:Q5966473","lastrevid":39871754,"modified":"2025-01-27T19:24:03Z","type":"item","id":"Q5966473","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 4062585"}},"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":"Q5966473$77E96A23-E1F2-4728-8D81-5F1DD5CD4364","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":"Q5966473$36C6BCB8-156B-4EC3-9AD7-9B9480D986AB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"49545e2c9e8d4575fb1fd5b691e450d1387ee26d","datavalue":{"value":"0651.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5966473$A3307A3D-BA3B-4206-9543-A086302CF847","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":"Q5966473$56A78169-2484-4C0E-A5E9-14FAC3F7C171","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":"Q5966473$31C147C6-6404-4190-9244-5B1DB135F833","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":"Q5966473$9B1E6262-CB40-4AFC-BC0B-8BA797A9F9E4","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":"Q5966473$C74C6395-30A8-461A-87E6-607899039B55","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a985600a6e202ca722beaf9fb52b9604ac8876c9","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":"Q5966473$6B136310-9CB8-4B95-9112-26755E79E164","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":"Q5966473$0EECD4ED-E98C-46BF-84A7-046BC486A7E7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5966473$6F4EF80E-217A-4EC6-B968-C6C948F265E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2d65091154bcdcd55b19c17aadaa169aee2e3523","datavalue":{"value":"94C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5966473$B3EC98C0-09DF-49F6-B8AE-E1F345B8E81D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"51c3e0e92a9268af473c62b71b413ce20bbd00ca","datavalue":{"value":"4062585","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5966473$9AD4FCCD-6BD8-4D4B-86C8-459A47EA4BD1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0062bff246f10874c360cb4d691bf5c2195f236c","datavalue":{"value":"Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q5966473$EFEA7360-C462-4599-8656-2192B530F29E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c8a3771d592253533a2e546c05e00722cd3a680","datavalue":{"value":"languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q5966473$5E8E5F1B-FE76-482D-8750-A0C1C294A2FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7f9dea029953fca6ed884e334765fc050bbc0bc","datavalue":{"value":"VLSI computations","type":"string"},"datatype":"string"},"type":"statement","id":"Q5966473$62FD03EC-319D-4359-95B9-08A2076D68B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d59f9270ba2c0b3161162dab212fcc774a42eba","datavalue":{"value":"communication complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5966473$3F9948A8-672A-4454-8FBA-4773A89C30DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25df60e3c85cd7cb604ca83b5557e00756af12cd","datavalue":{"value":"VLSI circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q5966473$CC460101-BC3D-4E75-97A8-E979085208C7","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":"Q5966473$07F32A47-8243-4437-B56D-41BBB9DA7301","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":"Q5966473$DDA969D3-1ADE-410C-911E-C785832802E0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ab67856e85f3dd59dee296db4b0f7aa74108703b","datavalue":{"value":"W1992687353","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5966473$016756C2-F6C8-41E9-A54F-1650065AD855","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72eb4094ce890f04d3ab9ba569a4fe2b7d1962ab","datavalue":{"value":{"entity-type":"item","numeric-id":1106661,"id":"Q1106661"},"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":"Q5966473$51E2C6B7-9B67-4640-876D-34E948A3410D","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":"975a45bf32bf2084f927516adb9a3490664665dd","datavalue":{"value":{"amount":"+0.92617863","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":"Q5966473$44C021BB-821F-4088-9649-722D9A6EE23C","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":"9956513acc50c0e49d7674309669a98533689fbd","datavalue":{"value":{"amount":"+0.86539614","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":"Q5966473$0C89845E-76AF-47A4-B637-B8B8075C9B3F","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":"11b8bc2e8ae4f4330b331f3c408afef2bb83f6c3","datavalue":{"value":{"amount":"+0.84794927","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":"Q5966473$23EB167B-0122-4C53-84C1-5EBEE7C52EC3","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":"f99fa4a648e9c3cecfce9e058b46c04cb76a09d3","datavalue":{"value":{"amount":"+0.8438369","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":"Q5966473$D8CDD86A-867D-470A-BB9C-18EDF55AEC86","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":"e788f977bf556fb4ddaf3b0ab21631554966c64c","datavalue":{"value":{"amount":"+0.82232445","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":"Q5966473$BD028BB7-F857-4D2A-AB6B-0E5F830658C8","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":"430171fcfe6cb2e80fa47f521e453dcd502ced57","datavalue":{"value":{"amount":"+0.82150626","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":"Q5966473$51BCCCD2-4500-42DF-B312-5F25F4736DDE","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":"5827e5623ee03ed2294213f5a29cfece680872ff","datavalue":{"value":{"amount":"+0.8118034","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":"Q5966473$33C5D689-EC89-4E6D-AC72-FEEA30035234","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":"7958038b5e90efd7a04b88a699ef321c3e07c892","datavalue":{"value":{"amount":"+0.80869955","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":"Q5966473$955D7376-5303-472A-891C-6C1757B9FC35","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":"4aec8237b2e5ad3381d6a1e604a5bfd86650f816","datavalue":{"value":{"amount":"+0.80816305","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":"Q5966473$95371326-F614-43B0-8DA3-6DF0ED0E10B2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5966473","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5966473"}}}}}