The Complexity of Bit Retrieval

DOI10.1109/TIT.2017.2754485zbMATH Open1390.94814arXiv1601.03428OpenAlexW2963446797MaRDI QIDQ4566643FDOQ4566643

Authors: Veit Elser 

Publication date: 27 June 2018

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

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.

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)

Cited In (12)

• Bit copying: the ultimate computational simplicity
• Finite alphabet phase retrieval
• Learning without loss
• SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
• Circumcentering reflection methods for nonconvex feasibility problems
• Benchmark Problems for Phase Retrieval
• Matrix product constraints by projection methods
• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• No existence of a linear algorithm for the one-dimensional Fourier phase retrieval
• The beltway problem over orthogonal groups
• Toward a Mathematical Theory of the Crystallographic Phase Retrieval Problem
• 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)