{"entities":{"Q1889794":{"pageid":1900536,"ns":120,"title":"Item:Q1889794","lastrevid":73711767,"modified":"2026-04-14T17:00:23Z","type":"item","id":"Q1889794","labels":{"en":{"language":"en","value":"Robust reconstruction on trees is determined by the second eigenvalue."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2121709"}},"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":"Q1889794$09F5DB60-3ADE-47D6-8CCD-860972596948","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"51af6658f306f75f79ceb35381a75e86f525cff1","datavalue":{"value":{"text":"Robust reconstruction on trees is determined by the second eigenvalue.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1889794$181B9190-C7D8-4D30-BFA7-C236938E4F39","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"832a9b033eeee5505d1ce1e27be5ad9ea8b45725","datavalue":{"value":"1061.60105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889794$7DC1BDF0-2FCE-4A18-9F33-641A3E30F89E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4ed6cbe6ed40ae3aaa59c8f3d2dccf711796b2a5","datavalue":{"value":"10.1214/009117904000000153","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889794$F35C4DE2-A702-4E29-88F8-7904BC1ACC55","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"069e814aa734681bf0a12485160cdb2936fe3e2f","datavalue":{"value":{"entity-type":"item","numeric-id":173690,"id":"Q173690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$1C088DF9-4994-4059-82A0-A86C32777EDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"95e03469b8abf1198e8e71d89e5f9540ea9718d3","datavalue":{"value":{"entity-type":"item","numeric-id":185102,"id":"Q185102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$A9BE87D0-533E-44B0-AFA2-5AE065449E4C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c9d829dece3e2d330deed49a6cb836edc666e294","datavalue":{"value":{"entity-type":"item","numeric-id":107063,"id":"Q107063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$4011FC76-21F5-4B0C-BE17-0D75D97694DA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fa61d181691a9ecdfcfb7ceb5c61a6e0332f304","datavalue":{"value":{"time":"+2004-12-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1889794$81C84022-B794-4B76-9066-32A528B31C41","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c08daa03c9c7a38569616ff4a70468d4b629b7a7","datavalue":{"value":"https://arxiv.org/abs/math/0406447","type":"string"},"datatype":"url"},"type":"statement","id":"Q1889794$A0853D51-6775-4C62-A4EE-3586351B537E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f08bb21d5aaffa5267f7def45f3977faa29ec813","datavalue":{"value":"Consider a process on a tree \\(T\\) in which information is transmitted from the root of the tree to all the nodes of the tree. Each node inherits information from its parent with some probability of error. The transmisson process is assumed to have identical distribution on all the edges, and different edges of the tree are assumed to act independently. The basic reconstruction question is: does the configuration obtained at level \\(n\\) of \\(T\\) typically contain significant information on the root variable?  The problem of robust reconstruction is studied. Roughly speaking, the reconstruction problem is robust-solvable if for any noise-rate and for all \\(n\\), the \\(n\\)th level of the tree contains a non vanishing amount of information on the root of the tree. It is proven that the reconstruction problem for a \\(B\\)-ary tree is not robust-solvable if \\(B| \\lambda_2| ^2<1,\\) where \\(\\lambda_2\\) is the second largest (in absolute value) eigenvalue of the Markov transition rule matrix. A similar result is proven for general bounded degree trees, where \\(B\\) is replaced by the branching number of the tree br\\((T).\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q1889794$B48C67C4-9F44-4062-B83F-7D9516849EC3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"7fdc23c20020356aaedd36d12d09aa94bd3b098e","datavalue":{"value":"60K35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889794$B78BE679-1B99-4C6C-98E2-3DEEBA847A72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d01ee9b98008029475379a23ca14bb199f2954e6","datavalue":{"value":"60J80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889794$0C1D3A95-41A0-4AB3-A307-2637A94C40CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6270beb3f138de18bcf9496281086bec933669ba","datavalue":{"value":"82B26","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889794$4C807BF1-81FE-4820-A480-2A7EDA90417E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"65baf021878ad0f79b1f3fb058de8fc1fd7f4031","datavalue":{"value":"2121709","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889794$086F020F-2ECD-4BE1-B954-B19332027447","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd1e27e17747c35dc73c3ceae4a52bce80e48430","datavalue":{"value":"robust phase transition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1889794$1FB7AE1C-F31A-4B1F-B2AC-8A08163C8C63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15f2bcb1232d73a9e7b64a15f97aa707749ca7d6","datavalue":{"value":"reconstruction on trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1889794$C16D8C78-F28C-4D99-8B6C-98B32EED1E96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a82374348f60c5d0a4cc2d3283e546d208219a3b","datavalue":{"value":"branching number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1889794$F088C8CD-3087-4E89-90F6-A036C01025A0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"aab34de99cdb77ce7db71ccd425ea17ee50a1403","datavalue":{"value":{"entity-type":"item","numeric-id":590126,"id":"Q590126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$D560ECDB-DA1C-4381-844D-B3E53908105B","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":"Q1889794$73FF1C35-9ACC-4F3D-868B-2BEA33A4C547","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ba505207d5a90247f1d3d785e4089e8e63cf3333","datavalue":{"value":"W3102586875","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889794$8B611542-143A-49C7-91F7-48950DCA3543","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"78bd3a7c164c07ad0c9a81b6dff532926f3a9a46","datavalue":{"value":{"entity-type":"item","numeric-id":1780979,"id":"Q1780979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$91D59A68-44BA-428F-B8C1-BE43D431A15A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9a289cae144bbc7e49fdbbf8e36db9f0b9bdeec","datavalue":{"value":{"entity-type":"item","numeric-id":1593222,"id":"Q1593222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$8575EA40-FAD7-4761-8C9F-4C517065365D","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":"Q1889794$42819E66-17E1-4DE2-96BC-5F6941B86142","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":"Q1889794$C00DF2C1-EA46-4237-9029-7393183A3FED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7d327da8b1f541c47ada9637e2211add464ca94","datavalue":{"value":{"entity-type":"item","numeric-id":5610469,"id":"Q5610469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$09EF1615-DC62-423F-9E65-57AA285B1B89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cef879ea55c07611c6803076f9eb6f58a7e87b63","datavalue":{"value":{"entity-type":"item","numeric-id":1210777,"id":"Q1210777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$F1D7B092-4C21-475E-BCAE-8EA2B1D3B15D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90ba1e39858e935e476a2ccda82a396b1173cded","datavalue":{"value":{"entity-type":"item","numeric-id":5753892,"id":"Q5753892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$FF5F505F-0AF9-454B-A7E9-17A378FCC911","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a574ce0e30c684a0d4f28e429a8ec0f18fdc094f","datavalue":{"value":{"entity-type":"item","numeric-id":1245537,"id":"Q1245537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$4E7E18D1-B301-4BA4-94AE-D7D90EA52048","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07f2d6de568c1a8be2fe427ec5ec66dcc9ad1b97","datavalue":{"value":{"entity-type":"item","numeric-id":1915202,"id":"Q1915202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$865078B2-1CE8-488C-B80B-2F3EDC93395C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1585e4669246ff05e841251ab30068a25b89ef6a","datavalue":{"value":{"entity-type":"item","numeric-id":5601883,"id":"Q5601883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$5681E301-CA29-4363-A393-1AF54F1F8C35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42e7598542d3d6d1b68c812a0f1f8eea2f6a1d9c","datavalue":{"value":{"entity-type":"item","numeric-id":1822849,"id":"Q1822849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$0BBFD4BF-D201-479E-A64B-09E8E63DF8C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f8d2ee5bf3a492297f1bf84186e59c371240aa7","datavalue":{"value":{"entity-type":"item","numeric-id":751075,"id":"Q751075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$B2EA4D40-8DF7-4A48-9AAC-E9539F5B3BD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ab7f833fe68f7c9ebb6a59c0b3bc1a3f6f98cf7","datavalue":{"value":{"entity-type":"item","numeric-id":4451048,"id":"Q4451048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$0C1B483B-543C-410D-B9DE-2FFA00C8E056","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab910d5a78a628f0fd9abaf10c25cf2ed2bce333","datavalue":{"value":{"entity-type":"item","numeric-id":1766910,"id":"Q1766910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$802C4A14-713F-4ED3-AA2D-A43E0812B5F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c002ad067b4aa712ea1c6cd09d6cf01d12fbb37f","datavalue":{"value":{"entity-type":"item","numeric-id":1872400,"id":"Q1872400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$55A40039-65A3-4BD8-BA66-33F59B2B502E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eefc16287914fbba03ec7e9c5d534559e50cc05d","datavalue":{"value":{"entity-type":"item","numeric-id":4461189,"id":"Q4461189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$5FF693AC-E35E-4396-B2B9-3BA19DE036B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdca8a4f741c264a9d34ac80fe550a589b861109","datavalue":{"value":{"entity-type":"item","numeric-id":4660727,"id":"Q4660727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$81D582AD-C79E-4460-90D2-359BB7D4B558","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb361edc053272753ecafbb9fdd00112e65e1c0e","datavalue":{"value":{"entity-type":"item","numeric-id":1425477,"id":"Q1425477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$FD07E22D-AF32-4960-8E68-87986320A8D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1df332d97de8ab0a4b2649301b4301a34c277735","datavalue":{"value":{"entity-type":"item","numeric-id":1429803,"id":"Q1429803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$AD129DDA-E28E-42BA-BBCF-D48140CE186D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bdd6c00d61336c7c7830dad6fb69c8932057158","datavalue":{"value":{"entity-type":"item","numeric-id":1807211,"id":"Q1807211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$AE5BBC20-60C1-4750-8F81-2ACE398CD3DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4a21ff9f84d5ce737d3830c3241f7c10b6b0e6f","datavalue":{"value":{"entity-type":"item","numeric-id":4792088,"id":"Q4792088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$0D43FEFE-7B99-469B-A6DF-03FAF21EA7B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2a06fe97c65ac7edf7420082818b86629341748","datavalue":{"value":{"entity-type":"item","numeric-id":1220321,"id":"Q1220321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889794$AD297CC2-4DDA-4768-B8F4-4937A2A40AAB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ddfc8de5747ccfb8f7dfa22fbae3ea79ef17ce6c","datavalue":{"value":{"entity-type":"item","numeric-id":1872400,"id":"Q1872400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed6c9a447d6b9424d587a3038af59252d0c012ee","datavalue":{"value":{"amount":"+0.8962550759315491","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":"Q1889794$E0A514E2-ABE6-43A1-AB02-13485D331A47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b05287e8dc36648dd45c612990d31d4b28f103dc","datavalue":{"value":{"entity-type":"item","numeric-id":2316364,"id":"Q2316364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68b2c85b32e79a777afff3f60bc3ddce4f9d0589","datavalue":{"value":{"amount":"+0.8952970504760742","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":"Q1889794$926902EA-C169-449F-AA1E-CC9732DC52D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf9c7f86c146d09eb074bc338bc45c609dd993ed","datavalue":{"value":{"entity-type":"item","numeric-id":4451048,"id":"Q4451048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5579983d11f0d959afcd75e265796bf229e57da3","datavalue":{"value":{"amount":"+0.8128546476364136","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":"Q1889794$4133B076-56F5-4D99-BD57-206FCAEAC0B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aab2daad9e7cc6259605a8b7884030a95899845d","datavalue":{"value":{"entity-type":"item","numeric-id":858033,"id":"Q858033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3fb10d7531d2b97f1063c61830593c62bc9d1b4","datavalue":{"value":{"amount":"+0.8027073740959167","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":"Q1889794$80B48FC9-90EC-47AF-A0AB-C50AC6C2CD44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"510efd8725e82157082ce0ae6ef837993bf44088","datavalue":{"value":{"entity-type":"item","numeric-id":717882,"id":"Q717882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63dd11ab4d19863f2d57224a404a444faaaa1e15","datavalue":{"value":{"amount":"+0.7895819544792175","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":"Q1889794$6C8A0897-3332-4062-8C25-BB05631FA4CB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Robust reconstruction on trees is determined by the second eigenvalue.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Robust_reconstruction_on_trees_is_determined_by_the_second_eigenvalue."}}}}}