arXiv雑要約
プログラム - 2025/10/13 公開
Uターン：方向転換による誤り分析の強化 [eess.SY, cs.SY, cs.LO]目的：誤り分析の精度向上
- 誤り検出は，プログラムの信頼性確保に不可欠であり，実用的な静的解析への応用が期待されている。
- 誤り検出技術は，誤検出を減らすことが課題であり，既存の手法では十分な精度が得られていない。
- 到達可能な誤り状態と，それにつながる可能性のある入力状態を組み合わせることで，より効果的な分析を目指す。
- 誤り状態を特定するIncorrectness Logic (IL)と，潜在的な誤り状態を見つけるSufficient Incorrectness Logic (SIL)を組み合わせることで，単独の手法よりも効果的な分析が可能となった。
- ILで得られたヒューリスティックな選択をSILに再利用することで，解析の誘導を実現し，探索空間を効率的に削減する。
- この組み合わせ分析は，デバッグとテストを支援し，スケーラブルで表現力豊かなコード契約への新たな道を開く。
AI活用ヘルスケアプラットフォームのためのモデル駆動エンジニアリングアプローチ [eess.SY, cs.SY, cs.SE, cs.AI, cs.LG]目的：AI搭載ヘルスケアプラットフォームの構築手法
- 医療分野におけるAIの活用は，診断精度向上や個別化医療の実現に貢献し，医療の質を大きく改善する可能性を秘めている。
- 医療データの分散性，厳格なプライバシー規制，信頼性のある臨床システム構築の技術的複雑さが，AIの導入を阻害する要因となっている。
- 医療データの相互運用性を確保し，プライバシーを保護しながらAI活用を促進する実践的な道筋を提示することを目標とする。
- モデル駆動エンジニアリング（MDE）フレームワークにより，高水準な仕様から実行可能なソフトウェアへの自動変換を実現した。
- グラフィカルDSLであるMILAと連合学習アーキテクチャの組み合わせにより，生データ交換なしでの機関間連携を可能にし，プライバシーを保護しながら意味の一貫性を維持した。
- がん免疫療法に関する多施設研究において，SVMは主要なタスクで98.5%および98.3%の精度を達成し，手動コーディングの労力を大幅に削減した。
拡張正規表現マッチングの改善 [cs.CL, cs.DS]目的：拡張正規表現マッチング問題の効率的な解法
- 正規表現は，文字列検索やデータ処理の基本的な要素であり，情報科学の根幹をなす。
- 従来のアルゴリズムは計算量が多く，大規模データの処理においてボトルネックとなる場合がある。
- より高速かつ省スペースなマッチングアルゴリズムを開発し，実用性を高める。
- 提案手法は，既存の最良アルゴリズムと比較して，時間計算量を大幅に改善した。
- 時間計算量はO(n^ωk + n^2m/min(w/log w, log n) + m)となり，空間計算量はO(n^2log k/w + n + m) = O(n^2 + m)である。
- 特に，時間計算量の主要項であるn^3kをn^ωkに置き換えることで，効率化を実現した。
行政区画最適化：エッジ重み付き道路グラフへの頂点$k$-中心アプローチ [cs.DS]目的：行政区画の最適化手法
- 効率的な行政サービスの提供には，適切な区画設定が不可欠である。
- 人口動態やインフラの変化に対応した区画の再編が求められる。
- 道路ネットワーク構造を考慮した区画設定で，移動時間格差の最小化を目指す。
- 本研究では，道路グラフのボロノイ分割と頂点$k$-中心問題に基づく新しい区画設定手法を提案する。
- ラトビアにおいて，地理的特徴と人口分布を考慮した実装例を示す。
- この手法は，住民への行政負担のバランス改善に貢献する。
産業用ロボットナビゲーションシステムのシミュレーションに基づくテスト：研究と実践の架け橋 [cs.RO, cs.SE]目的：産業用ロボットナビゲーションシステムのテスト手法
- ロボットの自律的な動作は重要であり，特に産業環境における安全性と効率性が求められる。
- 従来のテスト方法では，実際の運用で発生しうる多様な状況を網羅することが困難である。
- 本研究は，シミュレーションを活用したテスト自動化によって，より網羅的かつ効率的なテストを実現する。
- 本研究で導入したシミュレーション基盤は，従来の手法では見過ごされがちな障害物回避の課題を明らかにすることができた。
- 実験結果から，テストスイートがアルゴリズムの性能差を明確に示し，より堅牢なアルゴリズムの選択を支援することが示された。
- 6ヶ月間の産業評価では，本フレームワークが開発プロセスを改善し，客観的な評価指標を提供することが確認された。
LLMベースのコード翻訳のための木構造化命令チューニングアプローチ [cs.SE]目的：LLMベースのコード翻訳における性能向上
- ソフトウェア開発において，異なるプログラミング言語間のコード変換は重要であり，生産性向上に寄与する。
- 既存のLLMベースのコード翻訳手法は，言語固有の構文の影響を受けやすく，意味的な誤りも発生しやすい。
- 構文情報と意味的整合性を強化することで，より正確なコード翻訳を実現する。
- 提案手法TITは，構文情報を活用し，詳細な並列データ拡張により，構文的混乱を軽減する。
- 二段階の木構造化命令チューニングにより，LLMが構文情報を理解し，正確なコード生成を促進する。
- 実験結果は，TITが既存手法を凌駕し，コード翻訳の成功率を大幅に向上させることを示している。
宇宙地上統合ネットワークにおける時間決定性リモートセンシング画像バックホールの3Cリソース共同割り当て [eess.SY, cs.IT, cs.SY, math.IT]目的：時間決定性リモートセンシング画像の効率的な共同スケジュール
- 地球観測衛星のデータ活用において，リアルタイム性が重要課題となっている。
- 衛星搭載コンピュータ資源の制約から，画像データの転送に遅延が生じる場合がある。
- 変動する多次元リソースを捉え，効率的なリソース割り当てを実現することを目指す。
- 提案手法では，多次元リソースの時間展開グラフ(MDR-TEG)モデルを設計し，複雑性を低減した。
- 成功伝送率最大化問題をMILPとして定式化し，効率的なSRCCアルゴリズムを提案した。
- シミュレーション結果により，提案モデルとアルゴリズムの有効性が確認された。
一般グラフおよび最小次数制約グラフにおける安定カットセットについて [cs.CL, cs.CG, cs.DS, cs.CC, cs.DM]目的：安定カットセットの存在判定と効率的なアルゴリズムの開発
- グラフ理論は，ネットワーク分析や組み合わせ最適化など，様々な分野で不可欠な役割を果たしている。
- 安定カットセットの存在判定問題はNP困難であり，大規模グラフに対する効率的な解法が求められている。
- 既存アルゴリズムの計算量を改善し，最小次数制約下での安定カットセット問題に特化した解法を確立する。
- 新たなアルゴリズムにより，安定カットセット問題の計算量を $O^*(1.2972^n)$ へと改善した。
- 最小次数 $\delta$ が $\frac{2}{3}(n-1)$ 以上の場合，安定カットセットが存在しないことを示した。
- 最小次数が $\delta \geq \tfrac{1}{2}n$ のグラフに対して多項式時間アルゴリズムを開発し，$\delta = \tfrac{1}{2}n - k$ のグラフに対するカーネル化アルゴリズムを提案した。
自然言語推論のためのハイブリッドモデル：三段論理の場合 [cs.CL, cs.CL, cs.LG, cs.LO]目的：自然言語推論における，構成性と再帰性の二つの側面に関する研究
- 論理的推論能力は，応用展開において極めて重要であり，汎化能力が鍵となる。
- ニューラルモデルは汎化能力に課題を抱えており，特に論理的推論において顕著である。
- 構成性と再帰性の区別を明確にし，ハイブリッドモデルによる論理的推論の改善を目指す。
- 大規模言語モデル（LLM）は再帰性にはある程度堪能であるものの，構成性においては苦戦していることが判明した。
- 記号推論とニューラル計算を統合したハイブリッドアーキテクチャが，堅牢かつ効率的な推論を可能にする。
- 比較的小さなニューラルコンポーネントでも，高い効率性を維持できることが実験で示された。
セルラーネットワークにおけるキャリブレーションされたレイ・トレーシングによるサイト固有のRIS展開 [cs.IT, math.IT]目的：セルラーネットワークにおけるRIS展開戦略の自動化
- 通信環境の向上は現代社会の基盤であり，高品質な通信は経済発展に不可欠である。
- RIS技術は有望だが，実用的な展開にはコストや設置場所の最適化が課題となる。
- 現実的な都市環境におけるRIS展開の最適な条件を特定し，課題を明確化すること。
- シミュレーション結果から，有意なカバレッジ拡大には高密度かつ大面積のRIS展開が必要であることが示された。
- RISの大量導入における現実性やコストについては疑問が残る。
- 測定データでキャリブレーションされたデジタルツインを活用し，RIS配置，向き，設定，基地局ビームフォーミングを共同最適化する手法を提案した。
局所最適プライベートサンプリング：グローバルなミニマックスの限界を超える [cs.LG, cs.CR, cs.CY, cs.IT, math.IT]目的：局所的微分プライバシー下での分布からのサンプリング
- プライバシー保護は重要であり，特に個人情報を含むデータ分析においては不可欠である。
- 既存手法はグローバルな最適性に焦点を当てており，特定の分布周辺における局所的な最適性は未解明であった。
- 特定の分布周辺における局所的なミニマックスリスクを解明し，最適なサンプラーを設計すること。
- 局所的ミニマックスリスクは，分布クラスを固定分布P0の近傍に制限した場合，グローバルなミニマックスリスクによって決定されることが示された。
- 汎用的な関数型LDP枠組みへの拡張と，関数型LDPサンプラーの最適性が証明された。
- 提案手法は，既存のグローバル手法と比較して，公開データを持つプライベートサンプリングにおいて一貫して良好な性能を示した。
データ・エンクレーブの優位性：ゼロトラスト世界における最小権限データアクセスという新たなパラダイム [cs.CR, cs.DB, cs.SE]目的：最小権限データアクセスを実現するデータ・エンクレーブのアーキテクチャ
- クラウド環境の進化に伴い，データ保護の重要性が増している。
- 従来の固定的な権限設定が，クラウド環境における重大な脆弱性となっている。
- データレベルでの固定権限を排除し，動的なアクセス制御を実現する。
- データ・エンクレーブに基づくアーキテクチャにより，ゼロ・スタンディング・プリビレッジ(ZSP)とジャストインタイム(JIT)原則をデータレベルで実現。
- 静的な権限を一時的なデータ契約に置き換えることで，プロアクティブな保護を強化。
- 攻撃対象領域の縮小，権限の肥大化防止，監査の簡素化に貢献し，より安全で強靭なデータ環境への移行を促進。
VQ-VAEとGNNを用いた多重ユーザFDDシステムにおけるプリコーダ設計 [cs.IT, cs.AI, eess.SP, math.IT]目的：多重ユーザ無線システムにおける合計レート向上
- 無線通信において，電波伝搬環境に適応した効率的なプリコーディングは，通信品質向上の鍵となる。
- 従来のGMMを用いた手法では，フィードバックビット数が増加すると計算量が指数関数的に増加する問題があった。
- VQ-VAEを用いることで，GMMの欠点を克服し，少ないフィードバックビットで高性能なプリコーディングを実現する。
- 提案手法では，VQ-VAEとGNNを共同学習させることで，従来のサブDFTパイロット行列や反復プリコーダアルゴリズムを上回る性能を示す。
- シミュレーション結果から，提案フレームワークは少ないパイロットやフィードバックビットでシステムを展開できることが示された。
- 特に，合計レートの点で顕著な改善が確認された。
生態依存性を持つネットワークにおける多様性のパラメータ化アルゴリズム [cs.IR, cs.DS, math.CO]目的：生態学的制約下におけるネットワークの多様性を最大化するタスクのパラメータ化計算複雑性
- 生物多様性の保全計画において，限られた資源を効率的に配分するための重要な指針となる。
- 系統樹やネットワークと食物網といった生態学的制約が個別に研究されてきたが，両者を同時に考慮した研究は少ない。
- 系統樹ネットワークと食物網を統合的に考慮し，多様性と生存可能性を両立する効率的なアルゴリズムを開発する。
- 系統樹ネットワーク，食物網，制約パラメータを用いて，指定された多様性以上のタスク集合を見つけるための決定問題を提示した。
- パラメータ制約k，許容される多様性損失D，食物網のスキャン幅などのパラメータに関する計算複雑性の二分法を明らかにした。
- 食物網の依存関係を考慮した系統樹多様性問題を解決するための，色符号化アプローチに基づく新しいアルゴリズムフレームワークを提案した。
単一機械における再開を伴う荷重加重メイクスパンの最小化 [cs.DS]目的：単一機械における再開を伴う荷重加重メイクスパンの最小化
- スケジューリング問題は，資源の効率的な利用に不可欠であり，現実世界の様々な場面で最適化が求められる。
- 再開を伴うジョブスケジューリングは，中断と再実行を伴うため，最適化が難しい。
- オンラインアルゴリズムの性能限界を明らかにし，より良いアルゴリズムを開発すること。
- 決定論的なオンラインアルゴリズムの競争比の下限を1.4656と確立した。
- 全てのジョブの処理時間が同一の場合，競争比を1.3098より改善する決定論的なオンラインアルゴリズムを設計した。
- 同一処理時間ジョブの場合の競争比の下限を1.2344と証明した。
多言語対応Pythonプログラミング言語 [cs.PL]目的：プログラミング言語へのアクセス性向上
- プログラミング教育のグローバル化が重要であり，言語の壁は大きな障壁となる。
- 英語知識の不足が，プログラミング学習の参入障壁となっている。
- 母語でのプログラミングを可能にし，学習機会の拡大を目指す。
- Pythonコードを他の言語に変換するトランスパイラ「UniversalPython」を開発した。
- ウルドゥー語でのPythonプログラム作成の実現可能性を示した。
- 今後，対応言語を拡大し，より多くの人々がプログラミングを学べるようにする。
MIMO検出のためのソフトグラフTransformer [cs.LG, cs.IT, eess.SP, math.IT]目的：MIMO検出における高性能なニューラルアーキテクチャの開発
- 無線通信において，MIMO技術は容量と信頼性を向上させる重要な技術である。
- 最大尤度検出は最適だが計算量が膨大であり，既存手法は現実的な次元での仮定に依存する。
- MIMOファクターグラフ構造を考慮し，事前情報を活用することで，高性能かつ効率的な検出を実現する。
- 提案手法SGTは，最大尤度検出に匹敵する性能を達成する。
- SGTは，自己注意機構とグラフ認識型クロス注意機構を組み合わせることで，文脈依存性と構造的なメッセージパッシングを効果的に行う。
- SGTは，柔軟性と解釈可能性に優れた受信システムを提供し，事前情報を活用する。
MDL様式のコスト汎関数KC，分布保存還元($A2^d$)，および3SATに対する$AC^0$+log下界 [cs.CC, cs.IT, cs.LO, math.IT]目的：リソース制約のある分類器に対するMDL様式のコスト汎関数$K_C$の導入と，分布保存的な多対一還元のための全変動安定還元補題($A2^d$)の証明
- 計算複雑性理論において，問題の難易度を形式的に示すことは，効率的なアルゴリズム設計の基礎となる。
- 現在の小深度回路の下界証明は，厳密な条件を課す場合が多く，より緩やかな条件下での証明が求められている。
- 分布を保存する還元を用いることで，小深度回路の下界証明の適用範囲を広げ，より現実的なモデルに対する限界を示す。
- バランスのとれた3XORインスタンスの分布において，$P$-一様$AC^0$+logモデルに対するサイズを考慮した下界が得られた。
- 決定論的かつ射影的な3XOR->3SAT変換は，その像ウィンドウ上で測度保存的であり，この還元により下界が3SATに移行する。
- この研究は，小深度回路下界証明における測度保存的な還元の下での，このようなサイズを考慮した下界の初の明示的な$K_C$-解釈を提供する。
ロバスト統計を用いた無知識プロダクト混合状態トモグラフィ [quant-ph, cs.DS]目的：プロダクト混合状態への近似
- 量子状態の特性評価は量子情報処理の基礎であり，その精度向上が重要である。
- 従来の無知識トモグラフィは純粋状態に限定されており，混合状態への適用が課題であった。
- 本研究は，混合状態に対する効率的な無知識トモグラフィアルゴリズムを開発し，その限界を明らかにする。
- 本研究では，プロダクト混合状態に対する無知識トモグラフィアルゴリズムを提案し，効率性を示す。
- このアルゴリズムは，単一量子ビット測定のみを使用し，多項式時間で動作する。
- また，提案手法は，バイナリプロダクト分布のロバスト学習問題への帰着を通じて実現されている。
Leanにおける一般化量子シュタインの補題の形式化 [quant-ph, cs.LO]目的：量子仮説検定における相対エントロピーの操作的意味
- 量子情報理論は，量子技術の発展に不可欠であり，その厳密な理論的基盤が求められる。
- 一般化量子シュタインの補題の原証明には誤りがあり，修正された証明が必要とされていた。
- Leanを用いて証明を形式化することで，厳密性と信頼性を高めることを目指す。
- 本研究では，HayashiとYamasaki(2024)の証明をLeanインタラクティブ定理証明器で形式化することに成功した。
- 形式化の過程で，[HY24]の証明における微細な不正確さを修正し，量子資源理論のより精密な定義を確立した。
- この成果は，量子情報を網羅的に扱うLean-QuantumInfoライブラリの堅牢な基盤を構築し，量子理論のより広範な形式化を促進する。
$\Phi$-進再帰のフラクタル論理 [math.LO, cs.LO]目的：$\Sigma_1$命題推論の削減
- 論理学の基礎を揺るがす可能性があり，計算可能性理論との関連が重要である。
- 従来の論理検証は，計算コストが高く，効率性に課題があった。
- フィボナッチ数列を用いたアプローチにより，検証の効率化を目指す。
- 有効な$\Sigma_1$命題推論がフィボナッチ指標化された証明方程式に還元可能であることが示された。
- モダス・ポネンスの検証は，$O(M(\log n))$時間で線形ディオファントス方程式を解くことで実現する。
- 論理的帰結がフィボナッチ弧の探索問題に対応し，算術的整列による証明検証が可能となった。
独立同一分布の対数凹型確率変数の逆エントロピーべき乗不等式 [math.CO, cs.DM, math.PR, cs.IT, math.FA, math.IT]目的：独立同一分布の対数凹型確率変数における，無限次Rényiエントロピーの最大化条件
- 情報理論において，確率変数のエントロピーは不確実性の尺度として重要である。
- 対数凹型確率変数のエントロピーに関する一般的な上限は未だ十分には解明されていない。
- 本研究は，独立同一分布の対数凹型確率変数和のエントロピー増分の最大値を求める。
- 独立同一分布の対数凹型確率変数$X$と$Y$に対し，$h_\infty(X+Y)-h_\infty(X)$は，$X$と$Y$が指数分布を持つときに最大となることが示された。
- 無限次Rényiエントロピー$h_\infty(\cdot)$を用いて，その最大化条件が解析的に導かれた。
- 整数値の対数凹型確率変数に対しても同様の結果が得られた。
完全動的サブモジュラーカバー問題における制約付き再考 [cs.DS]目的：サブモジュラーカバー問題における解の維持
- 集合被覆問題などに応用可能であり，様々な最適化問題の基礎となる分野である。
- 関数が時間と共に変化する動的な状況下では，効率的な解の維持が課題となる。
- 関数変化に対する解の再計算コスト（再考）を抑えつつ，質の高い解を維持することを目指す。
- 提案アルゴリズムは，$O(\log(f_{max}/f_{min}))$ の競争率で解を維持できる。
- 総再考回数は，$O(\log(c_{max}/ c_{min})\cdot\sum_{t\leq T}g_t(N))$ と評価される。
- 特に正の混合第三微分を持つ関数に対しては，最適な再考回数上限が示された。
K-ASTRO：コード脆弱性検出のための構造を意識したLLMの適応 [cs.NI, eess.SP, cs.NI, eess.SP, cs.SE, cs.LG]目的：コード脆弱性検出における効率と精度向上
- ソフトウェアセキュリティにおいて，コード脆弱性の検出は極めて重要であり，その自動化が求められている。
- 既存手法は，計算資源を大量に消費するか，複雑なグラフ構造に依存し，実用性に課題がある。
- LLMの利点とASTの構造的特徴を組み合わせ，効率的かつ高精度な脆弱性検出を実現することを目指す。
- K-ASTROは，LLMのセマンティック埋め込みとASTの構造的特徴を組み合わせた軽量なTransformerモデルである。
- ASTを基盤としたデータ拡張，構造を意識した注意機構，そしてコードのセマンティクスと構文を統合する適応パイプラインを導入した。
- BigVul，DiverseVul，PrimeVulの3つの大規模データセットで最先端の性能を示し，CPU上での高速な推論を可能にした。
オンライン・メイクスパン最小化：動的ロックによるLPTの性能向上 [cs.DS]目的：オンライン・メイクスパン最小化における性能向上
- スケジューリングは計算資源の効率利用に不可欠であり，様々な分野で重要な課題である。
- 既存のアルゴリズムは，一定の性能限界に達しており，更なる改善が求められている。
- 本研究では，LPTアルゴリズムの性能を超える，より効率的なスケジューリング手法を開発する。
- 提案手法は，3台の機械において競争比1.482を達成し，既存の1.5の壁を超えることを示した。
- 機械数が増加すると提案手法の性能が低下する課題を，動的ロックという新たな技術で克服した。
- その結果，競争比1.5 - 1/O(m^2)を達成し，あらゆる定数mにおいてLPTアルゴリズムを上回る性能を示した。
ノイズのない量子多重アクセスチャネルにおけるベクトル線形計算の容量 [cs.IT, math.IT]目的：量子多重アクセスチャネルにおけるベクトル線形計算の最適通信コスト
- ネットワーク符号化は，情報伝送効率向上に不可欠であり，線形計算はその重要な構成要素である。
- 量子多重アクセスチャネルにおいては，送信側共有量子エンタングルメントの効率的活用が課題となっている。
- 送信側エンタングルメントを活用し，量子多重アクセスチャネルにおける線形計算の通信コストを最小化する。
- 3つの送信機の場合，最適な通信コストを完全に決定した。
- $N$-sum boxプロトコルに基づく符号化方式が，あらゆる場合において情報理論的な最適性を持つことを示した。
- 時間分割やバッチ処理と組み合わせることで，最適な性能を実現できる。
組合せ的n重フォールドのための新しいアルゴリズムと応用 [cs.DS]目的：組合せ的n重フォールド整数計画問題の効率的な解法
- ブロック構造整数計画問題は，様々な応用分野で重要な役割を果たす。
- n重フォールド整数計画問題は，特殊な構造を持つため，既存手法では効率的な解法が難しい。
- 本研究は，特定の構造を持つ組合せ的n重フォールド整数計画問題に特化したアルゴリズムを提案し，解法を可能とする。
- 提案アルゴリズムは，問題を分割統治法によって効率的に解くことが可能である。
- 本アルゴリズムは，実行時間$(n r \Delta)^{O(r)} \log(\|b\|_\infty)$を達成し，問題の規模に対するスケーラビリティを示す。
- 一様マシン上でのスケジューリング，最近傍文字列問題，グラフの不均衡問題への応用を提示し，既存手法と同等またはそれ以上の性能を示す。
変動する状況下での公平な分割 [cs.CL, cs.GT, cs.DS]目的：分割対象のアイテムとエージェントが変動する場合における，1つアイテムまでの羨望自由性の回復
- 公平な分割は，資源配分において不可欠であり，社会的な公正性を実現するための基盤となる。
- 従来の公平分割研究は，静的な状況を前提としており，現実の変動する状況に対応できていない。
- アイテムの損失やエージェントの追加といった変動が生じた際に，公平性を維持するための手法を確立すること。
- 一様単調な評価関数と，すべてが良いものまたはすべてが苦痛なアイテムの場合に，EF1回復問題に対する効率的なアルゴリズムを開発した。
- これらのアルゴリズムは，同一の加法的な評価関数に対して，最適な転送回数（最大で$km/n$）を達成する。
- グラフ構造を持つ評価関数や，単調な二値評価関数を用いた場合においても，最適なアルゴリズムや問題の計算複雑性を明らかにした。
有向 Steiner 木 LP の積分ギャップ：比較的積分解における考察 [cs.HC, cs.DS, cs.DM]目的：有向 Steiner 木問題の LP 緩和における積分ギャップの分析
- ネットワーク設計は，通信ネットワークや輸送システムなど，様々な現実世界の応用において重要な役割を果たす。
- 有向 Steiner 木問題の近似アルゴリズムの性能向上は未解決問題であり，効率的な解法が求められている。
- 比較的積分解を持つ場合に，多項式時間で近似可能なアルゴリズムの存在を検証する。
- 本研究では，有向 Steiner 木問題に対するフローベースの LP 緩和が，比較的積分条件の下で多項式時間近似可能であることを示した。
- 特に，各辺においてフローが 0 または容量に達する（比較的積分解）場合に，標準的な緩和よりも良い積分ギャップが得られることを示した。
- また，比較的積分解を利用することで，$O(\log^3 k)$ 近似のランダム化多項式時間アルゴリズムを提案した。
OrcaLoca：ソフトウェア問題特定のためのLLMエージェントフレームワーク [cs.SE, cs.AI]目的：ソフトウェア問題の特定における精度向上
- ソフトウェア開発の自動化が重要視される中，LLMエージェントの活用が注目されている。
- LLMエージェントとコード検索メカニズムの連携が不十分で，問題特定精度が課題となっていた。
- LLMエージェントとコード検索の連携を強化し，ソフトウェア問題の正確な特定を目指す。
- OrcaLocaは，LLMの行動計画の優先度設定，アクション分解，コンテキストの剪定により，問題特定精度を向上させた。
- SWE-bench Liteにおける関数マッチング率は65.33%を達成し，オープンソースのSOTAを更新した。
- オープンソースフレームワークの修正成功率を6.33%ポイント改善した。
深層畳み込みニューラルネットワークのパラメータ化が，学習後量子化に与える影響について [cs.IT, math.IT]目的：量子化されたニューラルネットワークの出力に関する新たな理論的近似限界
- 深層学習モデルの軽量化は，エッジデバイスなどへの応用において不可欠である。
- 量子化による精度劣化が，モデルの性能を阻害する大きな要因となっている。
- 深層畳み込みニューラルネットワークにおける量子化誤差を理論的に抑制する手法を確立する。
- 本研究では，畳み込みニューラルネットワークに対する量子化誤差の近似限界を大幅に改善することに成功した。
- 層ごとのパラメータ化を考慮することで，MobileNetV2やResNetsなどの既存モデルと比較して，数桁の性能向上を達成した。
- 理論的な結果に加え，MobileNetV2とResNetsを用いた数値的検証により，提案手法の有効性を確認した。
SWE-Arena：ソフトウェア工学におけるファウンデーションモデル評価のためのインタラクティブプラットフォーム [cs.SE, cs.LG]目的：ソフトウェア工学におけるファウンデーションモデルの評価
- ソフトウェア開発の効率化や品質向上に，ファウンデーションモデルの活用が期待されている。
- 既存の評価フレームワークでは，実際のソフトウェア開発ワークフローを十分に再現できない。
- 反復的で文脈に富んだ開発プロセスにおけるモデルの性能を評価するプラットフォームを提供する。
- SWE-Arenaは，透明性の高いオープンソースのリーダーボードを提供し，多段階の会話型ワークフローと，モデルの包括的な比較を可能にする。
- モデルの出力の一貫性を測る「モデル一貫性スコア」や，結論に至るまでの対話ラウンド数を考慮する「会話効率指数」といった新しい指標を導入した。
- リポジトリ関連の情報を対話に自動的に組み込む「RepoChat」機能により，より現実的な開発プロセスでの評価を実現する。
電力システム状態推定のためのオープンソースJuliaフレームワークJuliaGrid [cs.SE]目的：電力システム状態推定のためのフレームワークの開発
- 電力需要の増加と多様なエネルギー源の統合により，電力システムの複雑化が進んでおり，効率的な監視が不可欠である。
- 大規模電力システムの効率的な状態推定は計算負荷が高く，高性能なシミュレーションツールが求められている。
- 本研究は，高性能な状態推定を実現するためのオープンソースフレームワークを開発し，その有効性を示す。
- JuliaGridは，可視性解析，加重最小二乗法，絶対値最小二乗法，異常データ解析などの機能を実装している。
- 電力潮流計算や最適潮流計算も含まれており，状態推定ルーチン向けの計測データ生成を可能にする。
- 大規模システムでの性能評価の結果，既存のオープンソースツールと比較して競争力のある性能を示すことが確認された。
冪等交差型による強い正規化：新たな構文的アプローチ [cs.LO]目的：強い正規化の証明
- プログラムの実行可能性や信頼性を保証する上で，強い正規化は重要な概念である。
- 従来の証明は主に意味論的であり，構文的な証明は困難であった。
- 交差型システムを用いた，構文的な強い正規化の証明を目指す。
- CoppoとDezaniの交差型システム $\Lambda_\cap^e$ の，Church形式版 $\Lambda_\cap^i$ を設計した。
- $\Lambda_\cap^i$ における型付け可能性は，減少関数を用いた測定によって強い正規化を意味することが示された。
- $\Lambda_\cap^i$ と $\Lambda_\cap^e$ は互いにシミュレーション可能であるため，結果は $\Lambda_\cap^e$ にも拡張される。
LLM駆動型反復コードグラフ探索による課題局所化 [cs.SE, cs.AI, cs.CL]目的：課題記述に基づいたコードリポジトリの課題修正パッチ生成のための課題局所化
- ソフトウェア開発において，コードの課題発見と修正は品質向上に不可欠であり，迅速な解決が求められる。
- 既存のLLMベースの課題局所化手法は，探索範囲の広さと深さのバランスが難しく，効率的な課題特定が困難である。
- 本研究は，LLMの探索方向を制御し，より正確かつ効率的な課題局所化を実現することを目的とする。
- 提案手法CoSILは，トレーニングやインデックス作成を必要とせず，関数レベルで高精度な課題局所化を可能にする。
- SWE-bench LiteとSWE-bench Verifiedにおいて，それぞれ43.3％，44.6％のTop-1局所化精度を達成し，最先端手法を平均96.04％上回る。
- CoSILを課題解決手法Agentlessに統合することで，課題解決率が2.98％～30.5％向上した。
ホアール論理における循環証明とその双対 [cs.LO, cs.PL]目的：ホアール論理およびその双対である逆ホアール論理の公理的証明系と循環証明系の関係性
- プログラムの正当性保証はソフトウェア開発において不可欠であり，形式手法が重要な役割を果たす。
- 公理的証明系ではループ不変式や終止測度が必要となり，証明が煩雑になる場合がある。
- 循環証明系を用いることで，ループの展開と循環の妥当性保証により，より簡潔な証明を目指す。
- 部分ホアール論理と逆ホアール論理における循環健全性条件は類似しており，本質的に帰納法的な性質を持つ。
- 全ホアール論理についても同様に，循環健全性条件は類似しており，帰納法的な性質を持つ。
- 循環証明系が健全であり，かつ公理的証明からの変換を通じて相対的な完全性を持つことを示す。
開発者によるAI生成コードの自己申告に関する分析：実態調査 [cs.RO, cs.SY, eess.SY, cs.SE, cs.AI]目的：開発者によるAI生成コードの自己申告方法とその理由
- ソフトウェア開発においてAIの利用が拡大しており，AI生成コードの適切な管理が重要になっている。
- AI生成コードと人間が書いたコードの区別が難しく，透明性の確保が課題となっている。
- 開発者の自己申告を通じて，AI生成コードの可視性を高め，品質管理を支援することを目指す。
- 開発者の多く(76.6%)は，AI生成コードを常に，または時々自己申告していることが明らかになった。
- 自己申告の理由は，将来のレビューやデバッグのための追跡と監視，そして倫理的な配慮である。
- 一方，自己申告を行わない理由は，AI生成コードの大幅な修正，および自己申告の必要性に対する認識の低さである。
- 倫理的およびコード品質の観点から，AI生成コードの自己申告に関するガイドラインが提示された。
動的r-index：LCP境界時間で更新可能な自己インデックス [cs.CL, cs.DS]目的：文字列検索における自己インデックスの動的更新手法
- 文字列検索は情報科学の根幹技術であり，大規模データ処理に不可欠である。
- 従来の自己インデックスは更新にコストがかかり，動的な文字列への適用が困難であった。
- 高重複度文字列において，効率的な更新を可能にする自己インデックスを開発すること。
- 動的r-indexは，更新操作をLCP境界時間で実現する。
- 検索クエリは$\mathcal{O}(m \log r / \log \log r + \mathsf{occ} \log r)$時間，カウントクエリは$\mathcal{O}(m \log r / \log \log r)$時間で実行可能である。
- 実験により，高重複度データセット上での実用的な効率が確認された。
非拡大模糊ALC [cs.LO]目的：非拡大模糊ALCの推論手法
- 不確実な知識の表現は，AI分野において重要であり，記述論理はそのための形式的な枠組みを提供する。
- 従来の模糊記述論理は，表現力と計算複雑性のトレードオフがあり，論理的特性と計算可能性のバランスが課題である。
- この研究は，Zadeh基底を拡張することで，論理的特性と計算可能性のバランスを取り，より実用的な模糊論理を目指す。
- 非拡大模糊ALCは，Zadeh基底にLukasiewicz連結詞を追加し，合理的な定数シフト演算子を導入することで，論理的特性を改善する。
- 提案手法は，EXPTIME時間計算量で非拡大模糊ALCの推論を可能にする，ラベルなしタブロ法である。
- この手法により，古典的なALCと同程度の計算効率で，一般的なTBoxに対する推論が可能となる。
ソフトウェア工学タスクにおける人間評価との乖離を埋めるためのLLMを裁判官とする評価指標 [cs.HC, cs.RO, cs.SE, cs.AI, cs.CL]目的：ソフトウェア生成物の正確性の評価
- ソフトウェア開発支援において，生成物の品質評価は不可欠であり，開発効率と信頼性に直結する。
- 既存の自動評価指標は，スケーラビリティに優れるものの，人間による評価との相関が低いという課題がある。
- 人間評価のコストを削減しつつ，より正確な自動評価指標を確立すること。
- SE-Juryは，複数のLLMを裁判官としてアンサンブルすることで，既存の自動評価指標よりも人間評価との相関が高いことが示された。
- 特に，コード生成とプログラム修復において，SE-Juryは人間間の評価者間の合意に近いレベルに達した。
- SE-Juryは，スケーラビリティと信頼性を兼ね備えた，人間評価の代替となりうる評価指標としての可能性を示す。
AIエージェントがまだあなたを必要とする理由：実際の開発者とエージェントの連携から [cs.SE, cs.HC]目的：開発者とソフトウェアエンジニアリングエージェントの連携における課題と成功要因の特定
- ソフトウェア開発の効率化が求められており，AIエージェントはその有力な手段となる。
- 実世界の複雑なタスクにおいて，AIエージェントは未だ課題を抱えており，開発者の支援が必要。
- 開発者とAIエージェントのより効果的な協調方法を明らかにすること。
- 開発者はAIエージェントとの段階的な連携によって問題解決の成功率を高めることが示された。
- AIエージェントの提案に積極的に関与し，反復的に改善を加えることが，開発者の成功に繋がる。
- AIエージェントへの信頼構築，およびデバッグとテストにおける協調が課題として挙げられた。
ミム幅をパラメータとするハミルトニシティは（実際に）パラNP困難である [cs.CC, cs.DS]目的：ハミルトニアンパスとハミルトニアンサイクル問題の計算困難性
- グラフ理論における重要な問題であり，組合せ最適化への応用も多い。
- ミム幅パラメータにおけるハミルトニシティ問題のパラNP困難性の証明に誤りがあった。
- ミム幅26の線形グラフにおいてもハミルトニアンパスとサイクルがNP困難であることを示す。
- 線形ミム幅26のグラフに対するハミルトニアンパスとハミルトニアンサイクル問題はNP困難であることが証明された。
- 入力グラフの線形順序が与えられても，この困難性は変わらないことが示された。
- ミム幅パラメータ化されたハミルトニシティ問題のパラNP困難性のギャップが解消された。
EvoC2Rust：プロジェクトレベルのCからRustへの変換のためのスケルトンガイド型フレームワーク [cs.SE]目的：大規模CコードベースからRustへの変換
- 安全性が要求されるシステム構築において，既存のCコードのRustへの移行ニーズが高まっている。
- 既存手法は，安全性とRustらしいコードの両立や，大規模コードベースでの意味的等価性の確保が課題である。
- EvoC2Rustは，プロジェクト全体のCコードをRustに変換する問題を解決することを目指す。
- EvoC2Rustは，スケルトンガイド型翻訳戦略を採用し，Cプロジェクトを機能モジュールに分解して変換を行う。
- オープンソースベンチマークおよび産業プロジェクトでの評価で，EvoC2Rustは構文・意味精度で最先端のLLMベース手法を上回った。
- また，既存のルールベースツールよりも43.59%高いコード安全性を実現した。
空間ビームRSRP予測のためのニューラルビームフィールド [cs.IT, cs.AI, cs.LG, math.IT]目的：空間ビームレベルの参照信号受信電力(RSRP)予測
- 高密度多重ユーザー無線ネットワークにおいて，ビーム管理は重要であり，正確なRSRP予測が不可欠である。
- 高負荷な測定と高速なチャネル変化により，RSRPの正確な予測は困難である。
- 本研究は，効率的かつ解釈可能な空間ビームRSRP予測を可能にする。
- 提案手法であるNBFは，従来のテーブルベースのチャネル知識マップ(CKM)や純粋なブラックボックスDNNと比較して，予測精度，学習効率，汎化性能において大幅な改善を示す。
- NBFは，マルチパス条件電力プロファイル(MCPP)を導入することで，サイト固有の伝搬環境を学習し，汎化能力を高めている。
- 事前学習と較正(PaC)戦略により，物理に基づいた事前学習と現場較正を行うことで，収束性と適応性を向上させている。
非結合代数を用いた傾斜多項式符号の分類：等距と等価性 [cs.IT, math.IT, math.RA]目的：傾斜多項式符号の分類
- 符号理論は，通信やデータストレージにおける誤り検出・訂正に不可欠である。
- 既存の分類法では，符号の重複や冗長性が生じ，効率的な符号設計が困難である。
- 新たな等価性と等距の定義により，より厳密な分類を実現し，冗長性を排除すること。
- 周囲の代数間の同型写像を用いることで，既存の分類よりもタイトな分類が可能となった。
- 既知の等距・等価性のクラス数を削減することに成功した。
- 符号の性能パラメータが同じ傾斜$(f,\sigma,\delta)$-多項式符号のクラスを分類し，等価性の異なる概念が一致する条件を明確にした。
ライフタイムが解放をもたらすとき：高階到達可能性追跡によるアリーナのための型システム [cs.PL]目的：アリーナを用いたメモリ管理のための型システム
- 静的リソース管理は，プログラムの安全性と効率性の確保に不可欠である。
- 既存のシステムは，柔軟性と表現力，制御のバランスを取ることが難しい。
- 高階関数と柔軟な共有をサポートしつつ，安全なメモリ管理を実現すること。
- 提案された型システムは，リソースをファーストクラスの値として扱い，ライフタイムと粒度を制御する。
- 到達可能性型を拡張し，アリーナ内のリソースを集合的に追跡することで，高階言語での安全性とメモリ安全性を保証する。
- Rocqにおいて，型安全性とメモリ安全性が形式的に証明された。
拒否耐性のある集合被覆に対するETHに基づくタイトなFPTアルゴリズム：腎臓交換への応用 [cs.DS]目的：拒否耐性のある集合被覆問題の解の存在判定
- 腎臓交換は，患者の生存率向上に不可欠な医療行為であり，効率的な交換スキームの設計が重要である。
- 既存の腎臓交換問題は，参加者の利己的な行動により，最適な解が見つからない場合がある。
- 本研究では，参加者が解を拒否できない「拒否耐性」という制約を導入し，より現実的な解を求める。
- 問題の集合被覆定式に対して，sunflower lemmaを活用することで，kに関して多項式サイズのカーネルを導出した。
- 提案アルゴリズムは，ETHの下で漸近的に最適となる $2^{\mathcal{O}(k \log k)} + n^{\mathcal{O}(1)}$ の時間計算量を達成する。
- パラメータcを導入した一般化問題では，計算困難度とアルゴリズムの効率に興味深い差異が見られた。
RPG：統合的かつスケーラブルなコードベース生成のためのリポジトリ計画グラフ [cs.CL, cs.AI, cs.SE]目的：大規模コードベース生成のための計画手法
- ソフトウェア開発の自動化は，生産性向上と開発コスト削減に不可欠である。
- 自然言語による計画は曖昧性が高く，一貫性のあるソフトウェア設計が困難である。
- リポジトリ全体の構造化された計画により，高品質なコード生成を実現する。
- 提案手法RPGは，機能，ファイル構造，データフローを統一的に表現するグラフ構造を用いる。
- 実験結果から，ZeroRepoは既存の最良手法(Claude Code)と比較して，コード量で約3.9倍の性能を示した。
- また，テストカバレッジ81.5%とテスト精度69.7%を達成し，Claude Codeをそれぞれ27.3点，35.8点上回った。
相関パンドラの箱問題に対する最適4近似解 [cs.DS]目的：相関パンドラの箱問題の4近似解
- 組合せ最適化問題の近似アルゴリズムは，現実的な規模の問題を効率的に解く上で重要である。
- パンドラの箱問題はNP困難であり，多項式時間で最適解を得ることが難しい。
- 相関パンドラの箱問題に対する近似解の性能向上を目指す。
- 本研究では，相関パンドラの箱問題に対する4近似解の最適性を示すことができた。
- この近似率は，Min Sum Set Cover問題の理論的な下界である4に一致する。
エージェント型サービスコンピューティング [cs.SE]目的：エージェント型サービスコンピューティングのパラダイム
- サービスコンピューティングは社会基盤を支える重要な技術分野である。
- 従来のサービスは静的で受動的であり，複雑な状況への対応が困難である。
- 自律的で協調的なエージェントによる動的かつ柔軟なサービスシステムの実現を目指す。
- 本研究は，サービスを自律的，適応的，協調的なエージェントとして捉える「エージェント型サービスコンピューティング」を提案する。
- このパラダイムは，設計，デプロイ，運用，進化の4つのライフサイクル段階と，知覚，意思決定，協調，評価の4つの研究次元で構成される。
- LLMベースのエージェント技術とサービスコンピューティングの基盤原理を統合し，知能的で信頼性の高いサービスエコシステムの構築を目指す。