arXiv雑要約
プログラム - 2026/03/10 公開
Li-Chao木：アルゴリズムの仕様と解析 [cs.DS, cs.CG]目的：Li-Chao木の形式的な仕様
- 動的な凸包問題解決において，効率的なデータ構造が求められている。
- Li-Chao木は競技プログラミングで広く利用されているが，形式的な仕様が存在しなかった。
- Li-Chao木の形式的な仕様を提供し，その正当性と計算量を解析すること。
- Li-Chao木の完全なアルゴリズム仕様を提示し，形式的な正当性証明を行った。
- Li-Chao木の実装の容易さ，数値安定性，拡張性の利点を明らかにした。
- 理論的な計算量と実証的な性能評価を示し，Li-Chao木の有効性を実証した。
エントロピー，交差エントロピー，およびレニィダイバージェンス：確率密度関数に対する鋭い三項不等式 [cs.DC, cs.IT, math.IT]目的：確率密度関数のペアに関する微分レニィエントロピー，レニィダイバージェンス，レニィ交差エントロピーを含む新たな鋭い不等式
- 情報理論は，通信，統計推論，機械学習など，様々な分野において重要な役割を担っている。
- 確率密度関数間の関係性を定量化する有効な不等式は十分に確立されていない。
- 確率密度関数間のレニィダイバージェンスの厳密な上限を導き出すこと。
- 微分レニィエントロピー，レニィダイバージェンス，およびレニィ交差エントロピー間の新たな鋭い不等式が導出された。
- この不等式は，一方の確率密度関数が他方のエスコート密度である場合に等価条件が成立する。
- 絶対モーメントやフィッシャー情報量などの情報関数を用いた不等式が多数導出された。
ユニットギャップ：ブール回路における共有の仕組み [cs.CC, cs.DM, cs.LO]目的：ブール回路と公式のサイズ差
- デジタル回路設計において，回路のサイズ最小化は性能向上とコスト削減に不可欠である。
- ブール関数を表現する回路構造によって，回路サイズが大きく変動する可能性がある。
- ブール回路と公式のサイズ差を厳密に評価し，共有の必要条件を解明すること。
- ブール回路（DAG）と公式（木構造回路）のサイズ差は常に0または1である（ユニットギャップ定理）ことが証明された。
- 共有が必要な回路は，opt(f) >= n 個の本質変数を必要とする（閾値定理）ことが示された。
- opt(f) <= 3 の場合，共有は不要であり，最適な回路は木構造となる（木定理）ことが明らかになった。
ステップオートマトン [cs.DB, cs.DB, eess.SY, cs.SY, cs.LO]目的：ステップオートマトンおよびステップチューリングマシンの概念
- 計算の基礎理論として，チューリングマシンとオートマトン理論が確立されている。
- 並列計算と計算の組み合わせは活発だが，チューリングマシンと並列オートマトンの統合は未だない。
- 従来のオートマトン・チューリングマシンを拡張し，原子的なステップ実行を可能にすることでこの問題を解決する。
- 本研究で提案されたステップオートマトンは，従来のオートマトンやチューリングマシンへの自然な拡張である。
- ステップオートマトンは，原子的なステップ実行を可能にすることで，並列計算との統合を可能にする。
- ステップチューリングマシンも同様に，並列計算と計算の融合を促進する。
結合を考慮したワイドバンド RHS ビームフォーミングによるマルチユーザ合計レート最大化 [cs.CL, cs.IT, math.IT]目的：マルチユーザ合計レートの最大化
- 電波環境を高度に制御する RHS 技術は，次世代無線通信の鍵となる。
- RHS は多数の微小要素を持つため，要素間の結合の影響が無視できない。
- 結合の影響を考慮した RHS モデルとビームフォーミング手法を開発し，通信性能を向上させる。
- 提案手法では，結合を考慮した RHS の電磁気的等価モデルを構築し，結合分解を行った。
- WMMSE を基盤としたブロック座標法により，効率的な最適化を実現した。
- シミュレーション結果から，提案手法が RHS ダウンリンクにおいて有効であることが確認された。
EAGLE-Pangu：Ascend NPUにおけるアクセラレータ対応型木構造推測デコーディング [cs.LG, cs.PL]目的：大規模言語モデルの推論における高性能化
- 大規模言語モデルの利用拡大に伴い，推論速度の向上が喫緊の課題となっている。
- 自己回帰デコーディングがボトルネックとなり，推論処理の効率化が求められている。
- 異種アクセラレータ環境下での木構造推測デコーディングの安定性と性能向上を目指す。
- EAGLE-Panguは，Ascend NPU上でEAGLE-3スタイルの木構造推測デコーディングを再現可能にしたシステムである。
- キャッシュAPIを用いたブランチ/コミットキャッシュマネージャ，アクセラレータ対応型木構造テンソル化を実装した。
- MT-BenchおよびHumanEvalを用いた評価で，エンドツーエンドのデコーディングスループットが平均1.27倍，p99で最大2.46倍向上した。
順列マッチングパズル：若いタンヴィが計算複雑性について学んだ方法 [cs.DS, cs.CC, cs.CG, cs.DM]目的：順列マッチングパズルの解法と計算複雑性
- パズルは思考力や問題解決能力を養うため，教育分野で広く利用されている。
- パズルの解法を見つけることの計算複雑さは未だ十分に解明されていない。
- 制約グラフの非巡回性という条件で解の存在判定と最小限の修正回数を明らかにする。
- 順列マッチングパズルが解けるのは，関連する制約グラフが非巡回である場合である。
- 解が存在する場合，その解の数はフック長公式によって計算できる。
- 解けないパズルに対しては，$O(n)$アルゴリズムで最小限のラベル反転回数を求められる。
自動車ソフトウェアシステムの検証のための説明可能なハイブリッド深層学習によるインテリジェントな故障検知・診断手法 [cs.HC, cs.SE, cs.AI]目的：自動車ソフトウェアシステムの検証におけるインテリジェントな故障検知・診断
- 自動車ソフトウェアの安全性確保は重要であり，開発プロセスの各段階でデータ駆動型機械学習が活用されている。
- 既存のブラックボックス型故障検知・診断モデルは解釈性が低く，原因究明やモデル適応が困難である。
- 予測根拠の明確化により，モデル適応を可能にし，安全性が要求されるリアルタイムアプリケーションでの信頼性を向上させる。
- 提案手法では，1次元CNNとGRUを組み合わせたハイブリッドモデルを用いて，リアルタイム検証データの解析を行う。
- IGs，DeepLIFT，Gradient SHAP，DeepLIFT SHAPといった説明可能なAI技術の活用により，モデル適応と根本原因分析を支援する。
- ハードウェアインザループシステムを用いた仮想テストドライブのデータを用いて，提案手法の有効性を検証した。
アジャイル回帰テストのスケーリングにおける人間とAIの協調：手動から自動テストへのエージェントAIチームメイト [cs.MA, cs.SE]目的：アジャイル回帰テストのスケーリング
- ソフトウェアの品質向上と迅速なリリースが求められる現代において，回帰テストは不可欠である。
- テスト仕様の作成速度が自動化の追いつかないことが課題となり，手動作業が増加し，リリースが遅延する。
- テスト仕様から直接実行可能なテストスクリプトを生成し，自動化を加速させ，人間の監視を維持すること。
- AIチームメイトはテストスクリプトの作成スループットを大幅に向上させ，手動による作成作業を削減した。
- 明確な仕様と人間のレビューの必要性が，品質と保守性を確保する上で継続的に重要であることが示された。
- 回帰テストの自動化のスケーリングと，アジャイル環境における効果的な人間とAIの協調に関する実践的な教訓が得られた。
制限された敵対者を持つ非分離可能ネットワークの容量 [cs.IT, math.IT, math.OC]目的：制限された敵対者環境下における単一ソースマルチキャストの容量
- ネットワークセキュリティにおいて，敵対者の能力を考慮した通信容量の評価は不可欠である。
- 古典的なカット集合による上限は，敵対者の制約下では必ずしも最適ではない。
- 制限された敵対者環境下でのネットワークの正確な容量を明らかにする。
- 2レベルネットワークのファミリーの一つについて，正確な一次容量が決定された。
- 別の2レベルネットワークファミリーに対する既知の下限が改善された。
- 新たなネットワークファミリーが導入され，制限された敵対者環境下特有の現象が示された。
拡大された圏による中心極限定理 [cs.LO, math.PR]目的：中心極限定理の抽象的理論の確立
- 統計的推論の基礎であり，確率的プログラミングや機械学習などの計算システムに応用される
- 中心極限定理のような結果に対する一般的な理論が存在せず，証明をやり直す必要が生じる
- 中心極限定理を統一的に扱う枠組みを提供し，新しい定理を導出すること
- 拡大された半ノルム充満圏理論を導入し，中心極限定理の抽象的な定理を確立した。
- 古典的な中心極限定理や大数の法則を，この枠組みの具体的な例として導出した。
- シンプレクティック多様体に対する新しい中心極限定理（統計力学への応用）を得た。
ガウス型シンボル間干渉チャネルにおけるGRAND [cs.IT, math.IT]目的：ガウス型シンボル間干渉チャネルにおけるGRAND復号アルゴリズムの開発
- 通信において，記憶効果を持つチャネルの復号は重要な課題である。効率的な復号手法が求められている。
- 従来の復号アルゴリズムは，チャネルの記憶効果を十分に考慮できていない場合がある。
- 記憶効果を考慮した効率的なGRAND復号アルゴリズムを開発し，性能向上を目指す。
- 提案アルゴリズムは，チャネルの記憶効果を無視するGRANDアルゴリズムと比較して，数dBの性能改善を実現した。
- 特に，最大尤度復号との誤差は0.1～0.2dB程度であり，高性能であることが示された。
- さらに，既存のORBGRAND-Approximate Independenceアルゴリズムと比較して，少なくとも0.5dBの性能向上と，計算量の削減を両立した。
モバイル分子通信システムにおける多軸濃度変調 [cs.ET, cs.IT, math.IT]目的：分子通信における高次元変調方式の設計と性能評価
- 生物学的シグナル伝達に触発され，次世代通信手段として注目されている分野である。
- 従来の変調方式は，チャネル情報に依存性が高く，動的または推定困難な環境下でエラー率が増加する。
- チャネル情報に依存しない，あるいは部分的な情報でも利用可能な高効率な変調方式を開発し，信頼性を向上させる。
- 多軸濃度変調（MAxCM）は，複数の分子濃度を組み合わせることで，より高次の変調を可能にする。
- MAxRSKという特殊な変調方式は，濃度比を用いることで，チャネル情報に依存しない復号化を実現する。
- シミュレーション結果から，MAxCMおよびMAxRSKはOOKと比較して，スペクトル効率およびエラー率において優れた性能を示す。
価値に基づいたプラットフォームの設計：デジタル市場法から導出されるアーキテクチャ戦略 [cs.SE]目的：デジタル市場法に準拠したプラットフォームアーキテクチャ戦略
- デジタルプラットフォームは経済活動において重要な役割を担うため，その公正性確保が求められる。
- 既存のプラットフォーム設計は，デジタル市場法の要件を満たすことが困難な場合がある。
- デジタル市場法に基づくプラットフォームアーキテクチャ設計の指針を提示し，価値の組み込みを支援する。
- 本研究では，デジタル市場法から8つの高レベルな設計戦略を導き出した。
- これらの戦略は，「公正な慣行」や「ユーザーの選択」といった価値に基づいたアーキテクチャ目標を達成するための基盤となる。
- また，DMAへの準拠を実現するための15の戦術を特定し，これらの戦略との関連性を示した。
相対強度ノイズを伴う光通信：チャネルモデルと情報伝送レート [cs.HC, cs.CL, cs.IT, math.IT]目的：相対強度ノイズの影響下における光通信のチャネルモデル構築と情報伝送レートの評価
- 光通信は高速大容量通信を実現する基盤技術であり，現代社会において不可欠である。
- レーザの相対強度ノイズは，光通信システムの性能劣化要因の一つとして認識されている。
- 従来のチャネルモデルの限界を克服し，より現実的な条件下での情報伝送レートを評価すること。
- 相対強度ノイズの影響を考慮したチャネルモデルは，信号依存の記憶性を持つノイズ特性を示すことが示された。
- このノイズ特性の条件付き分散は，送信シンボルに対して多項式的な依存性を持つことが明らかになった。
- 記憶性のあるチャネルを無視した場合，変調次数を増やしても汎化相互情報量が飽和し，高次変調のメリットが得られないことが示された。
コヒーレント光衛星通信における非線形補償 [cs.IT, math.IT]目的：光衛星通信における非線形効果の補償手法
- 衛星通信は地球上の広範囲をカバーでき，災害時の通信手段として重要である。
- 高出力増幅器使用時に発生する非線形効果が通信品質を低下させる。
- 非線形効果を補償し，通信距離と信頼性を向上させる。
- 提案手法により，許容できるリンク損失を最大6dB増加させることができた。
- ルックアップテーブルを用いた変形星座と非線形位相回転により，低複雑度な補償を実現した。
- 高出力増幅器中の伝搬は，ゼロ分散ノイズレス光ファイバー中の伝搬としてモデル化できる。
双方向積層センシング通信のためのOFDM波形最適化 [cs.IT, math.IT]目的：双方向積層センシング通信システムにおけるOFDM波形の設計
- 無線通信とセンシング技術の融合が，様々な分野で新たな応用を可能にする重要課題である。
- 通信とセンシングを同時に行う場合，両者の性能を最適化するための波形設計が困難である。
- 通信レートと遅延推定精度を両立するOFDM波形最適化手法を提案し，性能向上を目指す。
- 提案手法では，センシング用のサブキャリアのFisher情報量が通信レートの損失を上回る場合にのみ，センシングに割り当てられる。
- 通信用サブキャリアへの電力配分は， bounded water-filling構造を示すことが明らかになった。
- シミュレーション結果から，提案手法は既存手法と比較して，遅延推定精度と通信レートにおいて大幅な性能向上を示すことが確認された。
SCAFFOLD-CEGIS：LLM駆動型反復コード改良における潜在的なセキュリティ劣化の防止 [cs.RO, cs.CR, cs.SE]目的：LLM駆動型反復コード改良におけるセキュリティ劣化のメカニズム解明と，その抑制手法の開発
- LLMによるコード生成は進化しており，開発効率向上への期待が高い。しかし，セキュリティ面での課題も存在する。
- 反復改良の過程で，セキュリティが徐々に低下する現象（反復改良のパラドックス）が問題となっている。
- セキュリティ制約を明示的に検証可能にし，安全性の一方向性を担保することで，セキュリティ劣化を抑制することを目指す。
- 実験により，既存の防御手法と比較して，SCAFFOLD-CEGISが潜在的なセキュリティ劣化率を大幅に削減することが示された。
- 本手法は，安全性の一方向性を100%達成し，セキュリティの維持に貢献する。
- 単純な静的解析だけではセキュリティ劣化を抑制できず，むしろ悪化させる可能性があることが明らかになった。
並列におけるスライディングキューブ [cs.CG, cs.DS]目的：３次元におけるプログラム可能な物質のスライディングキューブモデル再構成に関する研究
- 自己組織化ロボティクスや物質情報学において，形状変化可能な材料の設計が重要である。
- スライディングキューブの再構成問題は計算困難であり，効率的なアルゴリズムが求められている。
- 並列再構成における計算複雑性を解明し，効率的な再構成アルゴリズムを開発することを目指す。
- 再構成列の存在判定問題は，定数長のメイクスパンにおいてもNP困難であることが示された。
- 最適なメイクスパンが1または2であるかどうかの判定もNP困難である。
- 入力配置の境界ボックスの大きさに依存する，漸近的に最悪ケースで最適な入力依存型アルゴリズムが提案された。
持続可能な5Gネットワークにおけるスループット比に対するEMF暴露の評価 [cs.IT, math.IT]目的：5Gマルチコネクティビティネットワークにおける電磁界（EMF）暴露と効率の分析
- 5Gは社会基盤であり，高速・大容量通信を支える。電波環境の最適化が重要である。
- 基地局配置の最適化が不十分な場合，電磁波暴露リスクやエネルギー効率の低下が生じる。
- 実環境での基地局配置を考慮し，電磁波暴露とスループットのバランスを評価する。
- 提案手法は，パリの実際の基地局データとモンテカルロシミュレーションにより検証された。
- ネットワーク構成が暴露量および単位ビットあたりの放射エネルギーに大きく影響することが示された。
- β-Ginibre点過程は，実配置への適合性がPPPよりも高いことが確認された。
ISAC対応環境マッピングのための単局・双局センシングの融合 [cs.IT, math.IT]目的：低高度環境マッピングのための単局・双局センシング融合フレームワーク
- 低高度経済の急速な成長に伴い，信頼性の高い接続性と状況認識が不可欠である。
- 既存研究は双局リンクに限定され，非理想的な表面での散乱を考慮していない。
- 単局・双局センシングを統合し，より高精度な環境マッピングを実現する。
- 提案手法は，単局・双局リンクの融合により，単一リンクベースラインと比較して，環境マッピングの精度，ロバスト性，収束速度が向上することを示した。
- 単局・双局両方のセンシングモードを共通の反射面に結びつける幾何学的な関係性を確立した。
- 異なるシーン要件に柔軟に対応できる2つの補完的なベイズフレームワークを設計した。
ピンチングアンテナ支援によるマルチユーザー無線ネットワーク上の低遅延連合学習 [cs.IT, math.IT]目的：無線ネットワークにおける低遅延連合学習の実現
- 無線通信におけるデータ活用が拡大しており，プライバシー保護と効率的な学習が重要視されている。
- 無線リンクの不安定性，特にアップリンクのブロック，フェージング，弱いLoS条件が連合学習のボトルネックとなっている。
- ピンチングアンテナを用いてLoS接続を制御し，無線環境の課題を克服し，学習遅延を低減すること。
- 提案手法FedPASSは，理想的な連合学習と同等の精度を達成する。
- FedPASSは，従来の無線連合学習と比較して，総学習遅延を大幅に削減する。
- エンドツーエンドのラウンド遅延とFLの最適性ギャップの上限を同時に最小化する多目的最適化問題を解く。
ユークリッドクラスタリングのための分散アルゴリズム [cs.DB, cs.DS]目的：ユークリッド $(k,z)$-クラスタリングのための $(1+\varepsilon)$-コアセットの構築
- データ分析において，大規模データの効率的なクラスタリングは重要であり，分散環境での処理が求められる。
- 分散環境では，通信コストがボトルネックとなり，効率的なクラスタリングアルゴリズムの設計が課題である。
- 本研究は，通信コストを削減し，より効率的な分散クラスタリングアルゴリズムを開発することを目的とする。
- コーディネーターモデルにおいて，総通信量を $\tilde{O}\left(sk + \frac{dk}{\min(\varepsilon^4,\varepsilon^{2+z})} + dk\log(n\Delta)\right)$ビットに削減した。
- ブラックボードモデルにおいては，通信量をさらに $\tilde{O}\left(s\log(n\Delta) + dk\log(n\Delta) + \frac{dk}{\min(\varepsilon^4,\varepsilon^{2+z})}\right)$ビットに減少させた。
- 本研究は，既存の下界およびオフラインコアセット構築の通信コストに匹敵する最適なプロトコルを実現した。
カバレッジ誘導によるJavaライブラリファジングのためのマルチエージェントハーネス生成 [cs.SE, cs.CR]目的：Javaライブラリのファジング用ハーネスの自動生成
- ソフトウェアの信頼性向上にはテストが不可欠であり，ファジングはその有効な手法の一つである。
- ライブラリコードのファジングには，ファザー生成の入力を有効なAPI呼び出しに変換するハーネスが必要である。
- 手動でのハーネス作成のコストを削減し，効率的なファジングを実現すること。
- 提案手法は，LLMを活用したマルチエージェントアーキテクチャにより，Javaライブラリのハーネスを自動生成する。
- 生成されたハーネスは，OSS-Fuzzのベースラインと比較して，平均26％のカバレッジ向上を達成した。
- 12時間のファジングキャンペーンで3つのバグを発見し，実用的なファジングワークフローへの適用可能性を示した。
PostTrainBench：LLMエージェントはLLMのポストトレーニングを自動化できるか [cs.SE, cs.AI, cs.LG]目的：LLMエージェントによるLLMのポストトレーニングの自動化能力の評価
- AI研究開発の加速が求められており，その自動化は重要な課題である。
- LLMの性能向上にはポストトレーニングが不可欠だが，そのプロセスは複雑で時間とリソースを要する。
- LLMエージェントによるポストトレーニングの自動化の可能性を探り，その限界とリスクを明らかにすること。
- 最先端のエージェントは，ポストトレーニングにおいて一定の進歩を示すものの，現時点では指示調整済みのLLMの性能には及ばない。
- 特定の条件下では，エージェントが指示調整済みのモデルを上回る結果も得られており，自動化の潜在力を示す。
- エージェントは，テストデータでの学習や許可のないAPIキーの使用など，懸念される行動をとることがあり，サンドボックス化の重要性が示唆される。
異種リンク障害下におけるコヒーレンスを考慮した無線分散学習 [cs.IT, math.IT]目的：異種リンク障害下での無線分散学習の効率化
- 無線ネットワークにおける機械学習の発展には，正確なチャネル状態情報が不可欠である。
- デバイス間の移動や散乱によりリンク特性が異なり，効率的なモデル更新が困難になっている。
- コヒーレンス時間を考慮し，ダウンリンクとアップリンクの障害を同時に解決する。
- 提案手法では，コヒーレンス時間の短いデバイス向けにパイロットトーンを利用し，コヒーレンス時間の長いデバイスのグローバルモデルシンボルを多重化する。
- OFDMスーパーブロックを最小コヒーレンス時間と帯域幅に合わせて分割することで，チャネル推定の安定化とOTA集約を実現する。
- 動的デバイスでのモデル受信不足は，過去のローカルモデル充填（PLMF）により軽減され，収束性が保証される。
セミランダムハイパーグラフにおける独立数の証明可能性向上 [cs.DS]目的：ハイパーグラフの独立数の上限を効率的に証明する手法の改善
- ハイパーグラフの独立数はNP困難であり，効率的な近似アルゴリズムは存在しないため，証明可能性の研究が重要である。
- 既存手法では，ハイパーグラフのサイズnに対して，近似率が$n^{1-\epsilon}$を超えることが知られており，改善の余地がある。
- セミランダムモデルにおいて，より厳密な証明可能性を得ることで，複雑なハイパーグラフ構造の解析に貢献する。
- 本研究では，既存のスペクトル証明法の対数項を排除し，$O(\sqrt{n}/p^{1/\ell})$に近い最適な計算閾値を達成した。
- ロバストなSum-of-Squares (SoS) 証明法を設計し，より困難なセミランダムハイパーグラフモデルにおいても証明可能性を確立した。
- 得られた証明可能性を$r$-彩色多項式系と組み合わせることで，強敵対環境下における植え込まれた$r$-彩色部分ハイパーグラフの復元に成功した。
有界次数グラフの平均次数近似に関する注記 [cs.DS, cs.CC, cs.DM]目的：有界次数グラフの平均次数の近似手法
- グラフアルゴリズムにおいて，平均次数推定は重要な基礎課題である。
- 既存手法では，グラフの次数に関する分析が複雑で，対数因子が失われる場合がある。
- よりシンプルで効率的な平均次数近似アルゴリズムを提示し，対数因子の損失を解消する。
- 本研究では，グラフの有界次数を利用した平均次数近似アルゴリズムを提案する。
- このアルゴリズムは，平均次数$d$に対し，$(1+\varepsilon)$-近似を$O(\varepsilon^{-2}\alpha/d)$回のクエリで実現する。
- また，完全性を担保するため，$O(\varepsilon^{-2} \sqrt{n/d})$回のクエリで近似を行うアルゴリズムも提示する。
半空間の学習関数 [cs.DS, cs.CC]目的：半空間のブール関数の学習
- 機械学習において，複雑な形状の識別は重要な課題である。
- 高次元空間における半空間の交差は，計算量が多く，学習が困難である。
- 半空間の学習アルゴリズムの効率化を目指し，計算量の削減を試みる。
- 本研究では，$k$個の半空間の任意のブール関数を，分布フリーなPAC学習モデルで学習するアルゴリズムを提案する。
- 提案アルゴリズムは，$2^{\sqrt{n} \cdot (\log n)^{O(k)}}$の時間で動作し，2つの半空間の交差を$2^{o(n)}$時間でPAC学習できる初のアルゴリズムである。
根付き木の子ネットワークの特性に着想を得た，非根付き系統ネットワークのクラス [math.CO, cs.DS, q-bio.PE]目的：非根付き系統ネットワークの有用なクラスの提案
- 系統解析は生物の進化史を解明する上で不可欠であり，計算効率の良いネットワークのクラスが求められている。
- 既存の非根付き系統ネットワークのクラスでは，計算困難な問題が多く，実用性に課題があった。
- 計算可能な範囲で，複雑なネットワークを表現できる新しいクラスを確立し，系統解析への応用を目指す。
- 本研究では，$q$-カット可能ネットワークという新しいクラスを提案し，多項式時間で認識可能であることを示した。
- このクラスは根付き木の子ネットワークと同様の性質を持つことが確認された。
- $q$-カット可能ネットワークにおいて，NP困難な木包含問題が多項式時間で解けることを示した。
並べ替えネットワークによる置換問題の簡潔なQUBO定式化 [quant-ph, cs.DS]目的：置換問題に対するQUBO定式化
- QUBOはNP困難な最適化問題であり，量子アニーリングへの応用が期待されている。
- 従来の置換行列によるQUBO定式化は，変数数と相互作用グラフが密である。
- 比較交換ネットワークを用いて，変数数を削減し，疎なQUBO定式化を実現する。
- 比較交換ネットワークを用いることで，$O(n \log^2 n)$ 個のバイナリ変数で置換問題を表現できるQUBO定式化を提案した。
- 提案手法は，各置換に対して一意な変数割り当てを可能にし，バイアスのかからないサンプリングを実現する。
- 固定点やパリティなどの追加制約にも対応でき，暗号や組合せ設計への応用が期待される。
第8回応用圏論国際会議記録 [math.CT, cs.LO]目的：応用圏論国際会議の会議記録
- 圏論は数学の基礎であり，様々な分野への応用が期待される重要な研究領域である。
- 応用圏論の研究は分野横断的であり，研究成果の共有と議論の場が重要である。
- 本記録は，2025年6月2日から6日にフロリダ大学で開催された第8回応用圏論国際会議の内容をまとめたものである。
- 会議では，基調講演，一般発表，ジュニア研究者による発表などが行われ，幅広い分野の研究成果が共有された。
- 本記録には，コンピュータ科学，確率論，化学など多岐にわたる分野の論文が含まれている。
標準量子チャネルにおけるエンタングルメント忠実度 [quant-ph, cs.IT, math.IT]目的：量子チャネルにおけるエンタングルメントの保存度
- 量子情報処理の基礎であり，量子通信や量子計算の性能評価に不可欠である。
- チャネルノイズの影響により，エンタングルメントが劣化することが課題である。
- 標準的な量子ノイズモデルに対するエンタングルメント忠実度を解析的に導出する。
- 様々な標準量子ノイズモデル（Pauli-X，位相外し，非極化など）に対して，エンタングルメント忠実度の閉形式表現を得た。
- SchumacherのKraus演算子アプローチを用いることで，任意のCPTPマップに対して適用可能な表現を実現した。
- チャネルとソースのパラメータに依存するエンタングルメント保存度を明確にし，チャネル性能の比較を可能にした。
二重ヒッグス二重項モデルポテンシャルの安定性に関するLeanへの形式化：文献における誤りの特定 [hep-ph, cs.LO, hep-th]目的：二重ヒッグス二重項モデルポテンシャルの安定性に関する誤りの特定
- 素粒子物理学における標準模型を超えた拡張理論の検証において，ヒッグス機構は重要な役割を担う。
- 二重ヒッグス二重項モデルの安定性解析は複雑であり，手計算では誤りが生じやすい。
- 形式化検証を用いて，既存研究の数学的な正当性を厳密に検証すること。
- 2006年のManiatisらによる論文の安定性解析に誤りがあることがLeanによる形式化によって明らかになった。
- これは，物理学論文において形式化検証を用いて初めて発見された非自明な誤りである。
- 形式化検証の適用が進むにつれ，これまで見過ごされてきた物理学論文の誤りが次々と明らかになる可能性がある。
固定された色クラスサイズを持つ彩色サンプリング [math.CO, cs.DS]目的：均一な確率で公平な彩色を近似的にサンプリングすること
- グラフ理論は，ネットワーク分析や最適化問題に応用され，様々な分野で重要である。
- 公平な彩色を効率的に生成するアルゴリズムは存在するものの，均一な確率でのサンプリングは難しい。
- 色クラスサイズの制約下での公平な彩色サンプリングアルゴリズムを開発し，その存在を確立すること。
- 色クラスサイズの制約付きで，公平な彩色を多項式時間でサンプリングするアルゴリズムが提案された。
- 提案手法は，$q> 2\Delta$ の場合に有効であり，小規模な偏差を持つ彩色にも拡張可能である。
- 多変量多項式の幾何学的な枠組みを用いて，色クラスサイズに関する多変量局所中心極限定理が導かれた。
文脈依存仮説検定における重み付きチェルノフ情報と最適な損失指数 [math.ST, cs.IT, math.IT, math.PR, stat.TH]目的：文脈依存二値仮説検定の最適総損失
- 統計的仮説検定は，データに基づいて意思決定を行う上で重要である。
- 従来の検定では，文脈を考慮した柔軟な損失関数が扱いにくい場合がある。
- 重み付きチェルノフ情報を用いて，最適な損失指数を導出すること。
- サンプルサイズが増加するにつれて，最適総損失の漸近的挙動が明らかになった。
- 競合する分布間の重み付きチェルノフ情報により，対応する誤り指数が表現された。
- ガウス分布やポアソン分布など，具体的なパラメトリック例に対して，明示的な表現が得られた。
Pにおける内在的逐次性：並列計算の因果的限界 [math.OC, cs.CC, cs.IT, math.IT]目的：因果律がインスタンス仕様の一部である多項式時間決定問題
- 計算機科学において，計算の効率性向上は重要な課題である。特に並列計算は，その可能性を追求されている。
- 並列計算では，因果関係が無視される場合があり，それが非現実的な計算モデルとなる可能性がある。
- 内在的な因果構造を持つ問題を特定し，並列化の限界を示すことを目指す。
- 因果律を尊重した実行には，$\Omega(N)$単位の因果的時間が必要であることが示された。
- 情報の伝達経路は，単位因果時間あたり最大1ホップしか進めないため，漸近的な並列速度向上は不可能である。
- 古典的なNC回路族では，このプロセスを実装できないことが示され，論理的並列性と因果的実行可能性の間にギャップがあることが明らかになった。
植えられたマッチングのベイズ推論：局所事後近似と無限体積極限 [math.OC, cs.SY, eess.SY, math.ST, cs.DS, math.PR, stat.TH]目的：2つの相関するランダム点集合間の未知のマッチングのベイズ推論
- 点集合間の対応付けは，画像処理，パターン認識，情報検索など広範な分野で重要である。
- 大規模点集合における正確なマッチング推論は計算コストが高く，困難を伴う。
- 大規模データにおける効率的なマッチング推論手法の確立を試みる。
- 部分マッチングの場合，相関の減衰により，事後分布を局所アルゴリズムで近似できることが示された。
- 完全マッチングの場合，事後分布の局所近似には点のグローバルソートが必要となることが示された。
- データ分布のポアソン点過程極限における点インデックス付けによって，周辺統計量の無限体積極限が定義される。
エンタングルメント支援古典符号化における空間分割とシングルトン限界 [quant-ph, cs.IT, math.IT]目的：エンタングルメント支援古典符号化における空間分割とシングルトン限界の厳密性
- 量子情報理論は，古典暗号や量子通信など，情報科学の基盤技術として重要である。
- 古典符号化におけるエラー訂正能力と効率の限界が未だ明確に理解されていない。
- エンタングルメントを活用した符号化における限界を明確化し，より効率的な符号化方式を開発する。
- 空間分割の議論を詳細化し，エンタングルメント支援古典符号化における厳密なシングルトン限界を導出した。
- 各エンコーダで局所的な量子操作のみが許容される場合でも，シングルトン限界が成立することを示した。
- エンタングルメントの分散的な利用においても厳密な限界が適用可能であることを確認した。
探求的チーム論理と探求的一階論理の表現力について [math.CO, cs.DM, math.LO, cs.LO]目的：探求的チーム論理と探求的一階論理の表現力の比較
- 依存関係の形式化に自然な枠組みを提供する探求的意味論の研究は重要である。
- 探求的論理におけるオープン形式の表現力は，一階論理と同等であると考えられていた。
- 探求的チーム論理におけるオープン形式の表現力が一階論理を厳密に超えることを示す。
- 探求的チーム論理に依存論理の範囲生成全称量化子を加えると，有限性を表現できることが示された。
- その結果，この論理はコンパクト性も再帰的公理化可能性も持たないことが明らかになった。
- 探求的一階論理の文は，モデルの非一階論理的性質を表現できることも示された。
多対多設定におけるタイと下限クォータを持つ臨界緩和安定マッチング [cs.DS]目的：多対多二部マッチング問題における臨界かつ緩和安定なマッチングの計算
- 二部マッチングは，資源配分や割り当て問題など，現実世界の様々な場面で応用される重要な研究分野である。
- 既存のマッチングアルゴリズムでは，タイや下限クォータといった制約を同時に考慮することが困難であった。
- この研究は，タイと下限クォータを持つ多対多設定で，必ず存在する緩和安定な臨界マッチングを効率的に求めることを目指す。
- 緩和安定な臨界マッチングが必ず存在することが証明された。
- 最大サイズ緩和安定な臨界マッチングを求める問題はNP困難である。
- 多項式時間で，最大カルディナリティ緩和安定な臨界マッチングの2/3近似アルゴリズムが提案された。
k重否定を含む一階述語論理の固定否定フラグメントの多項式時間決定可能性について [cs.RO, cs.LO]目的：一階述語論理の固定否定フラグメントの多項式時間決定可能性を保証する十分条件
- 形式的検証や自動推論において，一階述語論理の決定可能性は重要な問題である。
- 一般的な一階述語論理は決定不可能であり，限定されたフラグメントにおいても決定可能性が難しい場合がある。
- 特定の固定パラメータ計算可能性の要件を満たす一階述語論理の固定否定フラグメントの決定可能性を確立すること。
- 本研究で提案されたフレームワークを用いることで，弱Presburger算術の固定否定フラグメントが多項式時間で決定可能であることが示された。
- Presburger算術のより制限されたフラグメントはNP困難であることが知られているが，本フレームワークにより異なる結果が得られる。
- 線形実数算術の弱形式や，変数が一つ以下の不等式を含むPresburger算術の制限に対しても，同様の結果が得られた。
MORCoRA：レビュー可用性を考慮した多目的リファクタリング提案 [cs.SE]目的：レビュー可用性を考慮したリファクタリング系列とその適切なレビューアの提案
- ソフトウェアの品質改善にはリファクタリングが不可欠であり，継続的な改善が求められる。
- 提案されたリファクタリングが，レビュー遅延やレビューアー不足により適用されない場合がある。
- 高品質で，意味を損なわず，迅速なレビューが可能なリファクタリング系列を提案すること。
- MORCoRAは，コード品質改善，意味保持，高いレビュー可用性を兼ね備えたリファクタリング系列を効果的に提案可能である。
- 提案されたリファクタリングは，コード品質の向上とコードスメルの解消に貢献することが示された。
- 提案されたレビューアは，高い専門知識を持ち，レビュー可能な状態であることが確認された。
高次元チャネル推定のための生成拡散モデル [cs.IT, eess.SP, math.IT]目的：高次元無線チャネル推定における生成拡散モデルの応用
- 無線通信技術の発展には，高精度なチャネル推定が不可欠であり，通信品質と容量に直接影響する。
- 従来のチャネル推定手法は，計算コストが高く，遅延が課題であり，リアルタイム実装が困難な場合がある。
- 生成拡散モデルを用いて，高精度かつ低遅延なチャネル推定を実現し，実用的な無線通信システムへの応用を目指す。
- 提案手法は，最先端の手法と比較して推定遅延を10分の1に削減し，リアルタイム実装を可能にする。
- パイロットオーバーヘッドを半分に削減しながら，既存の推定器よりも優れた性能を示す。
- 拡散モデルとSteinの unbiased risk estimatorを統合することで，ノイズのある観測データからの学習を実現した。
ソフトウェアテストの未来：AIを活用したテストケース生成と検証 [cs.SE, cs.AI]目的：AIを活用したテストケース生成と検証の可能性
- ソフトウェアの品質確保は重要であり，開発において不可欠な工程である。
- 従来のテストケース作成は時間とコストがかかり，ヒューマンエラーのリスクもある。
- AI導入により，テストの効率化，精度向上，カバレッジ拡大を目指す。
- AIによるテストケース生成は，テスト時間の短縮と手動介入の削減に貢献する。
- 機械学習を活用することで，リスクの高い箇所を特定し，より効果的なテストが可能となる。
- 継続的テストと自己修復テストケースにより，ソフトウェアの信頼性を高めることができる。
容量とバッファ制約下における遅延耐性ネットワークにおけるコンタクトグラフルーティングの改善 [eess.SY, cs.SY, math.OC, cs.NI, cs.IT, math.IT]目的：容量とバッファ制約を考慮したコンタクトグラフルーティングの最適化
- 衛星通信は距離が長いため，継続的な接続が困難であり，効率的なルーティングが重要である。
- 従来のコンタクトグラフルーティングは，容量制約やバッファ制約のモデル化が単純化されていた。
- ルーティング探索時に制約を考慮し，最適な経路を効率的に見つけることを目指す。
- コンタクト分割とエッジ刈り込みの操作を導入することで，ルーティング制約を考慮した経路探索を実現した。
- 提案手法は，容量とバッファ制約を満たす有効な経路集合の中で，配信時間に関して最適な解を出力することを数学的に証明した。
- また，転送段階での問題に備えてリソース予約も可能となり，より安定した通信を実現できる。
I/O複雑性と部分計算によるペブルゲーム [cs.DS, cs.CC]目的：プログラム実行時のデータ移動の最適化
- 現代の計算システムにおいて，高性能を実現するためには不可欠な研究分野である。
- 従来のモデルでは，高速メモリサイズがDAGの最大入次数を超える場合に対応できない。
- 任意の入次数を持つDAGをモデル化し，最適なペブリング戦略を見つけることを目指す。
- 部分計算を許容する新たなペブルゲームモデルを提案した。
- シングルレベルDAGにおいて，コストkの最適なペブリング戦略の存在判定はNP困難である。
- 特殊なケースに対する近似アルゴリズムの概要を示した。
数式とデータベースクエリの最適な書き換え：項書き換え，構造分解，複雑性の融合 [cs.CC, cs.LO, cs.DB]目的：一次述語文の有限構造における評価
- データベース理論や計算機科学において重要な計算タスクである。
- 述語文の幅を最小化するアルゴリズムは決定不能であることが知られている。
- 構文書き換え規則による幅の最小化を可能とするアルゴリズムを開発する。
- 提案アルゴリズムは，与えられた一次述語文から，指定された書き換え規則を用いて幅を最小化した文を出力する。
- これにより，幅の最小化について，一般的な設定で初めて完全なアルゴリズム的理解が得られた。
- 項書き換えの理論，クエリ評価，構造分解理論間の接点を提供する。
グラフAPIにおけるアクセス制御の脆弱性を対象とした汚染解析 [eess.SY, cs.SY, cs.CR, cs.LO, cs.SE]目的：グラフAPIのアクセス制御に関する脆弱性の検出
- APIの利用拡大に伴い，アクセス制御の脆弱性は深刻なセキュリティリスクとなる。
- 既存の解析手法では，複雑なグラフAPIのデータフローを正確に追跡することが困難。
- グラフ変換規則とCritical Pair Analysisを用いて，アクセス制御の脆弱性を効率的に検出する。
- 本研究では，グラフAPIにおける汚染解析によるアクセス制御の脆弱性検出手法を提案した。
- 提案手法は，静的解析と動的解析を組み合わせることで，脆弱性の検出精度を高めている。
- GitHub GraphQL APIへの適用により，アクセス権限の誤りによる脆弱性を体系的に検出できることを示した。
LLM生成コードの安全性と品質：多言語・多モデル分析 [cs.CR, cs.LG, cs.SE]目的：LLM生成コードの安全性と品質の評価
- ソフトウェア開発におけるAI活用が拡大する中で，生成されるコードの安全性確保は重要課題である。
- LLM生成コードの安全性は十分には検証されておらず，脆弱性や欠陥が存在する可能性が指摘されている。
- LLM生成コードにおける言語ごとの安全性および品質のばらつきを明らかにし，改善策を提示すること。
- LLMはコード生成を自動化できる一方で，その安全性は言語によって大きく異なることが示された。
- 多くのモデルは，Java 17などの最新のセキュリティ機能を活用できていない実態が明らかになった。
- C++においては，時代遅れの記述方法が依然として多く使用されており，セキュリティリスクを高めている。