The Complexity of Bit Retrieval

DOI10.1109/TIT.2017.2754485MaRDI QIDQ4566643zbMATH OpenOpenAlexFDO

Authors Veit Elser

Publication date 27 June 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Abstract: Bit retrieval is the problem of reconstructing a 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.

Cited in

(12)

• Learning without loss
• The beltway problem over orthogonal groups
• SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
• No existence of a linear algorithm for the one-dimensional Fourier phase retrieval
• Circumcentering reflection methods for nonconvex feasibility problems
• Bit copying: the ultimate computational simplicity
• Matrix product constraints by projection methods
• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• Toward a mathematical theory of the crystallographic phase retrieval problem
• Finite alphabet phase retrieval
• Benchmark problems for phase retrieval
• Applying iterated mapping to the no-three-in-a-line problem

This page was built for publication: The Complexity of Bit Retrieval

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