{"entities":{"Q1116337":{"pageid":1127086,"ns":120,"title":"Item:Q1116337","lastrevid":69678789,"modified":"2026-04-13T08:39:45Z","type":"item","id":"Q1116337","labels":{"en":{"language":"en","value":"Bit complexity of order statistics on a distributed star network"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4088929"}},"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":"Q1116337$48F2B984-A1D8-456C-A28C-46D7560388BF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"111e6607de221e7988f62bc2ebe4301e9aa74c63","datavalue":{"value":{"text":"Bit complexity of order statistics on a distributed star network","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116337$7D666255-E69D-4F44-99AC-51F658AEC02E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dece7f7bbea565a6f7c371583ac4faca1b757fc4","datavalue":{"value":"0665.68035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116337$F1C9E391-9085-4602-B8F8-187920964A02","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d7f018e110dbfb02f7300d768bc7abde1ac4d26e","datavalue":{"value":"10.1016/0020-0190(89)90130-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116337$3B4B364F-32CA-4ECB-8319-0ED8DFF46266","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":"Q1116337$8B4E1F11-A563-4484-B63B-01790798F5AB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1116337$BAA7AE90-62C5-4A73-9425-485F2365806F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"70824cf5916f2cdc162b18acd6efcd886f351b6f","datavalue":{"value":"We study the bit complexity of order statistics problem on an asynchronous distributed star network. We prove a lower bound of \\(\\Omega\\) (N log(LN)) bits for the k-selection problem, and lower bounds of \\(\\Omega\\) (N log(L-N)) bits for the problems of sorting and ranking. For each of the problems we introduce an algorithm that achieves that bound, thus showing all bounds to be optimal.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116337$EEA572CE-4FA2-471C-BB77-44D2331D3137","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116337$8F85027F-066C-410E-AB62-DA3C4879A856","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116337$31E9EF76-64A4-49AA-B606-965287333ABB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"517ace4a4f9c45a5475b4a8927a567447dbdb293","datavalue":{"value":"68N99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116337$26255708-EA55-498B-A7B4-B6A92D68F791","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"02d9ea453a2272b5e3ea5fdc291bc4d54ff06801","datavalue":{"value":"4088929","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116337$F0D111FB-E9F6-41BA-A461-19E1DFC457F6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0df094ce3faeec3bf0d6f63dfdd884491bce6fd1","datavalue":{"value":"bit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116337$9289D1A3-9769-44E3-918F-B757B6541C56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f270b8fd909db317ff4cd9e23d79b92775eea97","datavalue":{"value":"order statistics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116337$F64BDF9F-7C4F-4E1B-A89C-BDC31E4880CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5343612323276386e446201efe3bef4b2a32fcbe","datavalue":{"value":"asynchronous distributed star network","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116337$F978F467-6A94-4584-848C-B123D74D5CBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116337$9121C728-931F-4BFF-A5A2-994998AD9975","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54ab622f1d5d207327b01a43f7021cc5ea6aba5a","datavalue":{"value":"selection","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116337$A6C2F97D-7CA5-4273-928A-9EFEA7B867B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f11a697ca4320b2c5e334107aae45a37f7f8f8b","datavalue":{"value":"sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116337$0C9060AD-75ED-4BD7-9792-E004027BB081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4df73210227f5dfce7acc604ba8e77684da5f9d","datavalue":{"value":"ranking","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116337$B2CE6C11-B83F-48C3-83FD-BE0BAA260C8D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c158b14b86655d812820d865cf0f41dd9afcaea5","datavalue":{"value":{"entity-type":"item","numeric-id":1392533,"id":"Q1392533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116337$27DBABAE-85B3-4963-9EA8-1F78A3DA2FE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0fa357464d74acb9975fa4cd05187c5de744d8ff","datavalue":{"value":{"entity-type":"item","numeric-id":222241,"id":"Q222241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116337$C5E8246A-5791-405D-BEB4-995FD6B7656C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8871c12729fed1d4bf381166cf66ccf0277566b7","datavalue":{"value":{"entity-type":"item","numeric-id":248937,"id":"Q248937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116337$E1822267-9AC4-4688-B2DC-5C4E79938E6D","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":"Q1116337$3D8A1ADA-29C6-4891-82BD-252331D76340","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ec4a48c41221127e8661475f0f9bde73a09a5cf6","datavalue":{"value":"https://doi.org/10.1016/0020-0190(89)90130-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1116337$32076B31-4ED0-4027-B78D-472A203384C1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0abb43c4ac42a50a552edc95d1207ae95cfe0bbe","datavalue":{"value":"W2036481673","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116337$DD300660-392D-4F72-BD2D-04B4646887DD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1a3bb5aaa93bd510002b7307f514fc203c878be","datavalue":{"value":{"entity-type":"item","numeric-id":1361409,"id":"Q1361409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116337$0D8975CB-5933-4DC2-8692-1E990D8CF334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a9da85054d2821602679be82fa6c35a9a0339db","datavalue":{"value":{"entity-type":"item","numeric-id":4745251,"id":"Q4745251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116337$211CB07C-D824-4397-801F-1FC2D01ACF6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19e09c304c463a3485fb723778b073d9e62ccdab","datavalue":{"value":{"entity-type":"item","numeric-id":3718163,"id":"Q3718163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116337$6C9B48F9-FF59-4691-9D2B-B001F52F176E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50b0b1f7b850a51b611a8c5ec1ca0529f9a69d6b","datavalue":{"value":{"entity-type":"item","numeric-id":3219775,"id":"Q3219775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116337$19D9D56D-1543-4863-8289-3915BD3741AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07eb396120a155c6dd4e5ef690529cf04d51d764","datavalue":{"value":{"entity-type":"item","numeric-id":3219776,"id":"Q3219776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116337$3D95BBFC-DE80-42BD-8A62-4802EEC3220A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09b34949bda14d3f95edcee387f8574b33a7fa37","datavalue":{"value":{"entity-type":"item","numeric-id":1361409,"id":"Q1361409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06580f678d1ac99d742228953c82004f60fc0264","datavalue":{"value":{"amount":"+0.8707885","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":"Q1116337$6CDCB67E-EAD6-4CB3-93D8-725DC6574262","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"119ae49d8df2ff84a0096dd355db8256d2e63d5a","datavalue":{"value":{"entity-type":"item","numeric-id":673528,"id":"Q673528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"732d4004e8781e74be7fbac7a62725f4dbd3ae80","datavalue":{"value":{"amount":"+0.85829204","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":"Q1116337$B860DEF2-EF1F-4E74-A4A9-7F9814BDC18F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9711e4d5635a4ccb13ca4d4d38d12d407016e79","datavalue":{"value":{"entity-type":"item","numeric-id":2382670,"id":"Q2382670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27cbc9378d9ed248202329efb05c52771c7f7d1c","datavalue":{"value":{"amount":"+0.85434955","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":"Q1116337$97712F29-3314-4C53-A3E4-4EDDC4295826","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63c2a6206a0a9fda77c68417f7ff2b297138002b","datavalue":{"value":{"entity-type":"item","numeric-id":5710078,"id":"Q5710078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27cbc9378d9ed248202329efb05c52771c7f7d1c","datavalue":{"value":{"amount":"+0.85434955","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":"Q1116337$72008EC6-D6F8-48F8-910D-605D1D2228BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a810885e4dfc2a3ddb3df03b4a5e8197fb9c46d9","datavalue":{"value":{"entity-type":"item","numeric-id":5690734,"id":"Q5690734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb6033b90612519051d2f7af1014b03578e0c7f1","datavalue":{"value":{"amount":"+0.8527013","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":"Q1116337$D72EA565-3487-481F-BCFD-68D2B935201D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3c95bbb67b4976a192ed4b7a7792efc85618867","datavalue":{"value":{"entity-type":"item","numeric-id":6092455,"id":"Q6092455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c2c0673d457b286af62cc84fe19c4512fec8b9e","datavalue":{"value":{"amount":"+0.84253716","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":"Q1116337$54E00924-8C52-4540-B217-B9C2BDAAFBF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e73e0a9424126397c34f14a8a5571531a65dce2c","datavalue":{"value":{"entity-type":"item","numeric-id":1003763,"id":"Q1003763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0e5ec69b3e1069423840ab48cdf863888a43f5f","datavalue":{"value":{"amount":"+0.8401897","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":"Q1116337$E7D7F5F8-916B-46BB-B728-23251CEFC70B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b6e33ba61189465e885ec28e3c995a04a2136ef","datavalue":{"value":{"entity-type":"item","numeric-id":5897565,"id":"Q5897565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0e5ec69b3e1069423840ab48cdf863888a43f5f","datavalue":{"value":{"amount":"+0.8401897","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":"Q1116337$C9C71983-B99B-42A0-8BEA-44E1E9AC1135","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"957e4b8e8b9d38e56030473850fb443f993fbabe","datavalue":{"value":{"entity-type":"item","numeric-id":3766832,"id":"Q3766832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec846265d4c5f2fedd42fc5824b70afa4336be54","datavalue":{"value":{"amount":"+0.8336164","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":"Q1116337$3001CAEA-75C6-498F-BC61-9EF5DF7C067D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cba56d0e71ddc8f420810c17aabed5d9b0ad415","datavalue":{"value":{"entity-type":"item","numeric-id":658666,"id":"Q658666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4291e6f4fb5bfb2168f9cceca91df62304e57f0","datavalue":{"value":{"amount":"+0.8327687","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":"Q1116337$D5EBDC5B-403A-4666-9912-273A9B7E0540","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bit complexity of order statistics on a distributed star network","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bit_complexity_of_order_statistics_on_a_distributed_star_network"}}}}}