Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-17T06:13:11.176Z Has data issue: false hasContentIssue false

Indistinguishable Sceneries on the Boolean Hypercube

Published online by Cambridge University Press:  05 June 2018

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])

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.

Type
Paper
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 97135.Google Scholar
[2] Finucane, H., Tamuz, O. and Yaari, Y. (2014) Scenery reconstruction on finite abelian groups. Stochastic Process. Appl. 124 27542770.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 75115.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 17601765.Google Scholar
[6] Lindenstrauss, E. (1999) Indistinguishable sceneries. Random Struct. Alg. 14 7186.Google Scholar
[7] van Lint, J. H. (1975) A survey of perfect codes. Rocky Mountain J. Math. 5 199224.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 289300.Google Scholar
[10] O'Donnell, R. (2014) Analysis of Boolean Functions, Cambridge University Press.Google Scholar