新着情報［情報工学部 情報通信工学科］工藤桃成准教授 日本数式処理学会 第33回大会において「2024年度最優秀奨励賞」受賞

タイトル：半正則な非斉次多項式列に関連するグレブナー基底の求解次数について
概要 グレブナー基底は、計算代数幾何学における中心的な研究対象であり、暗号理論をはじめとする様々な応用分野においても重要な役割を果たします。しかしながら、その計算量の評価は当該分野における重要な未解決問題となっています。一般に、グレブナー基底の計算量は、計算過程で生成される多項式の最大次数（＝求解次数）を求めることで評価されますが、実際にグレブナー基底の計算を実行することなく求解次数の正確な値を事前に知ることは困難であると考えられています。本研究では、ランダムまたはそれに近い方法で生成された多項式列が高確率で満たすと予想される“半正則仮定”の下で、非斉次多項式列およびその斉次化について、Koszul複体のホモロジーをはじめとした可換代数的手法を用いることで、従来知られていた評価よりも厳密な求解次数の上界を導出することに成功しました。