# How to send a real number using a single bit (and some shared randomness)

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Oct 2020.

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

- [EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning](https://mlsanity.com/paper/2108.08842/) (2021)
- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [THC: Accelerating Distributed Deep Learning Using Tensor Homomorphic Compression](https://mlsanity.com/paper/2302.08545/) (2023)
- [ScionFL: Efficient and Robust Secure Quantized Aggregation](https://mlsanity.com/paper/2210.07376/) (2022)
- [QUIC-FL: Quick Unbiased Compression for Federated Learning](https://mlsanity.com/paper/2205.13341/) (2022)
- [Beyond Throughput and Compression Ratios: Towards High End-to-end Utility of Gradient Compression](https://mlsanity.com/paper/2407.01378/) (2024)
- [Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven](https://mlsanity.com/paper/2605.06014/) (2026)
- [DynamiQ: Accelerating Gradient Synchronization using Compressed Multi-hop All-reduce](https://mlsanity.com/paper/2602.08923/) (2026)
- [Optimal and Near-Optimal Adaptive Vector Quantization](https://mlsanity.com/paper/2402.03158/) (2024)
- [Entropy-Constrained Adaptive Stochastic Quantization](https://mlsanity.com/paper/2608.18147/) (2026)
- [Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation](https://mlsanity.com/paper/2609.27860/) (2026)
- [TORQUE: Optimizing What (not) to Quantize Before and After Rotation](https://mlsanity.com/paper/2609.36032/) (2026)

## Abstract (arXiv)

We consider the fundamental problem of communicating an estimate of a real number x∈[0,1] using a single bit. A sender that knows x chooses a value X∈set0,1 to transmit. In turn, a receiver estimates x based on the value of X. We consider both the biased and unbiased estimation problems and aim to minimize the cost. For the biased case, the cost is the worst-case (over the choice of x) expected squared error, which coincides with the variance if the algorithm is required to be unbiased. We first overview common biased and unbiased estimation approaches and prove their optimality when no shared randomness is allowed. We then show how a small amount of shared randomness, which can be as low as a single bit, reduces the cost in both cases. Specifically, we derive lower bounds on the cost attainable by any algorithm with unrestricted use of shared randomness and propose near-optimal solutions that use a small number of shared random bits. Finally, we discuss open problems and future directions.