⇐ Diary
非対称通信
2020-10-18

Protocol for Asymmetric Communication Channels

非対称通信の始めの研究かね.
要するに,相手が送る $n$ bitをその分布がわかってる状態でどれほど早く特定出来るかって話ね.
分布がともにわかってる状態だったらシャノン符号なりハフマン符号なりあるけど,その分布を片方しか知らない状態でどうしたらいいかって.
3つのプロトコルが紹介されていて

  • computaion-efficient
  • round-efficient
  • computation-round-tradeoff

があるんやけど,round-efficientが何言ってるのかさっぱりわからん.
日本語でok,いや日本語でもわからん.
computation-effiecntはすっごい簡単にぶっちゃけると,天秤問題よね.
いくつかおもりがあってどれか一つが重いんだけど,それを天秤使って最低何回で特定出来るかってやつ.
あれ,天秤が左傾き,右傾き,水平の3種類の状態が取れるから,おもりの数を $i$,最低回数を $m$としたら, $ m = \lceil\log_3 i\rceil$ という形で表せるから,それと似たような感じなんやよね.
だから基準を $\frac{1}{3},\frac{2}{3}$にしてるんかな.

round-efficientがまじでわからんぞ.
やばい,草案提出まで時間が......

てぉん.