Indistinguishable sceneries on the Boolean hypercube

DOI10.1017/S0963548318000305MaRDI QIDQ5219310zbMATH OpenOpenAlexWikidataFDO

Authors Renan Gross, Uri Grupel

Publication date 11 March 2020

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.07667

Mathematics Subject Classification ID

Hypergraphs (05C65) Random walks on graphs (05C81) Sums of independent random variables; random walks (60G50) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Combinatorics in computer science (68R05)

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 neighbors colored by $1$, and locally stable functions, in which every vertex has a constant fraction of neighbors colored by its own color. 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 $mathbb{Z}^n$ and other graphs, and offer several follow-up questions.

Recommendations

• Locally biased partitions of \(\mathbb{Z}^n\)
• The number of locally p-stable functions on Q_n
• Shotgun reconstruction in the hypercube
• Retrieving random media
• Reconstruction of random sceneries

Cites work

• A survey of perfect codes
• Analysis of Boolean Functions
• Distinguishing sceneries by observing the scenery along a random walk path
• scientific article; zbMATH DE number 3763833 (Why is no real title available?)
• Indistinguishable Sceneries
• Noise Sensitivity of Boolean Functions and Percolation
• On the Number of 1-Perfect Binary Codes: A Lower Bound
• Reconstructing a piece of scenery with polynomially many observations.
• Scenery reconstruction on finite abelian groups

Cited in

(3)

• The number of locally p-stable functions on Q_n
• Locally biased partitions of \(\mathbb{Z}^n\)
• Shotgun reconstruction in the hypercube

This page was built for publication: Indistinguishable sceneries on the Boolean hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219310)