3 ms·

What are some real-world situations where you can only send a single bit but have shared randomness? That seems like a bizarre constraint. Is this just - and no

by wk_end 5y ago

What are some real-world situations where you can only send a single bit but have shared randomness? That seems like a bizarre constraint. Is this just - and no shame in this - math for math’s sake?

0cVlTeIATBs 5y ago
This sounds halfway related to a problem my statistics professor worked on, sending data over a shared interface without detection. Note that these scenarios assume discrete time. "Shared randomness" might be the current noise level on some radio frequency in enemy territory. You and your receiving friend can both hear everything, but as soon as one of you starts transmitting you must have a very careful strategy to avoid detection.
deleted 5y ago
[deleted]
asxd 5y ago
I could imagine a scenario where you have many clients sending you information repeatedly, and you’d like to restrict the size of each packet. I think what this post is saying is that during the initial client setup you could add an arbitrary amount of shared randomness to increase accuracy while keeping the packet size down. To more directly answer your question, the post mentions federated learning of machine models as an application.
- JoachimSchipper 5y ago
  Concretely, imagine a sensor node sampling a lot of low-quality sensors frequently. You can afford some setup (to share an AES key, generating as much shared (pseudo-)random as you want), but you want your per-measurement overhead to be small. … it’s not the most practical, and the single-but version seems to be a toy problem, but I can imagine it being useful in some very particular cases?
  - asxd 5y ago
    On the hardware side, I think delta-sigma ADCs [1] might solve the same problem. They only sample 1-bit at a time, but they do so at a much faster rate than conventional ADCs. I'm a bit out of my scope here, but I think the concept is really cool. [1] https://en.wikipedia.org/wiki/Delta-sigma_modulation https://en.wikipedia.org/wiki/Delta-sigma_modulation
TuringNYC 5y ago
This wouldn't count as "real world" but this topic reminds me of communication protocols described in the novel: https://en.wikipedia.org/wiki/The_Three-Body_Problem_(novel) https://en.wikipedia.org/wiki/The_Three-Body_Problem_(novel)
deleted 5y ago
[deleted]
mprime1 5y ago
Real world situation that is very similar to this: you send a friend a few bits (a seed) they plug it into Minecraft and the both of you can play in the same exact yet practically infinite world. That is possible due to the shared randomness built into the world generation on both computers.
mateo1 5y ago
The article clearly mentions distributed learning and its really not that hard to generalise on literally any partially parallelizable computing problem with bandwidth limitations between the compute nodes.

by wk_end 5y ago

0cVlTeIATBs 5y ago

This sounds halfway related to a problem my statistics professor worked on, sending data over a shared interface without detection. Note that these scenarios assume discrete time. "Shared randomness" might be the current noise level on some radio frequency in enemy territory. You and your receiving friend can both hear everything, but as soon as one of you starts transmitting you must have a very careful strategy to avoid detection.

deleted 5y ago

[deleted]

asxd 5y ago

I could imagine a scenario where you have many clients sending you information repeatedly, and you’d like to restrict the size of each packet. I think what this post is saying is that during the initial client setup you could add an arbitrary amount of shared randomness to increase accuracy while keeping the packet size down. To more directly answer your question, the post mentions federated learning of machine models as an application.

JoachimSchipper 5y ago
Concretely, imagine a sensor node sampling a lot of low-quality sensors frequently. You can afford some setup (to share an AES key, generating as much shared (pseudo-)random as you want), but you want your per-measurement overhead to be small. … it’s not the most practical, and the single-but version seems to be a toy problem, but I can imagine it being useful in some very particular cases?
- asxd 5y ago
  On the hardware side, I think delta-sigma ADCs [1] might solve the same problem. They only sample 1-bit at a time, but they do so at a much faster rate than conventional ADCs. I'm a bit out of my scope here, but I think the concept is really cool. [1] https://en.wikipedia.org/wiki/Delta-sigma_modulation https://en.wikipedia.org/wiki/Delta-sigma_modulation

TuringNYC 5y ago

This wouldn't count as "real world" but this topic reminds me of communication protocols described in the novel: https://en.wikipedia.org/wiki/The_Three-Body_Problem_(novel) https://en.wikipedia.org/wiki/The_Three-Body_Problem_(novel)

deleted 5y ago

[deleted]

mprime1 5y ago

Real world situation that is very similar to this: you send a friend a few bits (a seed) they plug it into Minecraft and the both of you can play in the same exact yet practically infinite world. That is possible due to the shared randomness built into the world generation on both computers.

mateo1 5y ago

The article clearly mentions distributed learning and its really not that hard to generalise on literally any partially parallelizable computing problem with bandwidth limitations between the compute nodes.