arXiv雑要約
プログラム - 2026/05/06 公開
効率的なショートカットと構成可能性に関する構造的基準のためのより良い直径上限 [cs.DS]目的：効率的なショートカット構築と，その構成可能性を測る構造的基準の確立
- 有向グラフにおける到達性や最短経路問題解決において，効率的なショートカット構築は不可欠である。
- 既存の手法では，グラフの直径をどの程度縮小できるかの限界が明確でなく，並列化の度合いにも影響する。
- ショートカットの「構成可能性」を評価する新たな基準を設け，直径の上限を改善することを目指す。
- グラフGに対するショートカットHが「認定済み」であるとは，Hの任意の辺(u,v)に対し，uからwへ，wからvへのパスがG∪H内に存在することを意味する。
- 認定済みショートカットの存在は，効率的な構築可能性と密接に関連しており，時間tで構築可能なショートカットは，サイズがÕ(t)の認定済みショートカットに拡張できる。
- 認定済みショートカットの直径の下限が改善され，現在の技術ではn^(1/4-o(1))よりも直径を縮小することは困難であることが示された。
S-ハミルトンサイクル問題 [cs.DS]目的：S-ハミルトンサイクルの存在判定問題の複雑性
- グラフ理論はネットワーク分析や最適化問題に応用され，現実世界の様々な問題を解決する基盤となる。
- ハミルトンサイクル問題はNP困難であり，大規模グラフに対する効率的な解法が求められている。
- 固定された自然数集合Sに対するS-ハミルトンサイクル問題の複雑性を分類し，解法の指針を得る。
- S={2}およびS={2,4}に対するS-ハミルトンサイクル問題はNP困難であることが示された。
- S={1,2,4}, S={2,4,6}，および奇数全体の集合Sに対するS-ハミルトンサイクル問題は多項式時間で解けることが示された。
- グラフのクリーク幅が制限されている場合，S-ハミルトンサイクルとパスの探索は容易になる。
Vibe Code Bench: エンドツーエンドのWebアプリケーション開発におけるAIモデルの評価 [cs.SE, cs.AI, cs.CL]目的：エンドツーエンドのWebアプリケーション開発におけるAIモデルの性能評価
- AI技術の発展に伴い，コード生成は重要な応用分野となっている。
- 既存の評価指標は個別のタスクに焦点を当てており，アプリケーション全体の開発プロセスを評価できていない。
- 本研究は，ゼロからWebアプリケーションを構築する一連のプロセスを包括的に評価する。
- Vibe Code Benchは，100個のWebアプリケーション仕様と964のブラウザベースのワークフローから構成される。
- 最先端モデルのテスト分割における正答率は61.8%であり，信頼性の高いエンドツーエンド開発は依然として課題である。
- 生成中の自己テストが性能の重要な予測因子（ピアソンのr=0.72）であり，評価者の選択が結果に大きく影響することが示された。
原始・双対アルゴリズムの形式的解析 [cs.LO, cs.DM, cs.DS]目的：アルゴリズム解析における原始・双対法の形式化
- アルゴリズムの信頼性確保は，社会インフラや安全保障において不可欠である。
- アルゴリズムの複雑性や正当性を形式的に検証する手法が不足している。
- アルゴリズムの正当性を数学的に証明可能な環境の構築を試みる。
- Isabelle/HOLを用いて，アルゴリズムの原始・双対法を形式化するフレームワークとライブラリを構築中である。
- ハンガリー法やAdwordsアルゴリズムなど，マッチングアルゴリズムの古典的なものから現代的なものまで形式化例を示す。
- 形式的な検証により，アルゴリズムの信頼性を高め，新たなアルゴリズム設計への応用を目指す。
ステップ複製原始再帰子における作用的不表現性境界 [cs.LO]目的：項書き換え証明システムの構造的性質である作用的不表現性の特定
- 計算可能性理論において，証明システムが表現できる計算の限界を明らかにすることは重要である。
- 原始再帰のような基本的な計算を表現する際，証明システムがその計算の特定の部分を捉えられない場合がある。
- ステップ引数の複製を含む原始再帰子の表現限界を，作用的不表現性の観点から明確にすること。
- 作用的不表現性は，特定の入力と次元において，証明における次元への依存とターゲット質問の制約が両立しない性質として定義された。
- この性質は，原始再帰子の複製構造と密接に関連しており，証明システムの限界を示す境界を特定するのに役立つ。
- 証明システムの健全性と複雑さの関係が示され，健全性の証明に必要な負担が二次的に増加する一方で，残りの証明作業は線形的に増加することが示された。
ClawMark: マルチターン，複数日，マルチモーダルな協働エージェントのための生きた世界ベンチマーク [cs.ET, cs.AR, eess.IV, cs.CV, cs.SE]目的：マルチターン，複数日，マルチモーダルな協働エージェントの性能評価
- 業務支援エージェントの重要性が増しており，継続的なタスク遂行能力が求められている。
- 既存のベンチマークは静的な環境で評価することが多く，現実の動的な業務環境に対応できていない。
- 変化する環境下で複数日にわたるタスクを遂行できる協働エージェントの評価方法を確立すること。
- ClawMarkは，変化する状態を持つ環境で，ファイルシステム，メール，カレンダーなどを操作する100のタスクで構成される。
- 最良のモデルは75.8のスコアを獲得したが，完全なタスク成功率は20.0%にとどまり，部分的な進捗が一般的である。
- 環境の変化後，性能が低下することが示され，変化への適応が重要な課題であることが明らかになった。
Mathlibのネットワーク構造 [cs.LO, cs.PL, cs.SI, math.HO]目的：Mathlibの依存構造の分析
- 形式数学の発展において，大規模ライブラリの構造理解は不可欠である。
- ライブラリの規模拡大に伴い，依存関係の複雑化が問題となっている。
- 形式化された数学の構造特性を定量的に評価することを目指す。
- Mathlibは30万件以上の宣言，840万件のエッジ，7500以上のモジュールから構成される巨大な依存ネットワークを持つ。
- 人間の分類体系と論理構造の間には，50.9%の結合が見られ，乖離があることが示された。
- 開発者はインポートされたスコープの平均1.6%しか利用せず，形式化により意味階層が圧縮される傾向にある。
EvoSuiteにおけるモジュールテストの有効性 [cs.SE]目的：オブジェクト指向Javaプログラムに対するモジュールランダムテストの有効性
- ソフトウェアの品質保証において，テストは不可欠であり，特にモジュールテストは局所的な欠陥検出に有効である。
- EvoSuiteのモジュールテストモードは，ターゲット以外のセットアップメソッドの呼び出し制限が厳しく，十分なカバレッジが得られないという問題がある。
- EvoSuiteのモジュールテスト機能を強化し，セットアップメソッドの呼び出しを許可することで，テストカバレッジの向上を目指す。
- 提案手法 \textsc{emote} は，EvoSuiteのモジュールテストモードを拡張し，ターゲット以外のメソッドの呼び出しを許可することでカバレッジを改善する。
- 適合度関数を修正し，ターゲットメソッドからのコールチェーンにおけるブランチカバレッジへの貢献に焦点を当てる。
- SF100ベンチマークの一部で評価した結果，ターゲットメソッドのカバレッジが15.15%向上した。
CI-Repair-Bench: CIワークフローを通じた自動パッチ検証のためのリポジトリ対応ベンチマーク [cs.SE]目的：CIワークフローにおける自動パッチ検証のためのベンチマーク
- 現代のソフトウェア開発においてCIは不可欠であり，リポジトリレベルの正確性を担保する。
- CI障害の診断と修復は困難であり，従来のプログラム修理ベンチマークでは対応が不十分である。
- 現実的なCI環境下での自動プログラム修理研究を促進するための評価基盤を提供する。
- CI-Repair-Benchは，GitHub Actionsの実行から収集された567件のCI障害事例を提供する。
- 自動修理は，書式設定やリンティングなどのツールで強制される局所的な障害に対して最も効果的であることが示された。
- 環境，依存関係，設定に関連する障害は依然として課題であり，最高性能のLLMでも18.9%の修復成功率である。
幻影から接地へ：信頼性の高いマルチモーダル回路-Verilogコード生成に向けて [cs.CL, cs.SE, cs.AI]目的：回路図からRTLコードへの変換を通じた，マルチモーダル大規模言語モデルの信頼性評価
- ハードウェア設計において，回路図はタイミングやビットレベルの情報を表現する重要な設計言語である。
- 既存の視覚-コード生成モデルは，視覚情報ではなく，識別子に依存する傾向があり，誤ったコード生成につながる。
- 視覚情報に基づいた正確なコード生成を実現し，モデルの信頼性を向上させることを目指す。
- モデルが回路図の代わりに空白画像を使用した場合でも性能が変わらない「幻影」現象を確認した。
- 識別子を匿名化した「Anonyモード」では，既存モデルの性能が大幅に低下し，性能向上が幻影によるものであることを示した。
- 識別子匿名化，拒否拡張，D-ORPOを用いて学習したVeriGround(4B)は，GPT-5.4と同等以上の性能を示し，視覚情報の接地を達成した。
LLM生成コードにおける社会的な偏り：ベンチマークと緩和策 [cs.SE, cs.AI, cs.SI]目的：LLM生成コードの社会的な偏りの評価と軽減
- 人間中心のアプリケーションでは，人口統計学的公平性が重要であり，LLMの利用が拡大している。
- 既存の研究は機能的な正しさに焦点を当てており，LLM生成コードにおける社会的な偏りは十分に調査されていない。
- LLM生成コードに存在する社会的な偏りを検出し，それを軽減するための手法を開発すること。
- SocialBias-Benchを用いた評価の結果，主要なLLM全てに深刻な偏りが認められ，Code Bias Scoresは最大60.58%に達した。
- Chain-of-Thoughtや公平性ペルソナの割り当てといった標準的なプロンプトレベルの介入は，偏りを軽減するどころか，むしろ増幅させる傾向があることが示された。
- Fairness Monitor Agent (FMA)を導入することで，偏りを65.1%削減し，機能的な正しさを75.80%から83.97%に向上させることができた。
最遠点ボロノイ図を用いた最小外接円クエリ [cs.CG, cs.DS]目的：軸平行なクエリ矩形内に存在する点集合の最小外接円の効率的な計算
- 幾何学的問題解決において，効率的なデータ構造とアルゴリズムは重要である。特に，大規模データに対する高速なクエリ処理が求められる。
- 従来の最小外接円クエリに対するデータ構造は，計算量と実装の複雑さにおいて課題があった。
- 本研究は，より単純で効率的なアルゴリズムを開発し，最小外接円クエリの性能を向上させることを目指す。
- 本研究では，2次元最遠点ボロノイ図のみを用いることで，計算複雑さを大幅に削減した。
- 決定的なクエリ時間は $O(\log^4 n)$ を，確率的なクエリ時間は $O(\log^{5/2} n \log\log n)$ を達成した。
- 前処理時間と空間はそれぞれ $O(n \log^2 n)$ であり，既存の手法と同等である。
構造化NP探索における情報アクセシビリティの限界 [cs.IT, cs.CC, math.IT, math.OC]目的：構造化行列族における違反主小行列の特定
- 行列計算は科学技術計算の基盤であり，効率的なアルゴリズム開発が重要である。
- P行列の境界付近の行列の検証は計算コストが高く，効率的な探索手法が課題である。
- 情報理論的なボトルネックを解析し，効率的な探索の限界を示す。
- 違反の特定はグローバルに符号化されており，局所的な問い合わせだけではアクセスできない場合がある。
- 各問い合わせが違反部分集合に関する情報をほとんど提供せず，多項式個の問い合わせでは十分な情報を得られない。
- 制限されたアルゴリズムは，一定の確率で違反部分集合を復元できないことが示された。
AIワークフローアーキテクチャにおける効果透明性のガバナンス：意味的保存，表現的最小性，および決定可能性境界 [cs.AI, cs.LO, cs.PL]目的：AIワークフローアーキテクチャにおける効果レベルのガバナンスの実現可能性
- AIの利用拡大に伴い，その安全性と信頼性の確保が重要課題となっている。
- AIシステムの挙動制御は複雑であり，表現力と安全性の両立が困難である。
- 効果透明性を保ちつつ，AIワークフローをガバナンスする方法を形式的に検証する。
- 構造的に管理されたAIワークフローアーキテクチャの形式化を行い，効果レベルのガバナンスが内部計算表現力を損なわないことを証明した。
- ガバナンス演算子Gを定義し，メモリアクセスや外部API呼び出しを含むすべての副作用を制御可能であることを示した。
- ガバナンスと計算表現力は直交する次元であり，ガバナンスはプログラムの効果境界を制約する一方で，内部計算に対しては意味的に透明であることを示した。
統制実行の代数的な意味論：モノイド圏，効果代数，および共終境界 [cs.AI, cs.LO, cs.PL]目的：統制実行の代数的な意味論
- 現代のソフトウェアシステムにおけるセキュリティや信頼性の確保は重要であり，統制実行はそのための基盤技術となる。
- 従来の統制メカニズムは，表現力や形式的な検証が難しく，セキュリティ上の脆弱性を生む可能性がある。
- 統制実行の形式的な基礎を確立し，安全かつ確実なシステム構築を可能にすること。
- 本研究では，統制実行を形式的に記述するための代数的な枠組みを提案し，モノイド圏，効果代数，共終境界などの数学的概念を活用した。
- 提案手法は，安全性，透明性，妥当性の３つの公理に基づき，プログラムの統制を厳密に保証する。
- 抽出されたOCamlコードの動作検証により，仕様と実行時のインタプリタの行動が等価であることが確認された。
認知ワークフロー実行者に対する認証された純粋性：静的解析から暗号的証明まで [cs.CR, cs.AI, cs.PL]目的：認知ワークフローシステムにおけるガバナンスの実施を，構造的能力境界へと変換する認証された純粋性アーキテクチャ
- 認知ワークフローは複雑化の一途を辿り，ガバナンスの重要性が増している。
- 既存のガバナンス手法は，仮想マシンの脆弱性を悪用した回避が可能であった。
- 仮想マシン上のガバナンス回避を防ぐ，より強固なアーキテクチャを構築すること。
- 制限付きWebAssemblyコンパイルターゲット，純粋性証明書，実行時検証ゲート，リモートアテステーションを組み合わせた。
- 構造的純粋性，回避排除，証明書完全性，ゲート完全性に関する4つの定理を証明した。
- 実装された実行者による評価では，検証遅延時間が39～42μsであり，実行時のオーバーヘッドは0.4%未満であった。
リングネットワークにおけるペアワイズ鍵を用いたセキュア集約の最適な通信レート [cs.IT, math.IT]目的：ペアワイズ秘密鍵を用いたセキュア集約の通信レートの最小値を特徴づけること
- 分散環境におけるプライバシー保護は重要であり，セキュア集約はその鍵となる技術の一つである。
- 従来のセキュア集約は信頼された鍵サーバーに依存しており，単一障害点となるリスクが存在する。
- 鍵サーバーを必要とせず，より堅牢なセキュア集約を実現するための通信レートを明らかにすること。
- リングネットワークにおいて，ユーザー数Kが3または4の場合，1ビットの集約値を計算するために，各ユーザーは隣接ユーザーに少なくとも1ビットを送信する必要がある。
- ユーザー数Kが5以上の場合は，少なくとも2ビットの送信が必要となる。これは，ユーザーが両隣のユーザーとの鍵整合制約を同時に満たす必要があるためである。
- ユーザー数Kが4以上のネットワークでは，全てのペアワイズ鍵ではなく，リング距離2のユーザー間の鍵のみを使用することで最適性を達成できることが示された。
翻訳精度を超えて：LLMベースのコード翻訳における誤った失敗への対処 [cs.SE]目的：LLMベースのコード翻訳における誤った失敗の原因特定と分類
- コード翻訳はソフトウェア開発の効率化に不可欠であり，自動化のニーズは高い。
- 既存の評価フレームワークが，コンパイル設定や環境構築の不備により誤った評価を下す可能性がある。
- 正確な評価基準を確立し，LLMのコード翻訳能力を正しく評価することを目指す。
- 大規模な実験により，報告された失敗の多くがコード自体の誤りではなく，評価パイプラインに起因するものであることが示された。
- コンパイルフラグ，ライブラリリンク，実行環境の未構成などが，誤った失敗報告の主要な原因であることが判明した。
- モデルに依存する挙動と，パイプラインに起因する挙動を区別し，透明性の高い評価基準の必要性を強調した。
HEJ-Robust：LLMベースの自動プログラム修復の堅牢性評価ベンチマーク [cs.SE]目的：LLMベースの自動プログラム修復における堅牢性の評価
- ソフトウェアの品質向上には，自動プログラム修復技術が不可欠である。
- 既存のベンチマークはコードの多様性を考慮せず，実環境での堅牢性を評価できない。
- 多様なコード形式に対するLLMの頑健性を評価し，その課題を明らかにする。
- HEJ-Robustは，HumanEval-Java-Bugを基に8種類の意味保持的なコード変換を適用し，1,450件のテストケースを生成した。
- 5つのファインチューニング済みLLMを評価した結果，複数の変換で性能が50%以上低下し，構文的なわずかな変化に弱いことが示された。
- 現在のLLMベースの修復モデルは，実世界のソフトウェアにおける構文の多様性に対して頑健性に欠けることが明らかになった。
選択可能な定理証明器における構成的ニューラル-サイバー-物理システム検証 [cs.PL]目的：ニューラル-サイバー-物理システムの形式的検証手法
- ドローン等の安全性が重要視される現代において，システム全体の形式検証が不可欠である。
- ニューラルコンポーネントと記号的モデルの検証が個別に行われており，それらを統合するのが困難である。
- Vehicleフレームワークを用いることで，ニューラルコンポーネントと記号的モデルの検証を統合し，安全性を証明する。
- Vehicleフレームワークを拡張し，様々な定理証明器との連携を容易にした。
- Rocq，Isabelle/HOL，Agda，Imandra等の定理証明器で，ニューラルネットワーク制御器を持つ離散サイバー-物理システムの無限時間ホライズン安全性の証明に成功した。
- Vehicleの機能的インターフェースにより，医療機器の連続サイバー-物理システムにおける無限時間ホライズン安全性の証明をRocqで行った。
二段階量子推定と量子強化透過率センシングの漸近的性質 [quant-ph, cs.NI, quant-ph, cs.IT, math.IT, math.ST, stat.TH]目的：単一未知パラメータを含む量子状態の推定
- 量子精密測定は，古典測定の限界を超え，高精度なセンシングを可能にする重要な分野である。
- 量子クラメール・ラオ限界は究極の精度を示すが，その達成にはパラメータ依存な測定が必要となる場合がある。
- 本研究は，パラメータ非依存な測定を可能にする二段階推定法の適用範囲を広げることを目指す。
- 二段階推定法において，古典的推定器に対する制限を緩和し，より広いクラスの推定器が利用可能となった。
- 緩和された条件下では，漸近的性質はわずかに弱まるものの，実用性が向上することが示された。
- 量子強化透過率センシングへの応用を通して，得られた結果の有効性が確認された。
勾配とヘッセ行列の推定のための量子スペクトル法 [quant-ph, cs.DS]目的：勾配とヘッセ行列の推定に関する量子アルゴリズムの開発
- 最適化問題は科学技術計算の根幹であり，効率的な解法が求められている。
- 古典アルゴリズムによる勾配・ヘッセ行列の計算は計算コストが高い。
- 量子アルゴリズムにより，古典計算よりも高速な勾配・ヘッセ行列の推定を目指す。
- 複素関数に対する勾配推定のための量子アルゴリズムを提案し，クエリ複雑度 $\widetilde{O}(1/\varepsilon)$ を達成した。
- ヘッセ行列推定のための2つの量子アルゴリズムを提案し，それぞれクエリ複雑度 $\widetilde{O}(d/\varepsilon)$ と $\widetilde{O}(d^{1.5}/\varepsilon)$ を実現した。
- ヘッセ行列が$s$-sparseな場合は，クエリ複雑度 $\widetilde{O}(s/\varepsilon)$ と $\widetilde{O}(sd/\varepsilon)$ を持つ新しい量子アルゴリズムを開発した。
量子マルグリス符号の構成と復号 [quant-ph, cs.IT, math.IT]目的：量子マルグリス符号の構成と復号性能の評価
- 量子誤り訂正は，量子計算の信頼性を高める上で不可欠な技術である。
- 従来の量子LDPC符号は，誤り退化の問題があり，復号性能が制限される場合がある。
- 本研究は，誤り退化を抑制し，効率的な復号を可能にする新しい量子符号の設計を目指す。
- 量子マルグリス符号は，標準的なmin-sumデコーダを用いて効率的に復号可能であることが示された。
- 従来の二変数自転車符号とは異なり，線形複雑度で復号が可能であり，誤り退化の影響を受けにくい。
- シミュレーションにより，量子マルグリス符号は，BB符号よりも誤り床領域において優れた性能を示すことが確認された。
ローレンツ制約ホログラフィーによる電力分割SWIPT向けDMA支援MU-MISOシステム [math.CO, cs.DM, eess.SP, cs.IT, math.IT]目的：電力分割SWIPTにおける最適な電力分割およびビームフォーミング設計
- 無線通信と電力伝送の同時実行（SWIPT）は，低消費電力デバイスの普及に伴い重要性が高まっている。
- 従来のビームフォーミングアーキテクチャは，RFチェーンや位相シフターの数が増加し，コストと複雑性が増大する。
- 動的メタサーフェスアンテナ（DMA）を用いた設計により，RFチェーンを削減し，電力効率を向上させることを目指す。
- 提案手法は，既存手法と比較して送信電力を大幅に削減できることがシミュレーションによって示された。
- 適応半径LCH（ARLCH）と最適な電力分割が，DMA支援SWIPTシステムの効率向上に貢献することが明らかになった。
- ローレンツ制約下でのメタサーフェスの最適化と非線形エネルギーハーベスティングモデルおよび回路ノイズの影響を考慮した点が特徴である。
点線幾何の射影埋め込みから生じる最小符号について [math.CO, cs.IT, math.IT]目的：点線幾何の射影埋め込みから得られる線形符号の最小性
- 符号理論は，情報伝送や誤り訂正において重要な役割を担う
- 最小符号の構成は，効率的な誤り訂正符号の設計において課題となる
- 射影幾何を用いた最小符号の構成条件を明らかにする
- 射影システムΩを点線幾何Γの射影埋め込みε(mathcal{P})として得られる射影符号が，Γ∖ε⁻¹(H)上の連接グラフが連結である場合に最小となる。
- グラスマン符号，セグレ符号，直交，シンプレクティック，エルミート型の極Grassmann符号，射影空間の点超平面幾何から生じる符号が最小符号の例として挙げられる。