カテゴリー: ブログ

余談ですが、
フィールズ賞授賞式の数日前、
会場付近を散歩してました。

式典会場とは全く知らず（笑

仕事でヘルシンキ（フィンランド）に行ってました。
符号理論のシンポジウムでした。

Tooloという地域にホテルをとって、
Aalto大学のメインキャンパスであるEspooへ。

帰国後、授賞式の中継を見ていたら、
　会場が
　Aalto大学Tooloキャンパス
だったという。
ちょっと惜しい感じ！！！

Tooloキャンパスのすぐ傍に、
観光名所
　岩の教会（Rock Church）。
現地の言葉で
　テンペリアウキオ
があります。
側壁が岩で、天井が木で作られた不思議な教会。

テンペリアウキオ内部の
写真を撮ってきました。

写真右下の方に、なにやらオブジェがあったので、3Dスキャンしてきました。

余談が続きましたが
マリナさんを含め、受賞者の皆さん
おめでとうございます！

【追記】
８次元の最密充填問題の解を
拡張ハミング符号がどのように与えるか。
答えは【ここ】に！

Tweet

符号理論では、様々な距離が登場する。

というのも、雑音の大きさが距離によって表現されることと、雑音に様々な種類があるからだ。

例を挙げると、

・ビット反転誤りの大きさはハミング距離で表現される。

・挿入／削除誤りの大きさはLevenshtein距離で表現される。

・置換誤りの大きさはUlam距離などで表現される。

という具合。

と考えていたら、わからないことが出てきた。

・消失誤りとビット反転の復号誤りの大きさを表す距離って、名前付いてるの？

今まで見たことないし、聞いたこともない。

誰か、ご存じの方、教えてください。

Tweet

タイトル：Coordinate-ordering-free Upper Bounds for Linear Insertion-
Deletion Codes
著者名：Hao Chen
雑誌名：IEEE Transactions on Information Theory 
号数：-
DOI:10.1109/TIT.2022.3167662

Abstract：In this paper we prove several coordinate-ordering-free upper 
bounds on the insdel distances of linear codes. Our bounds are stronger 
than some previous known bounds. We apply these upper bounds to AGFC 
codes from some cyclic codes and one algebraic-geometric code with any 
rearrangement of coordinate positions. A strong upper bound on the 
insdel distances of Reed-Muller codes with the special coordinate 
ordering is also given.

タイトル：Explicit and Efficient Constructions of Linear Codes Against 
Adversarial Insertions and Deletions
著者名：Roni Con; Amir Shpilka; Itzhak Tamo
雑誌名：IEEE Transactions on Information Theory
号数：-
DOI:10.1109/TIT.2022.3173185

Abstract：In this work, we study linear error-correcting codes against 
adversarial insertion-deletion (insdel) errors, a topic that has 
recently gained a lot of attention. We construct linear codes over Fq, 
for q = poly(1/ε), that can efficiently decode from a δ fraction of 
insdel errors and have rate (1 - 4δ)=8-ε. We also show that by allowing 
codes over Fq2 that are linear over Fq, we can improve the rate to (1 - 
δ)/4 - ε while not sacrificing efficiency. Using this latter result, we 
construct fully linear codes over F2 that can efficiently correct up to 
δ < 1/54 fraction of deletions and have rate R = (1 - 54 · δ)/1216. 
Cheng, Guruswami, Haeupler, and Li [4] constructed codes with (extremely 
small) rates bounded away from zero that can correct up to a δ < 1/400 
fraction of insdel errors. They also posed the problem of constructing 
linear codes that get close to the half-Singleton bound (proved in [4]) 
over small fields. Thus, our results significantly improve their 
construction and get much closer to the bound.

Tweet