arXiv雑要約
プログラム - 2026/08/05 公開
消去半Thueシステムにおける右除算可能性：侵入者推論の最小限の視点 [cs.LO, cs.CR, cs.FL]目的：侵入者推論問題の構造的側面に関する研究
- 暗号プロトコルの安全性評価において，攻撃者の能力を正確に分析することが重要である。
- 一般的な項書き換えシステムでは，推論問題の決定可能性が保証されない場合が多い。
- 最小限の構造を持つシステムにおける推論問題の決定可能性を明らかにすること。
- 全ての関数記号が単項の場合，推論問題は半Thueシステムの右除算可能性問題として表現できる。
- 収束的プレフィックス消去システムおよび収束的サフィックス消去システムに対する新たな決定可能性結果を証明した。
- コンテキストを消去しつつ部分項または変数を持ち上げるシステムでは，推論問題は決定不可能であることが示された。
二項対称チャネルにおける決定論的識別に関する信頼性依存スケーリング則 [cs.IT, math.IT, math.PR]目的：二項対称チャネルにおける決定論的識別の漸近的挙動
- 通信システムにおいて，信頼性の高い情報伝達は不可欠であるため，決定論的識別に関する研究は重要である。
- 決定論的識別においては，誤り確率を十分に小さく保つためのスケーリング則が十分に解明されていない。
- 消失する誤り制約下において，決定論的識別の達成可能なレートが，誤り減衰の様相にどのように影響されるかを明らかにすること。
- 本研究では，大規模偏差，中規模偏差，中心極限の各領域において，達成可能性と上限を明示的に特徴付けた。
- 決定論的識別の漸近的挙動は，チャネル出力のハミングシェル集中幾何学によって支配されることが示された。
- この結果は，離散出力チャネルにおける決定論的識別の有限ブロック長挙動に関する洞察を提供する。
WebAssemblyのデコンパイルと手続き間型推論 [cs.AR, cs.SE]目的：WebAssemblyモジュールのデコンパイル技術
- WebAssemblyは多様な環境で利用が拡大しており，セキュリティ監査の重要性が高まっている。
- 既存のデコンパイルツールは，結果の冗長性，可読性の低さ，型推論の限界といった課題を抱えている。
- WebAssemblyバイナリの挙動理解を深め，潜在的な脆弱性を検出することを目的とする。
- NotDecは，WebAssemblyの型チェックアルゴリズムを拡張し，SSAベースのIRに変換することで，高精度なデコンパイルを実現した。
- JulietテストスイートとHowardデータセットにおいて，100%の再コンパイル成功率を達成し，Ghidraを大幅に上回る性能を示した。
- 実世界のプログラムにおいて，構造体メンバアクセスを85.33%の精度で復元し，Ghidraの9.24%を大きく上回った。
テラヘルツ無線システムにおける高密度接続のための周波数・位置・流体アンテナアレイとビームフォーミング [cs.IT, math.IT]目的：テラヘルツ通信における高密度接続をサポートするための動的周波数・位置・流体アンテナ（D-FPFA）アーキテクチャ
- 次世代通信において，テラヘルツ帯の利用は，大容量・高速通信を実現するための重要な技術となる。
- テラヘルツ帯の通信では，パスロスの影響が大きく，高密度環境下では干渉が深刻な課題となる。
- 本研究は，周波数・位置・流体アンテナ技術を用いることで，これらの課題を克服し，通信性能を向上させることを目指す。
- 提案するD-FPFAアーキテクチャは，従来の位相シフタ型アレイと比較して，合計スループットが約2.3倍向上する。
- D-FPFAアーキテクチャは，TTD型アーキテクチャのスループットの95%を達成しながら，エネルギー効率は約2.8倍向上する。
- 完全接続型D-FPFA（FPFA）は，検討したすべてのアーキテクチャの中で最高のエネルギー効率を実現する。
エンタープライズ自動化におけるLLMのトレードオフ評価：本番環境プラットフォームにおけるワークフロー生成からの教訓 [cs.SE, cs.AI]目的：エンタープライズにおけるLLMを活用したワークフロー生成の有効性とコストに関する評価
- 企業コンプライアンス管理は，変化する規制への迅速な対応が不可欠であり，自動化の重要性が増している。
- 従来の静的オーケストレーターは，ハイブリッドクラウド環境において，リアルタイムなコンテキストへの適応が困難である。
- 本研究は，LLMの分割パイプライン構造により，低コストで高精度なワークフロー生成を可能にすることを目的とする。
- LLMを用いたワークフロー生成において，分割パイプライン構造は，単一構造のパイプラインと比較して構造的成功率を大幅に向上させた。
- 小規模なLLM（mistral-small）でも，分割パイプラインを用いることで実運用レベルの精度を達成でき，高価な大規模モデルへの依存を軽減できることが示された。
- コスト，レイテンシ，モデル選択などの実運用上のトレードオフを分析し，クラウドエンジニアリングにおけるスケーラブルな自動化の実現に向けた課題を提示した。
行列符号上のACDGV MinRank Gabidulin暗号方式の解読 [cs.CR, cs.IT, math.IT]目的：行列符号上のACDGV MinRank Gabidulin暗号方式に対する解読手法
- 現代暗号は情報セキュリティの基盤であり，その安全性は社会機能の維持に不可欠である。
- 公開鍵暗号方式の安全性評価は難しく，新たな攻撃手法が常に開発されている。
- EGMC暗号方式の脆弱性を明らかにし，より安全な暗号方式への移行を促す。
- 提案されたEGMC暗号方式において，秘密鍵の同等な符号を復元できることを示した。
- 本研究では，組み合わせ的および代数的技術を組み合わせた新たな解読手法を提案した。
- この攻撃により，EGMC暗号方式の全パラメータセットが容易に解読可能となり，安全性評価が大幅に低下する。
AIの可視化，消失させないために：GitHubにおけるAIポリシーが開発者体験をいかに変えるか [cs.SE]目的：オープンソースソフトウェアにおけるAIガバナンスポリシーの現状と，開発者体験への影響
- 生成AIの急速な発展により，OSS開発におけるAI利用が拡大しており，その影響を理解することが重要である。
- AI支援開発に対するポリシーがどのように異なり，開発者体験にどのような影響を与えるのかが不明確である。
- 効果的なAIポリシー設計の指針を提供し，OSSコミュニティにおけるAI活用を促進すること。
- AIガバナンスポリシーは，AI支援開発を禁止するのではなく，主に規制することを目的としていることが示された。
- ポリシー採用は，メンテナーの関与増加，AI開示の促進，レビューの質の向上，コード品質の改善に繋がることが確認された。
- 透明性と責任を重視するポリシー設計が，制限的なアプローチよりもコミュニティと品質の向上に効果的であることが示唆された。
UIコンポーネントテストスイートにおけるメタモルフィック関係を用いた行動検証の評価 [cs.SE]目的：UIコンポーネントテストスイートにおける行動検証の度合い
- UIコンポーネントはソフトウェアの重要な構成要素であり，その品質確保は不可欠である。
- 従来のテスト評価指標は，コンポーネントAPIとドキュメントが示す行動関係の検証を十分に捉えられていない。
- メタモルフィック関係を用いて，UIコンポーネントテストスイートの行動検証能力をより詳細に評価することを試みる。
- 推論されたメタモルフィック関係とテストケースの対応付けを行い，関係レベルでのMRカバレッジを算出するフレームワークを開発した。
- 既存のテストスイートは，明示的に検証している行動関係よりも多くの行動関係を行使していることが明らかになった。MRカバレッジは42.5%～47.6%にとどまる。
- MRカバレッジは，ステートメントやブランチカバレッジでは捉えきれない行動のギャップを明らかにし，問題記述のマッピングや，誤り検出に有用であることが示唆された。
コード生成における機能的正確性のための経路・調整・検証 [cs.CL, cs.SE, cs.AI]目的：コード生成における機能的正確性の向上
- 大規模言語モデルの活用が広がっているが，コード生成における機能的正確性は課題である。
- 多様なプログラミングタスクにおいて，単一のプロンプト戦略では十分な精度が得られない。
- プロンプト戦略，モデルの適応，出力選択を最適化し，機能的正確性の向上を目指す。
- RAVパイプラインは，MBPP Sanitizedで0.8911，MBPP Fullで0.8520を達成し，最良の性能を示した。
- ベースモデルと比較して，それぞれ6.35ポイント，9.92ポイントの改善が見られた。
- タスク認識ルーティングと調整適応は，実行ベースの検証と組み合わせることで効果が向上した。
Lempel-Ziv因数分解の感度とサイズの関係 [cs.DS]目的：Lempel-Ziv因数分解の感度とサイズに関する関係性の解明
- データ圧縮において，繰り返し性の高い文字列の効率的な処理が重要であるため。
- 文字列編集操作に対する感度の上限が未解決であり，効率的な圧縮アルゴリズムの設計を妨げる。
- 特定の編集操作に対する感度を解析し，その限界を明らかにすることで，圧縮効率の向上に貢献する。
- 接頭辞削除，部分文字列削除，巡回シフト，文字列反転といった操作において，感度が$\Omega(\log n)$となる文字列の族を構成した。
- LZ因数分解のサイズと最小コラージュシステムのサイズとの関係を明らかにし，LZ因数分解が最小コラージュシステムよりも$\Omega(\log n)$倍大きい文字列の族を構成した。
- LZ因数分解とlex-parseのサイズ関係を明らかにし，lex-parseがLZ因数分解よりも$\Omega(\log n)$倍大きい文字列の族を構成した。
自己進化型コーディングエージェント [cs.SE]目的：自己進化型コーディングエージェントに関する研究の体系的合成
- ソフトウェア開発の効率化が求められる中で，AIエージェントの活用が重要になっている。
- 既存のコーディングエージェントは，ソフトウェアの変化に対応できず，能力が停滞しやすい。
- 過去の経験から学習し，自己改善することで，より適応性のあるエージェントを開発する。
- 本調査では，自己進化型コーディングエージェントの定義，既存研究との違いを明確にした。
- 進化する対象，タイミング，ソフトウェア特有の証拠に基づいた分類法を提案した。
- 実行可能なフィードバックやリポジトリの情報が，エージェントの自己進化を促進する一方，信頼性や安全性といった課題も明らかになった。
パターン数え上げにおける品質管理アルゴリズム [cs.DS, cs.LG, math.CO, math.PR]目的：シーケンスにおける特定のパターン出現頻度の異常を検知する品質管理問題
- 真にランダムな入力の識別は，暗号化やシミュレーションなど，多くの分野で不可欠である。
- 既存のアルゴリズムは品質管理問題の非対称性を活かせておらず，効率的な検証が困難である。
- 品質管理問題の非対称性を利用し，効率的なパターン数え上げアルゴリズムを開発する。
- シーケンス中のパターン（または順列パターン）の出現頻度を効率的に判定するアルゴリズムを提案した。
- 提案アルゴリズムは，最悪の場合でも指数関数的なクエリを必要とせず，多項式時間で動作することが示された。
- 自然な分布下では，品質管理アルゴリズムは，$k$ に対して超線形なクエリを必要とする。
AIがチームに参加するとき！ソフトウェアエンジニアリングチームにおけるAI導入と社会パターンとの関係のモデル [cs.SE, cs.HC]目的：ソフトウェアエンジニアリングチームにおけるAI導入と社会パターンの関係性のモデル
- ソフトウェア開発におけるAI活用は増加の一途を辿っており，チームの連携や知識共有に影響を与えることが予想される。
- AI導入がチームのコミュニケーションや協調にどのような影響を与えるのか，明確な理解が不足している。
- AI導入が引き起こす可能性のあるチーム内の問題（コミュニケーション不足など）を特定し，解決策を提示すること。
- AI導入は，作業の種類によってチームのコミュニティ・スメル（問題）に異なる影響を与えることが明らかになった。
- 専門性の高い作業においては，AI利用がピア間の知識共有を促進し，コミュニティ・スメルの減少に繋がることが示された。
- 協調作業においては，AIがコミュニケーションの質を向上させ，人間同士の連携を補完することが確認された。
並列字句解析のための認定分割点：厳密および剰余による破棄トークン [cs.FL, cs.DC, cs.PL]目的：並列字句解析における分割点の認定条件の提示
- 字句解析はコンパイラの基本的な処理であり，プログラムの実行速度に大きく影響する。
- 従来の字句解析は逐次処理であり，並列化が困難であるという課題がある。
- 入力文字列を分割可能な地点を特定し，並列処理による高速化を実現すること。
- 認定分割点を適用することで，並列字句解析において，シミュレーション，推測，プレスキャン，オーバーラップなどの手法なしに，逐次解析と同等の結果を得ることが可能となる。
- 特に，8スレッド環境において92.6-95.3%の並列効率を達成し，4スレッド環境では3.46-3.94倍の高速化を実現した。
- この手法により，言語固有の仮定ではなく，コンパイラが検証可能な性質として並列字句解析を確立することができる。
パイロットアシストによるナイキストレートを超える高速信号：非漸近的アプローチ [cs.DB, cs.IT, math.IT]目的：超高信頼・低遅延通信におけるナイキストレートを超える高速信号の性能評価
- 次世代通信において，より高いデータレートと低遅延を実現することが重要である。
- ナイキストレートを超える高速信号は，チャンネル推定誤差の影響を受けやすいという課題がある。
- 短パケット長下での信頼性の高いチャンネル推定を考慮した性能限界を明らかにすること。
- ナイキストレートを超える高速信号は，適切な電力配分とパイロットオーバーヘッドにより，最大2dBのSNR利得が得られることが示された。
- 不完全なチャンネル状態情報下でのエラー確率を評価するため，ランダム符号化ユニオンバウンドが導出された。
- 次世代超高信頼・低遅延通信システムの効率的な設計には，非漸近的解析が不可欠である。
システムレベルの観測を用いた，定量検証のためのモデルパラメータのベイズ学習の活用 [cs.DB, cs.IR, cs.SE, cs.AI, cs.LO]目的：定量検証のためのモデルパラメータのベイズ学習における事前知識の獲得と組み込み
- ソフトウェアの信頼性や応答時間といった定量的な特性分析には，ベイズ学習と定量検証の組み合わせが有効である。
- ベイズ推論の精度は事前知識に大きく依存するが，不正確な事前知識は定量分析を阻害する可能性がある。
- システムレベルの観測可能な特性から事前知識を抽出し，定量検証に活用することで，正確な検証結果を得る。
- 提案手法EPIKは，従来の形式モデル遷移パラメータに依存するアプローチとは異なり，現実世界の意味に直接関連するシステムレベルの特性を活用する。
- EPIKは，未知の遷移パラメータの分布を導き出し，それを定量検証に組み込むための二重最適化問題を定式化する。
- 実際のケーススタディや多様なEPIKのインスタンスを用いた実験により，提案手法の有効性，柔軟性，汎用性が示された。
CodeAssay：LLMコード生成のための多指標ベンチマーク，監査済みの正解データ付き [cs.SE]目的：LLMコード生成の評価のためのベンチマーク
- ソフトウェア開発におけるLLMの活用が拡大しており，その性能評価が不可欠である。
- 既存のテストベースの評価は，テストデータの信頼性や網羅性に課題がある。
- 信頼性の高い評価基準と多角的な指標によるLLMコード生成性能の検証を目指す。
- CodeAssayは，185のPythonタスクと，監査済みの正解データ，公開・非公開テスト，テストスイート検証，コード特性測定を組み合わせた。
- 正解データの監査により，1,890件の正誤ラベルのうち9.0%が修正され，モデル間の性能差が拡大した。
- LLMの標準プロンプトによる正答率は77.3%〜98.9%と幅があり，セキュリティ重視のプロンプトはプログラムの長さと複雑性を増加させた。
EffiHolmes：差分プロファイリング誘導リポジトリレベルの時間効率不良箇所特定 [cs.SE]目的：リポジトリレベルの時間効率不良の修正箇所特定
- 大規模ソフトウェアでは時間効率の悪化が頻発し，パフォーマンス低下を招くため，迅速な特定が重要である。
- 従来のデバッグ手法やLLMベースの故障局所化は，時間効率不良には適用困難である。
- EffiHolmesは，差分プロファイリングとLLMを活用し，効率的な修正箇所特定を目指す。
- EffiHolmesは，デフォルトおよびスケールされたワークロード下での差分プロファイリングを用いて時間効率不良箇所を特定する。
- 特定された箇所と非効率な関数を結ぶコンパクトな実行パスを抽出し，ドメイン知識に基づいたLLM推論により根本原因を特定する。
- RepoEffi-Benchを用いた実験により，EffiHolmesは既存手法を上回り，GPT-5.1でファイルレベルAcc@3を4.29％，qwen3-4bで関数レベルAcc@5を15.00％改善した。
GenOS：AIコード生成における意味的堅牢性に関する構成的証明 [cs.PL, cs.AI, cs.SE]目的：AIコード生成におけるプロンプト，コントラクト，ジェネレーター，プログラムの安全な置換基準の確立
- AIによるコード生成は自動化を促進するが，その確率的性質上，わずかな入力変化で出力が大きく変動する可能性がある。
- 既存のシステムは正当性を評価するものの，AIエージェントワークフロー内での構成要素の安全な置換を保証する基準が不足している。
- GenOSは，置換に伴う動作変化を数学的に保証し，意味的な堅牢性を評価する枠組みを提供する。
- GenOSは，各層をマルコフ核としてモデル化し，インターフェースを観測者相対的な同値性で表現することで，置き換え問題を形式化する。
- 同値性を持つプロンプトは，検証済みコミットを含む，下流の同値性閉じたイベントの確率分布を等しくする。
- 挿入ソートの監査実験により，自然言語の言い換えや形式的なコントラクトを用いた場合でも，GenOSが予測した範囲内で確率分布が一致することを確認した。
分離多項式で定義される曲線からのAG符号の置換復号 [cs.IT, math.AG, math.IT]目的：分離多項式で定義される曲線から得られる代数幾何符号に対する置換復号
- 符号理論は，通信やデータストレージにおける信頼性の高い情報伝送に不可欠である。
- AG符号の復号は計算量が大きく，特に高次元の場合に効率的な復号手法が求められる。
- 曲線上の自己同型を利用し，AG符号の復号を効率化する手法を開発すること。
- 分離加法多項式曲線（SAP曲線）と呼ばれる曲線クラスを導入し，それらで定義される1点AG符号について研究した。
- 共通座標を持つ有理点に関連付けられた座標に支持されるバースト誤りを訂正する置換復号集合が得られた。
- エルミート曲線などを含む特殊なSAP曲線のサブクラスに対し，追加の自己同型を利用して，より強力な復号集合を特定した。
バグ報告からブラウザ実行可能な手順へ：LLM駆動のエージェントによるWeb GUIバグ再現 [cs.SE]目的：Web GUIバグの再現手順の自動生成
- ソフトウェア保守において，自然言語によるバグ報告からの再現は重要だが困難である。
- バグ報告には依存関係や入力ファイルなどの前提条件が不足している場合が多い。
- Web GUIバグ報告から，ブラウザレベルの実行と検証を含む再現手順を自動的に構築すること。
- ReBugは，バグ報告と利用可能な成果物から前提条件を再構築し，高レベルな再現計画を生成する。
- ReBugは，ブラウザ内でのツールを介した操作を実行し，ページの状態とアクション履歴を構造的に記録し，報告書から期待される最終状態と比較して検証する。
- 4つのオープンソースWebアプリケーションにおける667件のバグ報告で評価した結果，ReBugは既存手法を上回り，平均RSRが49.96%，タスク完了率が74.96%，アクション実行成功率が86.54%を達成した。
LiveEvalBench: Web生成におけるオープンワールド評価に向けて [cs.AI, cs.SE]目的：Web生成評価のための自動化されたフレームワーク
- Web技術は社会基盤であり，その品質向上は重要である。大規模言語モデルの活用が期待されている。
- 既存の評価方法は静的であり，Webアプリケーションのインタラクティブ性や多様な実装に対応できない。
- Web生成評価を，適応的かつ拡張可能なエージェントベースのプロセスとして実現する。
- LiveEvalBenchは，ビルドエンジニア，コードエンジニア，UIテスターが共同で評価を行うワークフローを構築する。
- 共有可能な評価基準と，実装に即した評価基準を組み合わせることで，多様な実装に対応する。
- 実験の結果，LiveEvalBenchは専門家の判断と高い一致度を示し，モデルのWeb生成能力に関する詳細な分析を可能にする。
パターンをピクセル以上に：マルチモーダルコード生成におけるパターン補完バイアスの測定 [cs.SE, cs.AI, cs.CV]目的：マルチモーダル大規模言語モデルにおけるパターン補完バイアスの評価
- ウェブページをコードに変換する技術は，Web開発の自動化に貢献し，効率化が期待されている。
- 視覚的なパターンが繰り返される場合，モデルが視覚的に誤りながらもパターンに一貫したコードを生成する問題がある。
- ウェブページのスクリーンショットからコードを生成する際の，パターン補完バイアスの影響を定量的に評価する。
- 最先端の5つのマルチモーダル大規模言語モデルを評価した結果，すべてが繰り返し現れるパターンに強いバイアスを持つことが明らかになった。
- カード幅の摂動では平均バイアス率が69.78％，テキストのフォントサイズの摂動では80.22％に達し，平均精度はそれぞれ21.17％と7.89％にとどまった。
- より多くの推論努力が低いバイアスと相関する一方，モデルは異常な要素を認識できても，パターンに一貫した回答で上書きすることがある。
定量ハイパープロパティの統計的検証：ブール量化を超えて [cs.IR, cs.LO]目的：定量ハイパープロパティの統計的検証手法
- 情報フロー制御等の関係的性質の検証基盤として重要である。複雑なシステムにおける安全性評価に不可欠。
- 既存の形式主義では，実世界のシステムの定量的な側面を捉える表現力に限界があった。
- 定量的な視点に基づき，ハイパープロパティの仕様と検証のギャップを埋めることを目指す。
- 定量ハイパーロジック(QHL)を提案し，定量的測度に基づく量化子と豊富な定量表現を導入した。
- QHL仕様の統計的検証問題に対し，サンプル複雑度と統計的保証の解析を行った。
- Hoeffdingの不等式や極値理論等の統計的手法を組み合わせたアルゴリズムを開発し，定量的な検証手法を提示した。
Linuxカーネルコメントにおける陳腐化した関数参照の検出と修正 [cs.SE]目的：Linuxカーネルコメント内の陳腐化した関数参照の検出と修正
- 大規模なコードベースの保守性向上が重要であり，正確なドキュメントが不可欠である。
- カーネルの進化に伴い，コメントとコードの不整合が生じやすく，保守の妨げとなる。
- Git履歴とLLMを活用し，陳腐化した関数参照を検出し，修正案を提示することで，保守を支援する。
- ReCiteはLinuxカーネルv6.18-rc1において，869個の陳腐化した関数参照を検出した。
- 200件の修正案を評価した結果，89.0%が有用な修正ガイダンスを提供し，42.5%が直接適用可能であった。
- 提出した75件のパッチのうち，50件が採用された。
属性間の依存性を定量化する指標：局所的差分プライバシー [cs.MA, cs.CL, cs.CR, cs.IT, math.IT]目的：属性間の依存性によるプライバシー漏洩の正確な測定
- 多次元ユーザーデータ収集は，多様な応用における重要な洞察を得る上で不可欠である
- 属性間の依存性はプライバシーリスクを高めるため，正確な測定が課題となる
- 既存手法の課題を克服し，実データへの適用可能性を高める
- 提案手法「依存性の三項」（DT）は，3つのパラメータでCPLに関連するペアワイズ依存性を要約する。
- DTは，事前分布知識の不確実性を明示的にモデル化し，堅牢な漏洩推定を提供する。
- 実験により，DTが多様な依存性や不確実性下でCPLを正確に推定することが示された。
LLMはターミナルユーザーインターフェースをテストできるか [cs.SE, cs.AI, cs.LG]目的：ターミナルユーザーインターフェースのテスト手法の確立
- 開発ツール等で利用が拡大しているが，GUIと比較してテスト手法が確立されていない現状がある。
- 既存のテストコードはインターフェースを十分にテストできておらず，静的な画面しか検証していないケースが多い。
- 大規模言語モデル(LLM)を活用し，ターミナルユーザーインターフェースの効率的なテスト手法を提案する。
- 4つの主要なLLMとランダム探索を比較した結果，特定のモデルが常に優位性を示すという結果は得られなかった。
- ランダム探索は時間予算内で高いスループットを実現するが，LLMによるガイダンスは，1回のインタラクションあたりの効率性が高く，入力依存性の高い不具合を発見しやすい。
- 自動的に起動入力を生成することで，それまで起動しなかったアプリケーションを動作させることが可能になり，実用的な改善が見られた。
短パケットリンクにおける耐障害性閾値決定のための予測的トリガ [cs.IT, math.IT]目的：遠隔閾値決定における信頼性向上と早期臨界決定の可能性
- 無線通信において，状態推定の精度だけでなく，信頼性の高い判断が不可欠である。
- 短パケット無線リンクでは，通信途絶のリスクがあり，判断の信頼性が損なわれる可能性がある。
- 通信途絶に強い，予測的な閾値決定メカニズムを開発し，信頼性とエネルギー効率を両立すること。
- 提案手法は，状態推定の実現可能性条件を導出し，予測的な判断更新トリガを実現する。
- 途絶に対する耐性を高めるため，AoI制御によるレジリエンス更新を導入し，信頼性と鮮度を維持する。
- シミュレーションにより，提案手法がベースラインと比較して，より早い，信頼性の高い判断を競争力のあるエネルギーで実現できることが示された。
構造化された因果入力におけるニューラルネットワーク予測の真の因果関係の計算 [cs.AI, cs.LG, cs.LO]目的：ニューラルネットワーク予測の真の因果関係
- 信頼性のあるAIを実現するには，ニューラルネットワークの予測根拠を説明することが不可欠である。
- 既存の説明手法は入力特徴を独立と仮定するため，構造化された依存関係を持つ入力に対して誤解を招く可能性がある。
- 本研究は，入力依存関係を考慮した真の因果関係を特定し，より正確な説明を可能にすることを目指す。
- 本研究では，Halpern-Pearlの真の因果関係を用いて説明を形式化し，Boolean Structural Causal Models（SCM）を用いて入力依存関係をモデル化した。
- 境界伝播と分枝限定法を適用することで，完全性と最小性を保証した真の因果関係を計算することに成功した。
- 実験結果から，提案手法はブルートフォースやILPと比較してスケーラビリティが大幅に向上し，大規模なSCMにおいても効率的に真の因果関係を算出できることが示された。
固定予算対目標カバレッジ：有界VC次元における部分的集合被覆の境界 [cs.DS]目的：有界VC次元における部分的集合被覆問題の近似アルゴリズムの限界と可能性
- 集合被覆問題は，情報検索，機械学習，最適化など，様々な分野で基礎的な問題である。
- 部分的集合被覆問題はNP困難であり，効率的な近似アルゴリズムの設計が難しい。
- 有界VC次元という制約下で，部分的集合被覆問題に対する近似アルゴリズムの限界を示す。
- 部分的集合被覆問題は，VC次元が7であっても，パラメータ化された$(2-\delta)$-近似アルゴリズムを持たない (FPT≠W[1]を仮定)。
- 有界セミラダー指数を用いることで，目標達成保証が回復する。これはVC次元よりも強い制約だが，$K_{d,d}$-フリー設定を一般化する。
- 重み付き部分的集合被覆問題において，$k$個の集合で重み$W$をカバーできる場合，$k+1$個の集合で同じ重みをカバーできるアルゴリズムを提案した。
b彩色からb*彩色へ：大きな周囲長とパラメータ化複雑性 [cs.DM, cs.DS, math.CO]目的：b*彩色に関するグラフの構造とアルゴリズム的性質の調査
- グラフ彩色問題は，計算機科学や組合せ最適化において基本的な研究対象である。
- b彩色およびその拡張であるb*彩色に関する計算量的な困難さが残されている。
- 特定のグラフクラスにおけるb*彩色可能性の判定と計算の効率化を目指す。
- 周囲長が7以上のグラフはb*単調である，すなわち誘導部分グラフにおけるb*彩色数は増加しないことが示された。
- 周囲長が5以上のd正則グラフにおいて，b*彩色数がd+1となるクラスを発見し，b彩色に関する既知の結果を強化した。
- b*彩色のパラメータ化複雑性を解析し，多くのパラメータにおいてb彩色と同程度の複雑性を持つことを示した。
RISベース送信器を持つMIMOシステムにおけるQoS制約下での電力最小化 [cs.IT, math.IT, math.PR]目的：RISベース送信器を用いた仮想マルチユーザMIMOシステムの電力最小化
- 無線通信において，電力効率の向上は重要な課題である。省電力化はバッテリー寿命の延長や環境負荷の低減に繋がる。
- 既存の電力最小化手法は，計算量が膨大になり，実用的なシステムへの適用が困難となる場合がある。
- 本研究では，RISの特性を考慮し，計算量を削減した電力最小化手法を開発することで，この課題を解決する。
- 提案手法は，QPSKおよび一般的なM-PSK変調方式において，QoS制約を満たしつつ，送信電力を最小化できることが示された。
- 部分的な分枝限定法(PBB)および二分法を用いることで，計算複雑さを抑えつつ，良好な電力効率を実現している。
- RISの高解像度化により，計算量をさらに削減できることが確認された。
2頂点連結性の拡張に対する単一指数FPTアルゴリズム [cs.DS]目的：2頂点連結性の拡張問題
- グラフ理論は，ネットワーク設計や最適化問題に応用され，様々な分野で重要である。
- グラフの連結性を高める問題は計算困難であり，効率的なアルゴリズムが求められている。
- この研究では，2頂点連結性を効率的に拡張するアルゴリズムを開発することを目的とする。
- この研究では，2頂点連結性の拡張問題に対し，O^*(36^kW)の実行時間を持つ決定性アルゴリズムを提案した。
- これにより，無重みの場合の実行時間はO^*(k^{O(k)})からO^*(36^k)へと改善され，リンクコストも扱えるようになった。
- このアルゴリズムは，カット頂点沿線の分割へのメビウス反転に基づいたキャンセル恒等式を利用している。
履歴は履歴を意味する：ワークフロー永続化層におけるチェックポイント，中断，および再開セマンティクスの機械検証可能な準拠契約 [cs.MA, cs.LG, cs.DC, cs.LO, cs.SE]目的：中断，クラッシュからの回復，および再開における効果のセマンティクスに関する機械検証可能な契約の確立
- ワークフロー管理は，現代の分散システムにおいて重要な役割を担う基盤技術である。
- 既存のワークフローフレームワークでは，再開時の挙動に一貫性がなく，明確な契約が存在しない。
- 本研究は，ワークフローの再開セマンティクスに関する信頼性のある基準を提示し，フレームワークの準拠性を検証する。
- 再開セマンティクスに関する6つの特性（継続性，効果の正確性，分岐の決定性など）を定義した。
- TLA+モデルを用いて参照セマンティクスを厳密に検証し，スケーラビリティを実証した。
- 複数のフレームワーク（LangGraph, CrewAI, pydantic-graph等）を評価した結果，互換性がないことが明らかになった。
最悪ケース最適ジョインアルゴリズムの能力向上 [cs.DB, cs.DS]目的：最悪ケース最適ジョインアルゴリズムへのフィルタ処理の組み込み
- グラフデータベースの普及に伴い，複雑なグラフパターン照合の効率化が重要である。
- 既存のグラフ照合では，フィルタ処理が前処理や後処理として扱われ，効率が低下する場合がある。
- 最悪ケース最適ジョインアルゴリズムにフィルタ処理を組み込むことで，効率改善を図る。
- 提案手法は，既存のコンパクトインデックス「Ring」を拡張し，プロパティグラフへの対応と効率的なフィルタ処理を実現した。
- 実装結果から，提案手法が様々なベースラインシステムと比較して優れた性能を示すことが確認された。
- フィルタ処理をネイティブに組み込むことで，グラフ照合の効率を大幅に向上させることが示された。
誘導部分グラフ同型性とクラスタ頂点削除数によるパラメータ化最大共通誘導部分グラフの複雑性 [cs.DS]目的：誘導部分グラフ同型性および最大共通誘導部分グラフのパラメータ化複雑性
- グラフ構造の比較は，生物情報学，ソーシャルネットワーク分析など，幅広い分野で重要である。
- 大規模グラフにおける部分グラフ同型性問題は計算困難であり，効率的なアルゴリズムが求められている。
- クラスタ頂点削除数をパラメータとして用いることで，問題の複雑さを軽減し，実用的な解法を開発することを目指す。
- 誘導部分グラフ同型性問題に対し，$O^*(k^{O(k)})$ 時間のランダム化アルゴリズムを提示し，固定パラメータ実行可能性を示す。
- 最大共通誘導部分グラフ問題については，$O^*(2^{O(k^2)})$ 時間のランダム化アルゴリズムを提示し，ETHに基づく下界を証明した。
- 3-MCIS の変種は，各入力グラフのクラスタ頂点削除数が2の場合でさえNP困難となることを示した。
二部スペクトル拡張子上のハードコアモデル：すべての逸散率における計数とサンプリング [cs.DS]目的：二部スペクトル拡張子上のハードコアモデルにおける近似計数およびサンプリングアルゴリズム
- グラフ理論における基本的なモデルであり，統計物理学や計算機科学への応用が期待される。
- ハードコアモデルの正確な計数はNP困難であり，効率的な近似アルゴリズムの開発が課題である。
- スペクトル拡張性という条件を利用し，あらゆる逸散率で効率的な計数とサンプリングを可能とする。
- スペクトル拡張条件 $\lambda\leq \frac{1-\xi}{\sigma_2(M_G)}$ が満たされる場合，ハードコアモデルの分割関数に対するFPRASと効率的な近似サンプラーが提供される。
- 高逸散率領域では，ポリマーモデルのアプローチを洗練し，特異スペクトル境界のみから必要な位相優勢およびクラスター展開条件が導かれることが示された。
- スペクトル拡張性を利用することで，ランダムなΔ規則二部グラフに対して，十分大きなΔに対してあらゆる逸散率でのアルゴリズムが再現される。
OTFS 기반無許可ランダムアクセスにおける構造スパースネスを考慮したユーザ活動検知とチャネル推定 [cs.IT, eess.SP, math.IT]目的：大量機械型通信におけるユーザ活動検知とチャネル推定の同時最適化
- 次世代無線通信において，多数のデバイス接続を支える大量機械型通信の実現が重要である。
- 高速移動環境下における二重選択性チャネルへの対応が，信頼性の高い通信の課題となっている。
- 遅延ドップラーチャネルの構造的スパースネスに着目し，高効率な活動検知・推定手法を確立する。
- 提案手法は，受信アンテナ間およびユーザ間における二重スパース構造を効果的に活用する。
- 構造化スパースネス期待値伝播(SS-EP)アルゴリズムにより，ベイズ推論を効率的に行うことを可能にした。
- シミュレーション結果から，提案手法が既存手法を大幅に上回る性能を示すことが確認された。
改良されたユークリッド浅いライトツリー [cs.CG, cs.DS]目的：ユークリッド空間における浅いライトツリーの構成
- グラフ理論はネットワーク設計や最適化問題に応用され，効率的なデータ伝送や通信を実現する上で不可欠である。
- 既存の浅いライトツリーの構成は，ルートストレッチとライトネスのトレードオフがあり，改善の余地が残されていた。
- ユークリッド空間における浅いライトツリーのライトネスを改善し，より効率的なネットワーク構築を目指す。
- 本研究では，ルートストレッチを$1+\epsilon$に固定した状態で，ライトネスを既存の$2/\epsilon$の障壁を大きく下回る$\left(\frac{5}{3} + o_\epsilon(1)\right) \cdot \frac{1}{\epsilon}$に削減することに成功した。
- さらに，ルートストレッチ$1+\epsilon$を持つ浅いライトツリーを構成し，ライトネスを$\left(\frac{2\pi}{\sqrt{4\pi^2+1}}+o_\epsilon(1)\right)\frac{1}{\epsilon} \approx (0.987+o_\epsilon(1))\frac{1}{\epsilon}$に抑えた。
- この結果は，既存の最良の下界に近づき，浅いライトツリー構成における重要な進歩を示す。
大規模言語モデルはコンパイラが見逃す意味的最適化機会を回復できるか？ [cs.PL, cs.AI]目的：コンパイラが捉えきれない意味的最適化機会の回復
- プログラム性能向上には最適化が不可欠であり，コンパイラはその主要な役割を担う。
- コンパイラは解析対象の表現に意味情報がない場合，有効な変換を見逃してしまう。
- LLMを活用し，コンパイラが捉えられない意味情報を推測・回復することで最適化を支援する。
- LLMは，C/C++コードの文脈から意味情報を回復し，検証可能な成果物を生成できることが示された。
- 最も性能の良いLLMは，94.8%の確率で正しい成果物を生成し，83.3%で1.05倍以上の高速化を達成した。
- LLMは，検証を通じて成果物の正しさを担保することで，コンパイラの分析を補完する役割を果たす。
ハル，線形同値性，および重み付き超楕円コード [math.AG, cs.IT, math.IT]目的：コードの包含関係と結合・交差演算の恒等式の解析
- 代数幾何符号は，情報理論における誤り訂正符号の重要な構成要素である。
- ハル（hull）の構造や，コードの結合・交差演算の関係性は未解明な部分が多い。
- ハルを用いて線形同値性を検出し，符号の構造をより深く理解することを目指す。
- コードの交差における剰余項ε(G,A)が，ハルが線形同値性を検出する鍵となることが示された。
- 超楕円曲線においては，重み付き平面モデルを用いることで，ハルの次元を明示的に計算できることがわかった。
- ハルの非対称性は剰余項に起因し，特定の条件下でハルの最大値はℓ(⌊M/2⌋ D∞)に達することが確認された。
ポアソン・フェルマー過程による間引き作用 [math.CO, cs.CC, math.PR, cs.IT, math.IT]目的：間引き作用の理論的解析
- 確率過程の数学的基礎を深め，応用範囲の拡大に貢献する学問分野である。
- 既存の間引き作用の証明は複雑であり，収束速度の評価が不十分な場合がある。
- 確率変分公式を用いた新しい証明により，収束速度の改善を目指す。
- ユーズの間引き補題と数の薄法則に対する別の証明を与えた。
- 相対エントロピーの確率変分公式を用いることで，新たな収束速度が得られた。
- 既存の結果を補完し，拡張することに成功した。
色制約下における組み合わせ最適化の期待コスト [math.CO, cs.DS]目的：色制約を持つ組み合わせ最適化問題における，最小コストな（張る）部分構造の期待コスト
- 組み合わせ最適化は，現実世界の様々な問題に応用可能であり，効率的な解法が求められている。
- 既存研究では，エッジの色制約がコストに与える影響の定量的な評価が不足していた。
- 色制約が期待コストに及ぼす影響を分析し，最適な構造のコストを予測すること。
- エッジを赤と青でランダムに色付けし，赤エッジの使用に制限を設けることで，バイアスを導入した。
- このバイアスが，最小コストな張る木，最短経路，最小コスト完全マッチング，非対称な巡回セールスマン問題に与える影響を調査した。
- 制約によって許容される赤エッジ数が減少することで，期待コストがどのように変化するかを明らかにした。
順位付きスプレッドとサンプルに基づくテスト [quant-ph, cs.SY, eess.SY, math.ST, cs.CC, cs.DS, math.CO, stat.TH]目的：順位付きスプレッドの概念とその性質
- ランダム性を含む様々な分野で，効率的なアルゴリズム設計の基礎となる。
- 従来のspread conditionでは，集合の最大サイズへの依存性が課題となっていた。
- 順位付きスプレッドを用いることで，この依存性を解消し，より精度の高い評価を目指す。
- 順位付きスプレッド系に対する幅のないヒット判定と重み付き集中定理を証明した。
- サンプルに基づくテスターによる非適応型プロパティテスターのシミュレーションが可能となった。
- 定数クエリ非適応型テスターに対し，Fischerらの予想に近い指数$1-\Theta(1/q)$を達成した。
量子構造化プログラムを高次の量子レジスタの構成として [quant-ph, cs.CC, quant-ph, cs.SE]目的：高次の量子構造化プログラミングの実現に向けた方法論的原理の確立
- 量子計算は複雑な問題解決に不可欠だが，プログラミングの認知負荷が高い。
- 既存の量子プログラムは低レベルなゲート操作に依存し，大規模プログラムでのエラーが発生しやすい。
- 量子レジスタを構成要素とし，高次の抽象化によってプログラミングを容易にすること。
- 本研究では，量子計算全体を量子レジスタの構造として捉える概念的枠組みを提案した。
- 代数的 formalism を用いて高次の構文と低レベル semantics を結びつけることを試みた。
- 提案された構文に基づいて量子 satisfiability modulo theories (SMT) ソルバーの設計が可能となる。
クロス集中サンプリング下におけるロバストな低チューブランクテンソル補完 [stat.ML, cs.IT, cs.LG, cs.NA, math.IT, math.NA]目的：スパースかつ大きな外れ値を含む，部分的なクロス集中サンプリング観測からの低チューブランクテンソルのロバストな復元
- テンソル分解は，高次元データの効率的な表現と処理を可能にする重要な技術である。
- 既存のテンソル補完手法は，観測データに重度の汚染が含まれないことを前提としている。
- クロス集中サンプリングの構造を明示的に活用し，外れ値に対するロバスト性を向上させる。
- 提案手法R-ItCURは，サンプリングされたテンソルクロスをブロック分割し，適応的なブロックごとのウェルシュ補正を適用することで，外れ値を抑制する。
- R-ItCURは，テンソル全体を再構成することなく直接サンプリングされたクロス上で動作し，メモリと計算量を削減する。
- 合成データ，心臓MRIデータ，３次元地震データを用いた実験により，正確な復元とスパースな重度汚染に対する高いロバスト性が確認された。
整数制約下における最適な丸め [cs.DS, math.OC]目的：総和が整数となる実数に対する，総和を維持しつつ丸め誤差を最小化する整数の探索
- 最適化問題において，整数制約は現実世界の資源配分や決定において不可欠である。
- 丸め誤差は，実数値を整数に変換する際に生じ，最適解からのずれを招く可能性がある。
- 丸め誤差を最小化しつつ，制約を満たす最適な整数解を効率的に求めることを目指す。
- 最適解は，各要素を切り上げまたは切り捨てによって得られることが示された。
- 最大となる小数部分を同時に切り上げることで，あらゆるL^q丸め誤差を最小化できる。
- 提案手法は，期待値でのみ制約を保つ独立ランダム丸めとは異なり，決定的な最適性を保証する。
時間特性の効率的な監視 [cs.FL, cs.LO]目的：時間特性の監視手法
- リアルタイムシステムの信頼性確保は重要である。誤作動は重大な結果を招く可能性があるため。
- 複雑な時間特性の監視は計算コストが高く，効率的な手法が求められている。
- 時間不確実性下や時間ずれに対する監視問題を解決する。
- 時間特性と相補特性をTimed B\"uchi Automataで表現し，ゾーン表現を用いた効率的なオンライン監視アルゴリズムを提案した。
- 時間ずれや時間不確実性を考慮した監視を可能にした。
- MoniTAalツールに実装し，長時間のトレースに対する有効性を示した。
欠陥のあるリスト彩色：分散アルゴリズムと応用 [cs.DC, cs.DS]目的：分散グラフアルゴリズムにおけるリスト欠陥彩色問題の解決
- 分散グラフアルゴリズムは，大規模ネットワークにおける効率的な情報処理に不可欠である。
- 従来の分散彩色アルゴリズムは，計算時間や通信量の面で課題が残されている。
- リスト欠陥彩色問題の効率的な解決を通じて，より高速な分散彩色アルゴリズムを開発する。
- リスト欠陥彩色アルゴリズムの高速化は，決定論的 $(\Delta+1)$-彩色アルゴリズムの高速化に直結することが示された。
- Maus と Tonoyan の分散リスト彩色アルゴリズムを拡張し，通信効率の良い解法を提案した。
- 標準 CONGEST モデルにおいて，時間計算量が $O(\sqrt{\Delta}\cdot polylog \Delta+\log^* n)$ の決定論的 $(\Delta+1)$-彩色アルゴリズムを初めて実現した。
Kotlin-Javaクロス依存性の実証的研究と検出 [cs.SE]目的：KotlinとJava間のクロス依存性の実態と検出手法
- Androidアプリ開発においてKotlinの利用が拡大しており，Javaとの相互運用性が重要となっている。
- JavaとKotlinの相互運用における課題や問題点が十分に解明されていない。
- 実証研究を通じて，Kotlin-Javaプロジェクトにおける課題を特定し，解決策を提示すること。
- KotlinとJavaは実プロジェクトで頻繁に相互作用しており，特にアクセスと呼び出しの依存関係が支配的であることが明らかになった。
- クロス言語相互作用のあるファイルは，同一言語内での相互作用と比較して，より多くのコミットと高い欠陥率を示す傾向がある。
- Kotlin-Java間の問題点10種類を特定し，修正戦略を考案。問題検出ツール InteropScan を実装した。