eprintid: 10152229
rev_number: 8
eprint_status: archive
userid: 699
dir: disk0/10/15/22/29
datestamp: 2022-07-20 16:14:39
lastmod: 2022-07-20 16:15:46
status_changed: 2022-07-20 16:14:39
type: proceedings_section
metadata_visibility: show
sword_depositor: 699
creators_name: Ben-Basat, Ran
creators_name: Mitzenmacher, Michael
creators_name: Vargaftik, Shay
title: How to send a real number using a single bit (and some shared randomness)
ispublished: pub
divisions: C05
divisions: F48
divisions: B04
divisions: UCL
keywords: Randomized Algorithms, Approximation Algorithms, Shared Randomness, Distributed Protocols, Estimation, Subtractive Dithering
note: © Ran Ben Basat, Michael Mitzenmacher, and Shay Vargaftik;
licensed under Creative Commons License CC-BY 4.0 (https://creativecommons.org/licenses/by/4.0/).
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.
date: 2021
date_type: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
official_url: https://doi.org/10.4230/LIPIcs.ICALP.2021.25
oa_status: green
full_text_type: pub
language: eng
primo: open
primo_central: open_green
verified: verified_manual
elements_id: 1853867
doi: 10.4230/LIPIcs.ICALP.2021.25
isbn_13: 978-3-95977-195-5
lyricists_name: Ben Basat, Shlomi Ran
lyricists_id: SRBEN76
actors_name: Flynn, Bernadette
actors_id: BFFLY94
actors_role: owner
full_text_status: public
pres_type: paper
series: Leibniz International Proceedings in Informatics (LIPIcs)
publication: ICALP 2021
place_of_pub: Dagstuhl, Germany
pagerange: 1-20
event_title: The 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
book_title: Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
citation:        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.       Green open access   
 
document_url: https://discovery.ucl.ac.uk/id/eprint/10152229/1/LIPIcs-ICALP-2021-25.pdf