arXiv雑要約
プログラム - 2025/12/22 公開
ヴァイラウフ問題のコンテナとしての捉え方 [cs.LO, math.LO]目的：ヴァイラウフ問題のコンテナとしての構造の解明
- 計算可能性理論において，問題を分類・比較する枠組みの確立が重要である。
- 既存のヴァイラウフ度数理論では，演算子の抽象的な理解が課題となっていた。
- コンテナの理論を用いて，ヴァイラウフ度数上の演算子の自然な解釈を目指す。
- ヴァイラウフ問題は，射影表現空間の圏上のコンテナとみなせる。
- ヴァイラウフ還元は，コンテナ間の射と厳密に対応する。
- バウアーの拡張ヴァイラウフ度数と分割集合上のコンテナの反射が同値であることが示された。
グラフ上の不確実点におけるk-センター問題 [cs.DL, cs.DS]目的：不確実点に対するk-センターの配置
- グラフ理論は，ネットワークの最適化や資源配分など，様々な分野で基盤技術として重要である。
- 現実世界のデータには不確実性が伴うことが多く，従来のk-センター問題では対応が困難である。
- 不確実な点の位置を考慮したk-センター問題の効率的な解法を確立することを目指す。
- 本研究では，グラフ上の不確実点におけるk-センター問題に対し，k=2の場合の厳密解法を提案した。
- k≥3の場合についても，計算時間に関する上限を導出し，アルゴリズムの有効性を示した。
- また，k=1（one-center）の場合については，より効率的なアルゴリズムを開発した。
RBCTest：RESTful APIの応答本体のオラクルをマイニング・検証するためのLLMの活用 [cs.SE]目的：RESTful APIの応答本体に対する論理的制約の抽出と検証
- APIテストにおいて，API応答の検証は自動化されたテストケース生成に不可欠である。
- 従来の検証手法は動的解析に限定され，システム実行に依存する。
- API仕様書から静的に制約をマイニングし，テストケースを生成すること。
- RBCTestは，LLMを用いてAPI仕様書を理解し，応答本体の制約をマイニングする。
- Observation-Confirmation(OC)スキームにより，LLMの幻覚を抑制し，制約の精度を向上させている。
- 実証実験の結果，制約のマイニング精度は85.1%～93.6%の範囲であり，テストケース生成の精度も86.4%～91.7%を示した。
LLMを活用したコード編集における開発者のプロンプト作成の実態理解と支援 [cs.SE, cs.AI, cs.HC]目的：LLMを活用したコード編集における開発者のプロンプト作成の実態と課題
- ソフトウェア開発における生産性向上は，ビジネス競争力に直結する重要な課題である。
- LLMを活用したコード編集ツールは普及しているが，開発者の利用状況に関する理解が不足している。
- 開発者のプロンプト作成における課題を特定し，より効果的なツール利用を支援すること。
- 開発者のTransform Code利用ログ分析から，頻繁な再プロンプトが利用の難しさを示す指標となることが明らかになった。
- 不十分なリクエストの定性的分析により，開発者のプロンプトから欠落している情報の5つの主要なカテゴリが特定された。
- コード文脈から欠落情報を推論しプロンプトを自動改善するAutoPrompterを提案・評価した結果，編集の正確性が27%向上した。
深掘りと広がり：有界ツリー深度およびツリー幅のグラフにおけるカウント論理と準同型識別 [cs.LO, cs.DM, math.CO]目的：グラフにおけるカウント論理の表現力
- グラフ理論は，ネットワーク構造の分析に不可欠であり，その応用範囲は広範である。
- グラフの複雑度を測る指標と論理表現力の関係は未だ不明な点が多い。
- 特定のグラフクラスにおける論理式の識別可能性を明らかにすること。
- カウント論理と準同型識別可能性の関係性が，グラフの構造的特性と密接に関連していることが示された。
- ツリー幅とツリー深度を持つグラフクラス間において，準同型識別可能性の分離が確立された。
- モンotone Cops-and-Robberゲームを用いた，グラフクラスの特性評価が実現された。
BOLT：行列関数のトレース推定のためのブロック直交ランツォス法 [math.NA, cs.DS, cs.LG, cs.NA]目的：行列関数のトレース推定効率の向上
- 大規模データ処理において，行列式，行列ノルム，分布の相違などの計算は重要であり，効率的なトレース推定が不可欠である。
- 大規模行列は保存やアクセスが困難であり，単純な行列ベクトル積すら実現できない場合がある。
- 部分行列や制限されたインデックス集合での行列ベクトル積のみが可能な状況下での高精度なトレース推定を目指す。
- BOLTは，Hutch++と同等の精度を，直交ブロックプローブとランツォス反復に基づく，より単純な実装で実現する。
- BOLTは，SLQフレームワークを基盤とし，ほぼ平坦なスペクトル領域においてHutch++よりも優れた性能を示す。
- メモリ制約や部分アクセス制約に対応するため，小さな主部分行列のみを扱うSubblock SLQを導入し，KLダイバージェンスやWasserstein-2距離の効率的な計算を可能にした。
大規模言語モデルを用いた変異導入に基づく単体テスト生成 [cs.SE]目的：単体テストの生成
- ソフトウェアの品質保証において，単体テストは不可欠な役割を担う。
- 既存手法では，コードカバレッジが重視されがちだが，欠陥検出能力の指標としては不十分である。
- 変異導入に基づくテスト生成を行い，大規模言語モデルの欠陥検出能力を向上させる。
- 提案手法MUTGENは，EvoSuiteや従来のプロンプトベースの手法と比較して，変異スコアにおいて有意に高い性能を示す。
- MUTGENは，反復的な生成メカニズムにより，大規模言語モデルの変異殺し能力の限界に挑戦する。
- 大規模言語モデルの生成における限界や，変異導入の種類が生成効果に与える影響についても分析した。
OntoGSN：アシュアランスケースのセマンティック管理と拡張のためのオントロジーベースのフレームワーク [cs.AI, cs.SE]目的：アシュアランスケースのセマンティック管理と拡張
- システムの安全性や堅牢性を保証するため，アシュアランスケースは不可欠な成果物である。
- アシュアランスケースの管理は知識の維持に手間がかかり，開発者の負担となる。
- OntoGSNを用いて，アシュアランスケースの変更に対する知識管理を効率化し，信頼性を高める。
- OntoGSNは，GSN標準に基づき，アシュアランスケースを管理するためのオントロジーとミドルウェアを提供する。
- GSNコミュニティスタンダードv3をOWLオントロジーとして形式化し，自動的な更新と評価を可能にする。
- 大規模言語モデルにおける敵対的堅牢性の保証を例に，動的なアシュアランスケース管理の実用性を示した。
弱い強オラクルモデルにおける相対誤差許容クラスタリング [cs.DS]目的：公平性を考慮したクラスタリング問題
- データ量の増大に伴い，正確だが高コストな類似度計算と安価だが不正確な代替手段のトレードオフが重要になっている。
- 不正確な情報が存在する場合でも公平性を実現する手法が不足している。
- 高コストな正確な距離情報の使用回数を最小限に抑えつつ，最適な公平クラスタリングを実現することを目指す。
- 提案手法は，公平k-中央値クラスタリングにおいて，多項式個(poly(k/ε・log n))の強オラクルクエリで(1+ε)-コアセットを初めて達成した。
- この結果は，公平性制約がない標準的な設定におけるコアセットの構築にも応用可能である。
- さらに，一般的なz=O(1)に対する(k,z)-クラスタリングについても，同様のクエリ数で(1+ε)-コアセットが得られる。
単一ソースパーソナライズされたPageRankのほぼ最適性 [cs.NI, cs.DS, cs.CC]目的：単一ソースパーソナライズされたPageRank計算の計算複雑性
- グラフOLAPにおいて，PageRankは重要な指標であり，様々な分析に利用される。
- 既存研究では，PageRank計算の計算複雑性の上界と下界に大きな隔たりが存在する。
- 本研究は，PageRank計算の計算複雑性の理論的限界に迫り，最適化を目指す。
- SSPPR-AおよびSSPPR-Rの上界を改善し，既存の上界よりもlog(1/ε)やlog(log(n)/mδ)のオーダーで高速化を実現した。
- SSPPR-AおよびSSPPR-Rの下界を強化し，理論的基盤をより強固なものにした。
- 特定のグラフ構造において，SSPPR-Rの計算複雑性の上下界が一致し，理論的な最適性を達成した。
平均集約を持つGNNの論理的特徴づけ [cs.CL, cs.AI, cs.LO]目的：平均を集合関数とするグラフニューラルネットワークの表現力
- グラフ構造データは現実世界の複雑な関係性を表現可能であり，その解析が重要である。
- GNNの表現力は，解くべき問題の複雑さに大きく依存するため，その評価が課題となる。
- 平均集約を用いたGNNの表現力の限界を明確にし，より効率的なモデル設計に貢献する。
- 非一様設定において，平均集約GNNは比率モダール論理と同等の表現力を持つことが示された。
- 一様設定下では，MSOに対する表現力はモダール論理と等しく，max集約GNNと同等の表現力となる。
- 連続関数と閾値関数を仮定した場合，平均集約GNNはalternation-freeモダール論理と同等の表現力に制限される。
大規模言語モデルによるソフトウェア脆弱性検出に関する系統的文献レビュー [cs.SE, cs.AI]目的：大規模言語モデルを用いたソフトウェア脆弱性検出の研究動向
- ソフトウェアの安全性確保は重要であり，脆弱性検出はその根幹をなす。
- 研究が急速に進む中で，手法やデータセットにばらつきがあり，比較が困難。
- LLMを活用した脆弱性検出研究の現状を整理し，今後の方向性を示す。
- 本研究では，2020年から2025年までに発表された263件の研究を系統的にレビューした。
- タスク設定，入力表現，システム構成などの観点から研究を分類し，脆弱性検出手法の分類体系を構築した。
- データセットの特徴，脆弱性の網羅性，多様性についても分析し，今後の研究課題を提示した。
機能要求分析と処理：タスク，技術，トレンド [cs.SE]目的：機能要求分析と処理に関する研究分野の体系的概要
- ソフトウェアの競争力向上や顧客満足度向上に直結するため，ユーザーの要望を的確に捉えることは重要である。
- 機能要求に関する研究は多様であり，課題と機会を特定するための包括的な分析が求められている。
- 機能要求の品質保証，仕様と検証の改善，大規模言語モデル活用タスクのための高品質なベンチマーク開発に取り組む。
- 131件の主要研究を分析し，要件工学の活動の観点から研究を分類した。
- 将来の研究のためのオープンツールおよびデータセットを調査した。
- 機能要求の品質保証，仕様・検証の改善，大規模言語モデル向けベンチマーク開発が重要な課題として特定された。
MatchFixAgent：言語非依存の自律的なリポジトリレベルコード翻訳検証・修正 [cs.SE, cs.LG]目的：コード翻訳の同等性検証と，必要に応じた修正
- コード翻訳は，異なるプログラミング言語間でのコード再利用を可能にし，開発効率の向上に貢献する。
- 既存の自動検証・修正手法は，多くの言語に対応するのに手間がかかり，不十分なテストスイートに依存しやすい。
- 言語に依存せず，より正確な翻訳検証と修正を自律的に行うフレームワークの開発。
- MatchFixAgentは，2,219組の翻訳ペア（6言語ペア，24GitHubプロジェクト，90万行超）に対し，99.2%のペアで同等性検証ができた。
- 先行研究と結果が異なる場合，MatchFixAgentの結果が正しいと判断されたのは60.7%だった。
- MatchFixAgentは，不十分な翻訳を50.6%修正できたのに対し，先行研究では18.5%にとどまる。
木の木構造化短絡 [cs.DS]目的：木の木構造化短絡の理論的限界
- 木構造の短絡は，範囲検索や最小全域木問題などへの応用が期待される重要な研究分野である。
- 既存の短絡構造は疎ではあるものの，高密度な部分グラフを含むという課題があった。
- この研究は，より木構造に近い短絡構造の理論的限界を明らかにすることを目的とする。
- 木の木構造化短絡における，ホップ直径とトレewidthのトレードオフについて，最適な上限と下限を確立した。
- 特に，ホップ直径が$O(\log\log n)$までの範囲で，最適なトレードオフが成立することが示された。
- また，ホップ直径とトレewidthの積に関して，$\Omega((\log\log n)^2)$という下限が導かれた。
テストコードにおける自己申告技術的負債：分類と検出に関する第一歩 [cs.SE]目的：テストコードにおける自己申告技術的負債の分類と検出
- ソフトウェアの保守性は重要であり，技術的負債はその保守性を低下させる要因となる。
- 技術的負債はソースコードに存在する研究が主流であり，テストコードにおける技術的負債の調査は不足している。
- テストコードにおける技術的負債の種類を明らかにし，既存の検出手法の限界を評価する。
- 50,000件のコメントを分析した結果，615件のテストコードにおける自己申告技術的負債を確認し，14種類のカテゴリに分類した。
- 既存のSATD検出ツールではMATが最も良い性能を示したが，再現率は中程度であった。
- オープンソースおよびプロプライエタリなLLMは，精度が低く，SATDを信頼性高く検出できないことが示された。
Mavenにおけるピン留めされた依存関係の鮮度について [cs.SE]目的：ソフトウェア依存関係の鮮度に関する調査
- ソフトウェア開発において，ライブラリ依存関係は重要な役割を果たす。依存関係の管理は，ソフトウェアの品質とセキュリティに直結する。
- 依存関係を特定のバージョンに固定(ピン留め)することは，再現性確保には有効だが，古くなった依存関係に起因するリスクがある。
- ピン留めされた依存関係の現状を把握し，依存関係を更新するための安全な方法を提案する。
- 調査の結果，Mavenライブラリの60%以上で鮮度の低いピン留めが行われていることが判明した。
- 最新のマイナーまたはパッチバージョンへのアップグレードにより，セキュリティ脆弱性が軽減されるケースが10%存在した。
- Pin-Freshenerは，ピアプロジェクトのテストを活用することで，安全なアップグレードを促すことが示された。
大規模言語モデル時代におけるソフトウェア工学研究の経験的側面と持続可能性：考察 [cs.RO, cs.SY, eess.SY, cs.SE]目的：大規模言語モデルを用いたソフトウェア工学研究における課題と改善策
- ソフトウェア開発の効率化と品質向上が求められ，新たな技術の導入は不可欠である。
- 大規模言語モデルの活用は，評価の厳密性，データ汚染，再現性の問題を引き起こす可能性がある。
- 大規模言語モデルを用いたソフトウェア工学研究の信頼性と持続可能性を向上させる。
- ICSEにおける大規模言語モデルを活用したソフトウェア工学研究の現状を体系的に分析した。
- 評価の厳密性，再現性において改善の余地があることが示された。
- ベンチマークの厳格化，再現性の向上，経済的・環境的コストへの配慮が推奨された。
ほぼ線形時間での高品質階層的輻輳近似器 [cs.DS]目的：グラフにおける単一商品フローの輻輳を近似的に予測するコンパクトなデータ構造の構築
- ネットワーク設計や分散システムの管理において，効率的なルーティングスキームの構築が重要である
- 既存の階層的輻輳近似器は，計算時間と近似精度の間にトレードオフが存在する
- 近似精度を向上させつつ，計算時間をほぼ線形時間で抑えることが課題である
- 本研究では，近似精度$O(\log^2 n \log \log n)$を持つ，初のほぼ線形時間での階層的輻輳近似器構築アルゴリズムを提案する
- 提案アルゴリズムは，既存のアルゴリズムと比較して，近似精度を大幅に向上させる
- また，並列環境においても効率的に実装可能であり，同様の近似精度を達成する
LLM生成コードにおけるスメルの測定，説明，軽減に関する因果的視点 [cs.SE]目的：LLM生成コードにおけるスメルの傾向性
- ソフトウェア開発において，コード品質は保守性や拡張性に直結するため重要である。
- LLM生成コードは，時に可読性や保守性を損なうコードスメルを含みやすいという課題がある。
- LLM生成コードにおけるスメル発生の要因を特定し，軽減策を提示することを目指す。
- 生成戦略，モデルサイズ，アーキテクチャ，プロンプト設計がコードの構造特性に影響を与えることが示された。
- プロンプト設計とアーキテクチャの選択がスメル発生の傾向に大きく影響することが明らかになった。
- スメル傾向スコア(PSC)はモデルの挙動解釈やコード品質評価に役立ち，開発者の判断を支援する可能性が示唆された。
地上コヒーレントFSOリンクにおける適応MQAM伝送による最大スペクトル効率 [cs.NI, cs.MM, eess.IV, cs.IT, math.IT]目的：地上コヒーレントFSOリンクにおける適応MQAM伝送のスペクトル効率限界
- 次世代無線ネットワークにおいて，大容量のフロントホール/バックホールリンクの実現に不可欠な技術である。
- 地上FSOチャネルにおける適応MQAM伝送に関する理論的解析が十分に進んでいない。
- ガンマガンマ大気タービュレンスとポインティング誤差を考慮したスペクトル効率の限界を明らかにすること。
- 適応MQAMのスペクトル効率限界を，ガンマガンマ大気タービュレンスとポインティング誤差を考慮して導出した。
- 6つの正方形MQAM星座を用いた適応伝送が，理論限界にほぼ近い性能（0.10-0.12ビット/s/Hz以内）を示すことが示された。
- これは，幅広い信号対雑音比およびチャネル条件において有効であることを意味する。
スケジューリングとパッキング問題に対する同等インスタンス [cs.CC, cs.DS]目的：スケジューリングとナップサック問題に対する同等インスタンスの存在
- 組み合わせ最適化問題の効率的な解法は，現実世界の様々な問題を解決する上で不可欠である。
- 問題の規模が大きくなると，計算量が指数関数的に増加し，現実的な時間で解を求めるのが困難になる場合がある。
- 問題の規模を縮小可能な同等インスタンスを構築することで，計算量を削減し，効率的な解法を導くことを目指す。
- スケジューリング問題とナップサック問題に対する同等インスタンスを提示した。
- 実行可能性整数計画問題(ILP)に対する $O(MN^2\log(NU))$ の同等インスタンスを導出した。
- ナップサック問題に対する $O(n^2\log(n))$ の同等インスタンスと，ILPに対する $O(M^2N\log(NM\Delta))$ のカーネルを得た。
AIを受け入れる：システム性能研究の加速 [cs.SE, cs.AI]目的：AIを活用したシステム性能研究の加速
- システム性能の向上は，現代の計算機システムにおいて不可欠であり，その重要性は増している。
- 従来のシステム性能研究は，人的労力に依存しており，効率的な改善が困難な場合がある。
- AIによる自動化を通じて，システム性能研究の効率性と効果を向上させることを目指す。
- AI駆動の研究（ADRS）によって生成された解が，人間の専門家による最先端設計と同等またはそれ以上の性能を示すことが，10のケーススタディで実証された。
- ADRSを効果的に活用するためのベストプラクティス（プロンプトの記述レベル，フィードバック量，堅牢な評価など）が特定された。
- ADRSの適用に関する課題と今後の研究方向性を示し，問題設定と戦略的監督への研究者の注力シフトを促す。
LLM4Perf：大規模言語モデルは多目的性能モデリングのための効果的なサンプラーである [cs.RO, cs.SE]目的：多目的性能モデリングにおける大規模言語モデルのサンプラーとしての有効性
- ソフトウェアシステムの性能は設定オプションに大きく依存する。性能予測はシステム最適化に不可欠である。
- 既存のサンプリング手法は多目的最適化に苦戦し，ドキュメントのセマンティック情報を活用できない。
- 大規模言語モデルを活用することで，性能モデリングのサンプリング効率と精度を向上させる。
- LLM4Perfは，評価シナリオの約68.8%（112件中77件）で従来のベースライン手法を上回る性能を示した。
- LLMによる設定空間の絞り込みとフィードバックに基づく戦略の改善が，その有効性の要因である。
- LLMの選択がLLM4Perfの性能に影響することを示し，性能工学におけるLLMの有効性を裏付けた。
生成アートにおけるパラメータ探索のためのフレームワーク [cs.AI, cs.HC, cs.SE]目的：生成アートにおけるパラメータ空間の探索
- 生成アートは創造性を拡張するが，パラメータ調整が困難である。
- パラメータ空間が広大で，魅力的な結果が得られる領域が限られている。
- 手動探索の効率を上げ，新たな表現の可能性を発見すること。
- ParamExplorerは，人間や自動フィードバックに基づいてパラメータ空間を探索するフレームワークである。
- 強化学習に着想を得た探索戦略（エージェント）を実装し評価した。
- 既存のp5jsプロジェクトへの統合が容易である。
シャンファー距離に対する完全動的アルゴリズム [cs.DS]目的：シャンファー距離の効率的な動的維持
- 点群間の類似度評価として，機械学習などの多様な分野で利用が広がっている。
- 動的に変化するデータセットに対して，高速な距離計算が課題となっていた。
- 動的な点挿入・削除に対応したシャンファー距離の近似計算アルゴリズムを開発する。
- 本研究では，$\ell_p$ノルム($p \in \{1,2\}$)におけるシャンファー距離の近似を，更新時間$\tilde{O}(\epsilon^{-d})$で$(1+\epsilon)$-近似，あるいは$\tilde{O}(d n^{\epsilon^2} \epsilon^{-4})$で$O(1/\epsilon)$-近似で維持する初の動的アルゴリズムを提案する。
- 提案手法は近似最近傍探索(ANN)を利用しており，オーバーヘッドも小さい。
- 実データを用いた評価により，既存手法と同等以上の性能を示すことが確認された。
飽和を考慮したスナップショット圧縮イメージング：理論とアルゴリズム [math.CO, cs.DM, eess.IV, cs.IT, math.IT, stat.AP]目的：飽和下におけるスナップショット圧縮イメージング復元に関する理論的特徴付けとアルゴリズム
- 高速データ取得が求められる分野で重要であり，計算コスト削減に貢献する。
- センサのダイナミックレンジを超える飽和により，線形モデルが破綻し復元精度が低下する。
- 飽和の影響を考慮し，より高精度な復元を可能とする理論とアルゴリズムを開発する。
- 飽和を考慮した理論的解析を行い，最適なベルヌーイマスクの密度が1/2以下となることを示した。
- 飽和測定との整合性を明示的に強制する新しい再構成フレームワーク「Saturation-Aware PnP Net (SAPnet)」を提案した。
- SAPnetは，既存のPnPベースの手法と比較して大幅に性能が向上することを示した。
エックマン・ヒルツォンを超えて：高次圏における可換性 [math.CT, cs.LO]目的：高次圏における全ての合成演算の可換性
- 圏論は数学の基礎であり，多様な分野に応用が広がっている。
- 高次圏の構造は複雑であり，構成の厳密な証明が困難である。
- 高次元におけるエックマン・ヒルツォンの議論を一般化した結果を示す。
- 弱い球状$\omega$-圏において，境界が十分に退化した細胞に対して，全ての合成演算が可換であることが示された。
- この構成の中心は，平行でない細胞間の関係を定めるパディングと再パディングの技術である。
- 実装により，計算が実行可能であり，結果はホモトピー型理論における同一型にエクスポート可能である。
ベント関数に基づくNOMA方式の符号化方式設計について [math.CO, cs.DM, cs.IT, math.IT]目的：NOMA方式の符号化方式設計
- 大規模接続と低遅延，高エネルギー効率が求められる現代の通信システムにおいて，NOMA技術は重要な役割を担う。
- 符号分割多重アクセスNOMAにおける符号化方式設計は，低PAPRと低いコヒーレンスを両立させる必要があり，課題である。
- ベント関数を用いることで，低コヒーレンスを実現するNOMA符号化方式を構築し，この課題を解決する。
- 本研究では，特定のベント関数に対して再帰的なアプローチを適用することで，NOMA符号化方式の理論的な構築を提案した。
- 提案手法により，長さ$N=2^{4m}$のゴレイ符号列$6\cdot N$個を含む符号化方式が得られ，コヒーレンスは$1/\sqrt{N}$となる。
- 1
- 2