AI Lab、理論計算機科学分野のトップカンファレンス「ICALP 2026」にて2本の論文採択

■背景

高度な情報社会の実現には、複雑な課題を効率よく解くための優れたアルゴリズムが不可欠です。そのため、新たなアルゴリズムを生み出し、その性能や限界を明らかにする基礎理論の重要性はますます高まっています。
「AI Lab」では、理論計算機科学を、AIやデータマイニングをはじめとする応用技術を支える重要領域のひとつと位置づけ、国内外の大学・研究機関と連携して最先端の基礎研究に取り組んでいます。

今回は、状態空間上の状態の移り変わりを扱う「組合せ遷移」と、セキュリティにも直結する「現代の正規表現の計算複雑性」という、理論的・社会的に重要な2つのテーマにおいて成果が認められました。 

■論文の概要

「On (In)approximability of MaxMin Independent Set Reconfiguration」
著者： Hung P. Hoang (ウィーン工科大学)・大坂直人 (サイバーエージェント AI Lab)・斉藤凜 (東北大学)・田村祐馬 (東北大学)

組合せ遷移は、ある問題の解を、実行可能性を保ちながら段階的に別の解へと遷移させる枠組みです。本研究では、グラフ上の基礎的な問題である独立集合を対象にした「独立集合遷移」という問題の近似可能性を解析しました。具体的には、一般のグラフに対する初の近似アルゴリズムを開発し、グラフ構造に制限がある場合にはより精度の優れた近似アルゴリズムを開発しました。一方で、この問題をある近似精度以上で解くことが困難であるという計算量理論的限界を証明しました。 本成果は、離散最適化やアルゴリズム理論における未解決課題を前進させるものであり、効率的かつ安全な状態遷移が求められるシステム設計などへの応用が期待されます。

「On the Complexity of the Matching Problem of Regular Expressions with Backreferences」
著者： 隈部壮・上里友弥（サイバーエージェント AI Lab）

Webサービス内で使われる正規表現に、処理に時間のかかる文字列を外部から与えてシステムを停止させる攻撃「ReDoS（正規表現によるDoS攻撃）」があります。入力文字列の長さNに対して二乗時間 O(N²) 程度かかるだけでも、最近では危険だと考えられており、安全面からも高速な正規表現エンジンの実現が求められています。古典的な正規表現には線形時間 O(N) で動く安全な実装が存在するものの、それらは広く使われる拡張機能「後方参照（変数）」をサポートしていないという実用上の問題も知られています。 本研究ではこの課題に対し、新たに「変数が1つ」かつ「1度だけ参照される」という実用上重要なクラスを対象として、ほぼ線形時間である O(N log² N) で動く高度なアルゴリズムを与えました。一方で、変数が1つであっても参照回数に制限がない場合には、標準的な計算量仮説のもとで二乗時間が避けられないといった理論的限界も明らかにしています。 本成果は、実社会で使われる正規表現の拡張を扱う高速アルゴリズムへの道を切り拓いたものです。今後は「真の線形時間性」の解明に向けたさらなる理論的挑戦とともに、高速な正規表現エンジンの実現と実装が進むことで、理論と応用が相互に高め合う新たな研究領域の発展へとつながることが期待されます。

■今後

これらの研究の成果は理論研究の発展に寄与し得る基礎研究成果であり、当社内に限らず理論計算機科学分野における問題の社会応用を促進することが期待されます。今後も「AI Lab」では事業に近い応用研究をすすめるとともに、基礎研究への学術貢献を見据えた研究・開発に努めてまいります。



※1　The 53rd EATCS International Colloquium on Automata, Languages, and Programming