The complexity of bit retrieval
Abstract
Bit retrieval is the problem of reconstructing a periodic binary sequence from its periodic autocorrelation, with applications in cryptography and x-ray crystallography. After defining the problem, with and without noise, we describe and compare various algorithms for solving it. A geometrical constraint satisfaction algorithm, relaxed-reflect-reflect, is currently the best algorithm for noisy bit retrieval. © 2017 IEEE.
Date Published
Journal
IEEE Transactions on Information Theory
Volume
64
Issue
1
Number of Pages
412-428,
URL
https://www.scopus.com/inward/record.uri?eid=2-s2.0-85030622989&doi=10.1109%2fTIT.2017.2754485&partnerID=40&md5=aea1e96c333cb2d310d963f499ca4190
DOI
10.1109/TIT.2017.2754485
Research Area
Group (Lab)
Veit Elser Group
Funding Source
DE-SC0005827