Ben-Basat, Ran;
Mitzenmacher, Michael;
Vargaftik, Shay;
(2021)
How to send a real number using a single bit (and some shared randomness).
In:
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021).
(pp. pp. 1-20).
Schloss Dagstuhl - Leibniz-Zentrum für Informatik: Dagstuhl, Germany.
Preview |
Text
LIPIcs-ICALP-2021-25.pdf - Published Version Download (930kB) | Preview |
Abstract
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 ∈ {0,1} to transmit. In turn, a receiver estimates x based on the value of X. The goal is to minimize the cost, defined as the worst-case (over the choice of x) expected squared error. 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 optimal and near-optimal solutions that use a small number of shared random bits. Finally, we discuss open problems and future directions.
| Type: | Proceedings paper |
|---|---|
| Title: | How to send a real number using a single bit (and some shared randomness) |
| Event: | The 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) |
| ISBN-13: | 978-3-95977-195-5 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.4230/LIPIcs.ICALP.2021.25 |
| Publisher version: | https://doi.org/10.4230/LIPIcs.ICALP.2021.25 |
| Language: | English |
| Additional information: | © Ran Ben Basat, Michael Mitzenmacher, and Shay Vargaftik; licensed under Creative Commons License CC-BY 4.0 (https://creativecommons.org/licenses/by/4.0/). |
| Keywords: | Randomized Algorithms, Approximation Algorithms, Shared Randomness, Distributed Protocols, Estimation, Subtractive Dithering |
| UCL classification: | UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science UCL > Provost and Vice Provost Offices > UCL BEAMS UCL |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10152229 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
