?url_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rft.title=How+to+send+a+real+number+using+a+single+bit+(and+some+shared+randomness)&rft.creator=Ben-Basat%2C+Ran&rft.creator=Mitzenmacher%2C+Michael&rft.creator=Vargaftik%2C+Shay&rft.description=We+consider+the+fundamental+problem+of+communicating+an+estimate+of+a+real+number+x+%E2%88%88+%5B0%2C1%5D+using+a+single+bit.+A+sender+that+knows+x+chooses+a+value+X+%E2%88%88+%7B0%2C1%7D+to+transmit.+In+turn%2C+a+receiver+estimates+x+based+on+the+value+of+X.+The+goal+is+to+minimize+the+cost%2C+defined+as+the+worst-case+(over+the+choice+of+x)+expected+squared+error.%0D%0AWe+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%2C+which+can+be+as+low+as+a+single+bit%2C+reduces+the+cost+in+both+cases.+Specifically%2C+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%2C+we+discuss+open+problems+and+future+directions.&rft.subject=Randomized+Algorithms%2C+Approximation+Algorithms%2C+Shared+Randomness%2C+Distributed+Protocols%2C+Estimation%2C+Subtractive+Dithering&rft.publisher=Schloss+Dagstuhl+-+Leibniz-Zentrum+f%C3%BCr+Informatik&rft.date=2021&rft.type=Proceedings+paper&rft.language=eng&rft.source=+++++In%3A++Proceedings+of+the+48th+International+Colloquium+on+Automata%2C+Languages%2C+and+Programming+(ICALP+2021).++(pp.+pp.+1-20).++Schloss+Dagstuhl+-+Leibniz-Zentrum+f%C3%BCr+Informatik%3A+Dagstuhl%2C+Germany.+(2021)+++++&rft.format=text&rft.identifier=https%3A%2F%2Fdiscovery.ucl.ac.uk%2Fid%2Feprint%2F10152229%2F1%2FLIPIcs-ICALP-2021-25.pdf&rft.identifier=https%3A%2F%2Fdiscovery.ucl.ac.uk%2Fid%2Feprint%2F10152229%2F&rft.rights=open