arXiv雑要約
プログラム - 2026/05/12 公開
平面上の最大値と凸包問題に対する同時時間とI/O最適性の不可能性 [cs.CL, cs.DS, cs.CG]目的：平面凸包および最大値問題に対する時間計算量とI/O複雑性の両方の最適性
- 幾何学的アルゴリズムは，計算幾何学の基礎であり，様々な応用分野で重要である。
- 既存のアルゴリズムは，時間計算量とI/O複雑性のトレードオフに陥ることが多い。
- 時間計算量とI/O複雑性の両方を最適化することの限界を示す。
- 平面凸包および最大値問題において，時間計算量とI/O複雑性の両方を同時に最適化することは不可能であることが証明された。
- 既存の最良アルゴリズムは，時間計算量の最適化を犠牲にしてI/O複雑性の最適化を達成していることの説明となる。
- 決定論的アルゴリズムに加え，時間とI/Oのトレードオフを提供するアルゴリズムや，それらを同時に最適化する確率的アルゴリズムも提示された。
位置LSH: アテンションにおける線形バイアス近似のための二値ブロック行列 [cs.RO, cs.CE, cs.MM, cs.CL, cs.LG, cs.DS]目的：アテンションにおける位置バイアスの構造的理解
- Transformerモデルの位置エンコーディングは性能に不可欠であり，その理論的理解が重要である。
- 位置エンコーディング手法間の繋がりが明確でなく，効率的な長文脈処理が課題となっている。
- ALiBiバイアスをLSHの視点から解析し，効率的な近似手法を提案することで，長文脈処理の高速化を目指す。
- ALiBiバイアス行列は，位置LSHスキームによって誘導される二値ブロックマスクの期待値として表現できることが示された。
- 提案手法は，文脈長に対してほぼ線形時間で計算可能であり，ALiBiバイアスの効率的な近似を実現する。
- 大規模言語モデルを用いた実験により，理論的知見の妥当性が検証された。
プログラマのための圏論的メッセージパッシング言語 (CaMPL) [cs.PL, cs.DC, cs.LO]目的：圏論的メッセージパッシング言語CaMPLの型システム，カスタムチャンネル型，制御された非決定性
- 並行処理は現代のソフトウェア開発において不可欠であり，その設計・実装は重要な課題である。
- 従来の並行プログラミング言語では，デッドロックやライブロックなどの問題が頻発する。
- CaMPLの型システムを用いて，デッドロックやライブロックを排除し，安全な並行処理を実現する。
- CaMPLは，線形圏論を基盤とする関数型並行プログラミング言語である。
- CaMPLの型システムは，メッセージパッシングの論理に対応し，プログラムの安全性と正確性を保証する。
- プロセス間でのメッセージパッシング，レースによる動的な適応，高階プロセス，プロトコル/コプロトコルといった機能を提供する。
安定モデル意味論における重み付きルール [cs.AI, cs.LO]目的：安定モデル意味論における重み付きルール
- 知識表現と推論の分野において，不確実性の扱いは重要な課題である。
- 従来の安定モデル意味論は決定論的であり，矛盾やモデル選択に課題があった。
- 安定モデル意味論の不確実性への対応と，モデルの確率的評価を可能とする。
- 本研究では，マルコフ論理の対数線形モデルに倣い，重み付きルールを導入した。
- これにより，矛盾の解消，モデルのランキング，確率付与といった多様な応用が可能となる。
- 安定モデルプログラム，マルコフ論理，ProbLog，P-logなどの関連形式との比較を行った。
準二次空間におけるフロー計算 [eess.SY, cs.SY, cs.DS]目的：最小コストフロー問題の空間計算量
- ストリーミング，並列計算など，様々な計算モデルにおいて空間計算量は重要な要素である。
- 最小コストフロー問題では，一般に$\Omega(n^2)$個のエッジを扱う必要があり，空間計算量の削減が課題となっていた。
- 既存の空間計算量の限界を打破し，ストリーミングや通信計算量の改善を目指す。
- 整数容量とコストが$W$で制限されたグラフに対し，$\tilde O(n^{1.5}\log (W/\epsilon))$空間，$\tilde O(\sqrt{n} \log(W/\epsilon))$パスのストリーミングアルゴリズムを提案。
- 提案アルゴリズムは，各エッジを読み込む際にフローを計算し，加法誤差$\epsilon$内でフローを返すことで，既存の$\Omega(n^2)$空間下限を回避。
- 2者間通信モデルでは，$\tilde O(n^{1.5}\log^2 W)$ビットの通信量で済むことを示した。
局所的差分プライバシー下の疎な離散ラプラスおよびガウス機構 [cs.IT, math.IT]目的：局所的差分プライバシーを保証する疎な機構のプライバシーとスパース性のトレードオフ
- プライバシー保護は重要であり，データ利用の促進と両立させる必要がある。
- 局所的差分プライバシーはプライバシー保護が強いが，データへの歪みを大きくする可能性がある。
- サポートサイズを最小化することで，プライバシー制約を満たしつつ，歪みを抑えること。
- 離散ラプラス機構とガウス機構の両方において，純粋および近似的な局所的差分プライバシーの正確な特徴付けを示した。
- サポートサイズが小さいほどプライバシー保護は弱まる一方，大きいほど歪みが増大するというトレードオフが明らかになった。
- ガウス機構の場合，サポート半径に対する二次の依存性があり，プライバシーとスパース性の関係がより厳密になることが示された。
ConCovUp：並行性テストのための効果的なエージェントベースのテストドライバ生成 [cs.SE]目的：並行性テストにおけるテストドライバの生成
- マルチスレッドプログラムの信頼性・安全性を担保する上で，並行性テストは不可欠である。
- 既存のテスト手法は逐次ロジックに重点を置いており，自動並行テスト生成のギャップが存在する。
- LLMのセマンティックな推論を活用し，複雑なパス制約を満たす入力の導出とテストの反復改善を目指す。
- ConCovUpは，プログラム解析とLLMを組み合わせたマルチエージェントフレームワークである。
- 静的解析により共有メモリへのアクセスと呼び出しコンテキストを抽出し，アクセスをトリガーする。
- 9つの実世界のC/C++ライブラリで評価した結果，SMAP Coverageを36.6%から68.1%に向上させた。
$\mathbb{Z}_N^*$ における高位数の要素の決定的な探索 [cs.DS, cs.DM, math.NT]目的：整数 $N$ を法とする乗法群 $\mathbb{Z}_N^*$ における高位数の要素の決定的な探索
- 現代の決定性因数分解アルゴリズムの重要な部分を担う問題であるため，その効率化は重要である。
- 既存のアルゴリズムでは，$D$ が $N$ に比べて非常に小さい場合にのみ，効率的に高位数の要素を見つけられるという課題があった。
- より広い範囲の $D$ に対して高位数の要素を効率的に探索し，因数分解アルゴリズムの性能向上を目指す。
- 本研究では，$D > \exp(\sqrt{2\log N \log \log N})$ を満たす $D$ に対して，位数が $D$ より大きい $\mathbb{Z}_N^*$ の要素を決定的に探索するアルゴリズムを提案した。
- 提案アルゴリズムは，高位数の要素の発見， $N$ の自明でない因数の発見，または $N$ が素数であるかの判定を $O(D^{1/2 + o(1)})$ の時間で行う。
- また，任意の $D < N$ に対して適用可能な，よりシンプルなアルゴリズムも提示し，その計算量は $O(D^{2.5+o(1)}\operatorname{polylog}(N))$ である。
幾何学的衝突：LLM継続的後学習における忘却の説明と制御 [cs.LG, cs.IT, math.IT]目的：LLM継続的後学習における忘却現象の解明と制御
- LLMの性能向上には，新しい知識やスキルの継続的な学習が不可欠である。
- 継続的学習では，既存の能力を損なう忘却の問題が顕著である。
- タスクの幾何学的表現を用いて忘却の原因を特定し，制御手法を開発する。
- 忘却は，モデルの状態に対する更新の統合の失敗として捉えられる。
- 更新間の幾何学的衝突が高い場合，干渉が生じやすい。
- 提案手法GCWMは，データを用いずに忘却を抑制し，性能向上に貢献する。
SmartEval：自然言語仕様からのLLM生成スマートコントラクト評価ベンチマーク [cs.MA, cs.AI, cs.CE, cs.LG, cs.PL, cs.SE]目的：LLM生成スマートコントラクトの品質評価
- ブロックチェーン技術の発展に伴い，スマートコントラクトの重要性が増している。
- 自然言語からスマートコントラクトを自動生成する際に，品質保証が課題となっている。
- LLM生成スマートコントラクトの品質を客観的に評価する基準と手法を確立する。
- SmartEvalは，9,000件の生成済みコントラクトと専門家による正解実装を含むベンチマークである。
- 評価指標は機能の完全性，変数の一貫性，状態遷移の正確性，ビジネスロジックの忠実性，コード品質の5次元である。
- LLM生成コントラクトは，正解実装と比較して仕様への忠実性において+8.29点の複合スコア優位性を示した。
重み付き順位集約のためのスケーラブルで統一的なフレームワーク [cs.DS, cs.DC]目的：複数の順位付けリストを統合し，合意された単一の順位付けを得ること
- ウェブ検索，人材採用，大学入試，投票など，様々な分野で順位付けの集約が必要とされている
- 入力された順位付けリストとの距離の合計を最小化する効率的なアルゴリズムが求められている
- 局所的な中央値の計算に焦点を当てることで，大規模データにおけるスケーラブルな近似解を導くこと
- 提案手法は，Ulam距離，Spearmanの足尺，Hamming距離，Kendall-tau距離などの古典的な距離尺度に対し，統一的なフレームワークを提供する。
- Ulam距離に対する新しい近似アルゴリズムは，Massively Parallel Computation (MPC)モデルにおいて，定数α>0に対する(2-α)-近似を定数ラウンドで達成する。
- また，Chakrabortyらの分析を簡略化・強化し，重み付き設定にも拡張可能な，改善された1.968近似解を得ている。
主要化格子上のレニィエントロピーの幾何学 [cs.IT, math.CO, math.IT, math.PR]目的：主要化格子上のレニィエントロピーの性質
- 確率分布の多様性を比較する主要化は，計量経済学，スペクトル理論，生態学などに応用される重要な概念である。
- 主要化の性質を詳細に分析し，レニィエントロピーとの関係を明らかにすることで，情報理論の進展が期待される。
- 主要化格子上のレニィエントロピーの加法性や超モジュール性を明らかにし，その幾何学的構造を理解すること。
- レニィエントロピーと共単調結合および独立結合の間の基本的な関係が確立された。
- 任意の次数αに対して，レニィエントロピーが主要化格子上で劣加法性を持つことが示された。
- αが{0}∪[1,∞]に属する場合，レニィエントロピーは主要化格子上で超モジュール性を示すことが明らかになった。
予算制約下SBSEにおけるリージョナル探索の優位性：パレート推論とグローバル最適化を凌駕して [cs.RO, cs.SE]目的：予算制約下SBSEにおける探索戦略の有効性に関する研究
- ソフトウェアの品質向上にSBSEが注目される中，効率的な探索手法の確立が重要である。
- 従来のSBSEは計算コストが高く，実用的な時間内に最適な解を得ることが困難であった。
- 限られた評価予算内で，より効率的に高品質な解を探索する手法を提案し，実用性を高める。
- 提案手法EZRは，パレート最適化やグローバル探索と比較して，3桁以上の速度向上を実現した。
- EZRは，限られた予算内でも高いランキングを獲得し，84-89%のデータセットで勝利または同率であった。
- パレート解が集中する狭い領域に焦点を当てることで，無駄な探索を削減し，効率的な最適化を可能にした。
森林の動的辺彩色 [cs.DS]目的：動的辺彩色問題におけるリコースの最小化
- グラフ理論はネットワーク設計やスケジューリングなどに応用され，重要な研究分野である。
- 動的辺彩色問題では，辺の追加・削除に対し効率的な再彩色が必要であり，リコースの削減が課題である。
- 森林という制限されたグラフ構造に対し，リコースを最小化するアルゴリズムを開発することを目指す。
- 決定論的環境において，Incrementalモデルでは貪欲法が$O(\frac{1}{c + \sqrt{\Delta}})$という償却リコースを達成し，最適であることが示された。
- Fully Dynamicモデルでは，貪欲法は$\Omega(\log_\Delta n)$という償却リコースが必要となることが示された。
- RootedなFully Dynamic森林に対し，非貪欲法により$O(1)$の償却リコースを達成するアルゴリズムが提案された。
RubricRefine：事前実行リファインによるツール利用エージェントの信頼性向上 [cs.LG, cs.SE]目的：ツール利用エージェントの信頼性向上
- 大規模言語モデルによるツール利用は，複雑なタスク解決に不可欠である。
- ツール利用時のエラーは，実行時フィードバックだけでは捉えにくい場合が多い。
- 実行前に契約違反を検出し修正することで，信頼性を高める。
- RubricRefineは，事前実行段階でタスクとレジストリに特化した評価基準を生成する。
- 生成されたコードを契約チェックに照らし合わせ，反復的に問題を修正する。
- M3ToolEvalにおいて，平均で0.86という高い性能を7つのモデルで達成した。
TreeWidzard：幅優先動的計画法と自動定理証明のためのエンジン [cs.DS, cs.LO, math.CO]目的：グラフ理論的性質を決定する幅優先動的計画法アルゴリズムの開発
- グラフ構造を扱う問題解決において，効率的なアルゴリズムの重要性は高い。
- 複雑なグラフに対する動的計画法の実装は，手間と専門知識を要する。
- 幅優先動的計画法を自動化し，定理証明を支援するフレームワークを提供する。
- TreeWidzardは，グラフのトレewidthとpathwidthをパラメータとする動的計画法アルゴリズムを開発するためのエンジンである。
- このエンジンを用いることで，複数のグラフ性質を組み合わせた複雑な性質に対する動的計画法アルゴリズムを構築できる。
- トレewidthがk以下の全てのグラフがBoolean組み合わせPを満たすかどうかを判定できる。
LLMにおける継続的なツール利用学習のための軌跡教師あり学習 [cs.SE, cs.AI, cs.MA]目的：LLMの継続的なツール利用学習における軌跡情報の有効性
- 大規模言語モデルの性能向上には，多様なデータと学習方法が不可欠である。
- 従来の学習データは最終結果のみを示し，過程の情報が欠如している場合が多い。
- API利用過程の軌跡情報を活用することで，継続学習の効率と精度を向上させる。
- API-Bankデータセットを用いた実験で，軌跡情報を含む条件Bは，含まない条件Aと比較して最終的な完全なAPIコール正確度が大幅に向上した。
- 条件BはAPI名予測の精度も7.7ポイント向上させたが，学習に必要なトークン数は25.1％増加した。
- 本研究は，次のAPIコール予測に焦点を当てているため，完全な対話の成功を評価するさらなる研究が必要である。
エントロピーに基づくデコーディング：適応情報駆動型分岐 [cs.LG, cs.AI, cs.IT, math.IT]目的：言語モデルのデコーディング戦略による生成品質の改善
- 大規模言語モデルは高性能だが，その出力品質はデコーディング戦略に依存する。
- 既存のデコーディング手法は，計算コストや単一路径への固執といった課題を抱える。
- モデルの不確実性に基づいて計算量を適応的に配分することで，効率的なデコーディングを実現する。
- 提案手法EDENは，エントロピーを推定し，分岐係数を動的に調整することで，計算効率を向上させる。
- 数学的推論，コード生成，科学的質問といった複雑なタスクにおいて，既存手法を上回る性能を示す。
- エントロピーに基づく分岐係数は，固定幅ビームサーチよりも優れた性能を発揮することが理論的に保証される。
線形バッチ符号に対する復元アルゴリズム [cs.IT, math.IT]目的：線形バッチ符号と復元アルゴリズムの関係性の体系的な調査
- バッチ符号は，データ保存における効率性と信頼性向上のために重要である。
- 既存の復元アルゴリズムは，符号の種類やグラフ構造に依存し，汎用性に欠ける。
- 様々なグラフに対応可能な復元アルゴリズムを開発し，バッチ符号の性能を最大限に引き出す。
- 線形バッチ符号に特化した復元アルゴリズムの調査を実施し，アルゴリズムの階層構造を明らかにした。
- グラフ構造に基づくバッチ符号に対し，任意の二部グラフでの復元アルゴリズムを検討し，既知の結果を一般化した。
- 異なる種類の復元アルゴリズムを導入・調査することで，バッチ符号の性能評価の新たな視点を提供した。
受容から学ぶ：コーディングゲームにおける累積後悔 [cs.CL, cs.IT, cs.DC, cs.LG, math.IT]目的：コーディングゲームにおける累積後悔の低減
- 分散システムにおいて，中央集権的な認証がない環境下での信頼性の確保が重要である。
- 既存のコーディング理論は，正直なノード数が多いことを前提としており，現実のシステムへの適用が困難である。
- 不確実な敵対者に対する学習アルゴリズムを開発し，累積後悔を最小化することを目指す。
- 本研究では，Stackelbergリーダーとして行動するデータ収集者が，敵対者のユーティリティトレードオフを学習する不完全情報コーディングゲームを分析した。
- 提案アルゴリズムは，有望な受容ルール周辺を探索し，累積後悔が亜線形になることを証明した。
- 数値実験により，提案アルゴリズムの有効性が確認された。
高速スケッチを用いたべき乗法加速による，より強固な低ランク近似 [math.NA, cs.DS, cs.LG, cs.NA, stat.ML]目的：低ランク近似のためのべき乗法加速手法
- 大規模データへの主成分分析は重要であり，データ次元削減やノイズ除去に利用される。
- 目標ランクが大きい場合，行列積計算コストがボトルネックとなり，計算時間が課題となる。
- 高速スケッチを用いてべき乗法を高速化し，計算コストを削減することを目指す。
- 高速スケッチを利用するアルゴリズムと理論的枠組みを開発し，べき乗法の加速を実現した。
- 特異値分解，低ランク因子分解，Nystr\"om 近似において，高い数値性能をベンチマーク問題で示した。
- 高速スケッチ法の特性である正則化されたスペクトル近似を用いることで，べき乗法の保証を拡張した。
有界属グラフに対する準線形時間汎用シンコーンアルゴリズム [cs.DS, stat.ME]目的：有界属グラフにおける近似汎用シンコーンアルゴリズムの設計と性能評価
- グラフ構造の最適輸送問題は，多様な応用分野において重要な役割を果たす。
- 従来の汎用シンコーンアルゴリズムは，計算時間が指数関数的に増加するという課題があった。
- 属が制限されたグラフ構造に着目し，計算効率を向上させることを目指す。
- GenusSinkは，グラフの分解，計算幾何学，高速行列ベクトル積の技術を駆使し，従来法よりも大幅な計算時間の短縮を実現した。
- 理論的解析と実装により，GenusSinkは他の効率的なシンコーンアルゴリズムよりも高精度な計算が可能であることが確認された。
- GenusSinkは，特定の条件下では，総当たり法と同等の結果を数値的に保証することも示された。
稠密および疎グラフにおけるストリーミング複雑度の分離 [cs.DS, cs.CC]目的：最大カット問題におけるストリーミング空間複雑度の分離
- 大規模グラフ処理において，ストリーミングアルゴリズムの効率性は重要である。
- 近似カットを出力する場合の空間複雑度に関する明確な理論的限界が不足している。
- 稠密グラフと疎グラフで空間複雑度の違いを明確にすること。
- 稠密グラフにおいては，O(n/ε^2)の空間で近似カットが実現可能であり，Ω(n)の空間が必要であることが示された。
- エッジ数がΘ(n/ε^2)の疎グラフでは，Ω(n log(ε^2 n)/ε^2)の空間が必要であり，これはタイトな限界である。
- 稠密ストリームにおけるDensest Subgraph問題やCSPにおいても同様の分離が確認された。
エージェントAIエコシステムにおけるツールクローニングの評価 [cs.CC, cs.SE, cs.CR]目的：エージェントAIエコシステムにおけるツールクローニングの現状把握
- LLMエージェントの発展に伴い，外部ツールへのアクセスが重要になっている。
- ツール市場におけるツールの重複は，多様性の評価を歪める可能性がある。
- ツールクローニングがエコシステムに与える影響を定量的に評価する。
- 大規模なツールリポジトリデータセットを構築し，クローニングを測定するパイプラインを開発した。
- MCPエコシステムにおいて，類似度が高いツールの多くが実際にクローンであることが確認された。
- ツールクローニングは，データセットやベンチマークの構築において考慮すべき重要な課題である。
オンライン・シュタイナー森におけるリコース [cs.DS]目的：オンライン・シュタイナー森問題における低コストな部分グラフの維持
- ネットワーク設計や通信網構築において，重要な接続性を効率的に実現する必要がある。
- 既存手法では，一度構築したネットワークからの削除が許されない場合，性能限界がある。
- 少ないエッジの挿入・削除で，安定した性能を維持するアルゴリズムを開発すること。
- 提案アルゴリズムは，定数倍の競争率を達成する。
- 平均的に，要求あたり$O(\log n)$本のエッジの挿入・削除で対応可能である。
- リコース（エッジの挿入・削除）の回数を抑えつつ，効率的な接続維持を実現した。
制約付き最小エントロピー結合によるクロスドメイン損失圧縮 [cs.IT, cs.LG, math.IT]目的：クロスドメイン損失圧縮における結合強度最大化
- データ圧縮は情報伝送と保存の基礎であり，効率的な手法が求められている。
- 異なるデータ分布間での圧縮は，情報損失を伴うため，課題が多い。
- 劣化ドメインから目標分布への情報伝送と，分類タスクの性能維持を目指す。
- 提案手法は，サンプルごとの歪みを最小化するのではなく，ソースと再構成間の結合強度を最大化する。
- 共通乱数を用いることで，中間表現の削除が可能となり，決定論的な結合定式が得られる。
- MNIST超解像やSVHNノイズ除去実験で，レート増加が分類精度向上と情報豊富な再構成に繋がることを示した。
有限体上OFDMのためのグローバル符号化方式 [cs.IT, math.IT]目的：多利用者通信における信頼性の高いグローバル符号化多重化方式
- 無線通信の効率化は，限られた周波数資源を有効活用する上で不可欠である。
- 既存の多重化方式では，性能向上や複雑な処理が課題となっていた。
- 有限体を用いたOFDMにより，効率的かつ信頼性の高い多重化を実現する。
- 本研究では，有限体上のOFDM（FF-OFDM）における効率的なグローバル符号化多重化方式を提案した。
- 素数長の巡回符号とアダマール同値性を代数的サブキャリアとして利用することで，データストリームの損失なくグローバル多重化を可能にした。
- 受信側では，バイナリ分解定理に基づき，並列バイナリ反復ソフト決定アルゴリズムを用いて非バイナリグローバル符号語を共同復号する。
COBOL-to-Python移行における決定論的オーケストレーションとLLM制御オーケストレーションの比較 [cs.SE, cs.MA]目的：COBOLからPythonへの移行におけるオーケストレーション戦略の比較
- 老朽化したCOBOLシステムの近代化は，専門家不足，大規模なコードベース，厳格な正確性要件から困難である。
- LLMベースの近代化システムはエージェントワークフローに依存するが，その正確性，堅牢性，効率性は不明確である。
- 決定論的オーケストレーションとLLM制御オーケストレーションの性能を比較し，最適な移行戦略を特定する。
- 決定論的オーケストレーションは，LLM制御オーケストレーションと同等の計算精度を達成しつつ，最悪の場合の堅牢性を向上させた。
- 決定論的実行は，実行時のばらつきを減らし，トークン消費量を最大3.5倍削減し，運用コストを大幅に削減した。
- 明示的な検証段階を持つ構造化された移行ワークフローにおいては，固定された実行ポリシーがより安定したコスト効率の良い動作を提供する。
動的ランク，基底，およびマッチング [cs.DS]目的：行列の基本的な代数的性質の維持
- グラフ理論や機械学習など，様々な分野で行列のランクや基底は重要な役割を果たす。
- 従来の動的アルゴリズムは行列の次元に依存し，効率的な更新が困難であった。
- 行列のランクに依存する更新時間のアルゴリズムを開発し，効率的な動的グラフマッチングを実現する。
- 本研究では，ランク$r$に依存する更新時間を持つ初の動的ランクアルゴリズムを提案した。
- エントリ更新は$\tilde O(r^{1.405})$，列更新は$\tilde O(r^{1.528}+ z)$の時間で完了する。
- これにより，最大マッチングのサイズ維持も$\tilde O(|M|^{1.405})$時間で実現可能となった。
多源部分情報分解のための閉形式ガウス推定器 [cs.IT, math.IT]目的：多源部分情報分解の推定
- 複雑なシステムの理解には，情報源間の相互作用を定量的に評価することが不可欠である。
- 既存の閉形式ガウス推定器は2つの情報源に限定され，汎用的な推定器は計算コストが高い。
- 多源からの情報分解を効率的に行う閉形式推定器を開発し，計算問題を解決すること。
- 本研究では，多源部分情報分解のための閉形式ガウス推定器を開発した。
- 推定器は，冗長性，固有情報，相乗効果を計算可能であり，理論的性質も保証されている。
- 実験により，提案手法の計算効率と安定性が確認された。
間接観測下におけるRényiレート-歪み-知覚-プライバシーのトレードオフ [cs.IT, math.IT]目的：間接ソース符号化のためのRényiレート-歪み-知覚-プライバシー（R-RDPP）フレームワーク
- 情報伝送における効率的な符号化と，データの機密性保護は重要な課題である。
- 従来のプライバシー指標は，意味的な回復を不必要に阻害する可能性がある。
- 残余漏洩のみを定量化する条件付きプライバシー指標を導入し，この問題を解決する。
- スカラーガウスRDPPトレードオフを特徴づけ，標準的なプライバシー指標が意味的な回復を不当に罰することを明らかにした。
- α > 1の場合において，ポアソン関数表現を用いた達成可能性の上界を洗練させた。
- ポアソン指数の正確な幾何混合分布を導出し，高次のRényiエントロピーの正確な閉形式表現を得た。
TeleResilienceBench：通信分野におけるLLM推論の回復力評価 [cs.IR, cs.DB, cs.LG, cs.SE]目的：大規模言語モデルの通信分野における推論回復力の定量化
- 通信分野では，高い精度に加え，現実的な状況下でのLLMの信頼性が不可欠である。
- 既存の評価は知識の網羅性を測る傾向にあり，推論能力の評価が不十分である。
- 中断された推論や誤った推論からの回復能力を評価し，改善に資する。
- TeleResilienceBenchは，通信分野の7つのサブドメインにおける推論回復力を定量化する。
- 最も性能の良いモデルでも，平均的な回復率は29.1%にとどまり，モデルの規模拡大だけでは回復力向上は期待できない。
- Nemotron-3-nano 4bは，Qwen3.5モデルを含む他のモデルを上回り，コストパフォーマンスに優れる。
ランダムハイパーグラフの非適応的学習のための高速階層分割アプローチ [cs.IT, math.IT]目的：ランダムハイパーグラフのハイパーエッジ集合の復元
- データ構造の効率的な学習は，様々な応用分野において重要な課題である。
- 既存研究では，復元に必要な計算時間が膨大であるという問題点が存在する。
- 本研究は，効率的な復元アルゴリズムを開発することで，この問題を解決する。
- 提案手法は，既存研究と同等のクエリ数を維持しつつ，復元計算量を大幅に削減した。
- 特に，θ > 2/3 の場合，復元計算量は O(m^{5/3} log n) となった。
- また，θ ≤ 2/3 の場合も，O(m^{5/3} log^2{m} log n) という効率的な計算量を実現した。
GraphInstruct：LLMグラフ生成における能力ギャップを診断するための漸進的ベンチマーク [cs.SI, cs.SE]目的：LLMによるグラフ生成能力の評価と改善
- グラフ構造データは多様な分野で基盤技術であり，その自動生成の重要性は高い。
- 既存のベンチマークは構造的複雑さを考慮せず，LLMの弱点を特定できない。
- LLMのグラフ生成能力のボトルネックを特定し，改善策を導き出す。
- GraphInstructは，グラフ生成の複雑さを6段階に分類し，5つの評価軸でLLMの能力を診断する。
- 制約条件の組み合わせがLLMの性能に最も影響を与えることが判明した。
- 検証と制約を考慮した反復フレームワークが，プロンプトエンジニアリングの限界を超える性能を示した。
機械的推論とエージェント的推論の組み合わせによるMoveの仕様推論 [cs.PL, cs.AI, cs.LO, cs.SE]目的：Move Proverのための仕様推論ツール
- スマートコントラクトの安全性確保は重要であり，Moveはそのための形式検証をサポートする。
- Moveでの形式検証には仕様記述が必要だが，手動での記述は手間がかかる。
- AIを活用し，仕様記述の自動化と形式検証の効率化を目指す。
- 本研究では，Moveのbytecodeに対する最弱事前条件(WP)解析と，Claude Codeのようなエージェント的コーディングCLIを組み合わせた。
- WP解析が機械的な基盤を提供し，AIはWPが苦手とするループ不変式や高レベルな仕様の推論を担当する。
- Move Proverが仕様の妥当性を検証し，エージェントは検証成功までヒント生成と仕様の改良を繰り返す。
Moveにおける命令型高階関数の形式検証 [cs.PL, cs.LO, cs.SE]目的：命令型高階関数を扱うMoveプログラミング言語の形式検証
- スマートコントラクトの安全性が重要視される中で，形式検証による信頼性の確保が不可欠である。
- 高階関数は複雑な挙動を引き起こしやすく，形式検証において新たな課題となっている。
- 命令型高階関数をMove言語で検証するためのフレームワークを開発し，安全性を向上させる。
- Moveの関数値表現と，形式検証器MVPにおける実装方法を定義した。
- 関数を状態遷移とみなすことで，高階関数を含むコードの検証を可能にした。
- 最弱前提条件分析を拡張し，関数の仕様を自動的に推論するツールを開発した。
一般化最小和集合被覆に対する4.509近似アルゴリズム [cs.DS]目的：一般化最小和集合被覆問題における近似解の探索
- 組合せ最適化問題であり，様々な現実問題に応用可能であるため重要である。
- 既存の近似アルゴリズムの性能限界が明確で，改善の余地がある。
- 既存手法の分析を改善し，より良い近似率のアルゴリズムを開発する。
- 本研究により，一般化最小和集合被覆問題に対する4.509近似アルゴリズムが提案された。
- 提案アルゴリズムは，既存の最良近似率である4.642を改善するものである。
- 線形計画法の制約を利用した解析や，ベルヌーイ変数の下界の導出が貢献している。
コーディングエージェント設定ファイルの指示遵守：4つのファイル構造変数の因子実験 [cs.SE, cs.CL]目的：コーディングエージェント設定ファイルの構造要素が指示遵守に与える影響の検証
- AIエージェントの利用拡大に伴い，設定ファイルの重要性が増している。
- 設定ファイルの構造がエージェントの性能に影響する可能性が指摘されているが，実証的な検証は不足している。
- 設定ファイルの構造要素が指示遵守に与える影響を定量的に明らかにする。
- ファイルサイズ，配置，構造，矛盾といった構造的変数に有意な差は見られなかった。
- セッション内で生成される関数数が増加するほど，指示遵守率は低下する傾向が確認された。
- タスクの種類やセッション中の関数生成順序が，指示遵守率に影響を与えることが示された。
2頂点連結性近似アルゴリズム：サイクル制限付き2辺被覆によるアプローチ [cs.DS]目的：2頂点連結な最小全域部分グラフの探索
- ネットワークの信頼性向上は重要であり，2頂点連結性は基本的な要求事項である。
- 既存アルゴリズムの近似比改善の余地があり，より効率的な解法が求められている。
- サイクル構造を制限した2辺被覆を利用し，近似比を向上させることを目指す。
- 本研究では，2頂点連結な全域部分グラフ問題に対する近似アルゴリズムを提案した。
- 提案アルゴリズムは，既存の最良近似比である4/3よりも改善された95/72+εを達成した。
- サイクル制限付き2辺被覆を初期解として利用することで，効率的な近似解を得ることに成功した。
GenioSim: 光ネットワーク上のエッジコンピューティングのための新しいシミュレーションプラットフォーム [cs.NI, cs.SE]目的：光ネットワークを活用したエッジインフラにおけるリソース管理方針の評価
- 光ネットワークとエッジコンピューティングの融合は，低遅延な分散処理を可能にする重要な技術である。
- 実機を用いたプロトタイピングはコストと時間がかかるため，開発初期段階での検証が困難である。
- 光ネットワークとエッジコンピューティングを統合したシステムを正確にモデル化するシミュレーションプラットフォームを提供する。
- GenioSimは，PONのリアルな挙動をモデル化し，コンテナとVMベースの仮想化をサポートする。
- 複雑な条件下でのリソース管理方針の評価が可能となり，キャパシティプランニングに貢献する。
- 産業用途のユースケースに基づいた実験により，コンテナ配置やタスクオフローディング方針の選択に有用であることが示された。
エージェントファジング：機会と課題 [cs.CL, cs.CR, cs.SE]目的：ロジックバグ検出のための新たなアプローチ
- 成熟したコードベースでは，論理的バグの発見が困難であり，ソフトウェアの信頼性向上には不可欠である。
- 従来のファジングや静的解析では，多段階の推論を必要とする論理バグの検出が難しい。
- 過去のバグを基に，深層エージェントが原因を分析し，新たなバグ候補を検証することで，検出率向上を目指す。
- AFuzzはV8 JavaScriptエンジン上で約1ヶ月間実行した結果，40個のバグを発見し，合計35,000ドルの報奨金を得た。
- V8のシードから，SpiderMonkeyとJavaScriptCoreにおいても19個のバグを発見した。
- エージェントファジングは初期段階であり，解決すべき課題は残るものの，論理バグ検出の有望な方向性を示唆する。
GELATO：生成エントロピーと Lyapunov 関数に基づく適応型トークンオフローディングによるデバイスエッジ推論のための投機的LLM [cs.NI, cs.DC, cs.IT, cs.LG, math.IT]目的：デバイスエッジ協調推論における，エネルギー制約下でのデコードスループット最大化
- 近年，デバイス上での大規模言語モデル(LLM)推論が活発化し，デバイスエッジ協調推論への関心が高まっている。
- リソース制約のあるエッジ環境において，推論に必要なリソースをトークンごとに効率的に割り当てることは課題である。
- GELATOは，トークンごとのリソーススケジューリングを最適化し，エッジ環境に適応した推論を可能にする。
- GELATOは，生成エントロピーとLyapunov関数に基づき，オンラインでドラフティング予算を決定し，長期的なエネルギー・スループットのトレードオフを管理する。
- 実験結果から，GELATOは既存の分散SDアーキテクチャと比較して，トークンスループットを64.98%向上させ，エネルギー消費量を47.47%削減することが示された。
- LLMのデコード品質を維持しつつ，リソース制約のある環境下で最適なトレードオフを実現する。
LLMベースのコード生成における安全性の攻撃：ユーザビリティ要件を武器として [cs.CR, cs.SE]目的：LLMベースのコード生成におけるセキュリティ脆弱性の攻撃手法と，その対策
- ソフトウェア開発においてLLMの利用が拡大しており，安全なコード生成能力が不可欠である。
- セキュリティ要件は暗黙的・不明確な場合が多く，ユーザビリティ要件とのバランスが課題である。
- ユーザビリティ要件を悪用し，セキュリティ要件を低下させる攻撃（UPAttack）を自動化するフレームワークを開発する。
- 本研究で開発したU-SPLOITは，複数のLLMにおいて最大98.1%の攻撃成功率を達成した。
- U-SPLOITは，脆弱性のある代替コードのユーザビリティに関する報酬を特定することで，効果的な攻撃シナリオを生成する。
- 攻撃の検証には，既存のテストケースと動的に生成されたエクスプロイトペイロードを使用している。
単なる予測 [cs.LO, math.FA, math.GN]目的：予測関数の表現と性質
- 不確実性の定量化や意思決定において，予測関数は重要な役割を果たす。
- 線形または超線形な予測関数に限定されがちで，より一般的な予測関数の性質は未解明な部分が多い。
- 単なる予測関数を，線形および超線形な予測関数のinfimum/supremumとして表現することを目指す。
- 全ての予測関数は，一定の条件下で，超線形予測関数の上限として表現可能である。
- 同様に，線形予測関数の下限としても表現可能であることが示された。
- 予測関数の空間と，線形/超線形予測関数の空間間の同相写像が，直交関係を用いて構築される。
微分代数プログラムに対する演繹的洗練計算 [cs.LO]目的：微分代数プログラムの性質と関係の演繹的検証
- 近年，制御システム等の安全性評価において，微分代数方程式を含むシステムの検証が重要視されている。
- 微分代数方程式は解析的に解くことが難しい場合が多く，正確かつ効率的な検証手法が課題である。
- 本研究は，微分代数方程式の複雑な検証を可能にする洗練計算手法を提示し，その正当性を保証することを目的とする。
- 微分代数プログラムの軌跡を比較するための新規なトレースベースのセマンティクスを導入した。
- 提案された洗練計算は，微分代数方程式のインデックス削減の証明を可能にし，各ステップの正当性を保証する。
- これにより，複雑な微分代数方程式の漸進的な検証・簡略化が，音性を保ちながら実現できる。
局所ラベル微分プライバシーにおける凸最適化：全てのプライバシーレベルにおけるタイトな限界 [cs.CL, eess.AS, cs.DS]目的：局所ラベル微分プライバシー制約下における確率的凸最適化
- 機械学習において，プライバシー保護は重要な課題であり，データ利用を促進する上で不可欠である。
- ラベル微分プライバシーは強力なプライバシー保護を提供するが，精度低下を招く可能性がある。
- ラベル空間サイズに対する線形コストがL-LDPモデルの根本的な制約であるかを検証し，改善を目指す。
- 本研究では，高プライバシーおよび中程度のプライバシーレベルにおいて，従来の線形依存性からラベル空間サイズに対する平方根依存性へと，過剰リスクの限界を改善するアルゴリズムを提案した。
- 提案アルゴリズムは，高プライバシー（$\epsilon \leq 1$）において$O\left({\sqrt{\frac{K}{\epsilon n}}}\right)$，中程度のプライバシー（$1 \leq \epsilon \leq \ln K$）において$O\left({\sqrt{\frac{K}{e^{\epsilon} n}}}\right)$という過剰リスクを達成する。
- また，十分大きな$n$に対して，全てのプライバシーレベルにおける情報理論的な下限を証明し，提案アルゴリズムの最適性を示した。
自律性を超えて：ガバナンスと回復力のあるエンタープライズAI実行のための動的階層型エージェントランナーフレームワーク [cs.NI, cs.CL, cs.CL, cs.AI, cs.SE]目的：エンタープライズAI実行のためのガバナンスと回復力を備えた動的階層型フレームワーク
- LLMエージェントの活用は重要だが，エンタープライズ環境での安全な運用が課題となっている。
- 既存のフレームワークは自律性を重視するあまり，ガバナンス機能が不十分である。
- リスクに応じたリソース配分と独立した検証プロセスにより，安全かつ効率的なAI実行を実現する。
- 動的階層型エージェントランナーは，タスクのリスクプロファイルに基づいて計算リソースとレビュー強度を動的に調整する。
- 提案，レビュー，実行，検証を独立したエージェントが行う「権力分立」アーキテクチャを導入することで，安全性を高めている。
- 検証と復旧の閉ループにより，システム障害をシステムの正常な状態として扱い，回復力を向上させている。
MARGIN：不均衡脆弱性検出のためのマージンを意識した正則化幾何学 [cs.SE, cs.CR, cs.LG]目的：ソフトウェア脆弱性検出の性能向上
- ソフトウェアのセキュリティと信頼性を確保する上で，脆弱性検出は不可欠である。
- 実際の脆弱性データセットは，頻度不均衡と難易度不均衡という深刻な課題を抱えている。
- 幾何学的歪みを軽減し，安定した決定境界を生成することで脆弱性検出の精度を向上させる。
- MARGINは，適応的なマージンmetric学習と双曲空間プロトタイプモデリングを通じて，識別可能な脆弱性表現を学習する。
- von Mises-Fisher濃度推定に基づき幾何学的正則化を動的に調整し，埋め込み分布の確率質量を対応するボロノイセルと整列させる。
- 公開脆弱性データセットにおける実験により，MARGINが強力なベースラインを上回り，特に不均衡データセットで顕著な改善が見られた。
機械学習を用いた2ビット位相シフトビームフォーミングによる低コストGNSS対妨害 [cs.IT, cs.SY, eess.SY, math.IT]目的：低コストGNSS対妨害手法の開発
- GNSSは現代社会の基盤であり，その安定稼働は不可欠である。そのため，GNSS信号に対する脅威への対策が重要となる。
- GNSSは電波妨害に脆弱であり，特に重要なインフラにおいては，妨害対策が課題となっている。
- 低コストで実現可能な妨害対策手法を確立し，GNSSの信頼性を向上させることを目指す。
- 2ビット位相シフトを用いたビームフォーミングは，低コストでの対妨害に有効であることが示された。
- 機械学習（勾配ブースティング決定木）と局所探索を組み合わせることで，高性能かつ低遅延な妨害対策が可能となった。
- 実験結果から，J/S=70dBの条件下で，従来のGNSS受信機と比較してC/N0を11.5dB向上させる効果が確認された。
普遍学習の誤指定 [cs.IT, math.IT]目的：モデル誤指定下における普遍学習の最小最大後悔
- 機械学習の応用範囲拡大のため，現実的なデータ生成過程への対応が重要である。
- 仮定するモデルクラスが真のデータ生成過程と異なる場合，学習性能が低下する。
- モデル誤指定下における普遍学習の理論的限界と最適な学習アルゴリズムを確立する。
- 本研究では，モデル誤指定下における最小最大後悔を解析し，対応する最適な普遍学習アルゴリズムを導出した。
- この定式化は，オンライン・バッチ学習，教師あり・教師なし学習など，様々な学習設定に適用可能な普遍学習の統一的枠組みを提供する。
- 従来の結果を拡張し，データ生成過程におけるあらゆる不確実性に対応する汎用性の高い枠組みを提案する。