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

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

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



「Asymptotically Optimal Inapproximability of Maxmin 𝑘-Cut Reconfiguration」
著者：平原秀一（国立情報学研究所）・大坂直人（サイバーエージェント AI Lab）

AIやシステム設計において、現在の「最適な状態」から別の「最適な状態」へ効率的に移行できるかを調べる研究で、本論文では「最大𝑘-Cut遷移問題」と呼ばれる組合せ遷移問題の近似可能性を調査しました。 この問題は、𝑘=4の時に近似のPSPACE困難性が判明していましたが、𝑘に関する漸近的な挙動は知られていませんでした。 今回の研究では、最大𝑘-Cut遷移問題の(1-2/𝑘)-近似が多項式時間で可能な一方、(1-Ω(1/𝑘))-近似がPSPACE困難であることを証明し、漸近的に最適な近似可能性を解明しました。

「Yet Another Simple Proof of the PCRP Theorem」
著者：大坂直人（サイバーエージェント AI Lab）

本研究は、AIなどの複雑なシステムにおける「最適な手順を見つけることの根本的な難しさ」を解明し、より効率的な問題解決手法の設計に繋がる可能性を秘めています。 Probabilistically Checkable Reconfiguration Proof (PCRP) 定理の証明を簡略化しました。 PCRP定理とは、組合せ遷移問題における近似困難性に応用をもつ定理で、AI Labによる国際会議「STOC 2024」での発表論文及び Karthik C. S. and Manurangsi による論文で独立が証明されました。どちらの証明も遷移問題に特化したad-hocな技法を伴うところ、本研究では、それらを必要としない、「頑健化」と「証明合成」が分離された証明に成功し、より直感的な理解が可能となりました。 ＜論文リンク＞ TBA

■今後

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



※1 The 52nd EATCS International Colloquium on Automata, Languages, and Programming