Published August 2014
| Submitted
Journal Article
Open
Scenery Reconstruction on Finite Abelian Groups
- Creators
- Finucane, Hilary
- Tamuz, Omer
- Yaari, Yariv
Abstract
We consider the question of when a random walk on a finite abelian group with a given step distribution can be used to reconstruct a binary labeling of the elements of the group, up to a shift. Matzinger and Lember (2006) give a sufficient condition for reconstructability on cycles. While, as we show, this condition is not in general necessary, our main result is that it is necessary when the length of the cycle is prime and larger than 5, and the step distribution has only rational probabilities. We extend this result to other abelian groups.
Additional Information
© 2014 Elsevier B.V. Received 22 May 2012, Revised 22 October 2013, Accepted 30 March 2014, Available online 3 April 2014. Supported by an ERC grant. Supported by ISF grant 1300/08. Omer Tamuz is a recipient of the Google Europe Fellowship in Social Computing, and this research is supported in part by this Google Fellowship.Attached Files
Submitted - 1105.5569.pdf
Files
1105.5569.pdf
Files
(442.0 kB)
Name | Size | Download all |
---|---|---|
md5:05c1b3c8d27ad8fff0ba44066eaec6d8
|
442.0 kB | Preview Download |
Additional details
- Eprint ID
- 71913
- Resolver ID
- CaltechAUTHORS:20161110-120309955
- European Research Council (ERC)
- 1300/08
- Israel Science Foundation
- Created
-
2016-11-10Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field