# The complexity of bit retrieval

arXiv: https://arxiv.org/abs/1601.03428 · HTML: https://mlsanity.com/paper/1601.03428/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jan 2016.

## Built on by (most cited first, 1 of 1)

- [Avoiding Traps in Nonconvex Problems](https://mlsanity.com/paper/2106.05206/) (2021)

## Abstract (arXiv)

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.