Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-23T13:48:35.367Z Has data issue: false hasContentIssue false
  • English
  • Français

Indistinguishable Sceneries on the Boolean Hypercube

Part of: Discrete mathematics in relation to computer science Graph theory Theory of data

Published online by Cambridge University Press:  05 June 2018

RENAN GROSS  and
URI GRUPEL
RENAN GROSS
Affiliation:
Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Herzl Street, Rehovot 7610001, Israel (e-mail: [email protected], [email protected])
URI GRUPEL
Affiliation:
Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Herzl Street, Rehovot 7610001, Israel (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that the scenery reconstruction problem on the Boolean hypercube is in general impossible. This is done by using locally biased functions, in which every vertex has a constant fraction of neighbours coloured by 1, and locally stable functions, in which every vertex has a constant fraction of neighbours coloured by its own colour. Our methods are constructive, and also give super-polynomial lower bounds on the number of locally biased and locally stable functions. We further show similar results for ℤn and other graphs, and offer several follow-up questions.

MSC classification

Primary: 05C60: Isomorphism problems (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Secondary: 68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) 68R05: Combinatorics
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 1 , January 2019 , pp. 46 - 60
Copyright
Copyright © Cambridge University Press 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

Supported by the European Research Council (ERC).

References

[1] Benjamini, I. and Kesten, H. (1996) Distinguishing sceneries by observing the scenery along a random walk path. J. Anal. Math. 69 97–135.Google Scholar
[2] Finucane, H., Tamuz, O. and Yaari, Y. (2014) Scenery reconstruction on finite abelian groups. Stochastic Process. Appl. 124 2754–2770.Google Scholar
[3] Garban, C. and Steif, J. E. (2015) Noise Sensitivity of Boolean Functions and Percolation, Institute of Mathematical Statistics Textbooks, Cambridge University Press.Google Scholar
[4] Hardy, G. H. and Ramanujan, S. (1918) Asymptotic formulæ in combinatory analysis. Proc. London Math. Soc. s2-17 75–115.Google Scholar
[5] Krotov, D. S. and Avgustinovich, S. V. (2008) On the number of 1-perfect binary codes: A lower bound. IEEE Trans. Inform. Theor. 54 1760–1765.Google Scholar
[6] Lindenstrauss, E. (1999) Indistinguishable sceneries. Random Struct. Alg. 14 71–86.Google Scholar
[7] van Lint, J. H. (1975) A survey of perfect codes. Rocky Mountain J. Math. 5 199–224.Google Scholar
[8] van Lint, J. H. (1998) Introduction to Coding Theory, third edition, Springer.Google Scholar
[9] Matzinger, H. and Rolles, S. W. (2003) Reconstructing a piece of scenery with polynomially many observations. Stochastic Process. Appl. 107 289–300.Google Scholar
[10] O'Donnell, R. (2014) Analysis of Boolean Functions, Cambridge University Press.Google Scholar