剰余指標の計算複雑さの解析とその応用

点击翻译按钮获取中文摘要

平成10年度および平成11年度を通じて計算量理論の応用研究を次のように行った。1.公開鍵暗号の安全性を保障する上で重要となる計算量理論の確立。特に,格子暗号の安全性の基礎理論となる最悪時・平均時の接続係数の改良について,ニューヨーク州立大学バッファロー校のCai教授らと共同研究を行った。また,量子計算機を用いた格子暗号の解読について名古屋大学の西村博士と共同研究を行った。2.ゲノム解析等で求められる発見学習アルゴリズムの設計について,東京工業大学の渡辺教授らと共同研究を行った。その成果はThe Tenth International Conference on Algorithmic Learning Theory(Tokyo,1999)において発表された。3.抱除の原理を用いたDNFの高速学習アルゴリズムの設計と解析について,東京電気通信大学の垂井講師と共同研究を行った。その成果はThe 14th IEEE Conference on Computational Complexity(Atlanta,1999)において発表された。4.ランダム生成回路回路の出力端子数および平均路長の解析について,ジョージ・ワシントン大学のMahmoud教授と共同研究を行った。その成果はThe Fifth Annual Symposium on Mathematical Analysis of Algorithms(Barcelona,1999)において発表された。5.割り算つきの有限段回路の下界の研究について,シカゴ大学のBeigel教授の協力のもとに研究を行った。その成果はThe 15th IEEE Conference on Computational Complexity(Italy,2000)において発表予定である。6.渡辺教授の協力のもとで,名古屋大学の相田博士とともに平均時一方向性関数理論について共同研究を行った。その成果は電気情報通信学会コンピュテーション分科会で発表された。