Shotgun reconstruction in the hypercube
Shotgun reconstruction in the hypercube
复制标题
超立方体中的霰弹枪重建
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
A. Scott
中科院分区：
文献类型：
--
作者：
Michal Przykucki;Alexander Roberts;A. Scott
Mossel和Ross提出了一个问题，当一个图的随机着色可以从局部信息，即给定半径的球的着色（具有多重性）重建。在这篇文章中，我们关注n维超立方体的顶点的随机2-着色，或者等价的随机布尔函数。在最坏的情况下，需要直径为Ω（n）的球进行重建。然而，随机着色的情况是显着不同的：我们表明，几乎每一个2-着色可以从半径为2的球的着色的多集重建。此外，我们证明了对于q≥n2+ n，几乎所有的q-染色都可以从1-球的多染色集重构。
Mossel and Ross raised the question of when a random coloring of a graph can be reconstructed from local information, namely, the colorings (with multiplicity) of balls of given radius. In this article, we are concerned with random 2‐colorings of the vertices of the n ‐dimensional hypercube, or equivalently random Boolean functions. In the worst case, balls of diameter Ω(n) are required to reconstruct. However, the situation for random colorings is dramatically different: we show that almost every 2‐coloring can be reconstructed from the multiset of colorings of balls of radius 2. Furthermore, we show that for q≥n2+ϵ , almost every q ‐coloring can be reconstructed from the multiset of colorings of 1‐balls.
超立方体中的顶点等周稳定性
DOI：
10.1016/j.jcta.2019.105186
发表时间：
2020
期刊：
Journal of Combinatorial Theory, Series A
影响因子：
--
作者：
Przykucki M
通讯作者：
Przykucki M