情報科学における確率的組合せ論及び極値集合論を通した離散構造の考究

本研究では、離散数学の一分野である確率的組合せ論を、情報科学における符号理論分野において活躍させ、効率的な構成法やより精度の高い理論限界の導出をすることを目指している。本研究課題2年目である本年度は、まず、昨年度得られた weak superimposed code の研究成果を類似の組合せ構造に応用することから着手した。本年度の研究において、特殊なグループテストに応用される、generalized cover-free family と呼ばれる構造について、既知の限界式を改良することができた。この結果は、weak superimposed code に関する研究成果とともに、現在論文にまとめている段階である。また、上述の研究成果は確率集中不等式を使った確率的手法を用いて得られたが、同様の手法にランダムシャッフルを応用することで、 difference system of sets（DSS）と呼ばれる組合せ構造に関する限界式を導出した。DSS を用いると、信号同期のために用いられる q 元の self-syncoronizing code を構成することができると知られており、DSS の redundancy というパラメータが小さいほどより多くの情報を格納でき、relative index と呼ばれるパラメータが大きいほどノイズに強くなる。本研究で得られた結果は、DSS の redundancy の必要条件である Levenshtein bound を漸近的に達成するという意味で漸近的に最適な DSS を任意の q と任意の relative index に対して構成できたというものである。さらにその証明は効率的な構成アルゴリズムを与えるものである。

本研究では、離散数学の一分野である確率的組合せ論を、情報科学における符号理論分野において活躍させ、効率的な構成法やより精度の高い理論限界の導出をすることを目指している。本研究課題2年目である本年度は、まず、昨年度得られた weak superimposed code の研究成果を類似の組合せ構造に応用することから着手した。本年度の研究において、特殊なグループテストに応用される、generalized cover-free family と呼ばれる構造について、既知の限界式を改良することができた。この結果は、weak superimposed code に関する研究成果とともに、現在論文にまとめている段階である。また、上述の研究成果は確率集中不等式を使った確率的手法を用いて得られたが、同様の手法にランダムシャッフルを応用することで、 difference system of sets（DSS）と呼ばれる組合せ構造に関する限界式を導出した。DSS を用いると、信号同期のために用いられる q 元の self-syncoronizing code を構成することができると知られており、DSS の redundancy というパラメータが小さいほどより多くの情報を格納でき、relative index と呼ばれるパラメータが大きいほどノイズに強くなる。本研究で得られた結果は、DSS の redundancy の必要条件である Levenshtein bound を漸近的に達成するという意味で漸近的に最適な DSS を任意の q と任意の relative index に対して構成できたというものである。さらにその証明は効率的な構成アルゴリズムを与えるものである。