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

広告 ｜2024年6月25日

株式会社サイバーエージェント（本社：東京都渋谷区、代表取締役：藤田晋、東証プライム市場：証券コード4751）は、人工知能技術の研究開発組織「AI Lab」に所属する研究員の大坂直人、上里友弥、隈部壮ならびに国立情報学研究所の？？田悠一教授および平原秀一准教授による論文4本が、理論計算機科学分野のトップカンファレンス「51st EATCS International Colloquium on Automata, Languages and Programming（ICALP 2024、以下ICALP）」※1に採択されたことをお知らせいたします。

「ICALP」は世界中の研究者達によって開催される国際会議で、理論計算機科学における欧州最高峰の国際会議です。このたび採択された論文は、2024年7月にエストニアのタリンで開催される「ICALP 2024」で発表される予定です。

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

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

「Lipschitz Continuous Allocations for Optimization Games」
著者：隈部壮（サイバーエージェント AI Lab）、？？田悠一（国立情報学研究所）

特性関数が不確かさを含むような協力ゲームを扱う場合、その不確かさに対して安定した配分を行うことが望ましいです。本研究では配分の安定性の尺度として、最適化ゲームと呼ばれるゲーム群に対し、「ゲームの単位変化あたりの配分の変化量」を意味するリプシッツ定数という値を導入しました。また、マッチングゲームおよび最小全域木ゲームに対し、配分を出力する安定なアルゴリズムを提案するとともに、シャープレイ値の安定性を解析しました。 ＜論文リンク＞ https://arxiv.org/abs/2405.11889

「Regular Expressions with Backreferences and Lookaheads Capture NLOG」
著者：上里友弥（サイバーエージェント AI Lab）

「後方参照」と「先読み」は、正規表現で現実的なテキスト処理をするための、多くの環境で使える便利な拡張機能です。今回は、利便性を追求した結果得られたと言える体系「正規表現＋後方参照＋先読み」の表現力＝言語クラスが、実は、NLOG（非決定性対数領域計算可能）という理論的に確立されたクラスと一致することを示しました。さらに、受理判定問題という基本的な問題の計算量が、PSPACE完全になることも示しました。 ＜論文リンク＞ https://arxiv.org/abs/2404.17492 ＜解説ブログ＞ https://cyberagent.ai/blog/research/19391/

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

「集合被覆遷移問題」と呼ばれる組合せ遷移問題の近似困難性を改善しました。過去にAI Labから「SODA 2024」にて発表した論文では、この問題の1.0029-近似困難性を証明しましたが、既知の2-近似可能性とは数値的に大きなギャップがありました。本研究では、集合被覆遷移問題の1.999-近似がPSPACE困難であるという最終的な解決を与えました。 ＜論文リンク＞ https://eccc.weizmann.ac.il/report/2024/039/

「Alphabet Reduction for Reconfiguration Problems」
著者：大坂直人（サイバーエージェント AI Lab）

様々な組合せ遷移問題の近似困難性を示すための証明技法を開発しました。過去にAI Labから「SODA 2024」にて発表した論文では、「ギャップ増幅」という技術により（ある遷移問題が）PSPACE困難となる近似比の具体的数値を導出しましたが、引き換えに「アルファベットサイズ」と呼ばれるパラメータが巨大となり、依然として多くの遷移問題へ帰着不可能であるという課題がありました。本研究では、近似困難性を数値的に大きく損なわずにアルファベットサイズを削減させるための新たな証明技法を開発しました。 ＜論文リンク＞ https://arxiv.org/abs/2402.10627

■今後

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

※1International Colloquium on Automata, Languages and Programming

Tweet