プレスリリース

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

AI ｜2026年8月10日

株式会社サイバーエージェント（本社：東京都渋谷区、代表取締役社長：山内隆裕、東証プライム市場：証券コード4751）は、人工知能技術の研究開発組織「AI Lab」に所属する研究員の大坂直人ならびに国立情報学研究所の平原秀一准教授による論文が、理論計算機科学分野のトップカンファレンス「67th IEEE Symposium on Foundations of Computer Science (FOCS 2026、以下FOCS）」※1にて採択されたことをお知らせいたします。

「FOCS」は世界中の研究者達によって開催される国際会議で、「ACM Symposium on Theory of Computing (STOC)」※2と並び理論計算機科学分野における最高峰の国際会議です。
1960年から開催されている歴史ある国際会議であり、現代の理論計算機科学の基礎を築く画期的な概念や定理が数多く提唱・証明されてきました。例えば1994年のFOCSではPeter Shorが素因数分解を効率的に解く量子アルゴリズムを発表し、1989年のFOCSでは戸田誠之助がゲーデル賞を受賞した「戸田の定理」を発表するなど、世界的に重要な成果発表の場となっています。

このたび採択された論文は、2026年11月にアメリカ・ニューヨークで開催される「FOCS 2026」にて発表予定です。

■採択された論文について

「AI Lab」ではマーケティング全般に関わる幅広いAI技術を研究・開発しており、大学・学術機関との産学連携を強化しながら様々な技術課題に取り組んでいます。また、応用研究だけでなく学術的に未解決な問題に対して貢献をする基礎研究にも注力をしており、今回採択された論文は、理論計算機科学分野の基礎研究に該当しています。

「Optimal PSPACE-hardness of Approximating 𝑞-CSP Reconfiguration」
著者：平原秀一（国立情報学研究所）・大坂直人（サイバーエージェント AI Lab）

「組合せ遷移」は、AIや大規模システムがある「最適な状態」から別の「最適な状態」へ移行可能かどうかをアルゴリズム理論・計算量理論の観点から研究する領域です。

AI Labがこれまで発表した論文（STOC 2024・ICALP 2024・ICALP 2025・FOCS 2025）では、「E𝑘-SAT遷移問題」などを対象に、遷移途中の解の品質をどこまで保てるか、またその保証がどれほど難しいかを明らかにしてきました。しかし、より幅広い問題を表現できる「制約充足問題（constraint satisfaction problem; CSP）」の遷移版については、遷移途中で満たせる制約の割合（近似率）の限界が分かっていませんでした。

本研究では、各制約に関わる変数を𝑞個に制限した「𝑞-CSP遷移問題」を対象としました。その結果、各𝑞≥2について、近似率2^-(𝑞-1)をわずかでも上回ることがPSPACE困難であると証明しました。さらに、「NP ≠ PSPACE」という計算量理論の標準的な仮定のもとで、この近似困難性が理論上最適であることを証明しました。

■今後

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

※1 The 67th Symposium on Foundations of Computer Science (FOCS 2026)
※2 ACM Symposium on Theory of Computing (STOC)