{"entities":{"Q2176072":{"pageid":2186815,"ns":120,"title":"Item:Q2176072","lastrevid":57759252,"modified":"2026-04-02T10:00:05Z","type":"item","id":"Q2176072","labels":{"en":{"language":"en","value":"Application of the information-percolation method to reconstruction problems on graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7195621"}},"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":"Q2176072$FA956C65-9D0E-48E9-96C3-82CB3C522B9F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"748c5754bffefccebb965b2d822f983731cc8c1e","datavalue":{"value":{"text":"Application of the information-percolation method to reconstruction problems on graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2176072$B9C4A3CB-8BC3-46F0-9D86-8155A8424888","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"78643d1c3ef4d0e4c7dd560071a0cae231763b8f","datavalue":{"value":"1439.05205","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2176072$55C25249-72DA-44F3-982B-7DE1E236D221","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9f6ce80710f3f2f5a4abaa1bdab600b430f71538","datavalue":{"value":"10.4171/MSL/10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2176072$A1550BFD-F380-45C6-969D-EA628AF81CFA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$4CECF040-6B30-4F77-8EFE-24691BD2C94A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dc21fa656a72c5bd4c84cbb6daa1826bf1ab50a3","datavalue":{"value":{"entity-type":"item","numeric-id":778886,"id":"Q778886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$CC4DE66E-467A-4C8F-809C-F0A59C29FCAA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"266349113821a9568dc8e478c029e41016cf97fa","datavalue":{"value":{"time":"+2020-05-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2176072$F50234A6-EB73-44D6-85BF-8A28DB3014CB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"393ecf924f42ed070fd2fa1acd115e9e9abb8a1f","datavalue":{"value":"https://arxiv.org/abs/1806.04195","type":"string"},"datatype":"url"},"type":"statement","id":"Q2176072$8CE37B22-9890-4444-A3B4-531D85A1FCD6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8c710addb09470f685207fe8fc9034c095094ad7","datavalue":{"value":"Summary: In this paper we propose a method of proving impossibility results based on applying strong data-processing inequalities to estimate mutual information between sets of variables forming certain Markov random fields. The end result is that mutual information between two ``far away'' (as measured by the graph distance) variables is bounded by the probability of the existence of an open path in a bond-percolation problem on the same graph. Furthermore, stronger bounds can be obtained by establishing mutual information comparison results with an erasure model on the same graph, with erasure probabilities given by the contraction coefficients. As applications, we show that our method gives sharp threshold for partially recovering a rank-one perturbation of a random Gaussian matrix (spiked Wigner model), yields the best known upper bound on the noise level for group synchronization (obtained concurrently by \\textit{E. Abbe} and \\textit{E. Boix} [``An information-percolation bound for spin synchronization on general graphs'', Preprint, \\url{arXiv:1806.03227}]), and establishes new impossibility result for community detection on the stochastic block model with \\(k\\) communities.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2176072$845F09C1-BE6A-4648-AF0C-C7238ACA29CC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2176072$7F5325E3-3BDA-4828-A813-3B41617ABDD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2176072$01A13500-DB58-4B70-AED1-B7DC06313CB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"99e75c38935b147cca2a0eac1e86993c645e76a5","datavalue":{"value":"94A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2176072$CCCA07DB-3729-4CF8-A512-EF7F35960011","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e1f144a9ab7064f6f8c78503075f6cd455ea06f6","datavalue":{"value":"94A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2176072$E7A1AFC1-8DB3-4786-BE09-E9115B70BB70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fedc54d041dbaf3922f156ba09e5514c44ab5169","datavalue":{"value":"60E15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2176072$FBEA3B47-4404-43FB-97F9-7B002CBC2015","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5a29947dc7037bb9dff759d92a19fb25fba943bf","datavalue":{"value":"7195621","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2176072$9C9482CD-1410-461B-962C-3A4AFDE967AE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"763154b34e4784df1ab77b9a4835ff1d981d63b1","datavalue":{"value":"information-percolation method","type":"string"},"datatype":"string"},"type":"statement","id":"Q2176072$9209A8CB-7E9A-4DAA-A591-C92D810626A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3331d9bce38ccbf34966a1b1bf1124a107974f9b","datavalue":{"value":"strong data processing inequality","type":"string"},"datatype":"string"},"type":"statement","id":"Q2176072$ED914D2F-91A7-45E3-B10D-0CE77D993D62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c835bdcb30541aebb9f147a28e6b0b223dd6c8c","datavalue":{"value":"correlated recovery","type":"string"},"datatype":"string"},"type":"statement","id":"Q2176072$C669B1C1-41D0-4064-93C2-3EF9C91D33EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1df9b3a6ce8f0d135ffb2ce79170b8bae1d00cf","datavalue":{"value":"group synchronization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2176072$9B1E055D-BE65-457F-89B7-1274A8991F73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d7db2ee8bcb6619dc340b1da1317f7fbda248b5","datavalue":{"value":"community detection","type":"string"},"datatype":"string"},"type":"statement","id":"Q2176072$9048C28B-00C6-4895-A4E3-969D8CEBB183","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc3c751a510e64df2bcc3fecc9ec6b3e4eb71bc2","datavalue":{"value":"spiked Wigner model","type":"string"},"datatype":"string"},"type":"statement","id":"Q2176072$82D49875-FDD6-47FE-B238-2EFD333BD3EE","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":"Q2176072$373EE15D-1D76-4D0A-88CE-2BC9BB8D147C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"354cc3fe69d23e389c48ba48571034bf0dfcafac","datavalue":{"value":{"entity-type":"item","numeric-id":2657904,"id":"Q2657904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$399720A6-42CF-4D6A-BC23-33B2D7D27AC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20e379e3641a11618d2863606b15f56ca2e0865e","datavalue":{"value":{"entity-type":"item","numeric-id":2319814,"id":"Q2319814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$FE3BD325-EEAB-4972-B2CA-C0FD8C549A8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ae000096e5ef685fe9b59d423a301504ae15065","datavalue":{"value":{"entity-type":"item","numeric-id":5674726,"id":"Q5674726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$21A5DDC3-3B23-4A84-A8FC-DB695B64D867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"633dce7da2e78d009da70fd9e3de8a42f0398f86","datavalue":{"value":{"entity-type":"item","numeric-id":2571691,"id":"Q2571691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$52D20BBC-8D63-484B-81C0-E479009BBC39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30946780fa62dddbdf88dbcb6d8ea0c424c52769","datavalue":{"value":{"entity-type":"item","numeric-id":5737389,"id":"Q5737389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$190BD6EE-974D-4593-9DF4-B4CC4E0BE19F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"763e3905bf47dfe4b400832ecce38198b0d97320","datavalue":{"value":{"entity-type":"item","numeric-id":5490912,"id":"Q5490912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$3E8627C3-4916-43DC-B4E3-11EEDED2B19B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57c708286be8463b4d3afdae2234b7fac90aaec4","datavalue":{"value":{"entity-type":"item","numeric-id":4603702,"id":"Q4603702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$78DE50AA-A2DF-4094-8532-10B42D1F4389","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40de01926036155724ea5a49a06019ca24fee4a0","datavalue":{"value":{"entity-type":"item","numeric-id":1884823,"id":"Q1884823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$FF218F16-E9F3-4B0A-A5FC-95BC6919B799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3773037dea3e939aa7c7d0aa5d3e24ed7248066b","datavalue":{"value":{"entity-type":"item","numeric-id":4503491,"id":"Q4503491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$2E59B147-7F82-4F60-BB71-5F3C55195B32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$9DEA64C2-3064-401B-B79F-84626ECBE588","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63c03b9341ac7f089a612075af0c304fa252dc1f","datavalue":{"value":{"entity-type":"item","numeric-id":1143063,"id":"Q1143063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$7200C884-2FD3-44E7-8EF5-4C5C3E8FE630","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e6a58cd67c67291dd840e01cb2f07f9d4dc276d","datavalue":{"value":{"entity-type":"item","numeric-id":4135390,"id":"Q4135390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$B279374D-31D0-477F-AC32-8499C06E5E85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5122fd1fadd10740405bc45b41ee61c246cbc1bf","datavalue":{"value":{"entity-type":"item","numeric-id":3970911,"id":"Q3970911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$12604E96-352E-4410-8D86-06517CBEB308","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71e93dd6502005fafef28f23875e521640e931cb","datavalue":{"value":{"entity-type":"item","numeric-id":1715062,"id":"Q1715062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$6E5D21EA-36B9-45FB-AC5D-EA9F1E9D8D39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"929fd3acf6dd1949ed14844dd510b2cc27567c65","datavalue":{"value":{"entity-type":"item","numeric-id":495549,"id":"Q495549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$2819AD88-D64A-43E3-BAF8-ABF71750A4F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ed40eca12f335959542665259e220c7bc763314","datavalue":{"value":{"entity-type":"item","numeric-id":4682871,"id":"Q4682871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$B19CC722-E32D-4F98-A912-68AC4B83D297","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a479401e6427303ca29acc3f57ac0dc2e738add","datavalue":{"value":{"entity-type":"item","numeric-id":2977032,"id":"Q2977032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$13039123-C175-464E-BD62-E3DFC239955A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"505e7faf946907a6bdfdd6768c1c01872f8cfd19","datavalue":{"value":{"entity-type":"item","numeric-id":2406343,"id":"Q2406343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$F0D017CB-88E8-45C3-91A6-487FD0244B29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39db246bd359f3695f9989644661cb049465c3ba","datavalue":{"value":{"entity-type":"item","numeric-id":3503427,"id":"Q3503427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176072$F2768E31-9E45-4394-9BA7-F91661E2EB71","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"793a03c6a516739f035f0fa38df253cb9f0f08fe","datavalue":{"value":"W3008067046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2176072$D24489DA-E5DC-4519-A7D6-607DF26B3926","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"790a24575d0b2829c977ea3ad00dd1abb772cea6","datavalue":{"value":{"entity-type":"item","numeric-id":2657904,"id":"Q2657904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2505cc8f9b491577348e432206dec6bff97a47be","datavalue":{"value":{"amount":"+0.832359254360199","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":"Q2176072$8B594F10-E298-4319-826E-5CA2F5674485","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2dff1b9c4612e9ec19045a32ef7b7ff36d08673b","datavalue":{"value":{"entity-type":"item","numeric-id":1740590,"id":"Q1740590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b8763c0c841bc9c7e244802d548960045df2cea","datavalue":{"value":{"amount":"+0.746533215045929","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":"Q2176072$ECB38116-94BA-4494-A0FD-7E0EF42EAA24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b87b26c2b04f7e96fed75816549335f6efc20778","datavalue":{"value":{"entity-type":"item","numeric-id":4603702,"id":"Q4603702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bdefe5d67abb38563657b12f95d2a27cc347268","datavalue":{"value":{"amount":"+0.746240496635437","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":"Q2176072$2A61E8AF-D8EF-4ECC-9E33-C8863C42334A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2176072","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2176072"}}}}}